Dersin Adı | Kodu | Yarıyıl | T+U+L (saat/hafta) | Türü (Z / S) | Yerel Kredi | AKTS |
---|---|---|---|---|---|---|
Biçimsel Diller ve Otomatlar Kuramı | CMPE 348 | Bahar | 03+00+00 | Seçmeli | 3 | 5 |
Akademik Birim: | Bilgisayar Mühendisliği |
Öğrenim Türü: | Örgün Eğitim |
Ön Koşullar | Yok |
Öğrenim Dili: | İngilizce |
Dersin Düzeyi: | Lisans |
Dersin Koordinatörü: | - - |
Dersin Amacı: | Bu derste vurgu üç kavramı öğrenme üstünedir: hesaplama nedir, hangi hesaplama modeli ile neler hesaplanabilir, neler hesaplanamaz? Ders konuları doğası gereği matemetikseldir ve ders boyunca ispatlar sunulur. Hesaplama problemlerinde mantık yürütme ve ispat yapabilme yeteneklerinin geliştirilmesi dersin temel amaçlarındandır. |
Dersin İçeriği: | Temel hesaplama kavramlarına giriş. Hesapsal problemler ile diller arasındaki ilişki kurulduktan sonra, diller (düzenli diller, bağlama duyarsız diller, vb.) hesapsal zorluklara göre sınıflanır ve her sınıfa karşılık gelen hesaplama modeli tanıtılır. Her hesaplama modeli karşılık gelen bir otomat (makine) ile temsil edilir. |
Dersin Öğrenme Çıktıları (ÖÇ): |
|
Dersin Öğrenme Yöntem ve Teknikleri | Yüzyüze ders anlatımı ve örnek problem çözümleri. |
Hafta | Konular | Ön Hazırlık | ÖÇ |
---|---|---|---|
1 | Otomatlar, Hesaplanabilirlik ve Karmaşıklığa Genel Bakış. Matematiksel Kavramlar ve Terminoloji | Ders kitabı ve yardımcı kitap | 1, 4 |
2 | Belirli Sonlu Otomatlar. Düzenli İfadeler. | Ders kitabı ve yardımcı kitap | 1, 2 |
3 | Belirli Olmayan Sonlu Otomat. NFA ve DFA Eşdeğerliği. | Ders kitabı ve yardımcı kitap | 2, 4 |
4 | Düzenli İfadelerin (Regular Expressions) Resmi Tanımı. Sonlu Otomatlarda Eşdeğerlik. | Ders kitabı ve yardımcı kitap | 4 |
5 | Birinci Ara Sınav | - | 1, 2, 4 |
6 | Birinci Ara Sınav Sorularını Gözden Geçirme ve Değerlendirme. Düzenli Olmayan Diller. Düzenli Diller için Pompalama Lemmaları. | Ders kitabı ve yardımcı kitap | 1, 4 |
7 | Düzenli Dillerin Özellikleri. | Ders kitabı ve yardımcı kitap | 4 |
8 | Bağlamdan Bağımsız Gramerlerin (CFG) ve Bağlamdan Bağımsız Dillerin Tanımı. | Ders kitabı ve yardımcı kitap | 3, 4 |
9 | Belirsizlik. Chomsky Normal Formu (CNF). | Ders kitabı ve yardımcı kitap | 3, 4 |
10 | Yığın Otomatlarının (PDA) Tanımı. PDA Örnekleri. | Ders kitabı ve yardımcı kitap | 1, 4 |
11 | İkinci Ara Sınav | - | 1, 2, 3, 4 |
12 | İkinci Ara Sınav Sorularını Gözden Geçirme ve Değerlendirme. PDA’ların ve CFG’lerin Eşdeğerliği. | Ders kitabı ve yardımcı kitap | 4 |
13 | Bağlamdan Bağımsız Olmayan Diller. | Ders kitabı ve yardımcı kitap | 3, 4 |
14 | Turing Makinelerinin (TM) Tanımı. TM Örnekleri. | Ders kitabı ve yardımcı kitap | 1, 4 |
Introduction to the Theory of Computation, 3. baskı (2.baskı da kabul olunur), Michael Sipser, Cengage Learning, 2013. |
- Introduction to Automata Theory, Languages, and Computation, 3rd Edition, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2007. - Ders Notları |
Yarıyıl İçi Çalışmaları | Sayı | Katkı Payı (%) |
---|---|---|
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar | 2 | 60 |
Final Sınavı | 1 | 40 |
Total: | 3 | 100 |
Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
---|---|---|---|
Ders Saati | 14 | 3 | 42 |
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar | 2 | 27 | 54 |
Final Sınavı | 1 | 29 | 29 |
Toplam İş Yükü (saat): | 125 |
# | PY1 | PY2 | PY3 | PY4 | PY5 | PY6 | PY7 | PY8 | PY9 | PY10 |
OC1 | ||||||||||
OC2 | ||||||||||
OC3 | ||||||||||
OC4 |