İ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.

DinamikProgramlamaBöl ve FethetYaklaşımıAçgözlüAlgoritmalarRastgeleAlgoritmalarParalelAlgoritmalarYaklaşımAlgoritmalarıGeri İzlemeAlgoritmalarıÇevrim İçiAlgoritmalarDal SınırAlgoritmaları
Şekil 1: Dersin haritası. Oklar, bir konunun hangi konunun üzerine kurulduğunu gösterir. Üst satırda tasarım paradigmaları, sağda zor problemler, solda diğer hesaplama modelleri yer alır.

Ş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ğ
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.