Komputasi Modern (Tugas Softskill 1 : Pengantar Komputasi Modern)

Teknik Komputasi

Komputasi bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Hal ini ialah apa yang disebut dengan teori koputasi. Suatu sub bidang dari ilmu komputer dan matematika, perhtungan komputasi umumnya dilakukan dengan menggunakan pada dan kertas, atau kapur dan batu tulis, atau juga dikerjakan secara mental, kadang-kadang dengan suatu tabel. Namun sekarang kebanyakan komputasi telah dilakukan dengan menggunakan komputer.

Komputasi Modern

Komputasi modern adalah sebuah konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah memory, memory disini bisa juga dari memory komputer.

Sejarah perkembangan komputasi modern dimulai dari seseorang ilmuan yang ternama dari hungaria bernama John Von Neumann (1903-1957). Von Neumann seorang ilmuan yang belajar dari Berlin dan Zurich dan mendapatkan diploma pada bidang teknik kimia pada tahun 1926. Pada tahun yang sama dia mendapatkan gelar doktor pada bidang matematika dari Universitas Budapest. Berkat keahlian dan kepiawaiannya Von Neumann dalam bidang teori game yang melahirkan konsep seluler automata, teknologi bom atom di Los Alamos pada Perang Dunia II , dan komputasi modern yang kemudian melahirkan komputer.

Teori Bahasa

Dan Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentinga perancangan kompilator (compiler) dan pemroses naskah(text processor).

• Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).
• Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.
• Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.
• Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
• Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. 

Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah fungsi-fungsi dari komputer digital. Menerima input, mengh asilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output.

Sebuah bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinaasikan ke dalam entitas yang disebut kalimat.

Meskipun bahasa formal yang dipelajari disini lebih sederhana daripada bahasa lebih sederhana daripada bahasa pemrograman, meraka mempunyai banyak hal yang penting. Kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.

Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yan lalu dandapaty dianggap sebagai memory mesin.

Finite State Machine

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).

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 state 0, pada keadaan ini sistem akan menghasilkan Action 1 jika terjadi masukan Event 0, sedangkan jika terjadi Event 1 maka Action 2 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 Mahine

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

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

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."

Mesin Turing merupakan pemodelan mesin komputasi yang ampuh. Berdarkan mesin Turing dapat diidentifikasi ketidakmungkinan penulisan program. Bila dinyatakan tidak dapat dikomputasi mesin Turing berarti persoalan tidak mungkin dapat diselesaikan secara komputasi dengan mesin komputasi apapun. Namun bila dikatakan persoalan dapat dikomputasi mesin Turing bukan berarti terdapat algoritma penyelesaian efisien. Mesin Turing sangat penting mengidentifikasi ketidakmungkinan komputasi sehingga kita tidak bersusah payah berusaha memperoleh solusi 100% terhadap fungsi yang diidentifikasi tidak mungkin dikomputasi.

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:

http://www.matadunia.id/2016/02/materi-teori-bahasa-dan-otomata.html
https://mazipanneh.wordpress.com/2011/09/27/teori-bahasa-automata-pertemuan-1/
http://teoribahasa-automata.blogspot.co.id/2012/01/teori-bahasa-dan-automata.html
https://id.wikipedia.org/wiki/Komputasi
http://www.globalkomputer.com/Bahasan/Teori-Bahasa-dan-Otomata.html
http://technologies-it.blogspot.co.id/p/finite-state-machines.html
http://duniainformatikaindonesia.blogspot.co.id/2013/03/finite-state-machine.html
http://blog.ub.ac.id/andriblog/2016/04/18/finite-state-machine/
http://tjerdastangkas.blogspot.co.id/2012/09/kuliah-bahasa-pemrograman-komputasi-dan.html