Teori
komputasi
Teori komputasi adalah
cabang ilmu komputer dan matematika yang membahas bagaimanakah suatu masalah
dapat dipecahkan dengan model komputasi dengan menggunakan algoritma. Jadi
secara umum teori komputasi itu dapat diartikan sebagai cara untuk menemukan pemecahan
masalah dari data input dengan menggunakan suatu algoritma.
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.
Perkembanganya
:
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 istilah tersebut.
Contoh-contoh awal perangkat penghitung mekanis termasuk sempoa (yang berasal
dari sekitar 150-100 SM). Seorang
pahlawan dari Alexandria (sekitar 10-70 AD) membangun sebuah teater mekanis
yang diadakan bermain berlangsung 10 menit dan dioperasikan oleh sebuah sistem
yang kompleks dengan tali dan drum yang dipakai sebagai sarana untuk memutuskan
bagian dari mekanisme. Ini adalah inti dari programmability.
Salah satu tokoh yang
sangat mempengaruhi perkembangan komputasi modern adalah 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.
Sejarah singkat dari perjalanan hidup dari Von Neumann , dilahirkan di
Budapest, Hungaria pada 28 Desember 1903 dengan nama Neumann Janos. Dia adalah
anak pertama dari pasangan Neumann Miksa dan Kann Margit.Nama keluarga
diletakkan di depan nama asli. Sehingga dalam bahasa Inggris, nama orang tuanya
menjadi Max Neumann. Pada saat Max Neumann memperoleh gelar, maka namanya
berubah menjadi Von Neumann. Setelah bergelar doktor dalam ilmu hukum, dia
menjadi pengacara untuk sebuah bank. Pada tahun 1903, Budapest merupakan tempat lahirnya para manusia genius dari
bidang sains, penulis, seniman dan musisi.
Von Neumann belajar
berbagai tempat dan beberapa tempatnya di Berlin dan Zurich. Di tempat itu
beliau mendapatkan diploma pada bidang teknik kimia pada tahun 1926. Pada tahun
yang sama dia mendapatkan gelar doktor pada bidang matematika dari Universitas
Budapest. Keahlian Von Neumann terletak pada bidang teori game yang melahirkan
konsep seluler automata, teknologi bom atom, dan komputasi modern yang kemudian
melahirkan komputer. Kegeniusannya dalam bidang matematika telah terlihat
semenjak kecil dengan mampu melakukan pembagian bilangan delapan digit (angka)
di dalam kepalanya.
Beliau pernah mengajar di
Berlin dan Hamburg, Von Neumann pindah ke Amerika pada tahun 1930 dan bekerja
di Universitas Princeton pada saat yang bersamaan Von Neumann menjadi salah
satu pendiri Institute for Advanced Studies. Von Neumann 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.
Seiring perkembangan
teknologi, teori komputasi semakin berkembang, sehingga membutuhkan hardware
yang mampu menangani perkembangan tersebut. Komputasi modern menghitung dan
mencari solusi dari masalah yang ada, dan dapat juga diimplementasikan pada
berbagai bidang, seperti bidang biologi, fisika, kimia, ekonomi, geologi,
geografi dan yang lainnya.
Jenis
– jenis komputasi modern
jenis -jenis komputasi
modern terbagi tiga macam, yaitu komputasi mobile (bergerak), komputasi grid,
dan komputasi cloud (awan). Penjelasan lebih lanjut dari jenis-jenis komputasi
modern sebagai berikut :
1.
Mobile computing
Mobile
computing atau komputasi bergerak memiliki beberapa penjelasan, salah satunya
komputasi bergerak merupakan kemajuan teknologi komputer sehingga dapat
berkomunikasi menggunakan jaringan tanpa menggunakan kabel dan mudah dibawa
atau berpindah tempat, tetapi berbeda dengan komputasi nirkabel.
Dan
berdasarkan penjelasan tersebut, untuk kemajuan teknologi ke arah yang lebih
dinamis membutuhkan perubahan dari sisi manusia maupun alat. Dan dapat dilihat
contoh dari perangkat komputasi bergerak seperti GPS, juga tipe dari komputasi
bergerak seperti smart phone, dan lain sebagainya.
2.
Grid computing
Komputasi
grid menggunakan komputer yang terpisah oleh geografis, didistibusikan dan
terhubung oleh jaringan untuk menyelasaikan masalah komputasi skala besar.
Ada
beberapa daftar yang dapat dugunakan untuk mengenali sistem komputasi grid,
adalah
· Sistem untuk koordinat sumber daya
komputasi tidak dibawah kendali pusat.
·
Sistem menggunakan standard dan protocol
yang terbuka.
· Sistem mencoba mencapai kualitas pelayanan
yang canggih, yang lebih baik diatas kualitas komponen individu pelayanan
komputasi grid.
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.
Teori
Otomata
Teori Otomata adalah
teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa
formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar
adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu
kalimat otomata berdasarkan suatu aturan tertentu.
Teori
Bahasa
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
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:
- Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut
- Karena mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa melakukan desain FSM terlbih dahulu. Biasanya akan terjadi FSM yang terfragmentasi
- Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis:
Mesin
Turing
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."
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 kekiri atau
kekanan.
Keterangan :
Tape : Tempat
diletakannya inputan yang berupa kata/untai.
Head: membaca dan
menulisi sel pita mesin turing, bisa bergerak ke kiri atau ke kanan.
Finite StateControl (FSC)
: otak dari TM, diimplementasikan dari algoritma pengenalan kalimat.
Sumber :