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 Genel Tanıtım Bilgileri

Ders Kodu:

3017002006

Ders İsmi:

Computational Complexity

Ders Yarıyılı:

Güz

Ders Kredileri:

Teorik	Pratik	Kredi	AKTS
3	0	3	6

Öğretim Dili:

Ders Koşulu:

Ders İş Deneyimini Gerektiriyor mu?:

Hayır

Dersin Türü:

Department Elective

Dersin Seviyesi:

Yüksek Lisans

TYYÇ:7. Düzey

QF-EHEA:2. Düzey

EQF-LLL:7. Düzey

Dersin Veriliş Şekli:

Yüz yüze

Dersin Koordinatörü:

Dr.Öğr.Üyesi Recep DURANAY

Dersi Veren(ler):

Dersin Yardımcıları:

Dersin Amaç ve İçeriği

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ü.

Öğrenme Kazanımları

Bu dersi başarıyla tamamlayabilen öğrenciler;

Öğrenme Kazanımları

1 - Bilgi
Kuramsal - Olgusal
1) Hesaplama kavramının önemini ve formalizasyonunu öğrenmek
2) P ve NP dahil olmak üzere temel karmaşıklık sınıflarıyla aşina olmak, ve bir karmaşıklık sınıfına nispeten tamlık kavramının önemi anlamak
3) Bir giriş dersinin ötesinde hesapsal karmaşıklık kuramının ileri konularını öğrenmek
4) Alanın temel açık problemlerini öğrenmek
2 - Beceriler
Bilişsel - Uygulamalı
3 - Yetkinlikler
İletişim ve Sosyal Yetkinlik
Öğrenme Yetkinliği
Alana Özgü Yetkinlik
Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği

Ders Akış Planı

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ü

Kaynaklar

Ders Notları / Kitaplar:	Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak, Cambridge University Press, 2009.
Diğer Kaynaklar:

Ders - Program Öğrenme Kazanım İlişkisi

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.

Ders - Öğrenme Kazanımı İlişkisi

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.

Öğrenme Etkinliği ve Öğretme Yöntemleri

Ölçme ve Değerlendirme Yöntemleri ve Kriterleri

Ölçme ve Değerlendirme

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

İş Yükü ve AKTS Kredisi Hesaplaması

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