|
|
| YZM3001 | Biçimsel Diller ve Otomata | 3+0+0 | AKTS:4 | | Yıl / Yarıyıl | Güz Dönemi | | Ders Duzeyi | Lisans | | Yazılım Şekli | Zorunlu | | Bölümü | YAZILIM 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 Eyüp GEDİKLİ | | Diğer Öğretim Üyesi | | | Öğretim Dili | Türkçe | | Staj | Yok | | | | Dersin Amacı: | | Ders, öğrencilere bilgisayar bilimi teorisinin matematiksel gelişimindeki çeşitli konularda, özellikle de diller ve makineler için sonlu gösterimler hakkında genel bilgi sağlamanın yanı sıra algoritmalar ve prosedürler hakkında daha resmi bir anlayış kazanmayı amaçlamaktadır. Derleyicilere yönelik uygulamalar, dizi arama ve kontrol devresi tasarımı tartışılmaktadır. Sonlu durum makinelerinin hiyerarşisi, aşağı açılan makineler, bağlamdan bağımsız gramerler ve Turing makineleri, varyasyonlarıyla birlikte analiz edilir. Karar verilebilirlik kavramları, karmaşıklık teorisi ve NP-Complete problemlerinin kapsamlı bir tartışması kursu tamamlıyor. |
| Öğrenim Kazanımları | BPKK | ÖY | | Bu dersi başarı ile tamamlayan öğrenciler : | | | | ÖK - 1 : | Tanımlanmış diller için RE, FA, PDA, CFG, TM ve PM üretebilir. | 1,8 | 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,8 | 1 | | ÖK - 3 : | Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir. | 1,8 | 1 | | ÖK - 4 : | Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir. | 1,8 | 1 | | BPKK :Bölüm program 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ı | | |
| OTOMAT TEORİSİ : Diller, Özyinelemeli Tanımlar, Düzenli İfadeler, Sonlu Otomatlar, Geçiş Grafikleri, Kleene Teoremi, Çıkışlı Sonlu Otomatlar, Düzenli Diller, Düzensiz Diller (Pumping Lemma, Myhill-Nerode Teoremi), Karar Verilebilirlik. AŞAĞI OTOMATA TEORİSİ : Bağlamdan Bağımsız Dilbilgileri (Ağaçlar, Belirsizlik), Dilbilgisel Format (Düzenli Dilbilgileri, Chomsky Normal Form, En Soldaki Türetmeler), Aşağı Açılan Otomata, CFG=PDA, Bağlamdan Bağımsız Olmayan Diller (CFL'ler için Pompalama Lemması), Bağlam -Serbest Diller (Kapama Özellikleri), CYK Algoritması. TURING TEORİSİ : Turing Makineleri (TM), Post Makineleri, Minsky Teoremi, TM'deki Çeşitlemeler (Durum İçinde Hareket Makinesi, Stay-Option Makinesi, k-Track TM, İki Yönlü Sonsuz Bant Modeli, Belirsiz Olmayan Model) TM, Salt Okunur TM), TM Dilleri (Turing Makinelerinin Kodlanması, Evrensel Turing Makineleri, Durma Sorunu), Chomsky Hiyerarşisi (Sözcük Yapısı Dilbilgileri, Bağlam Duyarlı Dilbilgileri), Bilgisayarlar (Hesaplanabilir İşlevler, Kilise Tezi) . |
| |
| Haftalık Detaylı Ders İçeriği | | 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 | Yarımağan, Ünal. 2011, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller | | | 2 | Cohen, D. 1997; Introduction to Computer Theory (2nd). | | | 3 | Sipser, M. 2013; Introduction to Theory of Computation (3rd). | | | |
| Ölçme Yöntemi | | Yöntem | Hafta | Tarih | Süre (Saat) | Katkı (%) | | Arasınav | 9 | | 2 | 50 | | Dönem sonu sınavı | 16 | | 2 | 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 | 3 | 14 | 42 | | Arasınav için hazırlık | 4 | 3 | 12 | | Arasınav | 2 | 1 | 2 | | Dönem sonu sınavı için hazırlık | 6 | 3 | 18 | | Dönem sonu sınavı | 2 | 1 | 2 | | Toplam Çalışma Yükü | | | 118 |
|