Pengertian
Teori Komputasi dan Komputasi Modern
Selama
ribuan tahun, perhitungan dan komputasi umumnya dilakukan dengan menggunakan
pena dan kertas, atau kapur dan batu tulis, atau dikerjakan secara mental,
kadang-kadang dengan bantuan suatu table. Namun sekarang, kebanyakan komputasi
telah dilakukan dengan menggunakan komputer, sehingga mempercepat dalam proses
perhitungan.
Komputasi
merupakan sebuah konsep yang digunakan untuk memecahkan permasalahan dari
sebuah data input dengan menggunakan algoritma. Teori komputasi merupakan suatu
sub-bidang dari ilmu komputer dan matematika.
Komputasi modern adalah 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. Dalam kerjanya
komputasi modern menghitung dan mencari solusi dari masalah yang ada dan
perhitungan yang dilakukan itu meliputi:
1. Akurasi
(big, Floating point)
2. Kecepatan
(dalam satuan Hz)
3. Problem
Volume Besar (Down Sizzing atau pararel)
4. Modeling
(NN & GA)
5. Kompleksitas
(Menggunakan Teori big O)
Jenis-Jenis
Komputasi Modern Jenis-jenis komputasi modern ada 3 macam, yaitu :
1. Mobile
Computing atau Komputasi Bergerak Mobile computing (komputasi bergerak)
merupakan kemajuan teknologi komputer sehingga dapat berkomunikasi menggunakan
jaringan tanpa menggunakan kabel serta mudah dibawa atau berpindah tempat,
tetapi berbeda dengan komputasi nirkabel.
2. Grid
Computing atau Komputasi grid memanfaatkan kekuatan pengolahan idle berbagai
unit computer dan menggunakan kekuatan proses untuk menghitung satu pekerjaan.
3. Cloud
Computing atau Komputasi Awan adalah perluasan dari konsep pemrograman
berorientasi objek abstraksi. Abstraksi menghapus rincian kerja yang kompleks
dari visibilitas.
Sejarah
dan Perkembangan Komputasi Modern
Sejarah
komputer modern dimulai dengan dua teknologi yang terpisah -perhitungan
otomatis dan dapat di program- tapi tidak ada satu perangkat pun yang dapat
dikatakan sebagai komputer, karena sebagian penerapan yang tidak konsisten
terhadap istilah tersebut.
Salah
satu tokoh yang paling berpengaruh terhadap perkembangan komputasi modern
adalah John Von Neumann (1903-1957). John Von Neumann adalah salah satu ahli
matematika terbesar abad ini.
Beliaulah yang pertama kali menggagas konsep
sebuah sistem yang menerima instruksi-instruksi dan menyimpannya dalam sebuah
memori. Konsep inilah yang menjadi dasar arsitektur komputer hingga saat ini.
Beliau juga salah seorang ilmuwan yang sangat berpengaruh dalam pembuatan bom
atom di Los Alamos pada Perang Dunia II lalu. Beliau telah memberikan
karya-karya yang menakjubkan lewat teori kuantum, game theory, fisika nuklir,
dan ilmu komputer.
Beliau
terlahir dengan otak yang jenius, karena saat usia nya masih beliau beliau
mampu menyeimbangkan kemampuan logika analitisnya dengan kemampuan sosial.
Beliau memiliki bakat pada bidang matematika.
John
Von Neumann juga sangat tertarik pada hidrodinamika dan kesulitan penyelesaian
persamaan diferensial parsial nonlinier yang digunakan, Von Neumann kemudian
beralih dalam bidang komputasi. Von Neumann menjadi seorang konsultan pada
pengembangan komputer ENIAC, dia merancang konsep arsitektur komputer yang
masih dipakai sampai sekarang. Arsitektur Von Nuemann adalah seperangkat
komputer dengan program yang tersimpan (program dan data disimpan pada memori)
dengan pengendali pusat, I/O, dan memori.
Berikut
ini beberapa contoh komputasi modern sampai dengan lahirnya ENIAC :
1.
Konrad Zuse’s electromechanical “Z mesin”.Z3 (1941) sebuah mesin pertama
menampilkan biner aritmatika, termasuk aritmatika floating point dan ukuran
programmability. Pada tahun 1998, Z3 operasional pertama di dunia komputer itu
di anggap sebagai Turing lengkap.
2.
Berikutnya Non-programmable Atanasoff-Berry Computer yang di temukan pada tahun
1941 alat ini menggunakan tabung hampa berdasarkan perhitungan, angka biner,
dan regeneratif memori kapasitor. Penggunaan memori regeneratif diperbolehkan
untuk menjadi jauh lebih seragam (berukuran meja besar atau meja kerja).
3.
Selanjutnya komputer Colossus ditemukan pada tahun 1943, berkemampuan untuk
membatasi kemampuan program pada alat ini menunjukkan bahwa perangkat
menggunakan ribuan tabung dapat digunakan lebih baik dan elektronik
reprogrammable. Komputer ini digunakan untuk memecahkan kode perang Jerman.
4.
The Harvard Mark I ditemukan pada 1944, mempunyai skala besar, merupakan
komputer elektromekanis dengan programmability terbatas.
5.
Lalu lahirlah US Army’s Ballistic Research Laboratory ENIAC ditemukan pada tahun
1946, komputer ini digunakan untuk menghitung desimal aritmatika dan biasanya
disebut sebagai tujuan umum pertama komputer elektronik (ENIAC merupakan
generasi yang sudah sangat berkembang di zamannya sejak komputer pertama Konrad
Zuse ’s Z3 yang ditemukan pada tahun 1941).
Teori
Automata dan Bahasa Formal
Automata
adalah mesin abstrak yang dapat mngenali (recognize), menerima (accept), atau
membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Untuk memodelkan
hardware dari komputer diperkenalkan automata. Automata adalah fungsi-fungsi
dari komputer digital. Menerima input, menghasilkan 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.
Automata
merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state
menyatakan informasi mengenai input yan lalu dandapaty dianggap sebagai memory
mesin.
Input
pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin.
Selanjutnya, mesin otomata membuat bkeputusan 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).
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.
1. Naive Approach
Menggunakan conditional statement (if-else
atau switch-case) tanpa memecah object menjadi objek-objek yang lebih kecil sesuai
state nya. Untuk agen yang cuma punya state yang sedikit, metode ini masih
memungkinkan. Tapi kalau sudah kompleks, penggunaan metode ini jelas tidak
dianjurkan, karena akan membentuk ‘spaghetti code’ dan monolithic conditional
statement. Selain itu juga tidak scalable, tidak fleksibel, dan proses
debugging menjadi lebih rumit.
2. State Transition Table
Bentuk ini sudah mengimplementasikan State
Pattern, dengan menempatkan transition logic di context (untuk lebih jelasnya tentang
State Pattern, baca ini dulu).
Bentuk ini juga sering disebut sebagai Classic FSM.
3. Embedded Rules
Bentuk ini adalah kebalikan dari bentuk
Classical Approach, yang berarti state transition didefinisikan di state itu
sendiri. Dan sama dengan Classical Approach, bentuk ini juga akan menawarkan
fleksibilitas dan skalabilitas yang baik, namun dengan efek samping agak sulit
untuk di-mantain karena aturan-aturan transisi diletakkan di state sehingga ketika
terjadi penambahan atau pengurangan state, maka harus dilakukan update juga
terhadap state-state yang terkait.
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.
Dalam
satu pergerakan, mesin Turing akan:
- Merubah state. Next state dapat
sama dengan current state.
- Menulis
sebuah tape symbol dalam sel yang di-scan. Tape symbol
ini mengganti symbol apapun yang ada dalam sel tersebut. Secara opsional,
simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape.
- Memindahkan tape head ke
kiri atau ke kanan.
Sumber:
