Dinamik Programlama: Aynı Soruyu İki Kez Çözmemenin Sanatı

Fibonacci'nin trajedisi

Klasik soru: $F(n) = F(n-1) + F(n-2)$ (Fibonacci dizisi). Naif rekürsif kod:

F(n):
    if n < 2: return n
    return F(n-1) + F(n-2)

$F(50)$ hesaplayın. Çok yavaş — dakikalar sürer. Niçin?

Çünkü $F(50)$, $F(48)$'i iki kere hesaplar (içeride). $F(48)$, $F(46)$'yı 3 kere hesaplar. $F(46)$, $F(44)$'ü 5 kere hesaplar. Üstel patlama: $\sim \phi^n$ kere fonksiyon çağrısı.

Çözüm: aynı şeyi iki kere hesaplama. Her değer hesaplandığında kaydet (memoizasyon):

memo = {}
F(n):
    if n in memo: return memo[n]
    if n < 2: return n
    memo[n] = F(n-1) + F(n-2)
    return memo[n]

Artık $F(50)$ milisaniyede çıkıyor. Üstel → doğrusal.

Bu, dinamik programlamanın özüdür: aynı alt problemi iki kez çözmemek.

Dinamik programlama nedir?

Dinamik programlama (DP), iki temel özellik gerektirir:

1. Optimal alt yapı: Genel problem optimal alt problemler kombinasyonu ile çözülür.
2. Çakışan alt problemler: Aynı alt problem defalarca karşımıza çıkar.

Eğer her ikisi de varsa, DP mükemmel uygundur.

İki yaklaşım

Top-down (memoization)

Yukarıdan başla, gerektiğinde aşağı in. Memo tablosu ile aynı şeyi iki kez hesaplama.

Pseudocode:

solve(state):
    if state in memo: return memo[state]
    if base_case(state): return value
    memo[state] = combine(solve(substate1), solve(substate2), ...)
    return memo[state]

Bottom-up (tabulation)

Aşağıdan başla — küçük alt problemleri önce çöz. Bunları kullanarak büyüklere çık.

Pseudocode:

dp[0] = base_case_0
dp[1] = base_case_1
for i in range(2, n+1):
    dp[i] = combine(dp[i-1], dp[i-2], ...)
return dp[n]

İkisi de aynı sonucu verir. Top-down daha sezgisel; bottom-up çoğunlukla daha hızlı ve hafıza-verimli.

Klasik örnekler

1. Fibonacci

Yukarıda anlatıldı. $O(2^n) \to O(n)$.

2. Sırt çantası problemi (Knapsack)

$n$ eşya, her birinin değeri ve ağırlığı var. Kapasiteli sırt çantasına maksimum değer paketle.

DP: $dp[i][w]$ = ilk $i$ eşyayı düşünerek $w$ kapasiteyle elde edilen max değer.

Karmaşıklık $O(nW)$ — pseudo-polinom (NP-zor problemde polinom çözüm).

3. En uzun ortak alt dizi (LCS)

İki string'in en uzun ortak alt dizesi. Diff araçlarının temeli.

DP: $dp[i][j]$ = ilk $i$ ve ilk $j$ karakterlerin LCS uzunluğu.

$O(mn)$.

4. Matris çarpım sırası

$A_1 \cdot A_2 \cdots A_n$ matris çarpımı için parantezleme — toplam çarpma sayısı min.

DP: $dp[i][j]$ = $i$'den $j$'ye kadar optimal maliyet.

$O(n^3)$.

5. En kısa yol (Bellman-Ford)

Negatif kenar ağırlıklarına izin veren shortest path.

DP: $dp[v]$ = $v$'ye giden en kısa yol; sürekli güncellenir.

$O(VE)$.

6. Yazım hatası düzeltme (Levenshtein mesafesi)

İki string arasındaki minimum edit mesafesi (insert, delete, substitute).

DP: $dp[i][j]$ = ilk $i$ karakter ile ilk $j$ karakter arasındaki min edit.

$O(mn)$. Modern autocomplete, spell-checker, DNA hizalama'da kullanılır.

7. Optimal binary search tree

Belirli frekanslı sorgular için en iyi BST yapı.

8. Coin change

Bozuk para — minimum sayı ile bir miktar oluşturma.

DP: $dp[v]$ = $v$ değerini oluşturmak için min sayı.

9. Eğitim ve test setlerinde regülarizasyon (k-fold cross validation optimizasyonu).

10. Reinforcement learning — Bellman optimality denklemi

$V^*(s) = \max_a [R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^*(s')]$.

Modern AI (AlphaGo, otonom araç) bu denklem ile öğrenir.

Tarihsel köken

Richard Bellman (1953'lerde) — RAND Corporation'da:

• "Dinamik programlama" terimini icat etti. ("Programlama" o zaman askeri planlama anlamına geliyordu.)
• Bellman denklemi: $V(s) = \max_a [R + V(s')]$.
• Yöneylem araştırması, kontrol teorisi, ekonomi uygulamaları.

Bellman'ın hikayesi (kendi yazısında): "Air Force'taki Wilson, kelime 'programlama' dedi ben de dinamik programlama' dedim — Wilson matematiki sevmediği için ifadeyi onaylamış olamazdı, ama 'dinamik' kelimesi askeri sayıldığı için kabul ettim."

Yani modern matematik terminolojisinin en garip kökeni.

Reinforcement learning bağlantısı

Modern derin pekiştirmeli öğrenme (deep reinforcement learning):

• Q-öğrenme: dinamik programlamanın örneklem halini öğrenir.
• Politika iterasyonu: Bellman denkleminin iteratif çözümü.
• AlphaGo, AlphaFold: dinamik programlama + sinir ağları.

Modern AI'nin "düşünme" yapısı temelde dinamik programlamadır.

Karmaşıklık analizi

DP karmaşıklığı $O(\text{durum sayısı}) \times O(\text{her durum için iş})$.

Eğer alt problemlerin sayısı çok büyükse, DP de patlar. Bu, boyut laneti (curse of dimensionality) problemidir. Bellman bunu kendisi vurguladı.

Modern uygulamalar

• Bilgisayar oyunları: yol bulma, AI davranışları.
• Finans: opsiyon fiyatlandırma (Black-Scholes'un sayısal hali).
• Biyoinformatik: DNA dizi hizalama (Smith-Waterman, BLAST).
• Doğal dil işleme: PCFG parsing, CKY algoritması.
• Makine öğrenmesi: kayıp fonksiyonu optimizasyonu.
• Robotik: optimal kontrol.

Sonuç

Dinamik programlama:

• "Aynı soruyu iki kez çözme" felsefesi.
• Üstel → polinom karmaşıklık dönüşümü.
• Bellman'ın 1950 keşfi — askeri planlamadan modern AI'ye.
• Memoizasyon, tabulasyon iki temel teknik.
• Modern algoritma teorisinin merkezi paradigması.

Bir tek prensip: "Önce hesaplanan, kaydedilir." Bu basit fikir, modern bilgisayar bilimi öğrencisinin ilk öğrendiği güçlü tekniklerden biridir.

Fibonacci'den AlphaGo'ya, basit ödevden milyar dolarlık AI sistemlerine, aynı zarif fikir: alt problemlerin çözümlerini sakla, tekrar tekrar hesaplama.

Bellman'ın askeri programlama bağlamında bulduğu kavram, 70 yıl sonra insanlığın en zor problemlerini çözmek için kullanılıyor.