Karmaşıklık ve Hesaplama Teorisi

Eğitim Şekli

Yüz Yüze

Ön Koşullar, Diğer Koşullar

Yok

Önerilen Destekleyici Dersler

İstenmemekte

Dersin İç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

Haftalık Ders İzlencesi

1) Matematiksel altyapı
2) Finite automata: DFA, NFA, DFA = NFA, How to implement?
3) Sonlu otomata: DFA, NFA, DFA = NFA, Nasıl gerçeklenir?
4) Kurallı ifadeler: kurallı diller, Kurallı gramerler, Kapalılık, Pigeonhole ilkesi, Pumping lemma
5) 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.
6) 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
7) Turing Makinesi: Nasıl hesaplar? Turing Makinesi çeşitleri
8) Turing Makinesi: Nasıl hesaplar? Turing Makinesi çeşitleri
9) Ara sınav
10) Undecidability: Curch-Turing Tezi, Universal Turing Makinesi, Özyineli sayılabilir diller, Sonlanma Problemi, Çözülemeyen Problemler
11) Undecidability: Curch-Turing Tezi, Universal Turing Makinesi, Özyineli sayılabilir diller, Sonlanma Problemi, Çözülemeyen Problemler
12) Undecidability: Curch-Turing Tezi, Universal Turing Makinesi, Özyineli sayılabilir diller, Sonlanma Problemi, Çözülemeyen Problemler
13) Hesaplama Karmaşıklığı: P-kümesi, NP-kümesi, Cook Teoremi
14) Hesaplama Karmaşıklığı: P-kümesi, NP-kümesi, Cook Teoremi
15) Hesaplama Karmaşıklığı: P-kümesi, NP-kümesi, Cook Teoremi
16) Final sınavı

Önerilen/İstenen Ders Kaynakları

1- Elements of the Theory of Computation, by H.R. Lewis and C.H. Papadimitriou, Prentice Hall, 1998
2- Introduction to Theory of Computation, by Michael Sipser, Thomson Course Technology, 2006.

Planlanan Öğrenim Faaliyetleri Ve Eğitim Yöntemi

1) Anlatım
2) Soru-Cevap
3) Tartışma
4) Alıştırma ve Uygulama
5) Bireysel Çalışma
6) Problem Çözme
7) Proje Temelli Öğrenme

Değerlendirme Yöntemi ve Ölçütleri

Yarıyıl İçi Çalışmalarının Başarıya Oranı	50%
Sayı Yüzde Yarıyıl İçi Çalışmaları Ara Sınav 1 60% Proje 1 40%
Yarıyıl Sonu Sınavının Başarıya Oranı	50%
Toplam	100%

Dersin Eğitim Dili

Türkçe

Mesleki Uygulama

İstenmemekte