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