Selasa, 28 Maret 2017

Pengantar Komputasi Modern

1. TEORI KOMPUTASI

Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.
Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi. Ada beberapa model yang digunakan, namun yang paling umum dipelajari adalah mesin Turing. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, namun hanya dapat diakses dalam bagian-bagian terpisah dan diskret. Ilmuwan komputer mempelajari mesin Turing karena mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena mesin ini mewakili model komputasi yang dianggap sebagai model paling masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan, namun setiap permasalahan yang "terputuskan" (decidable) yang dipecahkan oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas.

2. KOMPUTASI MODERN

Komputasi Modern merupakan sebuah sistem yang akan menyelesaikan masalah matematis menggunakan komputer dengan cara menyusun algoritma yang dapat dimengerti oleh komputer yang berguna untuk menyelesaikan suatu masalah.  Dalam komputasi modern terdapat perhitungan dan pencarian solusi dari masalah. Perhitungan dari komputasi modern adalah akurasi, kecepatan, problem, volume dan besar kompleksitas.

Salah satu tokoh yang sangat mempengaruhi perkembangan komputasi modern adalah John von Neumann (1903-1957), Beliau adalah ilmuan yang meletakkan dasar-dasar komputer modern.Von Neumann telah menjadi ilmuwan besar abad 21. Von Neumann memberikan berbagai sumbangsih dalam bidang matematika, teori kuantum, game theory, fisika nuklir, dan ilmu komputer  yang di salurkan melalui karya-karyanya . Beliau juga merupakan salah satu ilmuwan yang terkait dalam pembuatan bom atom di Los Alamos pada Perang Dunia II lalu.

Komputansi modern mempunyai karakteristik komputasi modern yang terdiri atas 3 macam, yaitu :
1. Komputer-komputer penyedia sumber daya bersifat heterogenous karena terdiri dari berbagai jenis perangkat keras, sistem operasi, serta aplikasi yang terpasang.
2.    Komputer-komputer terhubung ke jaringan yang luas dengan kapasitas bandwidth yang beragam.
3.  Komputer maupun jaringan tidak terdedikasi, bisa hidup atau mati sewaktu-waktu tanpa jadwal yang jelas.

Jenis-jenis komputasi modern :

1. Mobile computing
Mobile computing atau komputasi bergerak memiliki beberapa penjelasan, salah satunya komputasi bergerak merupakan kemajuan teknologi komputer sehingga dapat berkomunikasi menggunakan jaringan tanpa menggunakan kabel dan mudah dibawa atau berpindah tempat, tetapi berbeda dengan komputasi nirkabel.

Dan berdasarkan penjelasan tersebut, untuk kemajuan teknologi ke arah yang lebih dinamis membutuhkan perubahan dari sisi manusia maupun alat. Dan dapat dilihat contoh dari perangkat komputasi bergerak seperti GPS, juga tipe dari komputasi bergerak seperti smart phone, dan lain sebagainya.

2. Grid computing
Komputasi grid menggunakan komputer yang terpisah oleh geografis, didistibusikan dan terhubung oleh jaringan untuk menyelasaikan masalah komputasi skala besar.

3. Cloud computing
Komputasi cloud merupakan gaya komputasi yang terukur dinamis dan sumber daya virtual yang sering menyediakan layanan melalui internet.
Dampak adanya komputasi modern

Salah satu dampak dari adanya komputasi modern adalah dapat membantu manusia untuk menyelesaikan masalah-masalah yang kompleks dengan menggunakan computer. Salah satu contohnya adalah biometric. Biometric berasal dari kata Bio dan Metric. Kata bio diambil dari bahasa yunani kuno yang berarti Hidup sedangkan Metric juga berasal dari bahasa yunani kuno yang berarti ukuran, jadi jika disimpulkan biometric berarti pengukuran hidup.

Tapi secara garis besar biometric merupakan pengukuran dari statistic analisa data biologi yang mengacu pada teknologi untuk menganalisa karakteristik suatu tubuh ( individu ). Nah dari penjelasan tersebut sudah jelas bahwa Biometric menggambarkan pendeteksian dan pengklasifikasian dari atribut fisik. Terdapat banyak teknik biometric yang berbeda, diantaranya:

