CENG 611

İleri Algoritmaların Tasarım ve Analizi

Bu ders, algoritmaların tasarımı ve analizi üzerinde önemli pratik sonuçları olan çeşitli teorik konuları incelemektedir. Asimptotik analiz ve sequential ile paralel algoritmaların analizinde yaygın olarak kullanılan yöntemlerin önemi vurgulanmaktadır. Algoritmaların farklı bilgisayar mimarilerinde (örneğin, çok çekirdekli, paralel ve yüksek performanslı bilgisayarlar) gösterdiği performansı etkileyen faktörler ve bunların bilimsel uygulamalardaki yansımaları analiz edilecektir. Farklı algoritmaların karmaşıklık analizinde kullanılan temel tasarım stratejileri gözden geçirilecektir. Paralel hesaplama için yeni modeller incelenecek ve eleştirel bir şekilde değerlendirilecektir. Bu modellerin karmaşıklıkları ve sınırlamaları tartışılacaktır.

Dersin Amacı

Ders içeriğinde paralel ve seri algoritmaların karmaşıklık analizlerinin öğretilmesi ve tasarım kuram ve modellerinin çalışılıp, kritik değerlendirmelerinin yapılabilir bir seviyeye öğrencilerin getirilmesi bulunmaktadır.

Kaynakça

Introduction to Algorithms, second edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. The MIT Press, 2001

Öğrenim Çıktıları

Uygulamaların karmaşıklıklarını analiz edebilme
Verilen bir problem için algoritma tasarım seçeneklerini belirleyebilme
Algoritma yaklaşımı ile problemlere çözüm önerebilme.
Algoritma yaklaşım seçeneklerinin özelliklerini tanıyabilme.

Konu
Temel konular: asimptotik analiz
Sequential algoritmaların tasarım ve analizi
Böl ve yönet yaklaşımı
Dinamik programlama
Fırsatçı algoritmalar
Bazı sequential ve paralel algoritmaların analizi
Hesaplama karmaşıklığı
Olasılık ve algoritmanın ortalama karmaşıklığı
“Lower Bound” kuramına giriş
Verimlilik analizi ve paralel sistemlerin değerlendirilmesi
Paralel hesaplama modelleri
Space-Time tradeoffs ve Memory-Hierarchy tradeoffs

Notlandırma

Vize 25%

Ödev 40%

Final 35%