Mühendislik ve Doğa Bilimleri Fakültesi · Yazılım Mühendisliği (%30 İngilizce) · Lisans
Dersin Amacı
Bu dersin amacı, öğrencilere algoritmaların tasarlanması, doğruluğunun değerlendirilmesi ve çalışma verimliliğinin analiz edilmesi konusunda temel bilgi ve beceriler kazandırmaktır. Ders kapsamında zaman ve bellek karmaşıklığı, asimptotik notasyonlar, arama ve sıralama algoritmaları, özyinelemeli algoritmalar, açgözlü algoritmalar, böl ve fethet yaklaşımı, dinamik programlama ve graf algoritmaları gibi temel konular ele alınarak öğrencilerin farklı problemlere uygun algoritmaları seçebilmesi, karşılaştırabilmesi ve performans açısından değerlendirebilmesi hedeflenmektedir.
Ders İçeriği
Algoritma kavramı ve algoritma analizi, asimptotik gösterimler (Big-O, Θ, Ω), zaman ve alan karmaşıklığı analizi, sıralama algoritmaları ve karmaşıklıklarının incelenmesi, arama algoritmaları ve en iyi-ortalama-en kötü durum analizleri, ikili ağaç tabanlı algoritmaların zaman karmaşıklığı, grafik temsilleri ve graf tabanlı algoritmalar (BFS, DFS, en kısa yol ve minimum kapsayan ağaç algoritmaları), açgözlü (greedy) algoritma yaklaşımı ve uygulamaları.
Zorunlu Kaynaklar
Asıl: Introduction to Algorithms 3th Edition, Thomas H Cormen (Author), Charles E Leiserson
Yardımcı : The Algorithm Design Manual, S. S. Skiena, 2008., Veri Yapıları ve Algoritmalar Rıfat Çölkesen
Dersin Öğrenme Çıktıları
- Graf tabanlı algoritmaları uygular.
- Açgözlü (Greedy) algoritma yaklaşımını tanımlar.
- Algoritma ve algoritma analizi kavramlarını tanımlar.
- Algoritmaların zaman karmaşıklığını hesaplar.
- Algoritmaların alan karmaşıklığını hesaplar.
- Sıralama algoritmalarının zaman karmaşıklığını analiz eder.
- Arama algoritmalarının en iyi, ortalama ve en kötü durum karmaşıklıklarını hesaplar.
- Arama algoritmalarının en iyi, ortalama ve en kötü durum karmaşıklıklarını hesaplar.
Temel Alan Dağılımı
Öğretim Yöntem ve Teknikleri
Ölçme ve Değerlendirme
AKTS / İş Yükü
| Etkinlik | Sayı | Süre (saat) | Toplam İş Yükü |
|---|---|---|---|
| Ders Süresi (Sınav Haftası Dahil) | 0 | 0 | 0 |
| Sınıf Dışı Ders Çalışma Süresi | 0 | 0 | 0 |
| Ara Sınav | 0 | 0 | 0 |
| Kısa Sınav | 0 | 0 | 0 |
| Ödev | 0 | 0 | 0 |
| Uygulama | 0 | 0 | 0 |
| Final | 0 | 0 | 0 |
Ders Akışı
| Hafta | Konu | Ön Hazırlık |
|---|---|---|
| 1 | Algoritma Analizine Giriş | . |
| 2 | Asimptotik Notasyon ve Büyüme Sıraları | . |
| 3 | Döngülerle Zaman Karmaşıklığı (Kod Analizi, İç içe döngüler) | . |
| 4 | Rekürsif Algoritmalar, Rekürans Bağıntıları | . |
| 5 | Alan Karmaşıklığı Analizi | . |
| 6 | Sıralama Algoritmaları I (Kabarcık Sıralama, Seçmeli Sıralama, Ekleme Sıralaması) | . |
| 7 | Sıralama Algoritmaları II (Kabuk Sıralama, Quick Sort, Birleştirmeli Sıralama) | . |
| 8 | Ara Sınav | . |
| 9 | Arama Algoritmaları I (Doğrusal Arama, İkili Arama, Ara Değerle Arama) | . |
| 10 | Arama Algoritmaları II (BST üzerinde arama, Dengeli ağaçlarda arama) | . |
| 11 | Graf Gösterimi ve Uygulamaları | . |
| 12 | Graf Uygulamaları (En Kısa Yol Problemleri; Dijkstra, Bellman-Ford) | . |
| 13 | Gezgin satıcı Problemi, Şebeke Akış Problemi | . |
| 14 | Açgözlü Algoritmalar I (Huffman, Kruskal) | . |
| 15 | Açgözlü Algoritmalar II (Prim, Sollin) | . |
| 16 | Final Sınavı | . |