Türkçe | English
MÜHENDİSLİK FAKÜLTESİ / BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ
( I. ÖĞRETİM) - %30 İngilizce
Ders Bilgi Paketi
https://www.ktu.edu.tr/bilgisayar
Tel: +90 0462 377 2080
MF
MÜHENDİSLİK FAKÜLTESİ / BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ / ( I. ÖĞRETİM) - %30 İngilizce
Katalog Ana Sayfa
  Katalog Ana Sayfa  KTÜ Ana Sayfa   Katalog Ana Sayfa
 
 

COM2004Automata Theory3+0+0AKTS:4
Yıl / YarıyılBahar Dönemi
Ders DuzeyiLisans
Yazılım ŞekliZorunlu
BölümüBİLGİSAYAR 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 Selçuk CEVHER
Diğer Öğretim ÜyesiYok
Öğretim Diliİngilizce
StajYok
 
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,121
Ö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,121
ÖK - 3 : Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir.1,2,121
ÖK - 4 : Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir.1,2,121
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ı
 
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 Planı
 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
1Cohen, D. 1997; Introduction to Computer Theory (2nd).
2Sipser, M. 2013; Introduction to Theory of Computation (3rd).
 
İlave Kaynak
1Dersin web sayfası : http://ceng2.ktu.edu.tr/~cakir/otomata.html
 
Ölçme Yöntemi
YöntemHaftaTarih

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