| 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. |
| Hafta | Konular | Ö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 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
