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 Bahar 03+00+00 Seçmeli 3 8.0
Akademik Birim:
Öğrenim Türü:
Ö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
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- Algoritma analiz teknikleri ile ilgili mantık ve temel ayrık matematiksel ispat metodlarını uygulama becerisi kazandırmak
  • 2- Çizge reprezantasyonlarını ve ilgili veri yapılarını kullanabilmek
  • 3- Enlemesine arama, derinlemesine arama, topolojik sıralama gibi temel çizge algoritmalarını kavramak ve kullanabilmek
  • 4- Maksimal kapsayıcı ağaçlar, en kısa patikalar gibi çizge problemlerinin çözümleri için algoritmalar geliştirebilmek
  • 5- Çizge problemlerinin çözümleri için geliştirilen algoritmaların karmaşıklıklarını inceleme bilgi ve becerisi kazandırmak
Dersin Öğrenme Yöntem ve Teknikleri Klasik ders


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık
1 Matematiksel Temeller (Mantık, Kümeler Kuramı, Çizge Kuramı, İspat Metodları)
2 Çizgeler ve reprezantasyonları. Algoritma analizi.
3 Derinlemesine arama ve uygulamaları
4 Yönlü çizgeler. Enlemesine arama
5 Dijkstra algoritması.
6 Minimum kapsayan ağaçlar (MKA).
7 En kısa yol algoritmaları ve MKA.
8 Çizge boyamaları. Klikler.
9 İki parçalı çizgelerde eşleşmeler. Maksimal eşleşmeler. Köşe kaplamaları.
10 Proje sunumları
11 Proje sunumları
12 Kombinatoryal problemler ve algoritmaları
13 Çizge arama problemi ve ilgili algoritmik çözümler.
14 Zor problemler: Gezici satıcı problemi, En uzun patika problemi, Hamilton döngüsü problemi


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ı (%)
Katılım - -
Laboratuvar - -
Uygulama - -
Arazi Çalışması - -
Proje 1 30
Ödev 2 20
Sunum/Jüri - -
Derse Özgü Staj - -
Diğer Uygulamalar (seminer, stüdyo kritiği, workshop vb.) - -
Dersle İlgili Sınıf Dışı Etkinlikler (okuma, bireysel çalışma vb.) - -
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 1 10
Final Sınavı 1 40
Total: 5 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati14342
Laboratuvar000
Uygulama000
Arazi Çalışması000
Proje15050
Ödev23570
Sunum/Jüriye Hazırlık000
Derse Özgü Staj000
Diğer Uygulamalara Hazırlık000
Dersle İlgili Sınıf Dışı Etkinlikler000
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar13030
Final Sınavı15050
Toplam İş Yükü (saat):242


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                  
Dersin Adı Kodu Yarıyıl T+U+L (saat/hafta) Türü (Z / S) Yerel Kredi AKTS
Çizge Algoritmaları CE 608 Bahar 03+00+00 Seçmeli 3 8.0
Akademik Birim:
Öğrenim Türü:
Ö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
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- Algoritma analiz teknikleri ile ilgili mantık ve temel ayrık matematiksel ispat metodlarını uygulama becerisi kazandırmak
  • 2- Çizge reprezantasyonlarını ve ilgili veri yapılarını kullanabilmek
  • 3- Enlemesine arama, derinlemesine arama, topolojik sıralama gibi temel çizge algoritmalarını kavramak ve kullanabilmek
  • 4- Maksimal kapsayıcı ağaçlar, en kısa patikalar gibi çizge problemlerinin çözümleri için algoritmalar geliştirebilmek
  • 5- Çizge problemlerinin çözümleri için geliştirilen algoritmaların karmaşıklıklarını inceleme bilgi ve becerisi kazandırmak
Dersin Öğrenme Yöntem ve Teknikleri Klasik ders


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık
1 Matematiksel Temeller (Mantık, Kümeler Kuramı, Çizge Kuramı, İspat Metodları)
2 Çizgeler ve reprezantasyonları. Algoritma analizi.
3 Derinlemesine arama ve uygulamaları
4 Yönlü çizgeler. Enlemesine arama
5 Dijkstra algoritması.
6 Minimum kapsayan ağaçlar (MKA).
7 En kısa yol algoritmaları ve MKA.
8 Çizge boyamaları. Klikler.
9 İki parçalı çizgelerde eşleşmeler. Maksimal eşleşmeler. Köşe kaplamaları.
10 Proje sunumları
11 Proje sunumları
12 Kombinatoryal problemler ve algoritmaları
13 Çizge arama problemi ve ilgili algoritmik çözümler.
14 Zor problemler: Gezici satıcı problemi, En uzun patika problemi, Hamilton döngüsü problemi


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ı (%)
Katılım - -
Laboratuvar - -
Uygulama - -
Arazi Çalışması - -
Proje 1 30
Ödev 2 20
Sunum/Jüri - -
Derse Özgü Staj - -
Diğer Uygulamalar (seminer, stüdyo kritiği, workshop vb.) - -
Dersle İlgili Sınıf Dışı Etkinlikler (okuma, bireysel çalışma vb.) - -
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 1 10
Final Sınavı 1 40
Total: 5 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati14342
Laboratuvar000
Uygulama000
Arazi Çalışması000
Proje15050
Ödev23570
Sunum/Jüriye Hazırlık000
Derse Özgü Staj000
Diğer Uygulamalara Hazırlık000
Dersle İlgili Sınıf Dışı Etkinlikler000
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar13030
Final Sınavı15050
Toplam İş Yükü (saat):242


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