BİLGİ PAKETİ / DERS KATALOĞU
| 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: | 3017002005 | ||||||||
| Ders İsmi: | Approximation Algorithms | ||||||||
| 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 Amaç ve İçeriği
| 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. |
Öğrenme Kazanımları
Bu dersi başarıyla tamamlayabilen öğrenciler;
|
||||||||||||||||||||||||||||||||||||
Ders Akış Planı
| Hafta | Konu | Ön Hazırlık |
| 1) | P, NP, NP-tamlık, yaklaştırma algoritmalarına giriş | |
| 2) | Küme kaplama, minimum makespan zamanlaması, Steiner ağacı, metrik TSP | |
| 3) | Doğrusal programlamaya giriş | |
| 4) | Küme kaplamanın belirlenimci ve rassal yuvarlaması, elipsoid yöntemi, ayırma prosedürleri | |
| 5) | MAX-SAT ve MAX-CUT için basit rassal algoritmalar, MAX-SAT'ın rastgele yuvarlaması, ilişkisiz paralel makinelerin zamanlaması | |
| 6) | İlişkisiz paralel makinelerin zamanlaması, küme kaplama ve en kısa yol üzerinde primal-dual yöntemi | |
| 7) | Steiner ormanı üzerinde primal-dual yöntemi | |
| 8) | Kapasitesiz tesis yerleştirme ve k-median üzerinde primal-dual yöntemi | |
| 9) | k-median, Steiner ağı | |
| 10) | Steiner ağı, çoklu kesme | |
| 11) | En seyrek kesme, metrik gömmeler | |
| 12) | Semidefinite programming, MAX-CUT | |
| 13) | Seçme araştırma konuları, sunumlar | |
| 14) | Seçme araştırma konuları, sunumlar | |
| 15) | Seçme araştırma konuları, sunumlar |
Kaynaklar
| 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: |
Ders - Program Öğrenme Kazanım İlişkisi
| Ders Öğrenme Kazanımları | 1 |
2 |
3 |
4 |
5 |
||||
|---|---|---|---|---|---|---|---|---|---|
| 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 | ||