- Pembacaan sidik jari / telapak tangan
- Geometri tangan
- Pembacaan retina / iris
- Pengenalan suara
- Dinamika tanda tangan.

3. TEORI BAHASA DAN AUTOMATA

Bahasa adalah struktur yang dikendalikan sekumpulan aturan tertentu, semacam mesin untuk memproduksi makna. Akan tetapi seperti setiap mesin hanya terdapat kemungkinan terbatas bagi setiap orang dalam menggunakannya.

Dalam bahasa disediakan pembendaharaan kata atau tanda (vocabulary), serta perangkat aturan bahasa (grammar, sintaks) yang harus dipatuhi jika hendak menghasilkan sebuah ekspresi yang bermakna.

Proses Kemampuan Pemahaman Bahasa

Hipotesis Noam Chomsky menggugat postulat John Locke (tokoh empirisme) yang menyatakan segala pengetahuan yang dimiliki manusia berasal dari rangsangan-rangsangan luar (pengalaman) yang ditangkap oleh indera-indera manusia, sehingga meniadakan pengetahuan apriori (pengetahuan yang langsung tertanam di manusia)

Noam Chomsky menyandarkan pada pemahaman bahasa sebagai sesuatu yang bersifat khas dan bawaan (tertanam) pada manusia sejak lahir.

Secara khusus Chomsky dipengaruhi Descartes tentang bahasa dan pikiran yang terikat begitu erat sehingga pengetahuan tentang bahasa bisa membuka pengetahuan tentang pikiran manusia.

Secara mendasar bahasa adalah bagian psikologi manusia yang dipahami sebagai teori tentang kemampuan pikiran manusia berupa ungkapan dari subjek psikologi.

Chomsky dan para ahli bahasa telah mengamati anak kecil mampu menjadi lancar berbahasa lebih cepat dan mudah dibanding "algoritma belajar berbahasa".

Sehingga para ahli bahasa membuat hipotesis otak berisi/memuat suatu "mesin bahasa umum". Kemudian selama masa awal pertumbuhan anak, terjadi pertemuan dengan bahasa sehari-hari yang mengubah mesin bahasa umum menjadi mesin bahasa partikular (tertentu) ke bahasa spesifik.


Teori Bahasa

Teori Bahasa adalah konsep-konsep pada "string alpabet V" dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

- Alpabet

Adalah himpunan simbol (karakter) tak kosong yang berhingga. Alpabet digunakan untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Pada beberapa buku, alpabet dilambangkan dengan Σ

Istilah huruf, karakter dan simbol adalah sinonim menunjukkan elemen alpabet. Jika simbol berbaris bersebelahan, maka diperoleh "string simbol". Istilah kalimat, kata dan string adalah sinonim

Contoh :
{a,b} -> Himpunan yang terdiri dari simbol "a" dan "b".


- Penyambungan (Concatenation - o)

Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

Contoh :
'a' o 'b' = 'ab'
'ab' o 'baab' = 'abbaab'


- String pada alpabet V
Karakter atau barisan karakter pada alpabet V dibentuk dari penyambungan karakter pada alpabet V.

String pada alpabet V adalah deretan (sekeun) simbol dari V dimana perulangan simbol diijinkan.

Contoh :
V = {a,b,c,d}
String pada alpabet V antara lain -> 'a','abcd','bbba'

Pemangkatan
Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan

VoV = VV = V2 ----> Panjang string = 2
VoVoV = V2oV=V3 -> Panjang string = 3
VoVoVoV = N4 ----> Panjang string = 4
VoVoVo...oV=Vn ---> Panjang string = n


Vk = VoVoVo...oV
adalah himpunan string dengan panjang k, masing-masing simbol adalah alpabet V

V* = {ε} U V+ (Kleene closure)
adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol)
ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

V+ = V1 U V2 U V3 U ... (Positive closure)
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V0 = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong �


Maka 'bbba' dapat ditulis 'b3a'


Panjang String
Panjang string dilambangkan |w| dimana panjang string adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan kemunculan simbol dihitung.

Contoh:
|ε| = 0
|a| = 1
|aa| = 2
|aaa| = 3
|aaab| = 4



Otomata

Otomata adalah mesin abstrak yang menggunakan model matematika, tetapi matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model trnasisi state (state transition model).

