Materi Kuliah Teori Komputasi

Materi Kuliah Teori Komputasi

Pertemuan 1 Pengantar Teori Komputasi
Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.
PDF PRVW | DWNLD

Pertemuan 2 Review Teori Bahasa Formal
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat.
PPT PRVW | DWNLD

Pertemuan 3 Mesin Turing (Bagian 1)
Mesin Turing adalah model yang sangat sederhana dari komputer.  Secara esensial, mesin Turing adalah sebuah finite automaton yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.  Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses.  Elemen yang dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan.
PPT PRVW | DWNLD

Pertemuan 4 Mesin Turing (Bagian 2)
PPT PRVW | DWNLD

Pertemuan 5 Mesin Turing (Bagian 3)
PDF PRVW | DWNLD

Pertemuan 6 Undecidabality (Bagian 1)
Persoalan keputusan (problem) yang tidak dapat diselesaikan (solved) oleh komputer disebut undecidable.
Undecidable tidak dapat diputuskan jawabannya “ya” atau “tidak”.
Sebaliknya persoalan keputusan disebuat decidable jika terdapat algoritma yang apabila diberikan instansiasi (instance) persoalan tersebut maka akan memberikan jawaban “ya” atau “tidak”.
PDF PRVW | DWNLD

Pertemuan 7 Undecidabality (Bagian 2)
PDF PRVW | DWNLD

Pertemuan 8 Undecidabality (Bagian 3)
PDF PRVW | DWNLD

Pertemuan 9 RE Languages and Enumerator
PPT PRVW | DWNLD

Pertemuan 10 Tambahan Undecidablity
PPT PRVW | DWNLD