Teori Komputasi adalah cabang ilmu komputer dan matematika yang membahas bisakah suatu masalah di pecahkan pada model komputasi (suatu kumpulan nilai dan operasi) menggunakan algoritma.
Teori Komputasi dibagi menjadi 3 :
1. Teori Komputabilitas
2. Teori Kompleksitas
3. Teori Otomata
Teori Komputasi di fokuskan untuk menjawab 2 pertanyaan :
- Apa yang dapat di komputasi?
- Berapa banyak sumber daya (waktu, ruang/memori) yang di butuhkan untuk melakukan komputasi tersebut?
Jawabannya ada pada Teori Komputabilitas dan Teori Kompleksitas yang berhubungan erat.
Teori Komputabilitas bertujuan untuk memeriksa apakah persoalan komputasi dapat di pecahkan pada suatu model komputasi teoritis. Dengan kata lain mengklasifikasi persoalan yang dapat di pecah kan atau persoalan yang tidak dapat dipecahkan.
Teori Kompleksitas bertujuan mengkaji kebutuhan waktu dan ruang untuk memecahkan persoalan yang di selesaikan dengan pendekatan yang berbeda - beda. Dengan kata lain mengklasifikasi persoalan sebagai persoalan mudah atau persoalan yang sulit.
Teori Otomata mengacu pada pengertian dan sifat - sifat model komputasi.
Beberapa model komputasi :
1. Finite State Automata (FSA) / Finite State Machine (FSM)
(bentuk tunggal : automaton, plural : automata)
2. Push Down Automata (PDA)
3. Mesin Turing (TM)
Model Komputasi yang sering di pakai adalah Mesin Turing.
Sumber :
- https://id.wikipedia.org/wiki/Teori_komputasi
- http://informatika.stei.itb.ac.id/~rinaldi.munir/TeoriKomputasi/2014-2015/IF5110%20-%20Pengantar%20Teori%20Komputasi.pdf
Tidak ada komentar:
Posting Komentar