| Anasayfa English
 
Hesaplama Teorisi

Dersin Amacı
Bu derste temel amaç, dil sınıflarını gramer ve otomata açısından tanımlamaktır.
Kitap ve/veya Kaynaklar
  1. Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012.
  2. Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006.
  3. Introduction to Languages and the Theory of Computation, 4th Edition. John C. Martin, 2011, Mc Graw Hill.
Ölçme ve Değerlendirme
%40 Ara sınav + %60 Final sınavı
Ön koşul
resmi ön koşul yoktur, kesikli matematik dersini almış olmak önerilir.
 
Hafta Konular
1. Kesikli matematiksel yapılar tekrarı
2. Deterministik sonlu otomata (DFA) ve Deterministik olmayan sonlu otomata (NFA)
3. DFA'dan NFA'ya dönüşüm, Düzenli ifadeler
4. DFA'dan düzenli ifadeye dönüşüm, Düzenli diller için Pumping Lemma
5. İçerik bağımsız gramerler, Chomsky normalizasyonu
6. Push-Down otomata
7. İçerik-bağımsız diller için Pumping Lemma
8. Arasınav
9. Turing makineleri, Church-Turing tezi
10. Deterministik olmayan Turing makineleri
11. Karar-verilebilir ve Karar-verilemez diller
12. Sayılabilirlik ve Sayılabilir diller
13. Karmaşıklık Teorisine giriş, P ve NP sınıfları
14. Deterministik olmayan algoritmalar, NP-bütün diller
15. Final sınavı için tekrar
  Final Sınavı

 
Çukurova Üniversitesi Mühendislik Mimarlık Fakültesi Bilgisayar Mühendisliği Bölümü  
Telif Hakkı © 2012 Her hakkı saklıdır. Tasarım: Yrd. Doç. Dr. Umut ORHAN