Tugas 1 Pengantar Komputasi Modern

Komputasi modern bisa disebut sebuah konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah memory, memory disini bisa juga dari memory komputer. Dalam komputasi modern terdapat perhitungan dan pencarian solusi dari masalah. Perhitungan dari komputasi modern adalah akurasi, kecepatan, problem, volume dan besar kompleksitas. Oleh karena pada saat ini kita melakukan komputasi menggunakan komputer maka bisa dibilang komputer merupakan sebuah komputasi modern. Konsep ini pertama kali digagasi oleh John Von Neumann (1903-1957). Dalam kerjanya komputasi modern menghitung dan mencari solusi dari masalah yang ada, dan perhitungan yang dilakukan itu meliputi:

• Akurasi
• Kecepatan
• Problem Volume Besar
• Modelling
• Kompleksitas

Pengertian Komputasi
Komputasi bisa diartikan sebagai cara untuk memecahkan suatu permasalahan dari data yang di input dengan menggunakan suatu algoritma. Hal ini ialah apa yang disebut dengan Teori Komputasi, sub-bidang dari ilmu komputer dan matematika. Sebelum adanya komputer, perhitungan dan komputasi umumnya dilakukan dengan menggunakan pena dan kertas, atau kapur dan batu tulis terkadang dengan bantuan suatu tabel.
Secara umum Ilmu Komputasi adalah bidang ilmu yang mempunyai perhatian pada penyusunan model matematika dan teknik penyelesaian numerik serta penggunaan komputer untuk menganalisis dan memecahkan masalah-masalah ilmu (sains). Bidang ini berbeda dengan ilmu komputer (computer science), yang mengkaji komputasi, komputer dan pemrosesan informasi. Bidang ini juga berbeda dengan teori dan percobaan sebagai bentuk tradisional dari ilmu dan kerja keilmuan.

Sejarah Komputasi Modern 
Sejarah komputasi modern awal mula dari komputasi adalah adanya perhitungan-perhitungan angka yang dilakukan manusia. Manusia telah mengenal angka dan perhitungan sejak berabad-abad yang lalu, dan seiring perkembangan zaman manusia pun melakukan perhitungan yang lebih kompleks. Karena adanya keterbatasan otak manusia yang dapat mengalami keterbatasan dalam menghitung angka yang jumlahnya dapat berdigit-digit, maka terciptalah alat-alat yang bertujuan untuk mempermudah dalam menyelesaikan masalah tersebut. Alat-alat tersebut berupa sempoa, lalu dikembangkan menjadi kalkulator, dan karena semakin berkembangnya kebutuhan tersebut, maka banyak pula data-data yang ingin dihitung dan mulailah ide pembuatan untuk membuat komputer sebagai alat hitung dengan konsep komputasi modern. Tidak hanya itu, komputer yang diciptakan hingga sekarang bukan hanya sebuah alat yang hanya digunakan yang digunakan untuk perhitungan saja, namun masih banyak yang dapat digunakan dalam mengerjakan hal lain seperti menyimpan, mengedit, mengolah kata, dan masih banyak lagi.
Sejarah perkembangan komputasi modern dimulai dari seorang ilmuan ternama yang berasal dari Hungaria bernama John Von Neumann (1903-1957). Von Neumann merupakan sebuah ilmuan yang berlajari di Berlin dan Zurich dan mendapat diploma di bidang teknik kimia pada tahun 1926. Pada saat yang sama, beliau mendapatkan gelar doctornya pada bidang matematika dari Universitas Budapest. Berkat keahliannya Von Neumann dalam bidang teori game yang melahirkan automata, teknologi bom atom dan komputasi modern yang kemudian melahirkan komputer. Von Neumann memberikan berbagai sumbangsih dalam bidang matematika, teori kuantum, game theory, fisika nuklir, dan ilmu komputer yang disalurkan melaluli karya-karyanya. Kegeniusannya dalam matematika telah terlihat semenjak kecil yang dengan kemampuannya mampu melakukan pembagian bilangan delapan digit di dalam kepalanya.

Teori Automata
Berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Dalam tulisan ini akan dipergunakan istilah automaton sebagai bentuk tunggal dan automata sebagai bentuk jamak. Teori Automata adalah teori tentang mesin abstrak yang :

• Bekerja sekuensial
• Menerima input
• Mengeluarkan output

Pengertian mesin di tulisan ini, bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman. Setelah kita mengetahui definisi bahasa dan automata, pertanyaan selanjutnya adalah apakah hubungan antara teori automata dan bahasa formal ? Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata.
fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata.
Dalam tulisan ini, pembahasan akan ditekankan pada fungsi pertama dari automata. Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton yang memiliki komponen sebagai berikut :

• pita masukan, yang menyimpan string masukan yang akan dikenali;
• kepala pita (tape head), untuk membaca/menulis ke pita masukan;
• Finite State Controller (FSC), yang berisi status-status dan aturan-aturan yang mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat dan simbol masukan yang sedang dibaca oleh kepala pita;
• pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara Automaton pengenal, setelah membaca string masukan dan melakukan langkah langkah pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah string tersebut dikenali atau tidak.

Teori Bahasa Formal
Karena bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi anggotanya. Bagaimana kita bisa melakukannya jika jumlah string yang menjadi anggota bahasa tersebut banyak sekali atau bahkan tidak berhingga ? Pada Teori Bahasa Formal, hal ini dilakukan dengan mendefinisikan tata bahasanya.  Tata Bahasa G = (T,N,S,P), di mana :

• T adalah himpunan berhingga simbol-simbol terminal
• N adalah himpunan berhinggasimbol-simbol non terminal
• S adalah simbol awal, S ∈ N
• P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk α → β, α, β ∈ (T ∪ N)+, α harus berisi minimal 1 simbol non terminal.

Sentential form adalah semua string yang dapat diturunkan dari simbol awal S dengan menggunakan aturan produksi P. Kalimat (sentence) adalah sentential form yang tidak mengandung simbol non terminal. Bahasa yang dihasilkan dari G dinotasikan dengan L(G), yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.

Finite State Machine
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). 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.
• 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.

Dalam bahasa pemrograman prosedural seperti bahasa C, FSM ini umumnya direalisasikan dengan menggunakan statemen kontrol switch case atau/dan if..then. Dengan menggunakan statemen-statemen kontrol ini, aliran program secara praktis akan mudah dipahami dan dilacak jika terjadi kesalahan logika.

Mesin Turing
Mesin Turing adalah model komputasi teoritis 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 sendiri merupakan model yang sangat sederhana dari komputer. Secara esensial, mesin Turing adalah sebuah finite automaton yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.
Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya.

Mesin terdiri dari sebuah finite control, yang dapat berada dalam sebuah himpunan berhingga dari state. Terdapat sebuah tape yang dibagi ke dalam kotak-kotak atau sel-sel. Setiap sel dapat menampung sebuah dari sejumlah berhingga dari simbol. Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada tape.

• Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke kanan, pada awalnya menampung simbol khusus yang dinamakan blank.
• Blank bukan sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input symbol dan blank.
• Terdapat sebuah tape head yang selalu ditempatkan pada salah satu dari sel-sel tape.
• Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada pada sel paling kiri yang menampung input.

Mesin Turing dijelaskan oleh 7-tuple:
M = (Q, S, G, d, q0, B, F)
Komponen-komponennya adalah:

• Q: Himpunan berhingga dari state dari finite control.
• S: himpunan berhingga dari simbol-simbol input.
• G: Himpunan dari tape symbol. S merupakan subset dari G.
• d: Fungsi transisi. Argumen d(q, X) adalah sebuah state q dan sebuah tape symbol X. Nilai dari d(q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
• p adalah next state dalam Q
• Y adalah simbol, dalam G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada dalam sel tersebut.
• D adalah arah, berupa L atau R, berturut-turut menyatakan left atau right, dan menyatakan arah dimana head bergerak.
• q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.
• B: simbol blank. Simbol ini ada dalam G tapi tidak dalam S, yaitu B bukan sebuah simbol input.
• F: himpunan dari final state, subset dari Q.

Sumber :

1. http://ciualbert.blogspot.co.id/2016/04/teori-komputasi.html
2. http://teoribahasa-automata.blogspot.co.id/2012/01/teori-bahasa-dan-automata.html
3. http://technologies-it.blogspot.co.id/p/finite-state-machines.html
4. http://rudihadjo.blogspot.co.id/2015/09/mesin-turing.html
5. http://dzakitajudin.blogspot.co.id/2017/03/pengantar-komputasi-modern.html
6. http://julian.unsri.ac.id/userfiles/file/TBO/Modul_TBO-1.pdf
7. http://oolish.blog.uns.ac.id/komputasi/
8. http://windafebrii.blogspot.co.id/2017/03/pengantar-komputasi-modern.html