Terdapat 3 model komputasi pada teori otomata.
- Finite automata
- Pushdown automata
- Turing Mavhine


Memori Otomata

Otomata dibedakan berdasarkan jenis memori sementara yang dimilikinya, yaitu:

- Finite automata (FA)
Tidak memiliki memori sementara. Finite automata adalah kelas mesin dengan kemampuan-kemampuan paling terbatas.

- Pushdown automata (PDA)
Memiliki memori sementara dengan mekanisme LIFO (Last In, First Out). Mesin ini lebih ampuh karena bantuan keberadaan stack yang dipandang sebagai unit memori

- Turing Machine (TM)
Memiliki memori dengan mekanisme pengaksesan acak (Random akses memori). Turing Machine merupakan model matematika untuk komputer saat ini.


Sejarah Otomata dan Teori Bahasa

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.

Tahun 1931, Kurt G�del mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada.

G�del membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan G�del ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:
- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.

Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.

Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.

Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.

Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.

Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.

McCulloch dan Pitts mengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.

Finite automata juga digunakan untuk merancang switching circuit. Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.

Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.

Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.

Karena banyak yang berperan pada pengembangannya, bidang teori ini diberi aneka ragam nama yaitu:
- teori otomata (theory of automata)
- teori bahasa formal (theory of formal language)
- teori mesin turing (theory of Turing machine).

4. FINITE STATE MACHINE

Defenisi FSM 
Ada beberapa definisi mengenai Finite  State Machine (FSM) atau sering juga disebut dengan Finite State Automata (FSA). 
1. FSM didefenisikan sebagai perangkat komputasi yang memiliki input berupa string dan output yang merupakan satu dari dua nilai yang dapat di-accept dan reject (Rich : 2009). 
2. Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state (Hariyanto : 2004). 
3. FSM adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri. Transisi keadaan 
ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relatif kompleks (Setiawan : 2006). 
Contoh Diagram FSM
Diagram tersebut memperlihatkan FSM dengan dua buah state dan dua buah input serta empat buah aksi output yang berbeda : seperti terlihat pada gambar, ketika sistem mulai dihidupkan, sistem akan bertransisi menuju state0, pada keadaan ini sistem akan menghasilkan Action1 jika terjadi masukan Event0, sedangkan jika terjadi Event1 maka Action2 akan dieksekusi kemudian sistem selanjutnya bertransisi ke keadaan State1 dan seterusnya. 
Secara formal FSM dinyatakan oleh 5 tupel atau M=(Q, ∑, δ, S, F), 
(Utdirartama, 2001) dimana: 
Q = himpunan state/kedudukan 
∑ = himpunan symbol input/masukan/abjad 
δ = fungsi transisi 
S = state awal/ kedudukan awal (initial state), S Q 
F = himpunan state akhir, F Q
FSM terdiri dari dua jenis, yaitu FSM ber-output dan FSM tidak ber-output. FSM tidak ber-output digunakan untuk pengenalan bahasa dalam komputer, dengan input yang dimasukkan akan diperoleh apakah input tersebut dikenal oleh bahasa komputer atau tidak. Salah satu penggunaan FSM tidak ber-output adalah program compiler, yaitu program untuk memeriksa apakah perintah yang digunakan pengguna benar atau salah. Sementara untuk FSM ber-output digunakan untuk merancang mesin atau sistem (Zen, 2008). Dan FSM yang akan digunakan dalam penelitian ini adalah FSM ber-output, dan untuk selanjutnya akan dituliskan dengan FSM saja. 
Ada dua metode utama untuk memperlakukan FSM untuk menghasilkan output. Yaitu Moore Machine dan Mearly Machine yang dinamakan berdasarkan penemunya. 
  1. Moore State Machine 
Gambar Diagram Moore State Machine
Moore Machine adalah tipe dari FSM dimana output dihasilkan dari state. Pada gambar diatas mencontohkan dimana state mendefenisikan apa yang harus dilakukan (Brownlee, 2010). Keluaran pada Moore Machine diasosiasikan sebagai state (Hariyanto, 2004). Dan pada penelitian ini, penulis menggunakan Moore Machine. 
    2.  Mearly State Machine
