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.
Dersin Amacı
Matematiksel ispat işleyişini öğretmek.
Otomata, biçimsel diller ve Turing makineleri kavramlarını öğretmek.
Bilgisayarın yaratılmasındaki teorik temelleri vermek suretiyle makinenin yeteneklerinin sınırlarının anlaşılmasını sağlamak.
Kaynakça
Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the Theory of Computation. ACM SIGACT News, 29(3), 62-78.
Sipser, M. (1996). Introduction to the Theory of Computation. ACM Sigact News, 27(1), 27-29.
Öğrenme Çıktıları
1. Dil tanımlarını sınıflandırabilme.
2. Problemleri analiz edebilme, uygun gösterim şekilleri belirleyebilme.
3. Soyutlama yeteneği gösterebilme.
4. Bilgisayar bilimlerindeki bazı zor problemleri tanıyabilme.
| Konular |
| 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 Automata |
| Turing makineleri |
| Karar verilebilirlik |
| Chomsky hiyerarşisi |
| Hesaba dayalı karmaşıklık |
| NP-tamlık |
| P’ye karşı NP’nin durumu |
Notlandırma
Vize 35%
Final 45%
Ödev 20%
