| 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ü: |
Habib ŞENOL |
| 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- 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 |
Yüzyüze ders anlatımı ve örnek problem çözümleri. Her ana konu için bir ödev. |
| Hafta | Konular | Ön Hazırlık |
ÖÇ |
| 1 |
Hesaplama Teorisinin Otomatlar, Hesaplanabilirlik ve Karmaşıklık alanlarına genel bakış. Matematiksel kavramlar ve terminoloji: Alfabe, karakter dizisi, formal dil tanımları |
|
1, 2, 3 |
| 2 |
Deterministik Sonlu Otomatların Tanımı ve Oluşturulması. Düzenli işlemler. |
|
1 |
| 3 |
Deterministik Olmayan Sonlu Otomatların Tanımı ve Oluşturulması. Deterministik Olmayan Sonlu Otomatların Deterministik Sonlu Otomatlarla eşitliği ve birbirine dönüştürülmesi. Düzenli işlemlere kapalılık. |
|
1 |
| 4 |
Düzenli Diller ve Düzenli ifadeler, Düzenli ifadeler üzerine işlemler. Düzenli Diller ve Düzenli ifadelerin birbirine dönüştürülmesi. |
|
1 |
| 5 |
Düzenli olmayan diller. Pompalama teoremi ve düzesizliği ispatlama. |
|
1,3 |
| 6 |
1. Arasınav |
|
| 7 |
Bağlama duyarsız gramerlerin ve Bağlama duyarsız dillerin tanımı ve örnekler |
|
2 |
| 8 |
Bağlama duyarsız gramer oluşturma. Belirsizlik. |
|
2 |
| 9 |
Bağlama duyarsız diller için ters listeli otomat dizaynı. |
|
2 |
| 10 |
Terslisteli otomata modeli ile bağlama duyarsız gramerlerin eşdeğerliği |
|
2 |
| 11 |
2. Arasınav |
|
| 12 |
Bağlama Duyarsız Olmayan Diller. Pompalama teoremi ve bağlama duyarsız olmamayı ispatlama. |
|
2, 3 |
| 13 |
Turing Makinalarının tanımı ve örnekler. |
|
2, 3 |
| 14 |
Turing Makinaları varyantları. Church-Turing Tezi. Final sınavı öncesi ödev sorularının çözümü. |
|
3 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
