DERS TANITIM ve UYGULAMA BİLGİLERİ

Dersin Adı Kodu Yarıyıl T+U+L (saat/hafta) Türü (Z / S) Yerel Kredi AKTS
Çizge Algoritmaları CE 608 Güz-Bahar 03+00+00 Seçmeli 3 7.5
Akademik Birim: Bilgisayar Mühendisliği Bölümü
Öğrenim Türü: Örgün Eğitim
Ön Koşullar Çizgeler ve algoritma analizi ile ilgili temel kavramlar
Öğrenim Dili: İngilizce
Dersin Düzeyi: Doktora
Dersin Koordinatörü: Öznur YAŞAR DİNER
Dersi Veren(ler): Öznur YAŞAR DİNER
Dersin Amacı: Bu ders bir çizge probleminin çözümü için algoritma geliştirebilme, çizge algoritmalarının zamansal ve alansal karmaşıklığını analiz edebilme kavramlarını tanıtmayı amaçlamaktadır.
Dersin İçeriği: Bu derste çizge reprezantasyonları, enlemesine arama, derinlemesine arama, topolojik sıralama, maksimal kapsayıcı ağaçlar, en kısa patikalar, çizge boyamaları problemlerinin çözümü için algoritmalar ve bu algoritmaların karmaşıklıkları incelenmektedir.
Dersin Öğrenme Çıktıları (ÖÇ):
  • 1- Çizgelerdeki temel kavramları anlama ve bunları mühendislik problemlerini modellemek için kullanma becerisi.
  • 2- Rastgeleleştirme, dinamik programlama, açgözlü buluşsal yöntemler kullanan çizge algoritmaları tasarlayabilme.
  • 3- Bir çizge algoritmasının çalışma zamanı verimliliğini analiz edebilme.
  • 4- Çizgelerle ilgili problemlerin algoritmik çözümlerini anlama.
  • 5- Ağaç genişliği gibi çizge teorisinin ileri kavramlarını kullanarak algoritma tasarlama ve uygulama becerisi.
Dersin Öğrenme Yöntem ve Teknikleri Anlatım, Tartışma, Örnek verme, Problem Çözme, Soru-Cevap, Grup Çalışması


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık ÖÇ
1 Çizgelerle İlgili Temel Kavramlar. Gibbons 1.1 1
2 Algoritma Karmaşıklığana Giriş. Fonksiyonların Büyümesi. Gibbons 1.2 Cormen et. al. 1, 2, 3 1, 2, 3
3 Çizgeler için veri yapıları. Komşuluk matrisleri ve komşuluk listeleri. Gibbons 1.3.1 Cormen et. al. 22.1 1, 2
4 Sıralama yöntemleri. Cormen et. al. 6 ve 7 1, 2, 3, 4
5 Çizge Arama Yöntemleri (Önce Derinlik Araması, Önce Genişlik Araması) Cormen et. al. 22.2, 22.3 1, 2, 3, 4
6 Topolojik sıralama. Güçlü bağlantılı bileşenler Cormen et. al. 22.4, 22.5 1, 2, 3, 4
7 Minimum kapsayan ağaç. Cormen et. al. 23.1, 23.2 1, 2, 3, 4
8 Tek Kaynak En Kısa Yol. Cormen et. al. 24.1, 24.3 1, 2, 3, 4
9 Çok Kaynak En Kısa Yol. Cormen et. al. 25.2, 25.3 1, 2, 3, 4
10 Minimum ve Maksimum Ağ Akış Problemleri Cormen et. al. 26.1, 26.2 1, 2, 3, 4
11 Eşleme Gibbons 5.1, 5.2 1, 2, 3, 4
12 Gezgin satıcı problemi. Kombinatoryel Uygulamalar, Çizge Kuramı Problemleri, NP-Tam Problemler. Cormen et. al. 35.1, 35.2 1, 2, 3, 4
13 Ağaç genişliği ve dinamik programlama 1, 2, 3, 4
14 Proje sunumları 1, 2, 3, 4


ZORUNLU ve ÖNERİLEN OKUMALAR

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.


DİĞER KAYNAKLAR

1.R. Diestel, Graph Theory, Third Edition, Springer-Verlag, Heidelberg, 2000.

2.J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.

3.J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.

4.J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.


DEĞERLENDİRME SİSTEMİ

Yarıyıl İçi ÇalışmalarıSayıKatkı Payı (%)
Proje 1 20
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 2 40
Final Sınavı 1 40
Total: 4 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Toplam İş Yükü (saat):0


PROGRAM YETERLİLİKLERİ (PY) ve ÖĞRENME ÇIKTILARI (ÖÇ) İLİŞKİSİ

# PY1 PY2 PY3 PY4 PY5 PY6 PY7 PY8 PY9 PY10 PY11 PY12
OC1 3 3 3                  
OC2 3 3 3                  
OC3 3 3 3                  
OC4 3 3 3                  
OC5 3 3 3