#4IA19
#Teori Komputasi
#Pengantar Komputasi Modern
TEORI KOMPUTASI
Teori komputasi adalah cabang ilmu komputer teoritis. Teori komputasi berkaitan dengan studi bagaimana persoalan (problem) dapat diselesaikan pada sebuah model dengan menggunakan algoritma. Model tersebut dinamakan model komputasi. Teori komputasi dibagi lagi menjadi 3 yaitu:
- Teori Otomata (automata theory)
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 ini lebih mengarah mesin ke pengenalan masalah yang dipecahkan. ada tiga teori otomata yang dipakai pada komputasi yaitu :
- Finite State Automata (FSA)/Finite State Machine (FSM)
- Push Down Automata (PDA)
- Mesin Turing (Turing Machine) atau TM - Teori Komputabilitas (computability theory)
Teori komputabilitas bertujuan untuk memeriksa apakah persoalan komputasi dapat dipecahkan pada suatu model komputasi teoritis. Dengan kata lain, teori komputabilitas mengklasifikasikan persoalan sebagai dapat dipecahkan (solvable) atau persoalan yang tidak dapat dipecahkan (unsolvable). Teori kompleksitas bertujuan untuk mengkaji kebutuhan waktu dan ruang untuk memecahkan persoalan yang diselesaikan dengan pendekatan yang berbeda-beda. - Teori Kompleksitas (computational complexity theory)
Kompleksitas komputasi adalah cabang dari teori komputasi dalam ilmu komputer yang berfokus pada mengklasifikasikan masalah komputasi sesuai dengan kesulitan inheren mereka. Dalam konteks ini, sebuah masalah komputasi dipahami sebagai tugas yang pada prinsipnya setuju untuk menjadi dipecahkan oleh komputer. Informal, sebuah masalah komputasi terdiri dari contoh-contoh masalah dan solusi untuk masalah ini contoh. Sebagai contoh, primality pengujian adalah masalah menentukan apakah nomor yang diberikan perdana atau tidak. Contoh-contoh masalah ini adalah bilangan asli, dan solusi untuk sebuah contoh adalah ya atau tidak didasarkan pada apakah nomor perdana atau tidak.
Sumber :
https://id.wikipedia.org/wiki/Teori_otomata
http://komputasi.itb.web.id/id3/2372-2263/Komputasi_24014_komputasi-itb.html
https://id.wikipedia.org/wiki/Teori_komputasi
http://rizkyasgayuda.blogspot.com/2010/02/komputasi-dari-sisi-kompleksitas.html
