Oyun teorisi, rastgele eleman içermeyen iki kişilik oyunları analiz eder. Amaç; rakip ne yaparsa yapsın, eğer varsa oyunu kesinlikle kazandıracak bir strateji bulmaktır. Bu oyunlar nim teorisi ile analiz edilir.
Devamı...
Olasılık, rastgele bir sürecin sonuçlarını sayısal olarak ifade eder. $0$ ile $1$ arasında bir değer olan $P(A)$, $A$ olayının gerçekleşme ihtimalini verir; $P(A) = 0$ imkânsızı, $P(A) = 1$ kesinliği temsil eder.
Zar atma örneğiyle:
Matris, programlamadaki iki boyutlu dizinin matematikteki karşılığıdır. $m \times n$ büyüklüğündeki bir matris $m$ satır ve $n$ sütundan oluşur; $A[i, j]$ gösterimi $i$. satır ve $j$. sütundaki elemanı verir. Özel bir durum olarak $n \times 1$ büyüklüğündeki matrise vektör denir.
$A$ matrisinin transpozu $A^T$, satırlar ile sütunların yer değiştirmesinden elde edilir: $A^T[i, j] = A[j, i]$. Satır ve sütun sayısı eşit olan matris kare matristir.
Devamı...Kombinatorik, nesnelerin kombinasyonlarını sayma yöntemlerini araştırır. Genelde amaç her kombinasyonu ayrı ayrı oluşturmadan toplam sayıyı hesaplamaktır.
Örneğin toplamı $n$ olan tam sayı dizisi sayısı gibi problemler özyinelemeli formüllerle ele alınır. $f(n)$, $n$’yi toplam olarak yazma yollarının sayısı olsun:
\[f(n) = \begin{cases} 1 & n = 0 \\ f(0) + f(1) + \cdots + f(n-1) & n > 0 \end{cases}\]İlk değerler: $f(0)=1,\ f(1)=1,\ f(2)=2,\ f(3)=4,\ f(4)=8$. Bu durumda kapalı form $f(n) = 2^{n-1}$’dir; çünkü $n-1$ boşluktan istediğimizi seçip $+$ ya da hiç koyabiliriz.
Devamı...Sayılar teorisi, matematiğin tam sayılarla ilgilenen alt dalıdır. İlginç bir konudur; çünkü tam sayı içeren pek çok soru ilk bakışta kolay görünse de çözümü son derece zor olabilir. Örneğin $x^3 + y^3 + z^3 = 33$ eşitliğini sağlayan üç tam sayı bulmak hâlâ açık bir matematik problemidir.
Bu bölümde sayılar teorisinin rekabetçi programlamada sık karşılaşılan temel kavramları ve algoritmaları ele alınmaktadır.
Devamı...Bu bölümde iki temel soru üzerine yoğunlaşıyoruz:
Her iki problem için girdi; kaynak (kendisine gelen kenar bulunmayan) ve musluk (kendisinden çıkan kenar bulunmayan) olmak üzere iki özel düğüm içeren, yönlü ve ağırlıklı bir çizgedir.
Bu iki sorunun cevabı her zaman birbirine eşittir. Maksimum akış ile minimum kesim sanki paranın iki yüzüdür; Ford-Fulkerson Algoritması hem maksimum akışı hem de minimum kesimi aynı anda çözer.
Devamı...Bu bölümde çizgeler üzerindeki iki temel yol türü inceleniyor:
İlk bakışta birbirine benzer görünen bu iki kavram aslında tamamen farklı zorluktadır. Bir çizgenin Euler yolu içerip içermediğini belirlemek ve varsa bulmak çok verimli biçimde yapılabilir. Hamilton yolu ise NP-hard bir problemdir; bunu verimli çözen bilinen bir algoritma yoktur.
Devamı...Bu bölümde köklü ağaçların alt ağaçları ve yolları üzerinde yapılan sorguları çözme yöntemlerini inceliyoruz. Ele alınan sorgu türleri şunlardır:
Yönlü bir çizgede kenarlar yalnızca tek yönlü geçilir. Bu nedenle çizge bağlı olsa bile her düğümden diğerine gidileceği garanti edilemez. Daha güçlü bir bağlanırlık kavramına ihtiyaç vardır.
Bir çizge, her düğümden diğer tüm düğümlere gidilebiliyorsa güçlü bağlanılmış (strongly connected) olarak adlandırılır. Güçlü bağlanılmamış bir çizgede ise bazı düğüm çiftleri arasında tek yönlü bir ulaşım bile mümkün olmayabilir.
Güçlü bağlanılmış parçalar (strongly connected components, SCC), çizgeyi olabildiğince büyük güçlü bağlanılmış bölümlere ayırır. Bu parçalar, orijinal çizgenin derin yapısını ortaya koyan asiklik bir bileşen çizgesi (component graph) oluşturur.
Devamı...Bu bölümde yönlü çizgelerin iki türünden bahsedeceğiz:
Her iki durumda da bu özellikler sayesinde çeşitli verimli algoritmalar tasarlanabilir.
Devamı...Kapsayan ağaç (spanning tree), bir çizgenin bütün düğümlerini bağlı olacak şekilde birleştiren, çizgenin bazı kenarlarını içeren bir ağaçtır. Ağaçlardaki gibi, kapsayan ağaçlar da bağlı ve asikliktir. Genelde, kapsayan ağaç oluşturmanın birkaç yolu vardır.
Kapsayan ağacın ağırlığı kenar ağırlıklarının toplamıdır. En küçük kapsayan ağaç (minimum spanning tree), ağırlığı en küçük olan kapsayan ağaçtır. Benzer şekilde en büyük kapsayan ağaç, en büyük ağırlığa sahip kapsayan ağaçtır.
Bir çizgenin birkaç tane en küçük ve en büyük kapsayan ağacı olabilir; yani bu ağaçlardan sadece bir tane olmak zorunda değildir.
En küçük ve en büyük kapsayan ağaçları bazı açgözlü yöntemler kullanarak oluşturabiliriz. Bu bölümde kenarların ağırlıklarına göre sıralayarak yapılan iki algoritmadan bahsedeceğiz. Her ne kadar bölümde en küçük kapsayan ağaçları bulmaya odaklanacak olsak bile, en büyük kapsayan ağaç da kenarları ters sırada işleyerek bulunabilir.
Kruskal’ın Algoritması’nda başlangıçtaki kapsayan ağaçta sadece çizgenin düğümleri bulunur ve herhangi bir kenar içermemektedir. Sonrasında algoritma kenarlara ağırlıklarına göre bakar ve eğer kenar döngü oluşturmuyorsa kenarı kapsayan ağaca ekler.
Algoritma, ağacın parçalarını tutar. İlk başta çizgenin her düğümü ayrı bir parçadır. Her seferinde ağaca bir kenar eklendiği zaman iki parça birleşir. Sonunda bütün düğümler aynı parçaya ait olur ve en küçük kapsayan ağaç bulunur.
Algoritmanın ilk adımında kenarlar, ağırlıklarına göre küçükten büyüğe doğru sıralanır:
| Kenar | Ağırlık |
|---|---|
| 5–6 | 2 |
| 1–2 | 3 |
| 3–6 | 3 |
| 1–5 | 5 |
| 2–3 | 5 |
| 2–5 | 6 |
| 4–6 | 7 |
| 3–4 | 9 |
Bundan sonra algoritma listeden geçer ve kenar iki ayrı parçayı bağlıyorsa kenarı ağaca ekler. Başta her düğüm kendisine ait parçadadır. Ağaca ilk eklenen kenar 5–6 kenarıdır; bu kenar ${5}$ ve ${6}$ parçalarını ${5, 6}$ şeklinde birleştirir. Ardından 1–2, 3–6 ve 1–5 kenarları benzer şekilde eklenir.
Bu adımlardan sonra ağaçta iki parça kalmıştır: ${1, 2, 3, 5, 6}$ ve ${4}$. Listedeki sonraki kenar 2–3‘tür, ancak 2 ve 3 düğümleri aynı parçaya ait olduğundan bu kenar ağaca eklenmez. Aynı nedenden dolayı 2–5 kenarı da eklenmez. En sonunda 4–6 kenarı ağaca eklenir ve algoritma tamamlanır. Oluşan en küçük kapsayan ağacın ağırlığı $2 + 3 + 3 + 5 + 7 = 20$ olur.
Çizgedeki minimum ağırlıklı kenarı eklemediğimizi varsayalım. Bu durumda mevcut kapsayan ağaçtan bir kenarı çıkartıp yerine minimum ağırlıklı kenarı eklediğimizde daha küçük ağırlığa sahip bir kapsayan ağaç elde ederiz. Bu çelişki, en küçük ağırlığa sahip kenarı eklemenin her zaman optimal olduğunu gösterir. Benzer mantık sonraki kenarlar için de geçerlidir; dolayısıyla Kruskal’ın Algoritması her zaman doğru sonucu verir.
Kruskal’ın Algoritması’nı koda geçirirken çizgeyi bir kenar listesinde tutmak daha rahat olur. Algoritmanın ilk aşamasında listedeki kenarlar $O(m \log m)$ zamanda sıralanır. Bundan sonra algoritma en küçük kapsayan ağacı şu şekilde oluşturur:
Devamı...Bir ağaç (tree), $n$ düğüm ve $n - 1$ kenardan oluşan bağlı ve asiklik (döngüsüz) bir çizgedir. Ağaçtan herhangi bir kenarı çıkarmak onu iki parçaya böler; herhangi bir kenar eklemek ise bir döngü oluşturur. Her iki düğüm arasında tam olarak bir yol bulunur.
Örneğin 8 düğüm ve 7 kenardan oluşan bir ağaçta yapraklar (leaves), derecesi 1 olan yani tek komşusu bulunan düğümlerdir. Köklü bir ağaçta düğümlerden biri kök seçilir ve diğer tüm düğümler onun altına yerleştirilir. Köklü ağaçta bir düğümün çocukları (children) onun alt komşuları, ebeveyni (parent) ise üst komşusudur. Her düğümün kök hariç tam bir ebeveyni vardır.
Köklü ağacın yapısı özyinelemelidir: her düğüm, kendisini ve tüm torunlarını kapsayan bir alt ağacın kökü gibi davranır.
Genel çizge dolaşım algoritmaları ağaçlarda da kullanılabilir. Ancak ağaçlar döngü içermediğinden ve bir düğüme birden fazla yoldan ulaşılamadığından implementasyon genel çizgelere kıyasla çok daha sadedir.
Ağacı dolaşmanın klasik yolu herhangi bir düğümden DFS başlatmaktır:
Devamı...Bir çizgede iki düğüm arasındaki en kısa yolu bulmak, pek çok pratik uygulamaya sahip temel bir problemdir. Klasik bir örnek, yol uzunlukları bilinen bir ağda iki şehir arasındaki en kısa rotayı hesaplamaktır. Ağırlıksız çizgelerde yol uzunluğu kenar sayısına eşit olduğundan BFS ile çözülebilir; bu bölümde ise ağırlıklı çizgeler için geliştirilmiş algoritmalara bakacağız.
Bellman–Ford algoritması1, başlangıç düğümünden çizgedeki tüm düğümlere en kısa mesafeyi bulur. Negatif döngü içermeyen her türlü çizgede çalışır; üstelik çizgede negatif döngü varsa bunu tespit edebilir.
Algoritma, başlangıç düğümüne 0, diğer tüm düğümlere sonsuz mesafe atayarak başlar. Her turda tüm kenarlar incelenerek mesafeler kısaltılmaya çalışılır. Hiçbir mesafe artık kısalımıyorsa algoritma durur.
Aşağıdaki 5 düğümlü ağırlıklı çizgede 1. düğümden başlayan Bellman–Ford adımları:
Başlangıç: Mesafeler $[0, \infty, \infty, \infty, \infty]$
1. tur — 1. düğümden çıkan tüm kenarlar mesafeleri azaltır:
\[[0,\ 5,\ 3,\ 7,\ \infty]\]2. tur — $2 \to 5$ ve $3 \to 4$ kenarları devreye girer:
\[[0,\ 5,\ 3,\ 4,\ 7]\]3. tur — Son bir güncelleme daha:
\[[0,\ 5,\ 3,\ 4,\ 6]\]Artık hiçbir kenar mesafeyi azaltamaz; başlangıç düğümünden tüm düğümlere en kısa mesafeler bulunmuştur. Örneğin 1. düğümden 5. düğüme en kısa mesafe 3’tür.
Algoritma R. E. Bellman ve L. R. Ford tarafından birbirinden habersiz biçimde sırasıyla 1958 ve 1956 yıllarında yayınlanmıştır. ↩
Bu bölümde iki temel çizge dolaşma algoritması ele alınacaktır: derinlik öncelikli arama (DFS) ve genişlik öncelikli arama (BFS). Her ikisinin de bir başlangıç noktası vardır ve başlangıç düğümünden ulaşılabilen tüm düğümleri gezerler. İki algoritma arasındaki fark, düğümleri dolaşma sırasıdır.
Derinlik öncelikli arama (Depth-First Search — DFS), sezgisel bir çizge dolaşma tekniğidir. Algoritma başlangıç düğümünden hareket ederek çizgenin kenarlarını kullanır ve ulaşılabilir tüm düğümleri ziyaret eder. DFS, yeni bir düğüm buldukça tek bir yolu izlemeye devam eder; çıkmaza girdiğinde ise geri dönerek çizgenin diğer bölgelerini keşfeder. Her düğüm yalnızca bir kez ziyaret edilip işlenir.
Algoritmanın zaman karmaşıklığı $O(n + m)$’dir; burada $n$ düğüm sayısı, $m$ ise kenar sayısıdır. Bu, algoritmanın her düğümü ve kenarı tam bir kez işlemesinden kaynaklanır.
Aşağıdaki beş düğümlü çizgede DFS’in 1. düğümden nasıl ilerlediğini izleyelim:
Devamı...Çoğu kodlama sorusu bir çizge problemi olarak modellenip uygun bir çizge algoritmasıyla çözülebilir. Tipik bir örnek, bir ülkedeki yolları ve şehirleri temsil eden ağdır. Bazen çizge sorunun içinde gizli olduğundan fark edilmesi güçleşir. Bu bölümde çizgelerle ilgili temel kavramları ele alıp algoritmalarda çizgeleri göstermenin farklı yollarını inceleyeceğiz.
Bir çizge (graph), düğümlerden (nodes) ve kenarlardan (edges) oluşur. Bu yazıda $n$ çizgedeki toplam düğüm sayısını, $m$ ise toplam kenar sayısını belirtecektir. Düğümler $1, 2, \ldots, n$ tamsayılarıyla numaralandırılır.
Yol (path), $a$ düğümünden $b$ düğümüne kenarlar kullanılarak ulaşılmasını sağlar. Yolun uzunluğu, yolda geçilen kenar sayısına eşittir. Örneğin $1 \to 3 \to 4 \to 5$ yolu, 1. düğümden 5. düğüme 3 uzunluğunda bir yoldur.
Başlangıç ve son düğümün aynı olduğu yola döngü (cycle) denir. Bir yolda her düğüm en fazla bir kez geçiyorsa bu yol basittir (simple).
Her iki düğümü arasında bir yol bulunan çizge bağlıdır (connected). Bir çizgenin bağlı alt gruplarına parça (component) denir. Örneğin ${1,2,3}$, ${4,5,6,7}$ ve ${8}$ olmak üzere üç parçalı bir çizge bağlı değildir.
Bir çizge bağlıysa ve $n$ düğüm ile $n-1$ kenardan oluşuyorsa bu çizge bir ağaçtır (tree). Ağaçta her iki düğüm arasında tam olarak bir yol vardır.
Kenarların tek yönlü olduğu çizge yönlüdür (directed). Yönlü bir çizgede $3 \to 1 \to 2 \to 5$ yolu olabilirken $5$’ten $3$’e giden herhangi bir yol olmayabilir.
Ağırlıklı (weighted) bir çizgede her kenarın bir ağırlığı vardır; bu ağırlık genellikle uzunluk olarak yorumlanır. Ağırlıklı bir çizgedeki yolun uzunluğu, yoldaki kenarların ağırlıklarının toplamıdır. Örneğin $1 \to 2 \to 5$ yolunun uzunluğu 12, $1 \to 3 \to 4 \to 5$ yolunun uzunluğu 11 olabilir; burada ikinci yol daha kısadır.
İki düğüm arasında kenar varsa bunlar komşu (neighbor) düğümlerdir. Bir düğümün derecesi (degree), komşu sayısına eşittir.
$m$ kenarlı bir çizgenin toplam derece sayısı her zaman $2m$’dir; çünkü her kenar iki düğümün derecesini birer artırır. Bu nedenle derece toplamı daima çifttir.
Yönlü çizgelerde bir düğümün iç derecesi (indegree) o düğüme gelen kenar sayısını, dış derecesi (outdegree) ise o düğümden çıkan kenar sayısını verir.
Her düğümün derecesi $d$ ise çizge sıradan (regular), her düğüm birbirine bağlıysa (derece $n-1$) çizge tam (complete) olarak adlandırılır.
Çizgeyi boyarken komşu düğümlerin farklı renk almasına dikkat edilir. Yalnızca iki renkle boyanabilen çizge iki parçalıdır (bipartite). Bir çizgenin iki parçalı olabilmesi için tek sayıda kenarlı herhangi bir döngü içermemesi gerekir.
Örneğin altı düğümlü bir çizge iki parçalıysa düğümler iki gruba ayrılıp her kenar gruplar arasında geçer; iki renkle boyanabilir. Ama tek sayıda kenarlı bir döngü içeriyorsa boyama mümkün olmaz.
Genel durumda bir çizgenin $k$ renkle boyanıp boyanamayacağını bulmak zordur. $k = 3$ için dahi bilinen verimli bir algoritma yoktur — bu problem NP-hard‘dır.
Aynı düğümde başlayıp biten kenar (öz-döngü) veya iki düğüm arasında birden fazla kenar içeren çizge basit değildir (not simple). Genellikle çizgelerin basit olduğu kabul edilir.
Algoritmalarda çizgeleri göstermenin birkaç yaygın yolu vardır. Veri yapısının seçimi çizgenin büyüklüğüne ve algoritmanın çizgeyi işleme biçimine göre değişir.
Komşuluk listesi (adjacency list) gösteriminde her $x$ düğümüne bir liste atanır; bu liste $x$’ten çıkan kenarların ulaştığı düğümleri içerir. Komşuluk listeleri çizgeleri göstermenin en popüler yoludur ve çoğu algoritma bu yöntemle verimli biçimde kodlanabilir.
Komşuluk listesini oluşturmanın pratik yolu vektörlerden oluşan bir dizi kullanmaktır:
Devamı...Bilgisayar programlarındaki tüm veriler bit olarak yani 0 ve 1 sayıları biçiminde tutulur. Bu bölüm tam sayıların bit gösterimlerini açıklayıp bit operasyonlarının kullanıldığı örneklere değinecektir. Algoritma programlamasında bit manipülasyonunu kullanmanın pek çok farklı yolu vardır.
Programlamada bir $n$ bitlik tamsayı, $n$ bitten oluşan bir binary sayısı olarak tutulur. Örneğin C++’da int 32-bit olup her int sayısı 32 bitten oluşur.
int 43 sayısının bit gösterimi:
Bir dizinin alt aralıklarında hızlıca sorgu yapmak rekabetçi programlamada sık karşılaşılan bir ihtiyaçtır. Bir aralık sorgusunda görev, bir dizinin belirli bir alt aralığında bir değeri hesaplamaktır. Tipik aralık sorguları şunlardır:
sumq(a, b): $[a, b]$ aralığındaki sayıların toplamını bulminq(a, b): $[a, b]$ aralığındaki minimum sayıyı bulmaxq(a, b): $[a, b]$ aralığındaki maksimum sayıyı bulÖrneğin [1, 3, 8, 4, 6, 1, 3, 4] dizisinde $[3,6]$ aralığı için sumq(3,6) = 14, minq(3,6) = 1, maxq(3,6) = 6 olur.
En basit yaklaşım aralık içindeki tüm elemanlara tek tek bakmaktır; bu $O(n)$ sürer. $q$ sorgu için toplam $O(nq)$ zaman gerekir. Hem $n$ hem de $q$ büyük olduğunda bu yavaş kalır. Neyse ki aralık sorgularını çok daha verimli yapmanın yolları vardır.
Dizinin statik olduğu (sorgular sırasında değerlerin değişmediği) duruma ilk bakacağız. Bu durumda sorguları sabit zamanda yanıtlayan bir veri yapısı oluşturmak yeterlidir.
Statik bir dizideki toplam sorgularını prefix toplam dizisi ile kolayca çözebiliriz. Prefix toplam dizisindeki $k$. konum, orijinal dizinin $[0, k]$ aralığının toplamına eşittir; yani sumq(0, k) değerini tutar. Bu dizi $O(n)$ zamanda oluşturulabilir.
Örneğin [1, 3, 4, 8, 6, 1, 4, 2] dizisine karşılık gelen prefix toplam dizisi:
Bir algoritmanın sadece yapısını inceleyerek (örneğin döngü sayılarına bakarak) zaman karmaşıklığını hesaplamak kolaydır. Fakat bazen bu üstünkörü analiz, algoritmanın gerçek verimliliğini doğru yansıtmaz.
Amortize Analizi, zaman karmaşıklığı farklı olan operasyonları içeren algoritmaları inceler. Buradaki fikir, tek tek operasyonların en kötü durumuna bakmak yerine, algoritmanın çalışması sürecinde bütün operasyonlar için harcanan toplam zamanı tahmin etmektir. Bazen bazı operasyonlar yavaş olsa da, toplamda bu yavaş operasyonlar sık gerçekleşmediği için ortalama performans verimli olabilir.
İki işaretçi methodunda, dizinin elemanları üzerinden geçmek için iki işaretçi (pointer) kullanılır. Bu işaretçiler genellikle tek bir yöne doğru hareket ederler, bu da algoritmanın verimli çalışmasını sağlar.
Problem: n tane pozitif sayıdan oluşan bir dizide, toplamı x olan ardışık bir altdizi bulmak.
Fikir: Altdizinin başlangıcını ve sonunu gösteren iki işaretçi (sol ve sağ) tutulur. sağ işaretçi, toplam x‘i geçmediği sürece ilerletilir. Toplam x‘i geçerse, sol işaretçi ilerletilerek altdizi küçültülür. Eğer toplam tam olarak x olursa, bir çözüm bulunmuş olur.
[1, 3, 2, 5, 1, 1, 2, 3] dizisinde toplamı 8 olan altdiziyi bulmak için iki işaretçi yönteminin adımları
Her iki işaretçi de dizi boyunca sadece ileri doğru hareket ettiği için toplamda en fazla 2n adım atarlar. Bu yüzden algoritma $O(n)$ zamanda çalışır.
Problem: n sayıdan oluşan bir dizide, toplamı x olan iki eleman bulmak.
Fikir:
sol) dizinin başına, diğerini (sağ) dizinin sonuna yerleştirin.array[sol] + array[sağ] toplamını kontrol edin:
x‘ten küçükse, daha büyük bir değere ihtiyacımız var demektir, bu yüzden sol işaretçisini bir sağa kaydırın.x‘ten büyükse, daha küçük bir değere ihtiyacımız var demektir, bu yüzden sağ işaretçisini bir sola kaydırın.x‘e eşitse, bir çözüm bulunmuştur.Sıralama $O(n \log n)$, iki işaretçi ile arama ise $O(n)$ sürdüğü için toplam zaman karmaşıklığı $O(n \log n)$ olur. Daha zor bir problem olan 3SUM problemi (toplamı x olan üç eleman bulmak), bu fikir genişletilerek $O(n^2)$ zamanda çözülebilir1.
Problem: Bir dizideki her eleman için, o elemanın solunda bulunan ve kendisinden küçük olan en yakın elemanı bulmak.
Fikir: Dizinin solundan sağına doğru ilerlerken bir yığın (stack) kullanılır. Her eleman için:
[1, 3, 4, 2, 5, 3, 4, 2] dizisi için yığının adım adım değişimi
Bir eleman yığına en fazla bir kez eklenip bir kez çıkarıldığı için, her eleman amortize olarak $O(1)$ yığın operasyonu gerektirir. Bu yüzden algoritmanın toplam zaman karmaşıklığı $O(n)$’dir.
Problem: Sabit k boyutundaki bir altdizinin (sürgülü pencere), dizi boyunca soldan sağa hareket ederken her pozisyondaki minimum elemanı bulmak.
Fikir: Bir deque (çift yönlü kuyruk) veri yapısı kullanılır. Bu deque her zaman pencere içindeki elemanların indislerini artan değer sırasında tutar. deque‘in başındaki eleman her zaman o anki pencerenin minimumudur.
Her adımda pencere bir sağa kaydığında:
deque‘in sonundan, yeni eklenecek elemandan daha büyük olan elemanlar çıkarılır.deque‘in sonuna eklenir.deque‘in başındaki elemanın indisi pencerenin dışına çıkmışsa, baştan çıkarılır.Her eleman deque‘e en fazla bir kez eklenip bir kez çıkarıldığı için, bu algoritma da amortize olarak $O(n)$ zamanda çalışır.
Uzun bir zaman boyunca 3SUM problemini $O(n^2)$ zamandan daha verimli bir şekilde çözmenin mümkün olmayacağı kabul edilmiştir. Fakat 2014’te bu durumun böyle olmadığı anlaşılmıştır. ↩
Dinamik programlama, tam bir aramanın doğruluğu ile açgözlü algoritmaların verimliliğini birleştiren bir tekniktir. Eğer bir problemde aynı alt problemler birkaç defa çözülüyorsa ve bu alt problemler bağımsız bir şekilde çözülebiliyorsa dinamik programlama kullanabiliriz.
Dinamik programlamanın iki temel kullanımı vardır:
Bu bölüm, dinamik programlamanın temellerini ve klasik problemler üzerindeki uygulamalarını gösterecektir.
Bölüm 6’da gördüğümüz para problemini tekrar ele alalım: coins = {c_1, c_2, ..., c_k} değerlerinden oluşan bir para kümesiyle, n toplamını oluşturan en az sayıda parayı bulmak. Açgözlü yaklaşımın her zaman çalışmadığını görmüştük. Şimdi bu problemi her para kümesi için çalışan dinamik programlama ile çözeceğiz.
Problemin çözümünü daha küçük alt problemlerin çözümlerinden bulabiliriz. solve(x), x toplamı için gereken minimum para sayısını ifade etsin.
Eğer coins = {1, 3, 4} ise, x toplamına ulaşmak için ilk seçtiğimiz para ya 1, ya 3, ya da 4 olabilir.
x-1 toplamı için solve(x-1) kadar paraya ihtiyacımız olur.x-3 toplamı için solve(x-3) kadar paraya ihtiyacımız olur.x-4 toplamı için solve(x-4) kadar paraya ihtiyacımız olur.Bu durumda özyineleme formülü şu şekilde olur:
solve(x) = min(solve(x-1)+1, solve(x-3)+1, solve(x-4)+1)
Temel durum solve(0) = 0‘dır.
Yukarıdaki özyinelemeli fonksiyon, aynı solve(x) değerini tekrar tekrar hesapladığı için verimsizdir. Memoization tekniği ile, hesaplanan her solve(x) değerini bir dizide saklarız. Fonksiyon tekrar aynı x değeri için çağrıldığında, sonucu yeniden hesaplamak yerine doğrudan diziden alırız.
Açgözlü algoritma, her zaman o anki en iyi gözüken kararı vererek çözüme ulaşan bir yaklaşımdır. Açgözlü bir algoritma asla daha önce verdiği kararları geri almaz ve doğrudan son sonucu oluşturur. Bu yüzden açgözlü algoritmalar genellikle verimlidir. Açgözlü bir algoritma oluşturmanın zorluğu, her zaman en iyi (optimal) cevabı verecek bir açgözlü strateji bulmaktır. Yapılan küçük optimal kararların, genel olarak da optimal olması gerekir. Genellikle bir açgözlü algoritmanın doğru çalıştığını kanıtlamak zordur.
Elimizdeki madeni paraları kullanarak n miktarında bir para üstü vermemiz isteniyor. Elimizdeki paraların değerleri coins = {c_1, c_2, ..., c_k}‘dir ve her parayı istediğimiz kadar kullanabiliriz. Amaç, toplam için gereken minimum sayıda madeni para kullanmaktır.
Örneğin, {1, 2, 5, 10, 20, 50, 100, 200} paralarıyla n = 520 oluşturmak için en az 4 para gerekir: 200 + 200 + 100 + 20.
Basit bir açgözlü algoritma, gereken miktar toplanana kadar her zaman seçilebilecek en büyük değerli parayı seçmektir. Bu strateji, standart Euro madeni paraları gibi sistemlerde işe yarar.
Ancak genel durumda, sahip olduğumuz paralar rastgele değerlerde olabilir ve bu açgözlü algoritma her zaman optimal çözümü vermeyebilir. Örneğin, elimizdeki paralar {1, 3, 4} ise ve istenen toplam 6 ise, açgözlü algoritma 4 + 1 + 1 (3 adet para) çözümünü verirken, en iyi çözüm 3 + 3‘tür (2 adet para).
Para problemi için her zaman çalışan genel bir açgözlü algoritma bilinmemektedir1.
Çoğu zaman planlama sorusu açgözlü algoritmalar ile çözülebilir. Klasik bir problem, başlangıç ve bitiş zamanları bilinen n tane etkinlikten, birbiriyle çakışmayacak şekilde en fazla sayıda etkinliği seçmektir.
| Etkinlik | Başlama Zamanı | Bitiş Zamanı |
|---|---|---|
| A | 1 | 3 |
| B | 2 | 5 |
| C | 3 | 9 |
| D | 6 | 8 |
Bu durumda en fazla iki etkinlik seçilebilir, örneğin B ve D.
Farklı açgözlü stratejiler denenebilir:
Süresi ve son teslim tarihi bilinen n tane görevimiz olduğunu düşünelim. Amacımız görevleri yapmak için bir sıra oluşturmak. Her görev için $d - x$ puan kazanıyoruz, burada d görevin son teslim tarihi ve x görevi bitirdiğimiz zamandır. En fazla alabileceğimiz toplam puan kaçtır?
İlginç bir şekilde, bu sorunun optimal çözümü son teslim tarihlerine bağlı değildir. Doğru açgözlü strateji, görevleri sürelerine göre artan bir şekilde sıralamaktır. Bunun nedeni, eğer daha uzun süren bir görevi daha kısa süren bir görevden önce yaparsak, bu iki görevin yerini değiştirdiğimizde toplam puanın her zaman artması veya aynı kalmasıdır. Daha kısa görevleri önce bitirmek, sonraki tüm görevlerin bitiş zamanını öne çeker ve toplam puanı iyileştirir.
Bize n tane $a_1, a_2, …, a_n$ sayısı verildiğinde, $\sum_{i=1}^{n} \lvert a_i - x\rvert ^c$ toplamını en küçük yapacak x değerini bulma problemi.
$\sum \lvert a_i - x\rvert $ toplamını minimize etmek için en iyi x değeri, sayıların medyanıdır. Sayılar sıralandıktan sonra ortadaki eleman medyandır.
$\sum (a_i - x)^2$ toplamını minimize etmek için en iyi x değeri, sayıların aritmetik ortalamasıdır ($(\sum a_i) / n$).
Bir metni sıkıştırmak için her karaktere bir bit dizisi (kod) atanabilir. Daha sık geçen karakterlere daha kısa kodlar, daha az geçenlere daha uzun kodlar atayarak metnin toplam uzunluğu azaltılabilir.
Huffman Kodlaması, bir metni sıkıştırmak için en optimal kodu (prefix code) üreten bir açgözlü algoritmadır2.
Algoritma, karakterlerin metindeki frekanslarına (geçme sıklıklarına) dayalı bir ikili ağaç (binary tree) oluşturur.
Oluşturulan ağaçta, kökten bir karakterin yaprağına giden yol o karakterin kodunu verir (sola gitmek ‘0’, sağa gitmek ‘1’).
Bu yöntemle, sık geçen ‘A’ karakteri gibi karakterler kısa kodlar alırken, az geçen ‘B’ ve ‘D’ gibi karakterler daha uzun kodlar alır, bu da optimal sıkıştırmayı sağlar.