|
|
| COM2004 | Automata Theory | 3+0+0 | AKTS:4 | | Yıl / Yarıyıl | Bahar Dönemi | | Ders Duzeyi | Lisans | | Yazılım Şekli | Zorunlu | | Bölümü | BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ | | Ön Koşul | Yok | | Eğitim Sistemi | Yüz yüze | | Dersin Süresi | 14 hafta - haftada 3 saat teorik | | Öğretim Üyesi | Dr. Öğr. Üyesi Selçuk CEVHER | | Diğer Öğretim Üyesi | Yok | | Öğretim Dili | İngilizce | | Staj | Yok | | | | Dersin Amacı: | | Öğrenciye bilgisayar biliminin matematiksel gelişimi anlatmak ve dillerin sonlu gösterimleri ile derleyici tasarımının temelleri hakkında genel bilgiler vermektir. |
| Öğrenim Kazanımları | PÖKK | ÖY | | Bu dersi başarı ile tamamlayan öğrenciler : | | | | ÖK - 1 : | Tanımlanmış diller için RE, FA, PDA, CFG, TM ve PM üretebilir. | 1,2,12 | 1 | | ÖK - 2 : | Tanımlanmış dillerdeki RE ile FA'in, PDA ile CFG'nin ve TM ile PM nin eşdeğer olduklarını ispatlayabilir. | 1,2,12 | 1 | | ÖK - 3 : | Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir. | 1,2,12 | 1 | | ÖK - 4 : | Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir. | 1,2,12 | 1 | | PÖKK :Program öğrenim kazanımlarına katkı, ÖY : Ölçme ve değerlendirme yöntemi (1: Yazılı Sınav, 2: Sözlü Sınav, 3: Ev Ödevi, 4: Laboratuvar Çalışması/Sınavı, 5: Seminer / Sunum, 6: Dönem Ödevi / Proje),ÖK : Öğrenim Kazanımı | | |
| OTOMATA TEORİSİ : Diller, Özyinelemeli Tanımlamalar, Düzenli İfadeler, Sonlu Otomata, Geçiş Grafikleri, Kleene Teoremi, Çıkışlı Sonlu Otomata, Düzenli Diller, Düzenli Olmayan Diller (Şişirme Lemması, Myhill-Nerode Teoremi), Karar Verebilirlilik. YIĞIN OTOMATA TEORİSİ : Durumdan Bağımsız Dilbilgileri (Ağaçlar, Belirsizlik), Dilbilgisel Format (Düzenli Dilbilgileri, Chomsky Normal Form, Soldan Türetimler), Yığın Otomata, CFG=PDA, Durumdan Bağımsız Olmayan Diller (CFL için Şişirme Lemması), Durumdan Bağımsız Diller (Kapalılık Özellikleri), CYK Algoritması. TURING TEORİSİ : Turing Makinalar (TM), Post Makinalar, Minsky Teoremi, TM Çeşitleri (Durumda Hareket Makinası, Durma Opsiyonlu Makina, k-Yollu TM, İki Taraflı Sonsuz Bant Modeli, Belirli Olmayan TM, Yalnızca Okunabilir TM) , TM Dilleri (TM Kod Çözülmesi, Evrensel Turing Makina, Durma Problemi), Chomsky Hiyerarşisi (Deyim Yapılı Diller, Duruma Bağlı Dilbilgileri), Bilgisayarlar (Hesaplanabilir Fonksiyonlar, Church Tezi). |
| |
| Haftalık Detaylı Ders Planı | | Hafta | Detaylı İçerik | Önerilen Kaynak | | Hafta 1 | Diller | | | Hafta 2 | Özyinelemeli Tanımlamalar | | | Hafta 3 | Düzenli İfadeler | | | Hafta 4 | Sonlu Otomata | | | Hafta 5 | Geçiş Grafları | | | Hafta 6 | Kleene Teoremi | | | Hafta 7 | Çıkışlı Sonlu Otomata | | | Hafta 8 | Düzenli ve Düzenli Olmayan Diller | | | Hafta 9 | Arasınav | | | Hafta 10 | Durumdan Bağımsız Dilbilgileri | | | Hafta 11 | Yığınlı Otomata | | | Hafta 12 | Turing Makinaları | | | Hafta 13 | Post Makinaları | | | Hafta 14 | Minsky Teoremi | | | Hafta 15 | TM Çeşitleri | | | Hafta 16 | Dönem sonu sınavı | | | |
| 1 | Cohen, D. 1997; Introduction to Computer Theory (2nd). | | | 2 | Sipser, M. 2013; Introduction to Theory of Computation (3rd). | | | |
| 1 | Dersin web sayfası : http://ceng2.ktu.edu.tr/~cakir/otomata.html | | | |
| Ölçme Yöntemi | | Yöntem | Hafta | Tarih | Süre (Saat) | Katkı (%) | | Arasınav | 9 | 05/04/2016 | 1,5 | 50 | | Dönem sonu sınavı | 16 | 28/05/2016 | 1,5 | 50 | | |
| Öğrenci Çalışma Yükü | | İşlem adı | Haftalık süre (saat) | Hafta sayısı | Dönem toplamı | | Yüz yüze eğitim | 3 | 14 | 42 | | Sınıf dışı çalışma | 1 | 14 | 14 | | Laboratuar çalışması | 0 | 0 | 0 | | Arasınav için hazırlık | 5 | 1 | 5 | | Arasınav | 5 | 1 | 5 | | Uygulama | 0 | 0 | 0 | | Klinik Uygulama | 0 | 0 | 0 | | Ödev | 0 | 0 | 0 | | Proje | 0 | 0 | 0 | | Kısa sınav | 0 | 0 | 0 | | Dönem sonu sınavı için hazırlık | 5 | 1 | 5 | | Dönem sonu sınavı | 5 | 1 | 5 | | Diğer 1 | 10 | 5 | 50 | | Diğer 2 | 0 | 0 | 0 | | Toplam Çalışma Yükü | | | 126 |
|