CENG 512

İleri Hesaplama Kuramı

Bu ders farklı biçimsel hesaplama modellerini ortaya koyarak başlayacaktır. Sonrasında Church-Turing tezi ele alınacaktır. Ayrıca karar verilebilirlik ve indirgenebilirlik konuları işlenecektir. Son olarak, karmaşıklık ve ilgili kavramlar hakkında ayrıntılı bilgi verilecektir.

Konu
Giriş ve Genel Bakış
Matematik Tekrarı
Sonlu Otomata ve Düzenli Diller
Bağlamdan Bağımsız Diller ve Pushdown Otomata
Turing Makineleri ve Church-Turing Tezi
Karar Verilebilirlik
Gözden Geçirme
İndirgenebilirlik
Zaman Karmaşıklığı, P ve NP
NP-tamlık
Gözden Geçirme
Yer karmaşıklığı
Rastgeleleştirme
Paralel karmaşıklık