GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| 501002252010 | AUTOMATA THEORY | Ders | 2 | 3 | 4,00 |
Dersin Seviyesi
Lisans
Dersin Sunulduğu Dil
İngilizce
Dersin Amacı
Bu dersin amacı, öğrencilerin bilgisayar kuramının temelini oluşturan teoriler arasında yer alan; sonlu otomata teorisi, alta bastırmalı otomata teorisi ve Turing teorisi hakkında bilgi sahibi olmasını, bu modellerin bilgisayar bilimlerindeki uygulamalarını tanıyabilmesini ve soyut düşünme ve biçimsel ifade yeteneğini kazanmasını sağlamaktır.
Dersi Veren Öğretim Görevlisi/Görevlileri
Doç. Dr. Rıza Cenk ERDUR
Öğrenme Çıktıları
| 1 | Özyineli tanımlar yazabilme. |
| 2 | Düzenli dilleri düzenli ifadeler ile tanımlayabilme |
| 3 | Sonlu durum makinesi modelleri geliştirebilme. |
| 4 | Deterministik olmayan sonlu otomata modellerini deterministik sonlu otomata modellerine çevirebilme. |
| 5 | Sonlu otomatanın farklı gösterimleri arasında çevrim yapabilme. |
| 6 | Çıktılı sonlu otomata modelleri geliştirebilme. |
| 7 | Bir dilin düzensiz bir dil olduğunu ispatlayabilme. |
| 8 | Bağlamdan bağımsız gramerler yazabilme. |
| 9 | Bir bağlamdan bağımsız grameri Chomsky Normal Forma çevirebilme. |
| 10 | Alta bastırmalı otomata modelleri oluşturabilme. |
| 11 | Dil tanıyan veya fonksiyon hesaplayabilen Turing makineleri tasarlayabilme. |
| 12 | Bilgisayar kuramının temel modellerinin bilgisayar bilimlerindeki somut uygulamalarını tanıyabilme. |
| 13 | Soyut düşünme yeteneği kazanabilme. |
| 14 | Karar verilemezlik ve "halting" problemini tanımlayabilme. |
Öğretim Sistemi
Birinci Öğretim
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
Dersin İçeriği
Temel kavramlar ve ispat yöntemleri. Özyinelemeli tanımlar. Düzenli İfadeler. Sonlu Otomata. Geçiş Çizgeleri. Kleene Kuramı. Çıktılı sonlu otomata. Düzenli ve düzenli olmayan diller. Sonlu otomata için karar verilebilirlik. Bağlamdan bağımsız gramerler. Düzenli gramerler. Chomsky Normal Form. Alta bastırmalı otomata modelleri. Bağlamdan bağımsız diller ve bağlamdan bağımsız olmayan diller. Ayrıştırma. Turing makineleri.
Haftalık Ayrıntılı Ders İçeriği
| Hafta | Konular (Teorik) | Öğretim Yöntem ve Teknikleri | Ön Hazırlık |
|---|---|---|---|
| 1 | Giriş: Otomata teorisine giriş ve dersin tanıtımı. Alfabe, sembol, kelime ve dil kavramları. Temel ispat yöntemlerinin özetlenmesi. | ||
| 2 | Özyinelemeli Tanımlar: Kümelerin ve dillerin özyinelemeli olarak tanımlanması. Düzenli İfadeler: Düzenli ifade kavramı ve gösterim. Dillerin düzenli ifadeler ile tanımlanması. Düzenli ifadeler kümesinin özyinelemeli tanımı. Düzenli ifadeler ile ilgili çeşitli örneklerin incelenmesi. | ||
| 3 | Sonlu Otomata: Sonlu otomata tanımı. Düzenli dillere ilişkin sonlu otomata modelleri. Sonlu otomata modelinin bilgisayar bilimlerinde uygulamaları: iletişim protokolü tasarımı ve sözcük çözümleme. | ||
| 4 | Geçiş Çizgeleri: Geçiş çizgesi modeli ve deterministik olmayan modeller. Kleene Kuramı: Düzenli ifadeler, sonlu otomata modelleri ve geçiş çizgesi modelleri arasında çevrim yöntemlerinin ayrıntılı olarak incelenmesi. | ||
| 5 | Kleene Kuramı: Kleene kuramı ile ilgili çeşitli örnekler yapılarak konunun pekiştirilmesi. | ||
| 6 | Çıktılı Sonlu Otomata: Mealey ve Moore makinelerinin incelenmesi. Düzenli Diller ve özellikleri. | ||
| 7 | Düzenli Olmayan Diller, "Pumping Lemma" ve Sonlu Otomata için Karar Verilebilirlik: İki düzenli ifade veya iki sonlu otomata modelinin aynı dili kabul edip etmediğinin bulunması. Bir sonlu otomatanın sonlu veya sonsuz sayıda kelime kabul edip etmediğinin belirlenmesi. Ara sınav için tekrar amaçlı çeşitli problem çözümleri. | ||
| 8 | Ara sınav | ||
| 9 | Bağlamdan Bağımsız Gramerler (CFG): Sözdizim, Soldan ve sağdan türetimler, türetme ağaçları, toplam dil ağaçları. | ||
| 10 | Bağlamdan Bağımsız Gramerler için Biçemler: Düzenli gramerler, Normalizasyon: Chomsky Normal Form. | ||
| 11 | Alta bastırmalı Otomata Teorisi: Deterministik ve deterministik olmayan alta bastırmalı otomata modelleri. | ||
| 12 | Bağlamdan Bağımsız Diller ve Bağlamdan Bağımsız Olmayan Diller: Özellikler, “Pumping Lemma” kuramının bağlamdan bağımsız olmayan dilleri belirlemede kullanımı. | ||
| 13 | Ayrıştırma: Aşağıdan yukarıya ve yukarıdan aşağıya ayrıştırma algoritmaları. | ||
| 14 | Turing Makineleri: Turing kuramına giriş. Dil tanıyan Turing makinelerinin tasarımı. “Unary” kodlama gösterimi ve fonksiyon hesaplayan Turing makineleri. | ||
| 15 | Karar verilemezlik ve "halting" problemi. | ||
| 16 | Final Sınavı |
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
Ders Kitabı: 1. Cohen, I. A. D., “Introduction to Computer Theory”, John Wiley and Sons, Inc., Second Edition, 1997. Yardımcı Kitaplar: 1. Hopcroft, J.E., Motwani, R., and Ullman, J.D., “Introduction to Automata Theory, Languages, and Computation”, Addison-Wesley, Second Edition, 2001. 2. Yarımağan, Ü., Özdevinirler Kuramı ve Biçimsel Diller, Bıçaklar Kitabevi, Ankara, 2003.
Planlanan Öğrenme Aktiviteleri ve Metodları
Değerlendirme
| Yarıyıl (Yıl) İçi Etkinlikleri | Adet | Değer |
|---|---|---|
| Ara Sınav | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | Adet | Değer |
| Final Sınavı | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) İçi Etkinlikleri | 40 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | 60 | |
Staj Durumu
Yok
İş Yükü Hesaplaması
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ara Sınav | 1 | 2 | 2 |
| Final Sınavı | 1 | 2 | 2 |
| Derse Katılım | 14 | 3 | 42 |
| Problem Çözümü | 8 | 3 | 24 |
| Ara Sınav İçin Bireysel Çalışma | 1 | 21 | 21 |
| Final Sınavı içiin Bireysel Çalışma | 1 | 28 | 28 |
| Toplam İş Yükü (saat) | 119 | ||
Program ve Öğrenme Çıktıları İlişkisi
| PÇ 1 | |
| ÖÇ 1 | |
| ÖÇ 2 | |
| ÖÇ 3 | |
| ÖÇ 4 | |
| ÖÇ 5 | |
| ÖÇ 6 | |
| ÖÇ 7 | |
| ÖÇ 8 | |
| ÖÇ 9 | |
| ÖÇ 10 | |
| ÖÇ 11 | |
| ÖÇ 12 | |
| ÖÇ 13 | |
| ÖÇ 14 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek