| Bilgisayar Mühendisliği (YL) (Tezli) (İngilizce) | |||||
| Yüksek Lisans | TYYÇ: 7. Düzey | QF-EHEA: 2. Düzey | EQF-LLL: 7. Düzey | ||
| Ders Kodu: | COE5003 | ||||
| Ders İsmi: | Approximation Algorithms | ||||
| Ders Yarıyılı: | Bahar | ||||
| Ders Kredileri: |
|
||||
| Öğretim Dili: | English | ||||
| Ders Koşulu: | |||||
| Ders İş Deneyimini Gerektiriyor mu?: | Hayır | ||||
| Dersin Türü: | Bölüm/Program Seçmeli | ||||
| Dersin Seviyesi: |
|
||||
| Dersin Veriliş Şekli: | |||||
| Dersin Koordinatörü: | Doç. Dr. EMİR SEYYEDABBASİ | ||||
| Dersi Veren(ler): | Ali Çivril | ||||
| Dersin Yardımcıları: |
| Dersin Amacı: | Bu dersin amacı, kesin bir çözüm bulma umudumuzun olmadığı problemlere, yani NP-zor problemlere yaklaşık çözümler bulmak için algoritmik teknikleri tanıtmaktır. |
| Dersin İçeriği: | Ders, kombinatoryal optimizasyon ve çözülemezliğin temel kavramlarıyla başlar ve açgözlü ve yerel arama gibi en basit yaklaştırma tekniklerine hızla geçer. Doğrusal programlama, yuvarlama ve primal-dual şeması yoluyla pek çok yaklaştırma algoritmasının temelini oluşturduğu için derste merkezi bir rol oynar. Ayrıca rasgele algoritmaların ve semi-definit programlamanın temellerini de gözden geçireceğiz. |
|
Bu dersi başarıyla tamamlayabilen öğrenciler;
1) Yaklaştırma algoritmalarının analizini anlamak için matematiksel olgunluk oluşturmak ve geliştirmek. 2) Açgözlülük ve yerel arama gibi temel kombinatoryal teknikleri tanıyabilme. 3) Doğrusal programlamanın yaklaştırma algoritmalarının tasarımındaki önemini, özellikle iki teknikle anlamak: yuvarlama ve primal-dual şeması. 4) Semi-definit programlama ile tanışmak. 5) Derste öğretilenlere dayalı yeni yaklaşım algoritmaları geliştirebilme ve böylece araştırmaya hazırlanabilme. |
| Hafta | Konu | Ön Hazırlık |
| 1) | Yaklaştırma algoritmalarına giriş | |
| 2) | Küme kaplama (açgözlü), minimum makespan ayarlama (açgözlü) | |
| 3) | Steiner ağacı problemi, metrik gezgin satıcı problemi, knapsack problemi | |
| 4) | Lineer programlamaya giriş | |
| 5) | Küme kaplama (belirlenimci yuvarlama), küme kaplama (rasgele yuvarlama) | |
| 6) | Tesis yerleştirme (belirlenimci yuvarlama) | |
| 7) | Kutu paketleme (belirlenimci yuvarlama) | |
| 8) | MAX SAT, MAX CUT (Basit rasgele algoritmalar, rasgele yuvarlama), rasgeleliği ortadan kaldırma | |
| 9) | Küme kaplama (primal-dual), en kısa yol (primal-dual) | |
| 10) | Steiner ormanı problemi (primal-dual) | |
| 11) | Tesis yerleştirme (primal-dual), k-median (primal-dual) | |
| 12) | Steiner ağı (yinelemeli yuvarlama) | |
| 13) | MAX CUT ile semi-definite programlamaya (SDP) giriş | |
| 14) | 3 boyanabilir çizgeleri boyama (SDP) |
| 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 |
2 |
3 |
4 |
5 |
|||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Program Kazanımları | ||||||||||||
| 1) Lisans düzeyi yeterliliklerine dayalı olarak, aynı veya farklı bir alanda bilgilerini uzmanlık düzeyinde geliştirebilme ve derinleştirebilme. | ||||||||||||
| 2) Alanında edindiği uzmanlık düzeyindeki kuramsal ve uygulamalı bilgileri kullanabilme. | ||||||||||||
| 3) Alanında edindiği bilgileri farklı disiplin alanlarından gelen bilgilerle bütünleştirerek yorumlayabilme ve yeni bilgiler oluşturabilme, | ||||||||||||
| 4) Alanı ile ilgili karşılaşılan sorunları araştırma yöntemlerini kullanarak çözümleyebilme. | ||||||||||||
| 5) Alanı ile ilgili uzmanlık gerektiren bir çalışmayı bağımsız olarak yürütebilme. | ||||||||||||
| 6) Alanı ile ilgili uygulamalarda karşılaşılan ve öngörülemeyen karmaşık sorunların çözümü için yeni stratejik yaklaşımlar geliştirebilme ve sorumluluk alarak çözüm üretebilme. | ||||||||||||
| 7) Alanında edindiği uzmanlık düzeyindeki bilgi ve becerileri eleştirel bir yaklaşımla değerlendirebilme ve öğrenmesini yönlendirebilme. | ||||||||||||
| 8) Alanındaki güncel gelişmeleri ve kendi çalışmalarını, nicel ve nitel veriler ile destekleyerek alanındaki ve alan dışındaki gruplara, yazılı, sözlü ve görsel olarak sistemli biçimde aktarabilme. | ||||||||||||
| 9) Bir yabancı dili en az Avrupa Dil Portföyü B2 Genel Düzeyi'nde kullanarak sözlü ve yazılı iletişim kurabilme. | ||||||||||||
| 10) Alanının gerektirdiği düzeyde bilgisayar yazılımı ile birlikte bilişim ve iletişim teknolojilerini ileri düzeyde kullanabilme. | ||||||||||||
| 11) Alanı ile ilgili verilerin toplanması, yorumlanması, uygulanması ve duyurulması aşamalarında toplumsal, bilimsel, kültürel ve etik değerleri gözeterek denetleyebilme ve bu değerleri öğretebilme. | ||||||||||||
| 12) Alanında özümsedikleri bilgiyi, problem çözme ve/veya uygulama becerilerini, disiplinlerarası çalışmalarda kullanabilme. | ||||||||||||
| Etkisi Yok | 1 En Düşük | 2 Orta | 3 En Yüksek |
| Dersin Program Kazanımlarına Etkisi | Katkı Payı | |
| 1) | Lisans düzeyi yeterliliklerine dayalı olarak, aynı veya farklı bir alanda bilgilerini uzmanlık düzeyinde geliştirebilme ve derinleştirebilme. | 3 |
| 2) | Alanında edindiği uzmanlık düzeyindeki kuramsal ve uygulamalı bilgileri kullanabilme. | 3 |
| 3) | Alanında edindiği bilgileri farklı disiplin alanlarından gelen bilgilerle bütünleştirerek yorumlayabilme ve yeni bilgiler oluşturabilme, | 2 |
| 4) | Alanı ile ilgili karşılaşılan sorunları araştırma yöntemlerini kullanarak çözümleyebilme. | 3 |
| 5) | Alanı ile ilgili uzmanlık gerektiren bir çalışmayı bağımsız olarak yürütebilme. | 1 |
| 6) | Alanı ile ilgili uygulamalarda karşılaşılan ve öngörülemeyen karmaşık sorunların çözümü için yeni stratejik yaklaşımlar geliştirebilme ve sorumluluk alarak çözüm üretebilme. | 2 |
| 7) | Alanında edindiği uzmanlık düzeyindeki bilgi ve becerileri eleştirel bir yaklaşımla değerlendirebilme ve öğrenmesini yönlendirebilme. | 3 |
| 8) | Alanındaki güncel gelişmeleri ve kendi çalışmalarını, nicel ve nitel veriler ile destekleyerek alanındaki ve alan dışındaki gruplara, yazılı, sözlü ve görsel olarak sistemli biçimde aktarabilme. | 2 |
| 9) | Bir yabancı dili en az Avrupa Dil Portföyü B2 Genel Düzeyi'nde kullanarak sözlü ve yazılı iletişim kurabilme. | 2 |
| 10) | Alanının gerektirdiği düzeyde bilgisayar yazılımı ile birlikte bilişim ve iletişim teknolojilerini ileri düzeyde kullanabilme. | 2 |
| 11) | Alanı ile ilgili verilerin toplanması, yorumlanması, uygulanması ve duyurulması aşamalarında toplumsal, bilimsel, kültürel ve etik değerleri gözeterek denetleyebilme ve bu değerleri öğretebilme. | 2 |
| 12) | Alanında özümsedikleri bilgiyi, problem çözme ve/veya uygulama becerilerini, disiplinlerarası çalışmalarda kullanabilme. | 2 |
| Yarıyıl İçi Çalışmaları | Aktivite Sayısı | Katkı Payı |
| Ödev | 5 | % 50 |
| Projeler | 1 | % 20 |
| Final Sözlü | 1 | % 30 |
| Toplam | % 100 | |
| YARIYIL İÇİ ÇALIŞMALARININ BAŞARI NOTU KATKISI | % 100 | |
| YARIYIL SONU ÇALIŞMALARININ BAŞARI NOTUNA KATKISI | % | |
| Toplam | % 100 | |
| Aktiviteler | Aktivite Sayısı | Aktiviteye Hazırlık | Aktivitede Harçanan Süre | Aktivite Gereksinimi İçin Süre | İş Yükü | ||
| Proje | 1 | 40 | 40 | ||||
| Ödevler | 5 | 20 | 100 | ||||
| Final | 1 | 50 | 1 | 51 | |||
| Toplam İş Yükü | 191 | ||||||