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 | Diğer |
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. Performans Görevi (Seminer) | 70 |
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 |