Karmaşıklık ve Hesaplama Teorisi

Eken S.

• Dersin Düzeyi: Yüksek Lisans
• Tasarlanan Ders Kodu: BTM552
• Öğretim Türü: Örgün Öğretim (Normal Öğretim)
• Dersin Kapsamı: Teorik ve Uygulama
• Akademik Yıl: 2019 - 2020
• Ders İçeriği:

  Matematiksel altyapı, Sonlu otomata: DFA, NFA, DFA = NFA, Nasıl gerçeklenir? Kurallı ifadeler: kurallı diller, Kurallı gramerler, Kapalılık, Pigeonhole ilkesi, Pumping lemma, Bağlamdan Bağımsız Diller: Ayrıştırma ve Belirsizlik, Ayrıştırma Ağaçları, Yığın yapılı otomata, Bağlamdan Bağımsız Diller için Pumping lemma, Turing Makinesi: Nasıl hesaplar?, Turing Makinesi çeşitleri, Undecidability: Curch-Turing Tezi, Universal Turing Makinesi, Özyineli sayılabilir diller, Sonlanma Problemi, Çözülemeyen Problemler, Hesaplama Karmaşıklığı: P-kümesi, NP-kümesi, Cook Teoremi