DERS TANITIM ve UYGULAMA BİLGİLERİ

Dersin Adı Kodu Yarıyıl T+U+L (saat/hafta) Türü (Z / S) Yerel Kredi AKTS
Hesaplama Kuramı CE 516 Bahar 03+00+00 Seçmeli 3 8.0
Akademik Birim:
Öğrenim Türü:
Ön Koşullar None
Öğrenim Dili: İngilizce
Dersin Düzeyi: Yüksek Lisans
Dersin Koordinatörü: Öznur YAŞAR DİNER
Dersin Amacı: Bu ders öğrencilere hesaplama biliminin temellerini ve
bilgisayar bilimlerinde kullanıldığı alanları tanıtmayı
amaçlamaktadır.
Dersin İçeriği: Sonlu otomata, diller. Turing Makinaları. Gödel`in
tamamlanamazlık kuramı. Karmaşıklık Teorisi (Zamansal
ve uzaysal). Yakınsama Algoritmları. Olasılık
Algoritmaları
Dersin Öğrenme Çıktıları (ÖÇ):
  • 1- Matematiksel Temelleri (Mantık, Kümeler Kuramı, Çizge Kuramı, İspat Metodları) kavramak ve kullanmak
  • 2- Sonlu Otomata (Sonlu Durum Makinaları), Diller ve Turing Makinaları kurabilmek ve onları analiz edebilmek
  • 3- Gödel'in Eksiklik Teoremini matematiksel ve felsevi olarak kavramak
  • 4- Karmaşıklık Teorisi içinde Zamansal Karmaşıklık (P ve NP sınıfları) ve Uzaysal Karmaşıklık (PSPACE, L ve NL sınıfları) kavramlarını anlamak
  • 5- Temel NP-karmaşıklık problemleri kavrayabilme ve Polinom zamanlı indirgeme yapabilmek
  • 6- Yakınsama (Aproksimasyon) Algoritmaları ve Olasılık Algoritmalarını kavramak
Dersin Öğrenme Yöntem ve Teknikleri Lecturing


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık
1 Matematiksel Temeller (Mantık, Kümeler Kuramı, Çizge Kuramı, İspat Metodları)
2 Sonlu Otomata
3 Diller
4 Turing Makinaları (Sonlu Durum Makinaları)
5 Gödel`in Eksiklik Teoremi
6 Karmaşıklık Teorisi
7 Zamansal Karmaşıklık, P ve NP sınıfları
8 P ve NP sınıflarından problem örnekleri
9 NP-karmaşıklık, Polinom zamanlı indirgeme
10 NP-karmaşık Problemler
11 Uzaysal Karmaşıklık
12 PSPACE, L ve NL sınıfları
13 Yakınsama (Aproksimasyon) Algoritmaları
14 Olasılık Algoritmaları


ZORUNLU ve ÖNERİLEN OKUMALAR

Introduction to the Theory of Computation, Michael Sipser


DİĞER KAYNAKLAR

Computational Complexity, Christos H. Papadimitriou
Approximation Algorithms, Vijay V. Vazirani
Computers and Intractability, Micheal R. Garey and David S. Johnson
Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak


DEĞERLENDİRME SİSTEMİ

Yarıyıl İçi ÇalışmalarıSayıKatkı Payı (%)
Katılım - -
Laboratuvar - -
Uygulama - -
Arazi Çalışması - -
Proje 1 15
Ödev 2 10
Sunum/Jüri 1 5
Derse Özgü Staj - -
Diğer Uygulamalar (seminer, stüdyo kritiği, workshop vb.) - -
Dersle İlgili Sınıf Dışı Etkinlikler (okuma, bireysel çalışma vb.) - -
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 1 30
Final Sınavı 1 40
Total: 6 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati000
Laboratuvar000
Uygulama000
Arazi Çalışması000
Proje14040
Ödev24080
Sunum/Jüriye Hazırlık12020
Derse Özgü Staj000
Diğer Uygulamalara Hazırlık000
Dersle İlgili Sınıf Dışı Etkinlikler000
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar15050
Final Sınavı15050
Toplam İş Yükü (saat):240


PROGRAM YETERLİLİKLERİ (PY) ve ÖĞRENME ÇIKTILARI (ÖÇ) İLİŞKİSİ

# PY1 PY2 PY3 PY4 PY5 PY6 PY7 PY8 PY9
OC1 3 3 3            
OC2 3 3 3            
OC3 3 3 3            
OC4 3 3 3            
OC5 3 3 3            
OC6 3 3 3