Algoritmalar

Dersin Haritası

Bu sayfa dersin bütün bölümlerini tek bir haritada birleştirir. Her bölüm bir düğümdür; bir ok, sonraki konunun önceki konunun hangi fikrine dayandığını gösterir. Derse başlamadan önce okunursa konuların nereye gittiğini, ders sırasında okunursa bulunulan yeri gösterir.

GirişAlgoritmaKarmaşıklığıSıralamaAlgoritmalarıAramaAlgoritmalarıÇizge GezinmeAlgoritmalarıDizgiEşleştirme veSıkıştırmaEn Kısa YolAlgoritmalarıMinimumKapsayan AğaçAlgoritmalarıAğ Akışıİleri DizgiAlgoritmalarıTrie VeriYapısı
Şekil 1: Dersin haritası. Oklar, bir konunun hangi konunun üzerine kurulduğunu gösterir. Analizden sıralama ve aramaya, oradan solda çizge, sağda dizgi algoritmalarına geçilir.

Şekil 1 konular arasındaki bağları gösterir. Her düğüm bir bölümdür; bir ok, sonraki konunun öncekinin hangi fikrine dayandığını belirtir. Haritada yalnızca en yakın bağlar çizilmiştir; bir bölümün dayandığı bütün bölümler Tablo 1'dedir.

Tablo 1: Haritadaki bağlar.
Konu (bölüm)Dayandığı konuBağ
Giriş (1)—Algoritma kavramı, girdi boyutu ve çalışma süresinin girdiyle büyümesi; satır satır işlem sayma.
Algoritma Karmaşıklığı (2)GirişAsimptotik gösterimler, döngü analizi, yineleme bağıntıları ve Ana Teorem: sonraki bütün bölümlerin ölçüsü.
Sıralama Algoritmaları (3)Algoritma Karmaşıklığıİlk büyük problem sınıfı; O(n²) yöntemlerden O(n log n) yöntemlere geçiş analizle ölçülür.
Arama Algoritmaları (4)Algoritma Karmaşıklığı, Sıralama AlgoritmalarıSıralı dizide ikili arama; hash ile ortalama O(1) arama.
Çizge Gezinme Algoritmaları (5)Algoritma Karmaşıklığı, Arama AlgoritmalarıArama çizgeye taşınır: DFS ve BFS, güçlü bağlantılı bileşenler, topolojik sıralama.
En Kısa Yol Algoritmaları (6)Çizge Gezinme AlgoritmalarıGezinmeye ağırlık eklenir: gevşetme, Dijkstra, Bellman-Ford, Floyd-Warshall ve A*.
Minimum Kapsayan Ağaç Algoritmaları (7)Çizge Gezinme Algoritmaları, En Kısa Yol AlgoritmalarıBütün düğümleri en ucuza bağlayan ağaç; Prim, Dijkstra ile aynı öncelikli kuyruk düzenini kullanır.
Ağ Akışı (8)Çizge Gezinme AlgoritmalarıArtış yolları gezinmeyle bulunur (Edmonds-Karp'ta BFS); maksimum akış–minimum kesim teoremi.
Dizgi Eşleştirme ve Sıkıştırma (9)Algoritma Karmaşıklığı, Arama AlgoritmalarıMetinde örüntü arama: KMP, Boyer-Moore, Rabin-Karp; RLE ve LZW ile sıkıştırma.
İleri Dizgi Algoritmaları (10)Sıralama Algoritmaları, Dizgi Eşleştirme ve SıkıştırmaDizgi sıralama (basamak sıralaması), düzenli ifadeler ve otomatlar, düzenleme uzaklığı, sonek dizisi.
Trie Veri Yapısı (11)Dizgi Eşleştirme ve Sıkıştırma, İleri Dizgi AlgoritmalarıDizgileri ortak önekleriyle saklayan ağaç; otomatik tamamlama, sonek trie'si ve Aho–Corasick.

Haritanın ana omurgası şöyle okunabilir: analiz → sıralama ve arama → çizgeler ve dizgiler. İlk iki bölümdeki işlem sayma ve asimptotik analiz sonraki bütün bölümlerin ölçüsüdür. Sıralama ve arama, sonraki bölümlerin hem aracı hem örneğidir: çizgede gezinme aramanın çizgeye taşınmış biçimidir ve en kısa yol, kapsayan ağaç ve akış algoritmaları gezinmenin üzerine kurulur. Dizgi eşleştirme aramanın metne uygulanmasıdır; ileri dizgi algoritmaları ve trie bu temelden çıkar. Tasarım paradigmaları, zor problemler ve diğer hesaplama modelleri İleri Algoritmalar dersinde bu temelin üzerine kurulur.

Ders sayfası: Algoritmalar · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.