| Akademik Birim: |
Bilgisayar Mühendisliği Bölümü |
| Öğrenim Türü: |
Örgün Eğitim |
| Ön Koşullar |
Yok |
| Öğrenim Dili: |
İngilizce |
| Dersin Düzeyi: |
Lisans |
| Dersin Koordinatörü: |
İlktan AR |
| Dersi Veren(ler): |
İlktan AR |
| Dersin Amacı: |
Bu derste vurgu üç kavramı öğrenme üstünedir: hesaplama nedir, neler hesaplanabilir, neler hesaplanamaz? Ders konuları doğası gereği matemetikseldir ve ders boyunca ispatlar sunulur. Hesaplama problemlerinnde 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 problenmler ile diller arasındaki ilişki kurlduktan 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 otomaton (makine) ile temsil edilir. |
| Dersin Öğrenme Çıktıları (ÖÇ): |
- 1- Düzenli dilleri düzenli ifadeler ve sonlu durum makineleri kullanarak tanıyabilme, düzenli olmayan dillerin düzensizliğini ispatlayabilme.
- 2- Bağlama duyarsız diller için bağlama duyarsız gramer ve ters listeli otomata geliştirebilme, bağlama duyarsız olmayan dillerin bu özelliğini ispatlayabilme.
- 3- Hesapsal karar problemleri ile diller arasındaki ilişkiyi kavrama.
|
| Dersin Öğrenme Yöntem ve Teknikleri |
Ders |
| Hafta | Konular | Ön Hazırlık |
ÖÇ |
| 1 |
Otomatlara, Hesaplanabilirliğe ve Karmaşıklığa Genel Bakış. Matematiksel Kavramlar ve Terminoloji: Katarlar ve Demetler, Katarlar ve Diller. Sonlu Otomatlara Giriş |
Ders kitabı |
1, 2, 3 |
| 2 |
Hesaplamanın biçimsel tanımı. Deterministik Sonlu Otomatların (DFA) Tasarlanması. Düzenli Operasyonlar. |
Ders kitabı |
1 |
| 3 |
Deterministik Olmayan Sonlu Otomatın (NFA) Tanımı. NFA ve DFA'nın eşdeğerliği. Normal operasyonlar kapsamında kapatma. |
Ders kitabı |
1 |
| 4 |
Düzenli İfadelerin biçimsel tanımı. Sonlu Otomata ile eşdeğerlik. |
Ders kitabı |
1 |
| 5 |
Düzenli Olmayan Diller. Düzenli diller için Pumping Lemma. |
Ders kitabı |
1 |
| 6 |
Bağlamdan bağımsız dilbilgisinin (CFG) ve Bağlamdan Bağımsız Dilin resmi tanımı. CFG örnekleri. |
Ders kitabı |
2 |
| 7 |
Belirsizlik. Chomsky Normal Formu (CNF). |
Ders kitabı |
2 |
| 8 |
PDA resmi tanımı ve PDA örnekleri. |
Ders kitabı |
2 |
| 9 |
Kısa sınav 1. PDA'ların ve CFG'lerin denkliği. |
Ders kitabı |
2 |
| 10 |
Arasınav |
8 haftayı kapsayan değerlendirme sınavı |
| 11 |
Bağlamdan bağımsız olmayan diller. |
Ders kitabı |
2, 3 |
| 12 |
Kısa sınav 2. Turing Makinelerinin biçimsel tanımı. TM örnekleri. |
Ders kitabı |
2, 3 |
| 13 |
Karar verilebilirlik |
Ders kitabı |
2, 3 |
| 14 |
Kısa sınav 3. Final sınavı için konuların gözden geçirilmesi. |
Ders kitabı |
2, 3 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
