Türkçe | English
OF TEKNOLOJİ FAKÜLTESİ / YAZILIM MÜHENDİSLİĞİ BÖLÜMÜ
( I. ÖĞRETİM)
Ders Bilgi Paketi
http://www.ktu.edu.tr/ofyazilim
Tel: +90 0462 3778353
OFTF
OF TEKNOLOJİ FAKÜLTESİ / YAZILIM MÜHENDİSLİĞİ BÖLÜMÜ / ( I. ÖĞRETİM)
Katalog Ana Sayfa
  Katalog Ana Sayfa  KTÜ Ana Sayfa   Katalog Ana Sayfa
 
 

YZM3001Biçimsel Diller ve Otomata3+0+0AKTS:4
Yıl / YarıyılGüz Dönemi
Ders DuzeyiLisans
Yazılım ŞekliZorunlu
BölümüYAZILIM MÜHENDİSLİĞİ BÖLÜMÜ
Ön KoşulYok
Eğitim SistemiYüz yüze
Dersin Süresi14 hafta - haftada 3 saat teorik
Öğretim ÜyesiDr. Öğr. Üyesi Eyüp GEDİKLİ
Diğer Öğretim Üyesi
Öğretim DiliTürkçe
StajYok
 
Dersin Amacı:
Bilgisayar biliminin matematiksel gelişimi, biçimsel diller ve dillerin sonlu makine modellermeleri ile derleyicilerin temelleri hakkında bilgiler verilmesi.
 
Öğ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,81,
Ö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,81
ÖK - 3 : Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir.1,81
ÖK - 4 : Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir.1,81
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ı
 
Ders İçeriği
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 İçeriği
 HaftaDetaylı İçerikÖnerilen Kaynak
 Hafta 1Diller
 Hafta 2Özyinelemeli Tanımlamalar
 Hafta 3Düzenli İfadeler
 Hafta 4Sonlu Otomata
 Hafta 5Geçiş Grafları
 Hafta 6Kleene Teoremi
 Hafta 7Çıkışlı Sonlu Otomata
 Hafta 8Düzenli ve Düzenli Olmayan Diller
 Hafta 9Arasınav
 Hafta 10Durumdan Bağımsız Dilbilgileri
 Hafta 11Yığınlı Otomata
 Hafta 12Turing Makinaları
 Hafta 13Post Makinaları
 Hafta 14Minsky Teoremi
 Hafta 15TM Çeşitleri
 Hafta 16Dönem sonu sınavı
 
Ders Kitabı / Malzemesi
1Yarımağan, Ünal. 2011, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller
2Cohen, D. 1997; Introduction to Computer Theory (2nd).
3Sipser, M. 2013; Introduction to Theory of Computation (3rd).
 
İlave Kaynak
 
Ölçme Yöntemi
YöntemHaftaTarih

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
Diğer 1 1 8 8
Toplam Çalışma Yükü126