Ders Kitabı / Malzemesi / Önerilen Kaynaklar
Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006.
Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition Pearson-Addison-Wesley
Michael Sipser, Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005.
Introduction to Algorithms, T.Cormen, C.Leiserson, R.Rivest, MIT Press, 2009.
Dersin İçeriği
Algoritmaların tasarımı ve analizi: algoritma analizinin temelleri, computational tractability, asimptotik büyüme oranı, çizgeler: çizge bağlılığı ve çizge üzerinde geçiş algoritmaları, çift taraflılık, topolojik sıralama algoritması, açgözlü algoritmalar: aralık planlama, minimum kapsama ağacı algoritmaları, kümeleme algoritmaları. Böl ve fethet yaklışımlı algoritmaların, dinamik programlama yaklaşımı içeren algoritmalar ve dağıtık algoritmaların detaylı incelenmesi. NP ve computational intractability: polinom zamanlı indirgemeler, etkin sertifikasyon yöntemleri ve NP’nin tanımı, NP tam problem örnekleri, sıralama problemleri, partitionin problemleri, çizge boyama, numerik problemler, co-NP ve the asymmetry of NP intractability. Pspace’deki bazı zor problemlerin analizleri, yaklaşıklık algoritmalar ve örnekleri, rassal algoritmalar ve örnekleri.
Dersin Amacı
Bu dersin amacı, öğrencilerin algoritma tasarlayabilmesini ve bu algoritmaların analizini yapabilmesini, bir algoritmanın doğruluğunun kanıtlayabilmesini, NP tamlık, tractability, yaklaşık ve rassal algoritma kavramlarını öğrenmelerini sağlamaktır.
