Bu dersin sonunda öğrenciler; 1) Otomata Teorisinde sonlu durum makinaları, aşağı itmeli makinalar ve Turing makinaları; Biçimsel Dillerde ise, düzenli, içerikten bağımsız ve deyim yapılı diller gibi temel kavramları öğrenmiş olur. 2) Hesaplama sürecinin soyut modellerini anlarlar ve onların güçlerinin limitleri hakkında fikir yürütürler. 3) Soyut hesaplama makinalarına dayanarak; çözülebilir ve çözülemez problemler, etkili çözülebilir ve çözülemeyen problemler üzerine düşünme yeteneği kazanır. 4) Biçimsel modellerin, Bilgisayar Mühendisliğinin ve Bilgisayar Bilimlerinin farklı alanlarındaki önemini anlar.
DERSİN VERİLİŞ BİÇİMİ
Yüz Yüze
DERSİN ÖNKOŞULLARI
Yok
ÖNERİLEN DERSLER
Yok
DERS TANIMI
Otomata Teorisine Giriş: Problemler ve Uygulamaları. Temel Matematiksel Kavramlar ve Yöntemler. Alfabeler, Satırlar, Diller, Problemler. Deterministik Sonlu Durum Makinaları. Deterministik olmayan Sonlu Durum Makinaları. Düzenli İfadeler ve diller, uygulamaları. Düzenli dillerin özellikleri. Biçimsel Gramerler. Backus-Naur Formu. LR Gramerler. İçerikten bağımsız diller. Aşağı itmeli otomata. İçerikten bağımsız dillerin özellikleri. Chomsky Normal Formu. Turing Makinaları. Turing Makinalarının Problem Çözümünde Kullanımı. Fonksiyonların hesaplanması. Hesaplanamayan fonksiyonlar. Çözülemeyen karar problemleri. Kararsızlık ve Çözümsüzlük. Bilişimsel karmaşıklık. Yönetimi Güç Problemler. Hücresel Otomata.
DERS İÇERİĞİ
HAFTA
KONULAR
1. Hafta
Otomata Teorisine Giriş: Problemler ve Uygulamaları.
2. Hafta
Temel Matematiksel Kavramlar ve Yöntemler./Alfabeler, Satırlar, Diller, Problemler.
3. Hafta
Deterministik Sonlu Durum Makinaları. /Deterministik olmayan Sonlu Durum Makinaları.
4. Hafta
Düzenli İfadeler ve diller, Uygulamaları. /Düzenli dillerin özellikleri.
5. Hafta
Biçimsel Gramerler.
6. Hafta
Backus-Naur Formu. LR Gramerler.
7. Hafta
İçerikten bağımsız diller./Aşağı itmeli otomata.
8. Hafta
Ara-sınav
9. Hafta
İçerikten bağımsız dillerin özellikleri.
10. Hafta
Chomsky Normal Formu./Turing Makinaları.
11. Hafta
Turing Makinalarının Problem Çözümünde Kullanımı./Fonksiyonların hesaplanması.
12. Hafta
Hesaplanamayan fonksiyonlar./Çözülemeyen karar problemleri.
13. Hafta
Kararsızlık ve Çözümsüzlük./Bilişimsel karmaşıklık.
14. Hafta
Yönetimi Güç Problemler./Hücresel Otomata.
ZORUNLU YA DA ÖNERİLEN KAYNAKLAR
1. Sudkamp, T.A. (2005) Languages and Machines: an Introduction to the Theory of Computer Science /3E, Addison Wesley. 2. Hopcroft, J.E., Motwani, R., Ullman, J.D. (2006) Introduction to Automata Theory, Languages and Computation /3E, Addison Wesley. 3. Kelley, D. (1995) Automata and Formal Languages: an Introduction, Prentice Hall.
