A.
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.
Beberapa model komputasi :
- Finite State Automata (FSA)/Finite State Machine (FSM)
- Push Down Automata (PDA)
- Mesin Turing (Turing Machine) atau TM
Dan ini adalah ilmuwan yang menjadi pionir
di dalam teori komputasi : Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, John von Neumann dan Claude Shannon.
Sumber :
Tidak ada komentar:
Posting Komentar