DERS TANITIM ve UYGULAMA BİLGİLERİ

Dersin Adı Kodu Yarıyıl T+U+L (saat/hafta) Türü (Z / S) Yerel Kredi AKTS
Biçimsel Diller ve Otomatlar Kuramı CMPE 348 Bahar 03+00+00 Seçmeli 3 5
Akademik Birim: Bilgisayar Mühendisliği
Öğrenim Türü: Örgün Eğitim
Ön Koşullar Yok
Öğrenim Dili: İngilizce
Dersin Düzeyi: Lisans
Dersin Koordinatörü: - -
Dersin Amacı: Bu derste vurgu üç kavramı öğrenme üstünedir: hesaplama nedir, hangi hesaplama modeli ile neler hesaplanabilir, neler hesaplanamaz? Ders konuları doğası gereği matemetikseldir ve ders boyunca ispatlar sunulur. Hesaplama problemlerinde mantık yürütme ve ispat yapabilme yeteneklerinin geliştirilmesi dersin temel amaçlarındandır.
Dersin İçeriği: Temel hesaplama kavramlarına giriş. Hesapsal problemler ile diller arasındaki ilişki kurulduktan sonra, diller (düzenli diller, bağlama duyarsız diller, vb.) hesapsal zorluklara göre sınıflanır ve her sınıfa karşılık gelen hesaplama modeli tanıtılır. Her hesaplama modeli karşılık gelen bir otomat (makine) ile temsil edilir.
Dersin Öğrenme Çıktıları (ÖÇ):
  • 1- Soyut makinelerin kavramını ve dilleri tanıma güçlerini anlayabilme.
  • 2- Hesaplama problemlerini modellemek ve çözmek için sonlu durum makinelerini kullanabilme.
  • 3- Biçimsel diller için bağlamdan bağımsız gramerler tasarlayabilme.
  • 4- Matematiksel araçlar ve biçimsel yöntemler konusunda yetkinlik kazanabilme.
Dersin Öğrenme Yöntem ve Teknikleri Yüzyüze ders anlatımı ve örnek problem çözümleri.


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık ÖÇ
1 Otomatlar, Hesaplanabilirlik ve Karmaşıklığa Genel Bakış. Matematiksel Kavramlar ve Terminoloji Ders kitabı ve yardımcı kitap 1, 4
2 Belirli Sonlu Otomatlar. Düzenli İfadeler. Ders kitabı ve yardımcı kitap 1, 2
3 Belirli Olmayan Sonlu Otomat. NFA ve DFA Eşdeğerliği. Ders kitabı ve yardımcı kitap 2, 4
4 Düzenli İfadelerin (Regular Expressions) Resmi Tanımı. Sonlu Otomatlarda Eşdeğerlik. Ders kitabı ve yardımcı kitap 4
5 Birinci Ara Sınav - 1, 2, 4
6 Birinci Ara Sınav Sorularını Gözden Geçirme ve Değerlendirme. Düzenli Olmayan Diller. Düzenli Diller için Pompalama Lemmaları. Ders kitabı ve yardımcı kitap 1, 4
7 Düzenli Dillerin Özellikleri. Ders kitabı ve yardımcı kitap 4
8 Bağlamdan Bağımsız Gramerlerin (CFG) ve Bağlamdan Bağımsız Dillerin Tanımı. Ders kitabı ve yardımcı kitap 3, 4
9 Belirsizlik. Chomsky Normal Formu (CNF). Ders kitabı ve yardımcı kitap 3, 4
10 Yığın Otomatlarının (PDA) Tanımı. PDA Örnekleri. Ders kitabı ve yardımcı kitap 1, 4
11 İkinci Ara Sınav - 1, 2, 3, 4
12 İkinci Ara Sınav Sorularını Gözden Geçirme ve Değerlendirme. PDA’ların ve CFG’lerin Eşdeğerliği. Ders kitabı ve yardımcı kitap 4
13 Bağlamdan Bağımsız Olmayan Diller. Ders kitabı ve yardımcı kitap 3, 4
14 Turing Makinelerinin (TM) Tanımı. TM Örnekleri. Ders kitabı ve yardımcı kitap 1, 4


ZORUNLU ve ÖNERİLEN OKUMALAR

Introduction to the Theory of Computation, 3. baskı (2.baskı da kabul olunur), Michael Sipser, Cengage Learning, 2013.


DİĞER KAYNAKLAR

- Introduction to Automata Theory, Languages, and Computation, 3rd Edition, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2007. - Ders Notları


DEĞERLENDİRME SİSTEMİ

Yarıyıl İçi ÇalışmalarıSayıKatkı Payı (%)
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 2 60
Final Sınavı 1 40
Total: 3 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati14342
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar22754
Final Sınavı12929
Toplam İş Yükü (saat):125


PROGRAM YETERLİLİKLERİ (PY) ve ÖĞRENME ÇIKTILARI (ÖÇ) İLİŞKİSİ

# PY1 PY2 PY3 PY4 PY5 PY6 PY7 PY8 PY9 PY10
OC1                    
OC2                    
OC3                    
OC4