| 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ı |
| Hafta | Konular | Ö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 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
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. |
