Türkçe|English  
  KTU Course Catalogue  
Arama Yapmak İstediğiniz Anahtar Kelimeyi Giriniz :       
OF TEKNOLOJİ FAKÜLTESİ / YAZILIM MÜHENDİSLİĞİ / YAZILIM MÜHENDİSLİĞİ
  Genel Bilgiler
  Yönetim
  Amaç ve Öğrenme Çıktıları
  Akademik Personel
  Ders Programı
     1. Yıl
     2. Yıl
     3. Yıl
     4. Yıl
   Öğrenme Çıktıları Matrisi
 
  Doktora Programları
  Yüksek Lisans Programları
  Lisans Programları
  Meslek Yüksek Okulları
 
  Geri
  Ana Sayfa
  KTÜ Ana Sayfa

YZM3001 BİÇİMSEL DİLLER VE OTOMATA 3+0+0 ECTS:4
Yıl / Yarıyıl3. Yıl / Güz Dönemi
Ders DuzeyiLisans
Yazılım ŞekliZorunlu
BolumuYazılım Mühendisliği Bölümü
Ön KoşulYok
Öğretim SistemiYüz yüze , Grup çalışması
Dersin suresi14 hafta - haftada 3 saat teorik
Öğretim ÜyesiYRD. DOÇ. DR. Eyüp GEDİKLİ
Diğer Öğretim Üyesi / Üyeleri
Öğretim Dili Türkçe
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.
 

Öğrenme Çıktıları

BPÇK

ÖY

Bu dersi başarı ile tamamlayan öğrenciler :

ÖÇ - 1 :

Tanımlanmış diller için RE, FA, PDA, CFG, TM ve PM üretebilir.

1,2,3,4,5,6,7,8,12,13

1

ÖÇ - 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,3,4,6,12

1

ÖÇ - 3 :

Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir.

1,2,3,4,6,12,13

1

ÖÇ - 4 :

Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir.

1,2,3,4,5,6,8,12,13

1

BPÇK : Bölüm program çıktıları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), ÖÇ : Öğrenme Çıktısı

 

Dersin İç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

 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ı

 

Ders Kitabı / Malzemesi

1Ünal Yarımağan, 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öntem

Hafta

Tarih

Süre (Saat)

Katkı (%)

Arasınav

9

2

50

Dönem sonu sınavı

16

2

50

 

Öğrenci İş Yükü

İşlem adı

Haftalık süre (saat)

Hafta sayısı

Dönem toplamı

Yüz yüze eğitim

2

14

28

Sınıf dışı çalışma

3

14

42

Arasınav için hazırlık

4

3

12

Arasınav

2

1

2

Uygulama

1

14

14

Dönem sonu sınavı için hazırlık

4

3

12

Dönem sonu sınavı

2

1

2

Diğer 1

1

8

8

Toplam iş yükü

120