BİLGİSAYAR MÜHENDİSLİĞİ (YL) (TEZLİ) | |||||
---|---|---|---|---|---|
Kazanılan Yeterlilik | Program Süresi | Toplam Kredi (AKTS) | Öğretim Şekli | Yeterliliğin Düzeyi ve Öğrenme Alanı | |
YÜKSEK LİSANS DERECESİ | 2 | 120 | ÖRGÜN |
TYÇ, TYYÇ, EQF-LLL, ISCED (2011):7. Düzey QF-EHEA:2. Düzey TYYÇ, ISCED (1997-2013): 48,52 |
Ders Kodu: | 3016002005 | ||||||||||
Ders İsmi: | Yaklaştırma Algoritmaları | ||||||||||
Ders Yarıyılı: | Bahar | ||||||||||
Ders Kredileri: |
|
||||||||||
Öğretim Dili: | TR | ||||||||||
Ders Koşulu: | |||||||||||
Ders İş Deneyimini Gerektiriyor mu?: | Hayır | ||||||||||
Ders İçin Önerilen Diğer Hususlar: | |||||||||||
Dersin Türü: | Anabilim Dalı/Lisansüstü Seçmeli | ||||||||||
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 ders, kesin bir çözüm bulmayı ummadığımız problemlere, yani NP-zor problemlere yaklaşık çözümler bulmakla ilgilidir. Kurs, kombinatoryal optimizasyon ve inatçılığın temel kavramlarıyla başlar ve hızlı bir şekilde açgözlü ve yerel arama gibi en basit yaklaşım tekniklerine geçer. Doğrusal programlama, yuvarlama ve primal-dual şema yoluyla birkaç yaklaşım algoritması için temel sağladığı için kursta merkezi bir rol oynar. Ayrıca rastgele algoritmaların ve yarı kesin programlamanın temellerini de gözden geçireceğiz. |
Dersin İçeriği: | Küme kaplama, metrik TSP, Steiner ağacı üzerinde kombinatoryal algoritmalar, doğrusal programlama, yuvarlama, primal-dual yöntemi, semi-definit programlama. |
Bu dersi başarıyla tamamlayabilen öğrenciler;
|
Hafta | Konu | Ön Hazırlık |
1) | P, NP, NP-tamlık, yaklaştırma algoritmalarına giriş | ders kitabı |
2) | Küme kaplama, minimum makespan zamanlaması, Steiner ağacı, metrik TSP | ders kitabı |
3) | Doğrusal programlamaya giriş | ders kitabı |
4) | Küme kaplamanın belirlenimci ve rassal yuvarlaması, elipsoid yöntemi, ayırma prosedürleri | ders kitabı |
5) | MAX-SAT ve MAX-CUT için basit rassal algoritmalar, MAX-SAT'ın rastgele yuvarlaması, ilişkisiz paralel makinelerin zamanlaması | ders kitabı |
6) | İlişkisiz paralel makinelerin zamanlaması, küme kaplama ve en kısa yol üzerinde primal-dual yöntemi | ders kitabı |
7) | Steiner ormanı üzerinde primal-dual yöntemi | ders kitabı |
8) | ara sınav | ders kitabı |
9) | Kapasitesiz tesis yerleştirme ve k-median üzerinde primal-dual yöntemi | ders kitabı |
10) | k-median, Steiner ağı | ders kitabı |
11) | Steiner ağı, çoklu kesme | ders kitabı |
12) | En seyrek kesme, metrik gömmeler | ders kitabı |
13) | Semidefinite programming, MAX-CUT | ders kitabı |
14) | Seçme araştırma konuları, sunumlar | ders kitabı |
15) | Seçme araştırma konuları, sunumlar | ders kitabı |
16) | Final | ders kitabı |
Ders Notları / Kitaplar: | Approximation Algorithms, V. Vazirani, Springer (2001) The Design of Approximation Algorithms, D.P. Williamson, D.B. Shmoys, Cambridge University Press (2011) |
Diğer Kaynaklar: | Approximation Algorithms, V. Vazirani, Springer (2001) The Design of Approximation Algorithms, D.P. Williamson, D.B. Shmoys, Cambridge University Press (2011) |
Ders Öğrenme Kazanımları | 1 |
3 |
2 |
||||||
---|---|---|---|---|---|---|---|---|---|
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. | 4 |
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. | 4 |
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 |
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. | 4 |
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. | 3 |
6) | Analitik modelleme ve deneysel araştırma tasarlama ve uygulama, süreçte karşılaşılan karmaşık durumları çözme ve yorumlama becerisi. | 2 |
7) | Bir yabancı dili (İngilizce) en az Avrupa Dil Portföyü seviyesinde sözlü ve yazılı iletişimde kullanabilme kabiliyeti. | 3 |
8) | Çok disiplinli ekiplerde liderlik etme, karmaşık durumlara çözüm geliştirme ve sorumluluk alma kabiliyeti. | 4 |
9) | Toplumsal, yasal, etik ve ahlaki değerlerin bilincinde olmak ve bu değerler çerçevesinde araştırma ve uygulama çalışmaları yapabilmek. | 3 |
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. | 5 |
Ders | |
Ödev | |
Problem Çözme |
Yazılı Sınav (Açık uçlu sorular, çoktan seçmeli, doğru yanlış, eşleştirme, boşluk doldurma, sıralama) | |
Ödev | |
Bireysel Proje |
Yarıyıl İçi Çalışmaları | Aktivite Sayısı | Katkı Payı |
Ödev | 2 | % 30 |
Ara Sınavlar | 1 | % 30 |
Yarıyıl/Yıl Sonu Sınavı | 1 | % 40 |
Toplam | % 100 | |
YARIYIL İÇİ ÇALIŞMALARININ BAŞARI NOTU KATKISI | % 60 | |
YARIYIL SONU ÇALIŞMALARININ BAŞARI NOTUNA KATKISI | % 40 | |
Toplam | % 100 |
Aktiviteler | Aktivite Sayısı | Süre (Saat) | İş Yükü |
Ders Saati | 15 | 3 | 45 |
Sınıf Dışı Ders Çalışması | 15 | 5 | 75 |
Ödevler | 2 | 30 | 60 |
Ara Sınavlar | 1 | 3 | 3 |
Final | 1 | 3 | 3 |
Toplam İş Yükü | 186 |