Bilgisayar Mühendisliği (YL) (Tezli) (İngilizce) Önizleme
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:

COE5003

Ders İsmi:

Approximation Algorithms

Ders Yarıyılı:

Güz

Ders Kredileri:

AKTS

Öğretim Dili:

English

Ders Koşulu:

Ders İş Deneyimini Gerektiriyor mu?:

Hayır

Dersin Türü:

Bölüm/Program Seçmeli

Dersin Seviyesi:

Yüksek Lisans

TYYÇ:7. Düzey

QF-EHEA:2. Düzey

EQF-LLL:7. Düzey

Dersin Veriliş Şekli:

Dersin Koordinatörü:

Doç. Dr. EMİR SEYYEDABBASİ

Dersi Veren(ler):

Ali Çivril

Dersin Yardımcıları:

Dersin Amaç ve İçeriği

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.

Öğrenme Kazanımları

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.

Ders Akış Planı

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)

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:	Approximation Algorithms, V. Vazirani, Springer (2001). The Design of Approximation Algorithms, D.P. Williamson, D.B. Shmoys, Cambridge University Press (2011).

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

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.

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

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

Ölçme ve Değerlendirme

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

İş Yükü ve AKTS Kredisi Hesaplaması

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