GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| MAT2402 | REKÜRSİF FONKSİYONLAR | Ders | 4 | 8 | 4,00 |
Dersin Seviyesi
Lisans
Dersin Sunulduğu Dil
Türkçe
Dersin Amacı
Bu dersin amacı: Temel hesaplama modellerini ve aralarındaki ilişkileri anlayabilme ve yorumlayabilme; Hesaplama teorisinin tarihsel ve felsefesel temellerini ele alabilme; Hesaplanabilirlik teorisinin temel sonuçlarının bilgisayar bilimleri ve yapay zeka gibi alanlardaki etkilerinden haberdar olabilme; Hesaplanabilirlik teorisi ile lojik arasındaki yakın bağlantıyı anlayabilme ve yorumlayabilme; Hesaplanabilirlik teorisindeki en son kavram ve gelişmeleri uygulayabilme.
Dersi Veren Öğretim Görevlisi/Görevlileri
Assistant Professor Dr. Tahsin ONER
Öğrenme Çıktıları
| 1 | Hesaplamanın sınırları için bir değerlendirme geliştirebilme. |
| 2 | Çözülemeyen ya da hesaplanması mümkün olmayan problemleri belirleyebilme. |
| 3 | Tümevarım ve köşegenleştirme gibi temel teknikleri kavrayabilme. |
Öğretim Sistemi
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
Dersin İçeriği
Hesaplanabilir fonksiyon tanımı, konunun tarihçesi, veri tiplerinin de kodlanması, sayılabilir ve sayılamaz kümeler, URM ve halting problemi, Turing makineleri, hesaplanabilirliğe cebirsel yaklaşım, primitif rekürsif fonksiyonlar, kısmi rekürsif fonksiyonlar, Church-Turing tezi, Kleene Rekürsion Teoremi, S-m-n Teoremi, Ackermann fonksiyonu., Rekürsif kümeler.
Haftalık Ayrıntılı Ders İçeriği
| Hafta | Konular (Teorik) | Uygulama | Öğretim Yöntem ve Teknikleri | Ön Hazırlık |
|---|---|---|---|---|
| 0 | Hesaplanabilir fonksiyonun tanımı; exp, check, terminate fonksiyonlarının tanımları ve hesaplanabilirlikleri, issortingfun fonksiyonu ve saptanabilirlik sorunu. | Ders hakkında kısa bilgilendirme | ||
| 1 | Hesaplanabilirlikteki problemler; karmaşıklık, indirgenebilirlik, soyut hesaplanabilirlik durumları; matematiksel, felsefesel ve bilgisayar bilimleri açısından yaklaşımlar. | Rehberli problem çözümü. | ||
| 2 | Sonlu ve sonsuz küme; sayılabilir ve sayılamaz küme; kardinal sayı kavramlarının tanımları, köşegen yöntemi ve Cantor Teoremi; bir kümenin sayılabilirliği üzerine teoremler, sayılamaz kümelere örnekler. | Rehberli problem çözümü. | ||
| 3 | Kümeler Teorisine dönüş: Kontinuum Hipotezi, Hilbert problemi, tarihsel açıklamalar, ve kümelerinin kardinal sayıları, Gödel ve Cohen’nin sonuçları. | Rehberli problem çözümü. | ||
| 4 | Dizilerin de kodlanması; Kleene-Star pairing fonksiyonu (x, y). * ın bir elemanının kodunun uzunluğu. | Rehberli problem çözümü. | ||
| 5 | Bazı veri tipleri üzerindeki hesaplanabilirliğin üzerindeki hesaplanabilirliğe indirgenmesi, kodlama ve kod çözme (decode). | Rehberli problem çözümü. | ||
| 6 | Kısmi fonksiyonlar, -notasyon, yüklemler, Boole bağlaçları ve yüklemler, n-li bağıntı ve n-li fonksiyonlar. | Genel problem Çözümü ve Arasınava hazırlık. | ||
| 7 | Ara Sınav | |||
| 8 | Kısmi fonksiyonlar için bir hesaplama modeli: URM, URM nin sintaks ve semantiği, URM nin komutları, URM örnekleri. | Rehberli problem çözümü. | ||
| 9 | Halting problemi ve saptanamazlığı. | Rehberli problem çözümü. | ||
| 10 | Hesaplanabilirliğe cebirsel yaklaşım: zero, succ, proj primitif rekürsif baz fonksiyonları. | Rehberli problem çözümü. | ||
| 11 | Bir Turing makinesinin tanımı, Turing-Hesaplanabilir fonksiyonlar ve örnekler, URM komutlarının simülasyonları. | Ödev problemlerinin tartışılması | ||
| 12 | Kısmi rekürsif fonksiyonlar, Ackermann fonksiyonu, rekürsif kümeler ve rekürsif enumere edilebilir yüklemler. | Rehberli problem çözümü. | ||
| 13 | Church-Turing Tezi | Rehberli problem çözümü. | ||
| 14 | Kleene Rekürsion Teoremi, S-m-n Teoremi. | Rehberli problem çözümü. | ||
| 15 | Final Sınavı |
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
1. N. J. Cutland, “An Introduction to Recursive Function Theory”, Cambridge University Press, (1984). 2. H. R. Lewis and C. H. Papadimitriou, “Elements of the Theory of Computation”, Prentice Hall, 2nd edition, (1998). 3. J. Martin, “Introduction to Languages and the Theory of Computation”, McGraw-Hill, (2003). 4. D. J. Velleman, “How To Prove It”, Cambridge University Pres, 2nd edition, (2006).
Planlanan Öğrenme Aktiviteleri ve Metodları
Etkinlikler ayrıntılı olarak "Değerlendirme" ve "İş Yükü Hesaplaması" bölümlerinde verilmiştir.
Değerlendirme
| Yarıyıl (Yıl) İçi Etkinlikleri | Adet | Değer |
|---|---|---|
| Ara Sınav | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | Adet | Değer |
| Final Sınavı | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) İçi Etkinlikleri | 40 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | 60 | |
Staj Durumu
Yok
İş Yükü Hesaplaması
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ara Sınav | 1 | 2 | 2 |
| Final Sınavı | 1 | 2 | 2 |
| Derse Katılım | 16 | 2 | 32 |
| Uygulama/Pratik | 16 | 1 | 16 |
| Ara Sınav İçin Bireysel Çalışma | 1 | 25 | 25 |
| Final Sınavı içiin Bireysel Çalışma | 1 | 43 | 43 |
| Toplam İş Yükü (saat) | 120 | ||
Program ve Öğrenme Çıktıları İlişkisi
| PÇ 1 | PÇ 2 | PÇ 3 | PÇ 4 | PÇ 5 | PÇ 6 | PÇ 7 | PÇ 8 | PÇ 9 | PÇ 10 | PÇ 11 | PÇ 12 | PÇ 13 | PÇ 14 | PÇ 15 | |
| ÖÇ 1 | 4 | 4 | 4 | 5 | 4 | ||||||||||
| ÖÇ 2 | 4 | 4 | 4 | 5 | 4 | ||||||||||
| ÖÇ 3 | 4 | 4 | 4 | 5 | 4 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek