Teori komputasi merupakan cabang ilmu komputer dan juga cabang ilmu matematika yang membahas tentang bagaimana suatu masalah dapat dipecahkan pada model komputasi dengan menggunakan algoritma. Bidang ilmu ini terutama membahas tentang hal yang terkait dengan komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.
Untuk melakukan suatu studi komputasi yang ketat, ilmuwan komputer bekerja
dengan abstraksi matematika dari komputer yang dinamakan model
komputasi. Ada beberapa model yang digunakan, namun yang paling umum
dipelajari adalah mesin turing. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori
yang tak terhingga, namun hanya dapat diakses dalam bagian-bagian
terpisah dan diskret. Ilmuwan komputer mempelajari mesin Turing karena
mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena
mesin ini mewakili model komputasi yang dianggap sebagai model paling
masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak
terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan,
namun setiap permasalahan yang "terputuskan" (decidable) yang dipecahkan
oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga.
Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan)
oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah
memori terbatas.
2. Komputasi Modern
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. 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.
Sejarah dan Perkembangan
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.
John Von Neumann adalah anak pertama dari pasangan Neumann Miksa
dan Kann Margit. Kedua orang tua nya memberikan nama Neumann Janos,
begitulah nama asli dari John Von Neumann yang terlahir di Budapest, ibu
kota Hungaria, pada tanggal 28 Desember 1903. 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).
Sejarah dari komputasi modern sangat lah panjang perjalannya. Dari
seorang John Von Neumann komputasi modern tersebut bisa berkembang
sampai saat ini yang kita kenal dan kita tahu. Dari ilmu komputasi dan
dikembangkan menjadi komputasi yang modern dengan menggunakan komputer
yaitu Komputasi Modern. Penggunaan Komputasi Modern untuk memecahkan masalah, perhitungan komputasi modern seperti :
- Akurasi (bit, floating point)
- Kecepatan (dalam satuanHz)
- Problem volume besar (paralel)
- Modeling (NN dan GA)
- Kompleksitas (menggunakan Teori Bog O
Bagian - bagian komputasi modern
1. Mobile Computing
Mobile Computing atau biasanya disebut komputasi bergerak merupakan salah satu kemajuan teknologi komputer yang mampu membuat user berkomunikasi menggunakan jaringan tanpa kabel, tetapi berbeda dengan komputasi nirkabel. Contoh hasil dari bagian ini adalah GPS, juga terdapat berbagai tipe dari mobile computing
seperti smartphone yang saat ini sangat terkenal dan lain sebagainya.
2. Grid Computing
Komputasi Grid merupakan komputer yang terpisah oleh letak geografis, terhubung dan terdistribusi oleh jaringan komputer untuk menyelesaikan masalah komputasi dalam skala yang besar. Beberapa daftar yang digunakan untuk mengenali sebuah sistem grid computing, yaitu :
- Sistem untuk koordinat sumber daya komputasi tidak dibawah kendali pusat,
- Menggunakan standart dan protocol sistem yang terbuka,
- Sistem terus mencoba mencapai kualitas pelayanan yang canggih, dan lebih baik diatas kualitas komponen individu pelayan grid computing.
3. Cloud Computing
Komputasi
cloud merupakan gaya komputasi yang terukur dinamis dan sumber daya virtual
yang sering menyediakan layanan melalui internet. Komputasi cloud menggambarkan
pelengkap baru, konsumsi dan layanan IT berbasis model dalam internet, dan
biasanya melibatkan ketentuan dari keterukuran dinamis dan sumber daya virtual
yang sering menyediakan layanan melalui internet.
3. Teori Automata dan Bahasa Formal
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar)
yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih
tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan
mendahului pembangkitan setiap kalimatnya. Tata bahasa (grammar) adalah
kaidah/aturan pembentukan kata/kalimat. Pada pembahasannya, bahasa
formal hanya disebut bahasa saja.
Bahasa
dalam bentuk tulisan terdiri atas symbol-simbol satuan yang jika
dikombinasikan akan mempunyai arti yang berbeda. Simbol-simbol yang
biasa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang
membentuk sebuah himpunan dan disebut sebagai abjad/alphabet. Namun
kadangkala digunakan istilah karakter yang artinya sama dengan symbol.
Deretan dari karakter atau symbol ini membentuk string. Dan himpunan
dari semua string yang dibentuk dari suatu abjad ini didefinisikan
sebagai bahasa.
Karena
bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan
suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi
anggotanya. Tata Bahasa G = (T,N,S,P), di mana :
- T adalah himpunan berhingga simbol-simbol terminal
- N adalah himpunan berhingga simbol-simbol non terminal
- S adalah simbol awal, S ( N
- P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk * + ,, *, , ( (T U N)+, * harus berisi minimal 1 simbol non terminal
Automata
Automata
berasal dari bahasa Yunani automatos, yang berarti sesuatu yang
bekerja secara otomatis (mesin). Istilah automata merupakan bentuk
tunggal, sedangkan bentuk jamaknya adalah automaton. Teori automata
adalah teori tentang mesin abstrak yang bekerja secara sekuensial yang
menerima dan mengeluarkan output dalam bentuk diskrit.
Pengertian
mesin 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. 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.
- 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 langkahlangkah 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 :
- 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 nondeterministik.
4. Finite State Machine
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:
- Implementasinya mudah dan cepat,
- Memudahkan proses debugging. Karena telah dipecah menjadi kepingan yang lebih kecil, proses debugging kalau terjadi behavoiur yang tidak semestinya, menjadi lebih mudah,
- Proses komputasi yg minimal, karena sejatinya FSM hanyalah conditional statement yang dikemas dalam bentuk yang lebih elegan.
- 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.
5. Mesin Turing
Mesin Turing adalah model komputasi teoretis 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."
Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita ke kiri atau ke kanan.
http://www.csc.villanova.edu/~japaridz/CL/
https://faris6593.blogspot.co.id/2015/04/softskill-pengertian-komputasi-modern-dan-jenisnya.html
http://mersannurhakim.blogspot.co.id/2015/03/sejarah-singkat-komputasi-modern.html
http://arm2020.blog.widyatama.ac.id/2016/02/12/perkembangan-teknologi-komputasi-dan-implementasiannya/
http://technologies-it.blogspot.co.id/p/finite-state-machines.html
https://id.wikipedia.org/wiki/Teori_komputasi
