TEORI KOMPUTASI DAN KOMPUTASI MODERN

Assalamualaikum wr wb

 Pada post kali ini saya akan  memberikan penjelasan mengenai komputasi dan komputasi modern yang saya tulis berdasar tugas softskill saya.

Tentunya pada era global ini komputer sudah tak asing bahkan sudah menjadi bagian dari hidup kita, namun disini kita perlu mengetahui  apakah definisi dari komputasi yang sangat akrab di telinga kita.

Definisi Komputasi adalah Suatu pemecahan masalah terhadap data input (sebuah masukan yang berasal dari luar lingkungan sistem) dalam berbagai bidang pekerjaan yang
telah disebutkan sebelumnya dengan menggunakan sebuah algoritma.
 
Sedangkan, definisi dari Komputasi Modern adalah Penggunaan komputer dalam menganalisis dan memecahkan masalah-masalah ilmu (sains), dengan menaruh perhatian pada penyusunan model matematika dan teknik penyelesaian numerik.

Komputasi modern merupakan sebuah konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah memory, memory disini bisa juga dari memory komputer. 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). 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. Kegeniusannya dalam matematika telah terlihat semenjak kecil dengan mampu melakukan pembagian bilangan delapan digit (angka) di dalam kepalanya.

Begitulah sekiranya definisi Komputasi dan Komputasi modern serta sejarah perkembanganya, selanjutnya saya akan menjelaskan mengenai Bahasa automata dan bahasa formal.

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword.

FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching

Spesifikasi dari sebuah bahasa pemrograman meliputi, hal-hal :

1.     Himpunan simbol-simbol (alpabet) yang bisa dipakai untuk membentuk program yang benar

2.     Himpunan program yang benar secara sintaktik

3.     Makna dari program tersebut

 

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.

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.

Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin pengenal , yang terdiri atas :

- status FSC

- isi pita masukan dan posisi kepala pita

- isi pengingat

Mesin pengenal bersifat deterministik bila dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika tidak mesin pengenal bersifat non deterministik. Contoh mesin automata :

• Sebuah string input diterima bila mencapai state akhir/ final state yang digambarkan dengan lingkaran ganda.
• Pada gambar diatas, mesin mendapat string input berikut :

–        ada : diterima

–        adu : diterima

–        add : ditolak

• Mesin diatas memiliki 6 state {qo, q1, q2, q3, q4, q5}.
• State awal : q0, State akhir : {q3, q4}.
• Himpunan simbol input : {a,d,u}.

 

Konsep Bahasa dan Otomata

•         Simbol adalah suatu entitas abstrak yang tidak bisa didefinisikan secara formal

•         Huruf dan digit adalah contoh dari simbol yang sering di pakai

•         String adalah suatu deretan berhingga dari simbol-simbol, contoh : ‘a’, ‘b’, ‘c’ adalah simbol dan ‘abc’ adalah sebuah string.

•         String kosong dinyatakan dengan ε di definisikan panjangnya = 0 atau |ε|= 0

•         Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alpabet yang memiliki makna.

•         Ada istilah bahasa kosong, yaitu bahasa yang tidak terdiri dari string-string, contoh himpunan kosong Ø

•         Otomata adalah suatu bentuk yang memiliki fungsi-fungsi dari komputer digital, menerima input menghasilkan output, bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan input ke output

•         Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga (state), dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin.

•         Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan atau keluaran yang mengindikasikan apakah input itu diterima atau tidak 

sekian tulisan saya, dari tulisa ini saya mengambil rujukan dari beberapa sumber terkait.

source:

Gibbs, William R. (2006). Computation in Modern Physics. World Scientific.

Koenig, Herbert. (1998). Modern Computational Methods. CRC Press

https://id.wikipedia.org/wiki/Komputer
http://bintorobagus.blogspot.co.id/2015/04/implementasi-komputasi-modern-pada.html
https://niamoraa.wordpress.com/softskill-project-2/definisi-dan-penerapan-komputasi-modern/
http://teoribahasa-automata.blogspot.co.id/2012/01/teori-bahasa-dan-automata.html