BİLGİSAYAR MÜHENDİSLİĞİ (YL) (TEZLİ) (İNGİLİZCE) | |||||
Yüksek Lisans | TYYÇ: 7. Düzey | QF-EHEA: 2. Düzey | EQF-LLL: 7. Düzey |
Ders Kodu: | 3017002006 | ||||||||
Ders İsmi: | Computational Complexity | ||||||||
Ders Yarıyılı: | Güz | ||||||||
Ders Kredileri: |
|
||||||||
Öğretim Dili: | EN | ||||||||
Ders Koşulu: | |||||||||
Ders İş Deneyimini Gerektiriyor mu?: | Hayır | ||||||||
Dersin Türü: | Department Elective | ||||||||
Dersin Seviyesi: |
|
||||||||
Dersin Veriliş Şekli: | Yüz yüze | ||||||||
Dersin Koordinatörü: | Dr.Öğr.Üyesi Recep DURANAY | ||||||||
Dersi Veren(ler): | |||||||||
Dersin Yardımcıları: |
Dersin Amacı: | Bu dersin amacı modern hesapsal karmaşıklık kuramının özellikle son 30 yılda ortaya koyduğu temel kavramları tartışmaktır. Ders klasik konulardan olan P, NP ve NP-tamlığın tanımıyla başlar. Daha sonra yer karmaşıklığı, devre karmaşıklığı gibi konuları hızlıca geçerek ispat sistemlerinden, kuantum hesaplamadan, PCP teoreminden ve seçme ileri konulardan bahseder. |
Dersin İçeriği: | P, NP, NP-tamlık, yer karmaşıklığı, devreler, rassal hesaplama, etkileşimli ispatlar, kuantum hesaplama, PCP teoremi, ispat karmaşıklığı, cebirsel hesaplama modelleri, P vs NP probleminin çözümü. |
Bu dersi başarıyla tamamlayabilen öğrenciler;
|
Hafta | Konu | Ön Hazırlık |
1) | Giriş, Turing makineleri | |
2) | P, NP, NP-tamlık | |
3) | Yer karmaşıklığı, PSPACE, NL | |
4) | Polinomyal hiyerarşisi ve alternasyonlar | |
5) | Boolean devreler | |
6) | Boolean devreler, rassal hesaplama | |
7) | Rassal hesaplama | |
8) | Etkileşimli ispatlar | |
9) | Etkileşimli hesaplama | |
10) | Kuantum hesaplama | |
11) | Kuantum hesaplama | |
12) | PCP teoremi | |
13) | İspat karmaşıklığı, cebirsel hesaplama modelleri | |
14) | Cebirsel hesaplama modelleri, P ve NP probleminin çözümü | |
15) | P ve NP probleminin çözümü |
Ders Notları / Kitaplar: | Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak, Cambridge University Press, 2009. |
Diğer Kaynaklar: |
Ders Öğrenme Kazanımları | 1 |
2 |
3 |
4 |
|||||
---|---|---|---|---|---|---|---|---|---|
Program Kazanımları | |||||||||
1) Bilgisayar Bilimi ve Mühendisliği alanında bilimsel araştırma yaparak geniş ve derin bilgilere ulaşma, değerlendirme, yorumlama ve uygulama becerisi. | |||||||||
2) Sınırlı ya da eksik bilgiyi kapatmak ve uygulamak için bilimsel yöntemleri kullanma ve farklı disiplinlerin bilgilerini bütünleştirme kabiliyeti. | |||||||||
3) Bilgisayar Bilimi ve Mühendisliği problemlerini kurgulayabilme, problemleri çözmek için yöntemler geliştirebilme ve çözümde yenilikçi yöntemler kullanabilme. | |||||||||
4) Yeni ve/veya orijinal fikirler ve algoritmalar geliştirme becerisi; sistem, bileşen veya süreç tasarımında yenilikçi çözümler geliştirmek. | |||||||||
5) Bilgisayar Mühendisliğinde uygulanan güncel teknikler ve yöntemler ve bunların kısıtları hakkında geniş bilgi sahibi olma kabiliyeti. | |||||||||
6) Analitik modelleme ve deneysel araştırma tasarlama ve uygulama, süreçte karşılaşılan karmaşık durumları çözme ve yorumlama becerisi. | |||||||||
7) Bir yabancı dili (İngilizce) en az Avrupa Dil Portföyü seviyesinde sözlü ve yazılı iletişimde kullanabilme kabiliyeti. | |||||||||
8) Çok disiplinli ekiplerde liderlik etme, karmaşık durumlara çözüm geliştirme ve sorumluluk alma kabiliyeti. | |||||||||
9) Toplumsal, yasal, etik ve ahlaki değerlerin bilincinde olmak ve bu değerler çerçevesinde araştırma ve uygulama çalışmaları yapabilmek. | |||||||||
10) Bilgisayar Bilimi ve Mühendisliği alanında yeni ve gelişmekte olan uygulamalar hakkında farkındalık ve bunları inceleme ve gerekirse öğrenme kabiliyeti. |
Etkisi Yok | 1 En Düşük | 2 Düşük | 3 Orta | 4 Yüksek | 5 En Yüksek |
Dersin Program Kazanımlarına Etkisi | Katkı Payı | |
1) | Bilgisayar Bilimi ve Mühendisliği alanında bilimsel araştırma yaparak geniş ve derin bilgilere ulaşma, değerlendirme, yorumlama ve uygulama becerisi. | |
2) | Sınırlı ya da eksik bilgiyi kapatmak ve uygulamak için bilimsel yöntemleri kullanma ve farklı disiplinlerin bilgilerini bütünleştirme kabiliyeti. | |
3) | Bilgisayar Bilimi ve Mühendisliği problemlerini kurgulayabilme, problemleri çözmek için yöntemler geliştirebilme ve çözümde yenilikçi yöntemler kullanabilme. | |
4) | Yeni ve/veya orijinal fikirler ve algoritmalar geliştirme becerisi; sistem, bileşen veya süreç tasarımında yenilikçi çözümler geliştirmek. | |
5) | Bilgisayar Mühendisliğinde uygulanan güncel teknikler ve yöntemler ve bunların kısıtları hakkında geniş bilgi sahibi olma kabiliyeti. | |
6) | Analitik modelleme ve deneysel araştırma tasarlama ve uygulama, süreçte karşılaşılan karmaşık durumları çözme ve yorumlama becerisi. | |
7) | Bir yabancı dili (İngilizce) en az Avrupa Dil Portföyü seviyesinde sözlü ve yazılı iletişimde kullanabilme kabiliyeti. | |
8) | Çok disiplinli ekiplerde liderlik etme, karmaşık durumlara çözüm geliştirme ve sorumluluk alma kabiliyeti. | |
9) | Toplumsal, yasal, etik ve ahlaki değerlerin bilincinde olmak ve bu değerler çerçevesinde araştırma ve uygulama çalışmaları yapabilmek. | |
10) | Bilgisayar Bilimi ve Mühendisliği alanında yeni ve gelişmekte olan uygulamalar hakkında farkındalık ve bunları inceleme ve gerekirse öğrenme kabiliyeti. |
Yarıyıl İçi Çalışmaları | Aktivite Sayısı | Katkı Payı |
Ödev | 4 | % 40 |
Ara Sınavlar | 1 | % 30 |
Yarıyıl/Yıl Sonu Sınavı | 1 | % 30 |
Toplam | % 100 | |
YARIYIL İÇİ ÇALIŞMALARININ BAŞARI NOTU KATKISI | % 70 | |
YARIYIL SONU ÇALIŞMALARININ BAŞARI NOTUNA KATKISI | % 30 | |
Toplam | % 100 |
Aktiviteler | Aktivite Sayısı | Süre (Saat) | İş Yükü |
Ders Saati | 15 | 3 | 45 |
Sınıf Dışı Ders Çalışması | 15 | 3 | 45 |
Ödevler | 4 | 15 | 60 |
Ara Sınavlar | 1 | 10 | 10 |
Final | 1 | 10 | 10 |
Toplam İş Yükü | 170 |