CENG 213
İşlem Teorisi
Soyut automata, ağırlık olarak sonlu durum makineleri; push-down automata; ve Turing makineleri. Formal diller, özellikle içerik-bağımsız diller. Automata ve diller arasındaki ilişkiler. Hesaplanabilirlik ve çözülebilirlik.
Öğrenim Çıktıları:
- Dil tanımlarını sınıflandırabilme.
- Problemleri analiz edebilme, uygun gösterim şekilleri belirleyebilme.
- Soyutlama yeteneği gösterebilme.
- Bilgisayar bilimlerindeki bazı zor problemleri tanıyabilme.
| Konu |
| Giriş. |
| Kümeler, bağıntılar ve fonksiyonlar. |
|
Temel ispat teknikleri, kapsanımlar (closures).
|
| Diller. |
|
Deterministik ve deterministik olmayan sonlu otomata.
|
| Düzenli ifadeler. |
| Bağlamdan bağımsız gramerler. |
| Pushdown otomata. |
| Turing makineleri. |
| Karar verilebilirlik. |
| Chomsky hiyerarşisi. |
| Hesaba dayalı karmaşıklık. |
| NP-tamlık. |
| P’ye karşı NP’nin durumu. |
