Dzakey World

Perkembangan komputasi modern

Komputasi modern secara harafiah dapat diartikan dari dua kata yaitu komputasi dan modern untuk Komputasi dapat diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Dan disebut modern karena menggunakan alat canggih saat menyelesaian masalah. Maka Komputasi modern adalah perhitungan yang menggunakan computer canggih dimana pada komputer tersebut tersimpan sejumlah algoritma untuk menyelesaikan masalah perhitungan secara efektif dan efisien. Komputasi modern ini antara lain digunakan untuk memecahkan masalah menghitung:


1. Akurasi (big, Floating point)

Dalam mencari solusi dari beberapa masalah yang kompleks, akurasi tentu merupakan masalah yang paling penting dalam memecahkan masalah. Karena itu pada komputasi modern dilakukan perhitungan bagaimana bisa menghasilkan suatu jawaban yang akurat dari sebuah masalah. Apalagi kita pasti pernah mendengar istilah data bertipe float atau dapat disebut juga data yang menyimpan nilai pecahan didalamnya. Tipe data tersebut memiliki range penyimpanan numerik yang besar, sehingga dapat digunakan oleh komputer untuk melakukan komputasi yang akurat.

2. Kecepatan (dalam satuan Hz)

Sebagai sifat alami, manusia pasti menginginkan solusi didapat dengan cepat karena seperti pepatah mengatakan "time is money". Karena itu dalam sebuah perhitungan, masalah kecepeatan adalah suatu hal yang penting. Komputasi harus dapat dilakukan dalam waktu yang cepat ketika mengolah suatu data. Sehingga perlu algoritma yang tepat agar data yang diolah dapat dihitung dalam waktu singkat.

3. Problem Volume Besar (Down Sizzing atau paralel)

Volume data yang besar untuk dihitung tentu membutuhkan suatu penyelesaian yang khusus. Karena ukuran data yang besar dapat menjadi masalah ketika ada suatu data yang terlewatkan. Oleh karena itu digunakan metode Down Sizzing atau paralel pada komputasi modern untuk menangani masalah volume yang besar. Dengan metode ini data yang besar diparalelkan dalam pengolahannya sehigga dapat diorganisir dengan baik.

4. Modeling (NN & GA)

Modeling merupakan suatu hal yang penting dalam melakukan suatu perhitungan yang rumit. Bayangkan saja jika kita dihadapi dalam suatu masalah perhitungan yang banyak dan kompleks, tetapi tidak ada model matematika yang kita miliki. Perhitungan akan berjalan berantakan dan tidak akan mendapatkan hasil seperti yang diinginkan. Maka dari itu komputasi modern membutuhkan modeling sebelum melakukan perhitungan.

5. Kompleksitas (Menggunakan Teori big O)

Komputasi modern dirancang untuk menangani suatu masalah yang kompleks, sehingga diterapkan pada komputer. Dengan menggunakan teori Big O, maka komputasi modern dapat melakukan perhitungan untuk memecahkan masalah kompleksitas yang kerap ditemui.

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 :

1. fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata.
2. 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 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:
5. Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut
6. Karena mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa melakukan desain FSM terlbih dahulu. Biasanya akan terjadi FSM yang terfragmentasi
7. Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis

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.

Prinsip Kerja mesin Turing

1. Lihat state semula dan simbol yang ditunjuk head
2. Berdasarkan fungsi transisinya,tentukan :
     - State berikutnya
     - Lakukan penulisan ke pita
     - Gerakkan head ke kanan dan ke kiri
3. Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti
4. Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.