Gambar Diagram Mearly Machine
Mearly Machine berbeda dengan Moore Machine dimana keluarannya merupakan hasil dari transisi antar state (Brownlee, 2010). Keluaran pada Mearly Machine diasosiasikan sebagai transisi (Hariyanto, 2004)
Kelebihan FSM 
FSM memiliki beberapa kelebihan (Brownlee, 2010), diantaranya : 
1. Sederhana, sehingga mudah diimplementasikan 
2. Bisa diprediksi responnya 
3. Komputasi ringan 
4. Relatif fleksibel 
5. Merupakan metode AI lama yang bisa digunakan pada berbagai sistem 
6. Mudah ditransfer dari abstrak menjadi kode program 
Kelemahan FSM 
Selain memiliki banyak kelebihan, FSM juga mempunyai beberapa kelemahan (Brownlee, 2010), diantaranya : 
1. Karena sifatnya bisa diprediksi, maka implementasi pada game kurang disukai 
2. Implementasi pada sistem yang lebih besar lebih sulit karena pengaturan dan pemeliharaannya jadi kompleks 
3. Sebaiknya hanya digunakan pada sistem dimana sifat sistem bisa didekomposisi menjadi state. 
4. Kondisi untuk transisi state adalah tetap 
Teknik Pemodelan FSM 
Finite State Machine bukanlah metode yang baru. FSM sudah lama ada dan konsep dekomposisi biasanya sudah dipahami dan sering digunakan oleh orang-orang yang memiliki pengalaman dalam membuat program komputer atau desain program komputer. Ada beberapa teknik pemodelan abstrak yang bisa digunakan untuk membantu defenisi atau pemahaman dan desain dari FSM, mayoritas teknik ini berasal dari disiplin ilmu desain atau matematika (Lee: 1998). 
1. Diagram Transisi State Juga dikenal sebagai Diagram Gelembung (Bubble Diagram). Menunjukkan 
relasi antara state dengan input yang menyebabkan transisi state. 
2. Diagram Pengambilan Keputusan State-Aksi. Diagram Alir sederhana dengan tambahan gelembung yang menunjukkan penungguan terhadap input. 
3. Diagram Grafik State Salah satu bentuk dari notasi UML yang berfungsi untuk menunjukkan sifat 
individu dari objek sebagai nomor state dan transisi dari state tersebut. 
4. Analisa Hirarki Perintah Meskipun tidak seperti state, ini merupakan teknik dekomposisi perintah yang 
melihat dari sudut pandang bagaimana caranya perintah dibagi jadi sub perintah dan urut sesuai urutan kejadiannya. 
Implementasi FSM pada perangkat lunak
Implementasi Finite State Machine dalam perangkat lunak merupakan permasalahan tersendiri yang sudah banyak diteliti oleh pakar-pakar insinyur perangkat lunak (software engineer ). Desain Finite State Machine memang tampak mudah dan sederhana karena hanya terdiri dari serangkaian lingkaran dan anak panah yang 
masing-masing memiliki label. Desain FSM biasanya direpresentasikan dalam tabel transisi state atau dengan state diagram. Namun jika tiba waktunya mengimplementasikan FSM dalam suatu aplikasi perangkat lunak, maka ada suatu permasalahan yang sering timbul yaitu kode program FSM menjadi rumit dan kompleks ketika sistem yang dibangun adalah sistem yang besar atau kompleks. Bagi pemula yang masih belajar implementasi FSM dengan sistem sederhana mungkin hal ini tidak terlalu berpengaruh maupun terasa. Namun bagi seorang programer profesional, maka implementasi FSM untuk sistem yang besar atau kompleks memerlukan suatu desain struktur yang baik dan optimal.


5. MESIN TURING

Mesin Turing adalah model komputasi teoretis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."
Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita ke kiri atau ke kanan. 

Sumber  :
  • https://id.wikipedia.org/wiki/Teori_komputasi 
  • http://belajar-pemrograman2.blogspot.co.id/2013/03/komputasi-modern.html
  • http://www.globalkomputer.com/Bahasan/Teori-Bahasa-dan-Otomata.html
  • http://www.k-oneteknologi.tk/2014/04/fsm-finite-state-machine.html
  • https://id.wikipedia.org/wiki/Mesin_Turing

Tidak ada komentar:

Posting Komentar