Teori Komputasi

Pengertian Komputasi

Komputasi bisa diartikan sebagai cara untuk memecahkan suatu permasalahan dari data yang di input dengan menggunakan suatu algoritma. Hal ini ialah apa yang disebut dengan Teori Komputasi, sub-bidang dari ilmu komputer dan matematika. Sebelum adanya komputer, perhitungan dan komputasi umumnya dilakukan dengan menggunakan pena dan kertas, atau kapur dan batu tulis terkadang dengan bantuan suatu tabel.

Secara umum IIlmu Komputasi adalah bidang ilmu yang mempunyai perhatian pada penyusunan model matematika dan teknik penyelesaian numerik serta penggunaan komputer untuk menganalisis dan memecahkan masalah-masalah ilmu (sains).

Bidang ini berbeda dengan ilmu komputer (computer science), yang mengkaji komputasi, komputer dan pemrosesan informasi. Bidang ini juga berbeda dengan teori dan percobaan sebagai bentuk tradisional dari ilmu dan kerja keilmuan.

Teori Komputasi

Teori komputasi (theory of computation) adalah cabang ilmu komputer teoritis (theoritical computer science). 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 ranting :

Teori Otomata (automata theory)

Teori Komputabilitas (computability theory)

Teori Kompleksitas (computational complexity 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.

Dengan kata lain, teori kompleksitas mengklasifikasikan persoalan sebagai persoalan mudah (easy) atau persoalan sukar (hard). Teori komputabilitas memperkenalkan beberapa konsep yang digunakan di dalam teori kompleksitas. Teori otomata mengacu pada definisi dan sifat-sifat model komputasi. Di dalam teori komputasi, model komputasi yang sering dipakai adalah Mesin Turing.