Teori komputasi

Teori Komputasi

Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas mengenai masalah apa yang dapat diselesaikan pada model komputasi dengan menggunakan algoritma, seberapa efisien masalah tersebut dapat dipecahkan.

Teori komputasi terbagi menjadi 3 cabang utama:

  1. Automata theory and formal languages (teori automata dan bahasa formal). Teori ini terdiri atas 3 model, yakni finite automata, context-free grammars, dan turing machines.
  2. Computability theory (teori komputabilitas). Teori ini digunakan untuk memahami masalah mana yang dapat dipecahkan (solvable) dan yang tidak dapat dipecahkan (unsolvable).
  3. Computational complexity theory (teori kompleksitas komputasi). Teori ini mengklasifikasikan masalah berdasarkan tingkat kesulitannya. Memberikan bukti yang kuat jika masalah yang sulit memang sebenarnya sulit.

Dalam melakukan studi komputasi, para ilmuwan di bidang komputer bekerja dengan matematika abstrak yang biasa disebut dengan model komputasi.

Pada model komputasi, terdapat beberapa model yang digunakan. Akan tetapi, yang paling sering diteliti ialah mesin turing.

Mesin turing dipilih karena mudah dirumuskan, bisa dianalisis, dan dapat digunakan untuk membuktikan hasil, sehingga dianggap sebagai model komputasi yang paling kuat.

Sejarah Teori Komputasi

Teori komputasi
Teori komputasi

Teori komputasi dapat dianggap sebagai penciptaan model dari berbagai macam atau jenis di bidang ilmu komputer. Maka dari itu, matematika dan logika digunakan.

Beberapa pelopor teori komputasi:

  • Ramon Llull
  • Alonzo Church
  • Kurt Gödel
  • Alan Turing
  • Stephen Kleene
  • Rózsa Péter
  • John von Neumann
  • Claude Shannon

Berikut ini informasi rincian waktu sejarah teori komputasi:

TahunKeterangan
1936Alan Turing menemukan mesin turing dan membuktikan bahwasannya ada masalah yang tidak bisa dipecahkan.
1940Dibuatnya stored-program computers.
1943Pitts dan McCulloch menemukan finite automata.
1956Kleene menemukan regular expression.
1956Chomsky mendeskripsikan Chomsky Hierarchy, yang mengatur bahasa-bahasa yang dikenali ke dalam berbagai automata kelas-kelas hirarki.
1959Rabin dan Scott memperkenalkan nondeterministic finite automata (NFA) dan membuktikan ekuivalen dengan finite automata.
1950an – 1960anLebih banyak terfokus di bidang grammars, languages, dan compilers.
1965Hartmantis dan Stearns mendefinisikan mengenai time complexity (kompleksitas waktu). Sedangkan itu, Lewis, Hartmantis, dan Stearns mendefinisikan space complexity (kompleksitas ruang).
1971Cook menunjukkan adanya masalah NP-complete yang pertama, yakni satisfiability problem (masalah kepuasan).
1972Karp menunjukkan banyak masalah pada NP-complete yang lainnya.

Sementara itu, berikut merupakan daftar artikel tentang Teori Komputasi.

Finite Automata
Mesin automata berupa sistem model matematika dari suatu bahasa reguler.

Deterministic Finite Automata (DFA) dan Non-Deterministic Finite Automata (NFA)
Perbedaan teknik kompilasi Deterministic Finite Automata (DFA) dan Non-Deterministic Finite Automata (NFA).

Mesin Turing
Mengenal model komputasi teoretis yang ditemukan oleh Alan Turing.

Materi Kuliah Teori Komputasi
Materi kuliah teori komputasi sebagai bahan pembelajaran dan referensi bagi mahasiswa S1 Teknik Informatika.

Leave a Reply

Your email address will not be published. Required fields are marked *