| 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 | |
| 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 | Gezi / Gözlem, | |
| 2 | Problemler, sınıflandırabilir | Gezi / Gözlem, | |
| 3 | Dillerin tanımlanması ve tanıyıcıların tasarlanması için yöntemler geliştirebilir. | Gezi / Gözlem, | |
| 4 | Problemlerin ve çözümlerin karmaşıklık analizini yapabilir. | Gezi / Gözlem, |
| 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. |
| Sıra | Program Çıktıları | Katkı Düzeyi | |||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | |||
| 1 | Yaşadığı toplumun bilgi toplumu olmasına katkıda bulunmak, toplumsal, bilimsel, kültürel ve etik sorunlara çözüm sunmak amaçlarıyla alanındaki bilimsel, teknolojik, sosyal veya kültürel ilerlemeleri ulusal ve uluslararası bilimsel ortamlarda (toplantılarda) tanıtır. | ||||||
| 2 | Alanında bilimsel araştırma yaparak bilgiye genişlemesine ve derinlemesine ulaşır, alanında güncel teknik ve yöntemler ile bunların kısıtları hakkında kapsamlı bilgiye sahip olup ve elde ettiği bilgiyi değerlendirir, yorumlar ve uygular. | ||||||
| 3 | Alanı ile ilgili problemleri tanımlar ve formüle eder, yeni ve/veya özgün fikir ve yöntemler geliştirir; karmaşık sistem veya süreçleri tasarlar ve tasarımlarında yenilikçi/alternatif çözümler ile gelişmekte olan yenilikçi yöntemleri kullanır. | ||||||
| 4 | Kuramsal, deneysel ve modelleme esaslı araştırmaları tasarlar ve uygular, belirsiz, sınırlı ya da eksik verileri bilimsel yöntemlerle tamamlar; verilerin toplanması, yorumlanması, duyurulması aşamalarında ve mesleki tüm etkinliklerde toplumsal, bilimsel ve etik değerleri gözetir. | ||||||
| 5 | Alanındaki uygulamaların sosyal, çevresel, sağlık, güvenlik, hukuki boyutlarını ve iş hayatı uygulamalarını bilir ve bunların getirdiği kısıtların farkındadır. Disiplin içi ve çok disiplinli takımlarda etkin bir biçimde birlikte ve ya bağımsız çalışabilir ve sorumluluk alır. | ||||||
| 6 | Bilgi ve İletişim Teknolojileri konularında ileri uygulamaları yapacak düzeyde genişlemesine ve derinlemesine bilgi sahibidir. | ||||||
| 7 | Tanımlanmış bilgi ve iletişim teknolojileri problemlerini çözmek için yöntem geliştirir ve bu yenilikçi yöntemleri uygular. | ||||||
| # | Ders Öğrenme Çıktılarının Program Çıktılarına Katkısı | PÇ 1 | PÇ 2 | PÇ 3 | PÇ 4 | PÇ 5 | PÇ 6 | PÇ 7 |
|---|---|---|---|---|---|---|---|---|
| 1 | Hesaplama kavramının felsefesini öğrenir | |||||||
| 2 | Problemler, sınıflandırabilir | |||||||
| 3 | Dillerin tanımlanması ve tanıyıcıların tasarlanması için yöntemler geliştirebilir. | |||||||
| 4 | Problemlerin ve çözümlerin karmaşıklık analizini yapabilir. |
| Değerlendirme Sistemi | |
|---|---|
| Yarıyıl Çalışmaları | Katkı Oranı |
| Toplam | 0 |
| Toplam | 0 |
| AKTS - İş Yükü Etkinlik | Sayı | Süre (Saat) | Toplam İş Yükü (Saat) |
|---|---|---|---|
| Ders Süresi (Sınav haftası dahildir: 16x toplam ders saati) | 16 | 3 | 48 |
| Sınıf Dışı Ders Çalışma Süresi(Ön çalışma, pekiştirme) | 16 | 3 | 48 |
| Ara Sınav | 1 | 25 | 25 |
| Final | 1 | 20 | 20 |
| 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ü | 282 | ||
| Toplam İş Yükü / 25 (Saat) | 11,28 | ||
| Dersin AKTS Kredisi | 6 | ||