1. Anasayfa

Ders Notları

100% Complete (success)
Dikkat !!! Lütfen okuyunuz ...

Öğretim Üyesi (Üyeleri): Arş. Gör. Ahmet Faruk Dursun *

(*) Ders notu girebilmek için, bu alanda kendi isminiz yazıyor olmalı...

  • Bologna verilerinin girilmesi;
    ubys.omu.edu.tr adresinden,
    ÜBYS' de Öğretim Elemanları yetkisi seçilmeli... Öğretim elemanı danışmanlık işlemlerinden yapabilirsiniz...
Yıl: 2024, Dönem: Güz
BİL435, Hesapedilebilirlik Kuramı (TS 6) (mufredatId:4184, dersId: 11431, programId: 2727)
Ders Kitabı / Malzemesi / Önerilen Kaynaklar

Michael Sipser, Giriş Algoritma Teorisine, (Introduction to the Theory of Computation), Cengage Learning. Harry R. Lewis & Christos H. Papadimitriou, Elements of the Theory of Computation.

Dersin İçeriği

Turing makineleri, hesaplanabilirlik kuramı, karar verilebilirlik, durma problemi, evrensel makineler, Church-Turing tezi, indirgenebilirlik, çözülemeyen problemler ve hesaplanamazlık kavramları.

Dersin Amacı

Bu dersin amacı, hesap edilebilirlik ve karar verilebilirlik kavramlarını inceleyerek, öğrencilerin algoritmaların sınırlarını kavramalarını sağlamaktır. Öğrenciler, hesaplanabilirlik kuramının temel yapısını öğrenerek, çözülemeyen problemleri tanıyabilecek ve bu problemleri formel biçimde analiz edebilecektir.

Haftalık Ders İçeriği

Hafta Teorik Uygulama Laboratuar Ders Notları
1 Giriş ve temel kavramlar
2 Formel diller ve gramerler
3 Düzenli diller ve sonlu otomatalar
4 Deterministik ve deterministik olmayan modeller
5 Pushdown otomatalar ve bağlamdan bağımsız diller
6 Turing makineleri: tanım ve örnekler
7 Hesaplanabilirlik ve karar verilebilirlik
8 Vize Sınavı
9 Durma problemi ve evrensel Turing makineleri
10 Church-Turing Tezi
11 İndirgenebilirlik kavramı
12 Karar verilemezlik örnekleri
13 Zaman karmaşıklığı
14 P ve NP sınıfları
15 NP-Tamlık ve örnek problemler
16 Final Sınavı