| Ders Adı | Kodu | Yarıyıl | T+U Saat | Kredi | AKTS |
|---|---|---|---|---|---|
| İleri Hesaplama Teorisi | BSM 508 | 0 | 3 + 0 | 3 | 6 |
| Ön Koşul Dersleri | |
| Önerilen Seçmeli Dersler | Algoritma Analizi ve tasarımı, Derleyici Tasarımı |
| Dersin Dili | Türkçe |
| Dersin Seviyesi | YUKSEK_LISANS |
| Dersin Türü | Seçmeli |
| Dersin Koordinatörü | Prof.Dr. NEJAT YUMUŞAK |
| Dersi Verenler | Prof.Dr. NEJAT YUMUŞAK, |
| Dersin Yardımcıları | |
| Dersin Kategorisi | Alanına Uygun Temel Öğretim |
| Dersin Amacı | Hesaplama kavramı ve karmaşıklık teorisi hakkında genel ve ileri düzeyde bilgi sunumu yapmak. |
| Dersin İçeriği | Hesaplamanın tarihçesi, Chomsky sınıflandırması, Özdevinirler kuramı ve biçimsellik kavramları, Deterministik ve nondeterministik özdevinirler ve Regüler diller; Yığıtlı özdevinirler ve Bağlamdan bağımsız diller, Turing makineleri ve sayılabilir diller; Karar verilebilirlik, İzlenebilirlik, sayılabilirlik, Çözülemezlik kavramları; Karmaşıklık sınıfları; İndirgenebilirlik ve yöntemleri. |
| # | Ders Öğrenme Çıktıları | Öğretim Yöntemleri | Ölçme Yöntemleri |
|---|---|---|---|
| 1 | Hesaplama kavramının felsefesini öğrenir | Problem Çözme, | Ödev, |
| 2 | Problemler, sınıflandırabilir | Problem Çözme, | Ödev, |
| 3 | Dillerin tanımlanması ve tanıyıcıların tasarlanması için yöntemler geliştirebilir. | Problem Çözme, | Sınav, |
| 4 | Problemlerin ve çözümlerin karmaşıklık analizini yapabilir. | Problem Çözme, | Ödev, |
| Hafta | Ders Konuları | Ön Hazırlık |
|---|---|---|
| 1 | Hesaplama kavramı ve Hesaplamanın tarihçesi. | |
| 2 | Deterministik Sonlu Özdevinirlier, Regüler İfadeler | |
| 3 | DFA , NFA, boşluklu NFA ve bunların durum sayısı indirgenmeleri | |
| 4 | Bağlamdan Bağımsız Diller ve PDA makineleri | |
| 5 | PDA ve eşdeğer Gramerin bulunması, Chomsky Normal Formlar | |
| 6 | Geribech Normal Form ve Parsing | |
| 7 | Turing Makineleri | |
| 8 | Karar verilebilir ve karar verilemez diller | |
| 9 | İzlenebilir Problemler | |
| 10 | Ara sınav | |
| 11 | Reducibility | |
| 12 | Çözülebilir ve çözülemez Problemler | |
| 13 | Karmaşıklık sınıfları | |
| 14 | P, NP, NP-Tam, NP-Hard problemler |
| Kaynaklar | |
|---|---|
| Ders Notu | |
| Ders Kaynakları | Özdevinirler Kuramı ve Biçimsel Diller; Prof.Dr.Ünal YARIMAĞAN İntroduction to the Theory of Computation, Michael Sipser. |
| Değerlendirme Sistemi | |
|---|---|
| Yarıyıl Çalışmaları | Katkı Oranı |
| 1. Ara Sınav | 30 |
| 1. Ödev | 20 |
| 2. Ödev | 20 |
| 1. Performans Görevi (Seminer) | 30 |
| Toplam | 100 |
| 1. Yıl İçinin Başarıya | 50 |
| 1. Final | 50 |
| Toplam | 100 |
| AKTS - İş Yükü Etkinlik | Sayı | Süre (Saat) | Toplam İş Yükü (Saat) |
|---|---|---|---|
| Ders Süresi (Sınav haftası dahildir: 16x toplam ders saati) | 14 | 3 | 42 |
| Kısa Sınav | 1 | 5 | 5 |
| Ara Sınav | 1 | 15 | 15 |
| Ödev | 1 | 20 | 20 |
| Performans Görevi (Seminer) | 1 | 20 | 20 |
| Final | 1 | 25 | 25 |
| Sınıf Dışı Ders Çalışma Süresi(Ön çalışma, pekiştirme) | 14 | 1 | 14 |
| Toplam İş Yükü | 141 | ||
| Toplam İş Yükü / 25 (Saat) | 5,64 | ||
| Dersin AKTS Kredisi | 6 | ||