İleri 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ğ |
|---|---|---|
| Böl ve Fethet Yaklaşımı (1) | — | Birleştirme sıralaması ve hızlı sıralamanın ortak şablonu; yineleme bağıntısı ve Ana Teorem (Algoritmalar, Bölüm 2–3). |
| Açgözlü Algoritmalar (2) | 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 (Algoritmalar, Bölüm 6–7). |
| Dinamik Programlama (3) | 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ığı (Algoritmalar, Bölüm 10). |
| Geri İzleme Algoritmaları (4) | — | Durum uzayı ağacında derinlik öncelikli arama (Algoritmalar, Bölüm 5); P, NP ve NP-zor problemlere giriş. |
| Dal Sınır Algoritmaları (5) | Geri İzleme Algoritmaları | Geri izlemeye sınır eklenir: en iyi çözümü içeremeyecek dallar budanır. |
| Yaklaşım Algoritmaları (6) | 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 (7) | Böl ve Fethet Yaklaşımı | Rastgele pivotlu hızlı sıralama ve QuickSelect; Las Vegas ve Monte Carlo türleri. |
| Çevrim İçi Algoritmalar (8) | 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 (9) | 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: tasarım paradigmaları → zor problemler → diğer modeller. Ders, Algoritmalar dersindeki analiz, sıralama, arama, çizge ve dizgi algoritmalarının üzerine kurulur. Böl ve fethet sıralamadan doğar ve dinamik programlamaya, rastgele ve paralel algoritmalara açılır. Açgözlü yöntem çizge algoritmalarından tanıdıktır. 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ı: İleri Algoritmalar · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.