Pengertian Komputasi

Komputasi adalah algoritma yang digunakan untuk menemukan suatu cara dalam memecahkan masalah dari sebuah data input. Data input disini adalah sebuah masukan yang berasal dari luar lingkungan sistem. Komputasi ini merupakan bagian dari ilmu komputer berpadu dengan ilmu matematika. 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). Dalam penggunaan secara umum, biasanya berupa penerapan simulasi komputer atau berbagai bidang keilmuan, tetapi dalam perkembangannya digunakan juga untuk menemukan prinsip-prinsip baru yang mendasar terhadap bidang ilmu yang mendasari teori ini. 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. Dalam ilmu alam, pendekatan ilmu komputasi dapat memberikan berbagai pemahaman baru, melalui penerapan model-model matematika dalam program komputer berdasarkan landasan teori yang telah berkembang, untuk menyelesaikan masalah-masalah nyata dalam ilmu tersebut.

Pengertian 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. 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:

1.    Akurasi

2.    Kecepatan

3.    ProblemVolume Besar

4.    Modelling

5.    Kompleksitas

Sejarah Komputasi Modern

Dalam perkembangan komputasi modern, kita tidak bisa melupakan begitu saja orang dibalik perkembangan komputasi modern yang merubah semua pekerjaan jadi lebih mudah. Sejarah komputasi dimulai dari seseorang ilmuan yang ternama di bidang teknologi. Permulaan komputasi modern dimulai pada saat tahun 1926 oleh ilmuan yang berasal dari hungaria yang bernama John Von Neumann.

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, dan komputasi modern yang kemudian melahirkan komputer. Kegeniusannya dalam matematika telah terlihat semenjak kecil dengan mampu melakukan pembagian bilangan delapan digit (angka) di dalam kepalanya. Setelah mengajar di Berlin dan Hamburg, Von Neumann pindah ke Amerika pada tahun 1930 dan bekerja di Universitas Princeton serta menjadi salah satu pendiri Institute for Advanced Studies. Dipicu ketertarikannya pada hidrodinamika dan kesulitan penyelesaian persamaan diferensial parsial nonlinier yang digunakan, Von Neumann kemudian beralih dalam bidang komputasi. Sebagai konsultan pada pengembangan ENIAC, dia merancang konsep arsitektur komputer yang masih dipakai sampai sekarang. Arsitektur Von Nuemann adalah komputer dengan program yang tersimpan (program dan data disimpan pada memori) dengan pengendali pusat, I/O, dan memori. berdasarkan beberapa definisi di atas, maka komputasi modern dapat diartikan sebagai suatu pemecahan masalah berdasarkan suatu inputan dengan menggunakan algoritma dimana penerapannya menggunakan berbagai teknologi yang telah berkembang seperti komputer.

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 denganL(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 danautomata 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

FINITE STATE MACHINES

Finite State Machines (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 (misal interupsi timer). 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 relative kompleks. Berdasarkan sifatnya, metode FSM ini sangat cocok digunakan sebagai basis perancangan perangkat lunak pengendalian yang bersifat reaktif dan real time. Salah satu keuntungan nyata penggunaan FSM adalah kemampuannya dalam mendekomposisi aplikasi yang relative besar dengan hanya menggunakan sejumlah kecil item state. Selain untuk bidang kontrol, Penggunaan metode ini pada kenyataannya juga umum digunakan sebagai basis untuk perancangan protokol-protokol komunikasi, perancangan perangkat lunak game, aplikasi WEB dan sebagainya.
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.

 Finite State Machine di dunia AI Game Programming, merupakan salah satu teknik yang paling sering digunakan. Alasannya yaitu:

1. Implementasinya mudah dan cepat

2. Memudahkan proses debugging. Karena telah dipecah menjadi kepingan yang lebih kecil, proses debugging kalau terjadi behavoiur yang tidak semestinya, menjadi lebih mudah

3. Proses komputasi yg minimal, karena sejatinya FSM hanyalah conditional statement yang dikemas dalam bentuk yang lebih elegan.

4. Fleksibel, dapat dikombinasikan dengan teknik AI lain misalnya fuzzy logic dan neural network

Kekurangannya:

1. Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut

2. Karena mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa melakukan desain FSM terlbih dahulu. Biasanya akan terjadi FSM yang terfragmentasi

3. Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis:

MESIN TURING

Mesin Turing adalah 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. Stack pada PDA memiliki keterbatasan akses.  Elemen yang dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan.

Visualisasi dari sebuah mesin Turing diberikan oleh gambar berikut:

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. Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite control dan tape symbol yang di-scan.

Read More