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.
Ş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.
| Konu (bölüm) | Dayandığı konu | Bağ |
|---|---|---|
| Giriş ve Algoritma Karmaşıklığı (1) | — | Algoritma kavramı ve çalışma süresinin girdi boyutuyla büyümesi: asimptotik gösterimler. |
| Sıralama Algoritmaları (2) | Giriş ve 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ı (3) | Giriş ve Algoritma Karmaşıklığı, Sıralama Algoritmaları | Sıralı dizide ikili arama; hash ile ortalama O(1) arama. |
| Çizge Algoritmaları (4) | Giriş ve Algoritma Karmaşıklığı, Arama Algoritmaları | Arama çizgeye taşınır: DFS ve BFS, güçlü bağlantılı bileşenler, en kısa yollar. |
| Dizgi Algoritmaları (5) | Giriş ve Algoritma Karmaşıklığı, Arama Algoritmaları | Metinde örüntü arama: KMP, Boyer-Moore, Rabin-Karp; sıkıştırma ve dizi hizalama. |
| Böl ve Fethet Yaklaşımı (6) | Giriş ve Algoritma Karmaşıklığı, Sıralama Algoritmaları | Birleştirme sıralaması ve hızlı sıralamanın ortak şablonu; yineleme bağıntısı ve Ana Teorem. |
| Açgözlü Algoritmalar (7) | Çizge Algoritmaları, Böl ve Fethet Yaklaşımı | Her adımda en iyi görünen seçim; Prim, Kruskal ve Dijkstra açgözlü çizge algoritmalarıdır. |
| Dinamik Programlama (8) | Dizgi Algoritmaları, Böl ve Fethet Yaklaşımı | Böl ve fethetin örtüşen alt problemli hâli: bellekleme ve tablolama; dizgilerde LCS ve düzenleme uzaklığı. |
| Geri İzleme Algoritmaları (9) | Çizge Algoritmaları | Durum uzayı ağacında derinlik öncelikli arama; P, NP ve NP-zor problemlere giriş. |
| Dal Sınır Algoritmaları (10) | Geri İzleme Algoritmaları | Geri izlemeye sınır eklenir: en iyi çözümü içeremeyecek dallar budanır. |
| Yaklaşım Algoritmaları (11) | Açgözlü Algoritmalar, Geri İzleme Algoritmaları | NP-zor problemlerde kanıtlanmış oranlı çözüm: MST tabanlı 2-yaklaşım, LPT, düğüm kapsama. |
| Rastgele Algoritmalar (12) | Sıralama Algoritmaları, Böl ve Fethet Yaklaşımı | Rastgele pivotlu hızlı sıralama ve QuickSelect; Las Vegas ve Monte Carlo türleri. |
| Çevrim İçi Algoritmalar (13) | Açgözlü Algoritmalar, Yaklaşım Algoritmaları | Geleceği bilmeden karar: rekabet oranı yaklaşım oranının çevrim içi karşılığıdır; sayfalama. |
| Paralel Algoritmalar (14) | Giriş ve Algoritma Karmaşıklığı, Böl ve Fethet Yaklaşımı | Bağımsız alt problemler paralel çözülür: önek toplamı, paralel birleştirme sıralaması, iş ve derinlik. |
Haritanın ana omurgası şöyle okunabilir: analiz → temel problemler → tasarım paradigmaları → zor problemler → diğer modeller. Sıralama ve arama, sonraki bütün bölümlerin hem aracı hem örneğidir. Böl ve fethet sıralamadan doğar ve dinamik programlamaya, rastgele ve paralel algoritmalara açılır. Çizge algoritmaları açgözlü yönteme ve durum uzayı aramasına örnek verir. Geri izleme ile dal sınır en iyi çözümü üstel zamanda arar; yaklaşım algoritmaları bunun yerine kanıtlanmış bir oranla yetinir. Çevrim içi algoritmalar aynı oran fikrini bilinmeyen geleceğe uygular.
Ders sayfası: Algoritmalar · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.