[GeriDon]

[DersOgretimPlani]

[DersinKodu] [DersinAdi] [DersinTuru] [Yil] [YariYil] [Ects]
BİM-23-107 İLERİ ALGORİTMA ANALİZİ VE TASARIMI Seçmeli Ders Grubu 1 2 6,00

[DersinSeviyesi]

[YuksekLisans]

[DersDili]

Türkçe

[DersinAmaci]

Bu dersin amacı, algoritmaların verimliliğini ve kaynak kullanımını nicel olarak analiz edebilme yeteneğini kazandırmaktır. Öğrenciler, farklı algoritma tasarım paradigmalarını (böl ve yönet, açgözlü, dinamik programlama vb.) öğrenerek; zaman ve bellek karmaşıklığını hesaplayıp karşılaştırabilecek, çözüm yaklaşımının ölçeklenebilirliğini ve sınırlamalarını değerlendirebilecek yetkinliğe erişeceklerdir.

[DersiVerenGorevli]

Prof. Dr. Çetin Kaya KOÇ

[OgrenmeCiktilari]

1 Farklı algoritmaların zaman ve bellek karmaşıklıklarını asimptotik notasyonlarla ifade edip karşılaştırabilecek.
2 Böl ve yönet, açgözlü ve dinamik programlama paradigmalardan uygun olanını seçerek etkin algoritmalar tasarlayıp uygulayabilecek.
3 Grafikler ve ağaçlar üzerinde temel arama, sıralama ve optimizasyon algoritmalarını analiz ederek doğruluğunu ve performansını değerlendirebilecek.

[OgrenimTuru]

Birinci Öğretim

[DersOnKosulu]

Yok

[OnerilenDigerHususlar]

Yok

[DersinIcerigi]

Algoritma analizi dersinde öncelikle asimptotik notasyon (O, Ω, Θ) kavramları, temel karmaşıklık sınıfları (P, NP, NP-tam) ve karşılaştırmalı analiz yöntemleri ele alınır. Böl ve yönet (divide and conquer), açgözlü algoritmalar ve dinamik programlama paradigmasının temel uygulamaları üzerinde durulur. Ardından sıralama, arama, ağaç ve grafik yapılarına yönelik grafik algoritmaları (DFS, BFS, en kısa yol, minimum yayılım ağacı) incelenir. Algoritma tasarımına ilişkin geri dönüşümlü (backtracking) ve dallanıp-sınırlandırma (branch and bound) teknikleri ile NP-zor problemler ve yaklaşık algoritma yöntemleri dersin sonlarında tartışılır.

[HaftalikDersIcerigi]

[Hafta] [Teorik] [Uygulama] [Laboratuvar]
1 Asimptotik Notasyon ve Karmaşıklık Sınıfları
2 Karşılaştırmalı Analiz ve En Kötü/Ortalama/En İyi Durum Analizi
3 Böl ve Yönet Paradigması: Merge Sort, Quick Sort
4 Açgözlü Algoritmalar ve Örnek Uygulamaları
5 Dinamik Programlama: Temel Kavramlar ve Uygulamalar
6 Veri Yapıları Üzerinde Grafik Algoritmalarına Giriş
7 Derinlik Öncelikli ve Genişlik Öncelikli Arama (DFS, BFS)
8 Ara Sınav
9 En Kısa Yol Algoritmaları (Dijkstra, Bellman-Ford)
10 Minimum Spanning Trees: Kruskal, Prim
11 Geri Dönüşümlü (Backtracking) ve Dallanıp-Sınırlandırma (Branch & Bound)
12 NP-Tam ve NP-Zor Problemler; Karşılaştırmalı Örnekler
13 Yaklaşık Algoritmalar ve Rastgeleleştirilmiş Yaklaşımlar
14 Karmaşıklık Teorisine Ek Bakış: P vs. NP ve Modern Gelişmeler
15 Final Sınavı
16 Final Sınavı

[DersKitabi]

Cormen, Leiserson, Rivest, Stein – Introduction to Algorithms Kleinberg, Tardos – Algorithm Design Dasgupta, Papadimitriou, Vazirani – Algorithms

[PlanlananYontemler]

[Degerlendirme]

Yarıyıl (Yıl) İçi Etkinlikleri [Adet] [Deger]
Ara Sınav 1 100
[Toplam] 100
Yarıyıl (Yıl) Sonu Etkinlikleri [Adet] [Deger]
Final Sınavı 1 100
[Toplam] 100
Yarıyıl (Yıl) İçi Etkinlikleri 40
Yarıyıl (Yıl) Sonu Etkinlikleri 60

[StajDurumu]

Yok

[IsYukuHesaplamasi]

[Etkinlikler] [Sayisi] [Suresi] [ToplamIsYuku]
Ara Sınav 1 1 1
Final Sınavı 1 2 2
Bireysel Çalışma 16 6 96
Ara Sınav İçin Bireysel Çalışma 8 4 32
Final Sınavı içiin Bireysel Çalışma 8 6 48
[ToplamIsYuku] 179

[PCOCIliskisi]

[PC] 1
[OC] 1
[OC] 2
[OC] 3
[PCOCAciklama]