24 Dinamik Programlama 1: SRTBOT

Özyineleme + memoization: alt problemleri SRTBOT çerçevesiyle tanımla, bir recurrence ile ilişkilendir, topolojik sırada bir memo tablosunda sakla — Fibonacci üstelden polinoma iner, bowling ise suffix-DP’de yerel kaba kuvvetle O(n)’e; kursun yepyeni bölümünün, kendi algoritmanı tasarlama bölümünün açılış dersi

Oturum bilgisi

Demaine’in videosu: YouTube — Lecture 15: Dynamic Programming, Part 1 (≈57 dk)
OCW sayfası: MIT 6.006 Lecture 15: Dynamic Programming, Part 1
Seri: MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 23 (L15)
Hoca: Erik Demaine (dinamik programlama; DP ünitesinin AÇILIŞ dersi — 4 dersin 1.si)
Okuma süresi: ≈27 dk

Bu, kursun yepyeni bölümünün açılışıdır: hazır algoritma uygulamaktan kendi algoritmanı tasarlamaya geçiyoruz. Demaine ile başlayan bu blok, en güçlü algoritmik tasarım paradigmasını öğretir: dinamik programlama (DP). Özü iki kelimedir — özyineleme + memoization — ve tasarımı bir akronime bağlanır: SRTBOT.

24.1 Bu Derste Ne Var?

Kursun yepyeni bölümü başlıyor (Erik Demaine). Şimdiye dek hazır algoritmaları (sıralama, çizge, veri yapısı) uyguluyorduk; bundan sonra kendi algoritmamızı sıfırdan tasarlayacağız — özellikle dinamik programlama (DP), en güçlü algoritmik tasarım paradigması.

“dynamic programming… It’s probably the most powerful algorithmic design paradigm.” — Demaine, 1:00

DP’nin özü iki kelimedir: özyineleme + memoization. Tasarım için bir akronim: SRTBOT.

“when I say dynamic programming, I mean recursion with memoization.” — Demaine, 27:13

Üç ana fikir:

SRTBOT — özyinelemeli algoritma tasarımının 6 adımı: Subproblems, Relations, Topological order, Base case, Original problem, Time.
Memoization — alt problem çözümlerini sakla/yeniden kullan; Fibonacci’yi üstelden polinoma indirir.
Yerel kaba kuvvet (local brute force) — “ilk öğeye ne yapabilirim?” sorusunun polinom seçeneği varsa, polinom bir DP elde edilir.

flowchart TD
    A["Ders 23 (L15): Dinamik Programlama 1 — SRTBOT"] --> D["DP = özyineleme + memoization"]
    D --> Da["en güçlü tasarım paradigması<br/>iki kelimelik öz (Demaine)"]
    A --> S["SRTBOT — 6 adım"]
    S --> Sa["Subproblems / Relations / Topological<br/>Base / Original / Time; en zoru S"]
    A --> M["Memoization"]
    M --> Ma["alt problem çözümünü sakla + yeniden kullan<br/>Fibonacci üstelden polinoma"]
    A --> T["Süre formülü"]
    T --> Ta["alt problemler toplamı çarpı özyineleme-dışı iş<br/>her alt problem en fazla bir kez"]
    A --> B["Yerel kaba kuvvet"]
    B --> Ba["ilk öğenin sabit seçeneklerini dene + reuse<br/>bowling B(i)=max(atla,tek,çift) O(n)"]

    classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
    classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
    classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
    class A root
    class D,S,M,T,B branch
    class Da,Sa,Ma,Ta,Ba leaf

Şekil 24.1: Ders 23’ün (L15) kavram haritası: kök = Dinamik Programlama 1 ve SRTBOT (Demaine) — DP ünitesinin açılış dersi; algoritma uygulamaktan algoritma TASARLAMAYA geçiş. Beş dal — (1) DP = özyineleme + memoization: en güçlü tasarım paradigması, iki kelimelik öz. (2) SRTBOT 6 adım: Subproblems, Relations, Topological order, Base case, Original problem, Time; en zoru S (doğru alt problemi bulmak). (3) Memoization: alt problem çözümünü sakla, yeniden kullan; Fibonacci üstelden (phi üzeri n) polinoma (n alt problem). (4) Süre formülü: alt problemler toplamı çarpı özyineleme-dışı iş; her alt problem en fazla bir kez. (5) Yerel kaba kuvvet: ilk öğenin sabit sayıda seçeneğini dene plus reuse; bowling suffix-DP B(i) = max(atla, tek, çift) O(n). Sonuç: DAG en kısa yol da bir DP’dir, memo gizli bir DFS’tir; dizi girdide önek/sonek/alt-dizi seç, alt-dizilim ASLA (2 üzeri n).

Builder Notu — Memoization = caching

DP’nin tek değiştirdiği şey, saf özyinelemeye “hesaplananı sakla, gerektiğinde yeniden kullan” cümlesini eklemektir. Bu desen gerçek sistemlerde önbelleklemenin (caching) ta kendisidir: pahalı bir hesap (HTTP isteği, veritabanı sorgusu, embedding çıkarımı) bir kez yapılır, sonucu bir tabloya yazılır, aynı girdi tekrar gelince tablodan döner. Fibonacci’nin üstelden polinoma inişi, bir memcache/Redis katmanının neden bu kadar büyük bir hız farkı yarattığının minyatür ispatıdır.

İleriye → DP her yerde: dizi hizalama (DNA, diff), Viterbi/DTW (ses/ML), en kısa yol, knapsack, metin akıllı-kırpma — hepsi DP.
İleriye → memoization = caching: “hesaplananı sakla/yeniden kullan” deseni, gerçek sistemde önbellekleme.
Geriye → DAG shortest paths (Ders 16): DAG relaxation aslında bir DP; SRTBOT içinde gizli bir DFS çalışır.
İleriye → DP 2-4 (Ders 24-27): string, ağaç, pseudopolinom alt problemler.

Tek cümle: DP = özyineleme + memoization; SRTBOT ile alt problemleri tanımla, bir recurrence ile ilişkilendir, topolojik sırada çöz, çözümleri bir memo tablosunda sakla — böylece “yerel kaba kuvvet” üstel aramayı polinom zamana indirir.

24.2 1. Yeni Bölüm: Algoritmik Tasarım ve DP

Şimdiye dek “ver(il)en algoritmaya indirge” yaptık. Artık sıfırdan polinom-zaman algoritma tasarlıyoruz. DP, özyinelemeli bir tasarım türüdür ve tümevarımla kanıt tekniğimizle çok iyi uyuşur.

“Today we start a totally new section of the class.” — Demaine, 0:18

DP’nin temeli: alt problemleri tanımla, aralarındaki ilişkiyi (recurrence) yaz, çevrimsiz (DAG) bir alt-problem grafı kur, çözümleri sakla. Tüm dersi tek bir disiplinde toparlayan akronim SRTBOT’tur.

24.3 2. SRTBOT Çerçevesi

Özyinelemeli algoritma tasarımının altı adımı (akronim SRTBOT):

“SRTBOT… sub-problems, relations, topological order, base case, original problem, and time.” — Demaine, 2:33

S — Subproblems (alt problemler): problemi polinom sayıda alt probleme böl. En zor adım — doğru alt problemi bulmak.
R — Relations (ilişki): bir alt problemi daha küçüklerinden çöz (recurrence).
T — Topological order: alt-problem grafı DAG olmalı (çevrim = sonsuz döngü); topolojik sıra.
B — Base case (taban durum): özyinelemenin durağı.
O — Original problem: çözmek istediğin (genelde alt problemlerden biri).
T — Time (süre): $\sum$ (alt problemler) $\times$ özyineleme-dışı iş.

DP = SRTBOT + memoization.

Şekil 24.2 altı adımı tek bir yatay zincirde toplar; her kutuda adımın adı, Türkçe tek-satır açıklaması ve altında bu dersin bowling örneğindeki karşılığı yer alır (S: sonek $B(i)$, R: $\max$(atla, tek, çift), …, O: $B(0) = 109$ — bu sayı motordan canlı hesaplanır, T: $7$ alt problem $\times\, O(1) = O(n)$).

Şekil 24.2: SRTBOT — özyinelemeli tasarımın 6 adımı yatay zincir (Demaine L15 §2): S→R→T→B→O→T. Her kutuda adım adı (İngilizce) + Türkçe tek-satır açıklama + altında BOWLING karşılığı (amber). S: Subproblems — B(i) = i’den sona sonek max skoru. R: Relations — max(atla, tek v_i, çift v_i·v_{i+1}). T: Topological — i azalan (n → 0). B: Base — B(n)=B(6)=0. O: Original — B(0)=109 (motordan canlı). T: Time — 7 alt problem × O(1) = O(n). Amber oklar zinciri kutudan kutuya bağlar. Alt not: Demaine 2:33 — her DP çözümü bu altı adımın bir örneğidir. DP = SRTBOT + memoization. Veri MOTORDAN: bowling_bottom_up([1,9,9,2,−5,−5])[0] == 109 (assert); B(n)=B(6)=0 taban (assert); n=6 → T kutusu ‘7 alt problem × O(1) = O(n)’.

24.4 3. Örnek: Merge Sort SRTBOT ile

Bildiğimiz merge sort’u SRTBOT’a oturtalım. S: $S(i, j) = A[i..j-1]$’i sırala. O: $S(0, n)$. R: $S(i, j) = \mathrm{merge}(S(i, m), S(m, j))$ ($m$ = orta). T: $j - i$ artan sırada. B: boş dizi. Time: $O(n \log n)$.

(Merge sort memoization’dan yararlanmaz — alt diziler ayrık, tekrar yok. Ama çerçeve uygulanabilir; SRTBOT yalnızca DP’ye değil, her özyinelemeli tasarıma uyar.)

24.5 4. Fibonacci: Memoization’sız Üstel

Fibonacci: $f_n = f_{n-1} + f_{n-2}$, $f_1 = f_2 = 1$. S: $f(i) = i$. Fibonacci. R: $f(i) = f(i-1) + f(i-2)$. Doğal özyineleme — ama özyineleme ağacı çizilince $f(n-3), f(n-2)$ gibi alt problemler defalarca hesaplanır.

$T(n) = T(n-1) + T(n-2) + 1 \to$ çözüm yaklaşık $\varphi^n$ (altın oran, üstel). Üstel = kötü; yalnız çok küçük $n$ çözülür.

Şekil 24.3 bu dersin imza karşılaştırmasını verir: solda $f(6)$’nın tam özyineleme ağacı (memoization YOK) — motordan sayılan tekrarlar amber tonlarıyla işaretli ($f(3)$ tam 3 kez, $f(2)$ 5 kez, $f(1)$ 3 kez; ağaç $15$ düğüm = naif $15$ çağrı); sağda aynı alt problemler memoization ile tek kopya zincir-DAG ($f(1) \ldots f(6)$) ve büyük sayılar paneli ($n = 20$: naif $13.529$ çağrı, memo TAM $20$ alt problem; oran $\mathrm{calls}(20)/\mathrm{calls}(15) = 11{,}10 \approx \varphi^5 = 11{,}09$ — büyüme $\approx \varphi^n$ üstel).

Şekil 24.3: Fibonacci: özyineleme ağacından memoization’a — üstelden polinoma (Demaine L15 §4-5 İMZA). SOL: f(6) tam özyineleme ağacı (memoization YOK); tekrarlanan alt problemler aynı amber tonuyla — f(3) 3 kez, f(2) 5 kez, f(1) 3 kez (motordan sayıldı); ağaç 15 düğüm = naif 15 çağrı. SAĞ: aynı düğümler memo ile TEK KOPYA zincir-DAG (f(1)..f(6)); her f(i)’den f(i−1) ve f(i−2)’ye geri-ok (bir kez hesapla, sonra oku); büyük sayılar paneli — n=20: naif 13.529 çağrı vs memo TAM 20 alt problem; oran(20/15) = 11.10 ≈ phi^5 = 11.09 → büyüme yaklaşık phi^n ÜSTEL. Veri MOTORDAN (assert): fib_naive_counted(20) = (6765, 13529); fib_naive_counted(15)[1] = 1219; fib_naive_counted(6) = (8, 15); fib_memo_counted(20) = (6765, 20); ratio 13529/1219 = 11.10 ≈ phi^5 = 11.09; f(6) ağaç düğüm 15, f(3) tekrar 3.

24.6 5. Memoization: Üstelden Polinoma

Küçük bir kurnazlık her şeyi değiştirir: memoization — alt problem çözümlerini bir “memo” tablosuna yaz, gerektiğinde yeniden kullan.

“remember and reuse solutions to sub-problems.” — Demaine, 14:14

Generic DP yapısı (her DP böyledir):

memo = {}
def f(subproblem):
    if subproblem in memo:          # daha once cozuldu mu?
        return memo[subproblem]     # tekrar etme, dondur
    if base_case(subproblem):       # taban durum
        result = base_value
    else:                           # recurrence ile ozyinele
        result = relation(f, subproblem)
    memo[subproblem] = result       # sakla
    return result

Memo tablosu genelde bir doğrudan-erişim dizisi veya hash tablosu. Fibonacci için: her alt problem en fazla bir kez çözülür $\to$ n alt problem $\times\, O(1)$ $= O(n)$. (Bir DFS’in “ziyaret edildi mi” kontrolünü oynar memo tablosu.)

Şekil 24.4 bu generic iskeleti bir akış diyagramı olarak çizer: çağrı $\to$ “alt problem memoda mı?” (EVET $\to$ tabloyu döndür, tekrar hesaplama YOK) $\to$ “taban durum mu?” (EVET $\to$ taban değer; HAYIR $\to$ recurrence ile özyinele) $\to$ sonucu sakla $\to$ döndür. Sağ alt köşede, memonun bir DFS’in “ziyaret edildi mi” kontrolünü oynadığı not edilir. Motor tanığı: $\mathrm{bowling\_memo\_counted}([1,9,9,2,-5,-5]) = (109, 7)$ — $n+1 = 7$ alt problem, her biri tam bir kez.

Şekil 24.4: Generic DP iskeleti — f(alt problem) akış diyagramı (Demaine L15 §5 pseudocode birebir): memo kontrolü → taban → recurrence → sakla. SOL DİKEY ANA AKIŞ: çağrı → karar ‘ap ∈ memo?’ → (HAYIR) karar ‘taban durum?’ → (EVET) result = taban değer / (HAYIR) result = relation(f, ap), özyinele → her iki dal SAKLA kutusunda birleşir (memo[ap] = result, amber). SAĞ: memo HIT kısa-devresi — ‘ap ∈ memo?’ EVET → memo[ap] döndür, TEKRAR HESAPLAMA YOK (amber kalın) → return result. SAĞ ALT KÖŞE: memo = bir DFS’in ziyaret-edildi-mi kontrolü; DP içinde GİZLİ DFS çalışır (Demaine §7). ALT NOT (motor tanıklı): her alt problem EN FAZLA BİR KEZ çözülür → T = Σ (alt problem) × (özyineleme-dışı iş); tanık bowling([1,9,9,2,−5,−5]) → skor 109, 7 alt problem (n+1). Veri MOTORDAN (assert): bowling_memo_counted([1,9,9,2,−5,−5]) == (109, 7); fib_memo_counted(10) == (55, 10); ikisi de AYNI iskelet.

24.7 6. Çalışma Süresi Formülü

Memoization’lı bir DP’nin süresi:

T = Σ (tüm alt problemler) × (recurrence’ın özyineleme-dışı işi)

“the time it takes is at most the sum over all sub problems of the relation time.” — Demaine, 23:07

Çünkü her alt problem en fazla bir kez çözülür; özyinelemeli çağrılar zaten toplama dahildir. (Fibonacci: $n \times O(1) = O(n)$.)

Word-RAM inceliği. Fibonacci sayıları $n$-bit büyüklüğüne ulaşır; bir $w$-bit makine sözcüğünde toplama, $\lceil n/w \rceil$ sözcük işine mal olur. Dolayısıyla daha hassas süre $O(n + n^2/w)$’dir — ama bu da $w$ sabitken polinom kalır. Asimptotik tablo değişmez: memoization, Fibonacci’yi üstelden polinoma indirir.

24.8 7. DAG En Kısa Yol DP Olarak

DAG tek-kaynak en kısa yol (Ders 16) aslında bir DP’dir. S: $\delta(s, v)$ tüm $v$. O: hepsi. R:

\[\delta(s, v) = \min\bigl(\{\delta(s, u) + w(u, v) : (u, v) \text{ gelen kenar}\} \cup \{\infty\}\bigr)\]

T: alt-problem grafı = $G$’nin kendisi $\to$ $G$’nin topolojik sırası. B: $\delta(s, s) = 0$. Time: $\sum$ (gelen kenar sayısı $+ 1$) $= O(V + E)$.

İlginç: generic DP algoritması (memo-kontrol $\to$ özyinele) alt-problem grafının tersinde bir DFS çalıştırır; memo tablosu “ziyaret edildi mi” kontrolüdür. Yani DP, içinde DFS + topolojik sıra barındırır — “bedavaya”.

Şekil 24.5 bu denkliği Ders 16 örneğiyle kanıtlar: solda $8$ düğümlü DAG (topolojik sıra $a, b, e, f, g, h, d, c$; kaynak $e$), her düğümün üstünde motordan hesaplanan $\delta$ rozeti ($e{:}0, f{:}3, g{:}5, h{:}6, d{:}3, c{:}8$; $a = b = \infty$ soluk, erişilmez), ve $h$ için gelen-kenar min recurrence’ı vurgulu ($\delta(h) = \min(\delta(f)+8, \delta(g)+1) = \min(11, 6) = 6$; kazanan $g \to h$ amber, kaybeden $f \to h$ kesikli + “11” üstü çizik); sağda recurrence kutusu, SRTBOT eşleme tablosu (S/R/T/B/O/T) ve alt tanık rozeti — memoized çağrı sayısı $= 8 = V$ (gizli DFS tanığı), $\mathrm{dag\_sp\_memoized}$ ile $\mathrm{dag\_relaxation}$ aynı $\delta$’yı BİREBİR verir (D16 çapraz tanık).

Şekil 24.5: DAG en kısa yol = Dinamik Programlama (Demaine L15 §7; D16 köprüsü): delta(s,v) = min{ gelen δ(s,u)+w(u,v) } ∪ {∞}. SOL: D16 çizgesi (8 düğüm; topo sırası a,b,e,f,g,h,d,c soldan sağa); her düğümün üstünde δ değeri rozetli (e=0 amber kaynak; a,b=∞ soluk erişilemez). h için GELEN-kenar min recurrence vurgulu: δ(h) = min(δ(f)+8, δ(g)+1) = min(11, 6) = 6 — kazanan g→h amber kalın, kaybeden f→h kesikli + ‘11’ üstü çizik. SAĞ: recurrence kutusu + SRTBOT eşleme tablosu (S alt problem / R ilişki / T topo sıra / B taban / O orijinal / T süre = O(V+E)) + alt rozet (memoized çağrı sayısı = 8 = V gizli DFS tanığı; dag_relaxation ile BİREBİR). Veri MOTORDAN (assert): topo == [a,b,e,f,g,h,d,c]; delta == {a:∞,b:∞,e:0,f:3,g:5,h:6,d:3,c:8}; nsub == 8 == V; delta == dag_relaxation (D16 çapraz tanık); δ(f)+8=11, δ(g)+1=6, δ(h)=min(11,6)=6.

Builder Notu — DAG = build sistemi

Alt-problem grafının çevrimsiz (DAG) olması bir tesadüf değil, bir zorunluluktur: çevrim olsaydı bir alt problem kendini beklerdi (sonsuz döngü). Bu yapı gerçek mühendislikte her gün karşına çıkar — build sistemleri (Make, Bazel, webpack), paket bağımlılık çözücüler, elektronik tablo hücre yeniden-hesaplaması ve görev zamanlayıcıları hep bir bağımlılık DAG’ını topolojik sırada işler. Memoization’lı DP’nin “her düğümü bir kez çöz, sonucu sakla” mantığı, Make’in “değişmemiş hedefi yeniden derleme” mantığının ta kendisidir; ikisi de aynı gizli DFS’i koşturur.

24.9 8. Alt-Problem Tasarım Aracı: Prefix/Suffix/Substring

Girdi bir dizi ise, doğal alt problem adayları:

“if your input is a sequence, here are some good sub-problems… prefixes… suffixes… substrings.” — Demaine, 43:03

Önekler (prefixes): $x[:i]$, her $i$ için — $\Theta(n)$ tane.
Sonekler (suffixes): $x[i:]$, her $i$ için — $\Theta(n)$ tane.
Alt diziler (substrings): $x[i:j]$ — $\Theta(n^2)$ tane.

Alt-dizilim (subsequence) KULLANMA — $2^n$ tane (üstel). Önek/sonek genelde denktir ve yeterlidir; yetmezse substring’e geç.

Şekil 24.6 bu dört adayı $n = 6$ örnek dizide (“ABCDEF”) yan yana sıralar: önek satırı soldan büyür (A, ABC, ABCDEF), sonek sağdan büyür (F, DEF, ABCDEF) — ikisi de yeşil “$\Theta(n)$ — 7 tane” rozetiyle; substring ortadan bir aralık seçer (CD, BCDE, …) amber “$\Theta(n^2)$ — 28 tane”; subsequence atlamalı seçim (A_C_E, …) kırmızı üstü-çizik “$2^n = 64$ — YASAK”. Sayılar figür içinde gerçek enumerasyondan hesaplanır ($n+1 / n+1 / (n+1)(n+2)/2 / 2^n$).

Şekil 24.6: Alt-problem tasarım aracı: dizi girdide hangi alt problemi seçeyim? (Demaine L15 §8, 43:03; n=6 ‘ABCDEF’). 4 satır: PREFIX (önekler x[:i]) soldan büyüyen A / ABC / ABCDEF + yeşil ‘Θ(n) — 7 tane’; SUFFIX (sonekler x[i:]) sağdan büyüyen F / DEF / ABCDEF + yeşil ‘Θ(n) — 7 tane’; SUBSTRING (alt diziler x[i:j]) ortadan CD / BCDE / D + amber ‘Θ(n²) — 28 tane’; SUBSEQUENCE (alt dizilim, atlamalı) A C E / B D F / A F üstü-çizik kırmızı + ‘2ⁿ = 64 — YASAK’. ALT NOT: dizi girdide önce prefix/suffix dene → yetmezse substring → subsequence ASLA (Demaine 43:03); n+1 / n+1 / (n+1)(n+2)/2 polinom çözülebilir, 2ⁿ üstel DP tablosu patlar. Veri figür içinde GERÇEK enumerasyondan (assert): prefix = n+1 = 7; suffix = n+1 = 7; substring = (n+1)(n+2)/2 = 28; subsequence = 2ⁿ = 64; sıralama prefix=suffix < substring < subsequence.

24.10 9. Bowling Problemi: SRTBOT Uygulaması

Problem. $n$ pin, pin $i$ değeri $v_i$. Bir pin vurursan $v_i$ puan; bitişik iki pini ($i, i+1$) birlikte vurursan $v_i \cdot v_{i+1}$ puan. Skoru maksimize et (pinleri atlamak serbest).

Çalışılan Örnek — suffix DP. S: $B(i) = $ pin $i \ldots n-1$ ile elde edilebilecek maksimum skor. O: $B(0)$. R: ilk pin $i$’ye üç şey yapabilirim — atla, tek vur, ya da $i+1$ ile çiftle:

\[B(i) = \max\bigl(B(i+1),\; B(i+1) + v_i,\; B(i+2) + v_i \cdot v_{i+1}\bigr)\]

T: $i$ azalan (for $i = n-1 \ldots 0$). B: $B(n) = 0$. Time: $n$ alt problem $, O(1) = $ $O(n)$.

24.11 10. Bottom-Up DP ve Yerel Kaba Kuvvet

SRTBOT’u doğrudan bir for-döngüsü algoritmasına çevirebiliriz (bottom-up): taban durumu yaz, topolojik sırada döngü kur, recurrence’ı uygula, sonunda orijinali döndür.

def bowling(v, n):
    B = [0] * (n + 1)               # B[n] = 0 taban durum
    for i in range(n - 1, -1, -1):  # topolojik sira: i azalan
        B[i] = max(B[i + 1], B[i + 1] + v[i])
        if i + 1 < n:               # cift yalnizca >= 2 pin varsa
            B[i] = max(B[i], B[i + 2] + v[i] * v[i + 1])
    return B[0]                      # orijinal problem

Bu, yerel kaba kuvvettir (local brute force): pin $i$ için tüm seçenekleri (3 tane) dene, en iyisini al. Normalde $3 \times 3 \times \ldots$ üstel olurdu; ama alt problemleri yeniden kullandığımızdan doğrusal.

“dp is essentially an idea of using local brute force.” — Demaine, 54:47

DP sezgisi: “çözümün hangi özelliğini bilsem işim biterdi?” Bu özelliğin seçenek sayısı polinomsa, polinom bir DP elde edersin. (Sonek $\to$ ilk öğeyi düşün; önek $\to$ son öğe; substring $\to$ ortadaki öğe.)

“identify some feature of the solution that if we knew that feature we would be done.” — Demaine, 56:00

Şekil 24.7 bu dersin ikinci imza figürüdür ve bowling’i uçtan uca çözer: üstte pin dizisi $v = [1, 9, 9, 2, -5, -5]$ ve optimal plan izi (tek vuruşlar halka, çift kemerler amber yay; “$(-5) \cdot (-5) \to$ POZİTİFLEŞİR” rozeti) — toplam $1 + 81 + 2 + 25 = 109$; altta suffix-DP tablosu $B$ doldurma sırası $i = 6 \to 0$ (topolojik sıra, sağdan sola amber ok), her hücrede $B[i]$ değeri ve kazanan seçenek. Motor bunu üç bağımsız yoldan teyit eder: $\mathrm{bowling\_bottom\_up}(v) = [109, 108, 43, 27, 25, 0, 0]$, $\mathrm{bowling\_brute\_pairs}(v) = 109$ (bitmask-çift bağımsız tanık), $\mathrm{bowling\_memo\_counted}(v) = (109, 7)$ ($n+1$ alt problem).

Şekil 24.7: Bowling suffix-DP — pin dizisi + plan izi + B tablosu (Demaine L15 §9-10 İMZA): B[n]=0 taban; i azalan topolojik sıra; her pin 3 seçenek (atla / tek vuruş +v_i / çift kemer v_i·v_{i+1}); negatif çift çarpımla pozitifleşir. ÜST PANEL: pin dizisi v=[1,9,9,2,−5,−5] (negatifler slate dolgu); optimal plan izi — tek vuruşlar halka (✓ +1, +2), çift kemerler amber yay (9·9=81, (−5)·(−5)=25) + ‘(−5)·(−5) → POZİTİFLEŞİR’ rozeti; sağ toplam kutusu 1 + 81 + 2 + 25 = 109. ALT PANEL: suffix-DP tablosu B 7 hücre i=0..6, doldurma yönü i=6→0 (topolojik sıra, sağdan sola amber ok); her hücre B[i] değeri + kazanan seçenek (← çift/tek/atla) + formül; B[0]=109 CEVAP amber vurgu, B[6]=0 taban (boş sonek). ALT NOT: her pin 3 seçenek, alt problemler YENİDEN KULLANILIR → 3ⁿ kaba kuvvet yerine O(n); yerel kaba kuvvet sabit ≤3 seçenek/pin (Demaine 54:47). Veri MOTORDAN (assert): v=[1,9,9,2,−5,−5]; bowling_bottom_up(v)=[109,108,43,27,25,0,0]; plan=[(0,tek,1),(1,çift,81),(3,tek,2),(4,çift,25)]; bowling_brute_pairs(v)=109 (bağımsız); bowling_memo_counted(v)=(109,7); plan toplam=B[0]=109.

Builder Notu — DP → Viterbi / DTW / diff

“İlk öğeye ne yapabilirim?” + memoization şablonu, bowling’in çok ötesine geçer. Aynı yerel-kaba-kuvvet refleksi gerçek ML ve sistem araçlarının çekirdeğidir: Viterbi (gizli Markov modellerinde en olası durum dizisi — her adımda “bu gözlem hangi durumdan geldi?”), DTW (dynamic time warping — ses/zaman serisi hizalama), diff ve git merge (en uzun ortak alt-dizilim üzerinden satır eşleme), sequence alignment (Needleman-Wunsch, Smith-Waterman — DNA/protein). Hepsi bir dizide ilk/son öğenin sabit sayıda seçeneğini deneyip alt problem çözümlerini yeniden kullanır. Bu dersin bir sonraki adımı (Ders 24, LCS/LIS) tam da bu köprünün ilk taşıdır.

24.12 Bu Dersin Özeti

DP = özyineleme + memoization; en güçlü tasarım paradigması.
SRTBOT: Subproblems / Relations / Topological / Base / Original / Time.
Memoization: alt problem çözümünü sakla $\to$ her biri bir kez $\to$ Fibonacci $O(n)$.
Süre formülü: $\sum$ alt problemler $\times$ özyineleme-dışı iş.
DAG shortest path = DP; içinde DFS + topolojik sıra gizli.
Alt-problem aracı: prefix/suffix $\Theta(n)$, substring $\Theta(n^2)$; subsequence ($2^n$) YASAK.
Bowling: suffix DP, $B(i)$ = max(atla, tek, çift) → $O(n)$; yerel kaba kuvvet.

Tek Bir Cümle

DP, “ilk öğeye ne yapabilirim?” sorusunu polinom sayıda alt problem üzerinde memoization’la çözer: SRTBOT ile alt problemleri tanımla, recurrence ile ilişkilendir, topolojik sırada sakla — yerel kaba kuvvet üstel aramayı polinom zamana indirir.

24.13 Kontrol Soruları

Soru 1: Fibonacci’nin saf özyinelemesi neden üstel, memoization neden polinom yapar?

Cevap: Saf özyinelemede $f(n)$, $f(n-1)$ ve $f(n-2)$’yi çağırır; bunlar da kendi alt çağrılarını yapar — özyineleme ağacında $f(n-3), f(n-2)$ gibi alt problemler defalarca yeniden hesaplanır. $T(n) = T(n-1) + T(n-2) + 1 \approx \varphi^n$ (üstel). Memoization, her alt problemi çözünce bir memo tablosuna yazar; aynı alt problem ikinci kez istendiğinde yeniden hesaplanmaz, tablodan döner. Böylece yalnız $n$ farklı alt problem, her biri $O(1)$ $\to$ $O(n)$. Tek değişiklik “hesaplananı sakla/yeniden kullan”dır.

Soru 2: SRTBOT’un altı adımı nedir, ve hangisi en zordur?

Cevap: Subproblems (alt problemleri tanımla), Relations (recurrence ile ilişkilendir), Topological order (DAG + çözüm sırası), Base case (taban durum), Original problem (çözmek istediğin), Time ($\sum$ alt problem $\times$ özyineleme-dışı iş). En zoru genelde S (ve onunla bağlı R): doğru alt problemleri bulmak. Demaine’in sezgisi: “çözümün hangi özelliğini bilsem işim biterdi?” — o özelliğin polinom seçeneği varsa, alt problemler doğru kurulur.

Soru 3: Neden dizi problemlerinde alt-dizilim (subsequence) alt problem olarak seçilmez?

Cevap: $n$ öğeli bir dizinin $2^n$ alt-dizilimi vardır (her öğe ya alınır ya alınmaz) — üstel. Alt problemleri alt-dizilimlerle parametreleştirirsek, alt problem sayısı garantili üstel olur $\to$ DP’nin tüm avantajı kaybolur. Oysa önek ($\Theta(n)$), sonek ($\Theta(n)$) ve alt dizi/substring ($\Theta(n^2)$) polinom sayıdadır. DP’nin işe yaraması için alt problem sayısı polinom olmalı; bu yüzden dizilerde prefix/suffix/substring tercih edilir, subsequence asla.

Soru 4: Bowling’de B(i) = max(B(i+1), B(i+1)+v_i, B(i+2)+v_i·v_{i+1}) neden doğru? ‘Yerel kaba kuvvet’ ne demek?

Cevap: İlk pin $i$’ye yapılabilecek tüm şeyler: (1) atla $\to$ kalan sonek $B(i+1)$; (2) tek vur $\to$ $B(i+1) + v_i$; (3) $i+1$ ile çiftle $\to$ $B(i+2) + v_i \cdot v_{i+1}$. Bu üç seçenek tüm olasılıkları kapsar; max alarak en iyisini seçeriz. Geri kalan her durumda kalan bir sonektir (daha küçük alt problem) $\to$ özyineleme geçerli. “Yerel kaba kuvvet”: her adımda yalnız ilk öğenin seçeneklerini (sabit sayıda) dene; alt problemler yeniden kullanıldığından, normalde $3^n$ olacak arama $O(n)$’e iner.

24.14 Egzersizler

Egzersiz 1. Fibonacci’yi hem memoizasyonlu (top-down) hem bottom-up Python’da yaz; her ikisinin de $O(n)$ toplama yaptığını doğrula.

Egzersiz 2. Bowling’i verilen bir örnek dizide (örn. $[1, 9, 9, 2, -5, -5]$) elle $B(i)$ tablosuyla çöz; optimal stratejiyi göster.

Egzersiz 3. DAG en kısa yolu SRTBOT olarak yaz (S/R/T/B/O/T); recurrence’ın gelen kenarlar üzerinden min olduğunu açıkla.

Egzersiz 4. Bir dizi problemi için prefix, suffix ve substring alt problem sayılarını ($\Theta(n), \Theta(n), \Theta(n^2)$) ve subsequence’in neden $2^n$ olduğunu yaz.

Egzersiz 5. Bowling kuralını değiştir (örn. üç bitişik pin de vurulabilsin); recurrence’a yeni seçeneği ekle ve sürenin hâlâ $O(n)$ kaldığını göster.

24.15 Sonraki Ders İçin Hazırlık

Sonraki: Ders 24 (L16) — Dinamik Programlama 2 (Erik Demaine)

Ders 24 (L16): Dinamik Programlama 2 (string alt problemleri, Erik Demaine). DP’yi dizi/string problemlerine uyguluyoruz: en uzun ortak alt-dizilim (LCS), en uzun artan alt-dizilim (LIS) gibi klasikler, ve oyun ağaçları. SRTBOT aynı kalır; alt problemler önek/sonek/substring olur, recurrence “son karakteri eşleştir/eşleştirme” gibi yerel kaba kuvvetle kurulur. DP ünitesi burada devam eder (Ders 24-27 = L16-L18; araya Ders 25 = PS8 girer); blok, Quiz 3 kapsamının (DP) belkemiğidir ve Ders 30 = PS10/Quiz 3 Gözden Geçirme ile özetlenir.

Ders 24 Öncesi Yapılacak:

Bu dersin egzersizlerini, özellikle Egzersiz 1 (Fibonacci iki yöntem) ve 2 (bowling) çöz.
SRTBOT’un altı adımını ezberden say; her birine bowling’den örnek ver.
Ana cümleyi tekrar oku: “Çözümün hangi özelliğini bilsem işim biterdi? — polinom seçenek → polinom DP.”

24.16 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Sayfada
Dinamik programlama	Özyineleme + memoization; polinom tasarım	Böl. 1
SRTBOT	Subproblems/Relations/Topological/Base/Original/Time	Böl. 2
Memoization	Alt problem çözümünü sakla/yeniden kullan	Böl. 5
Süre formülü	$\sum$ alt problem $\times$ özyineleme-dışı iş	Böl. 6
Alt-problem aracı	prefix/suffix $\Theta(n)$, substring $\Theta(n^2)$; subsequence $2^n$ YASAK	Böl. 8
Bowling recurrence	$B(i)$ = max(atla, tek $v_i$, çift $v_i \cdot v_{i+1}$)	Böl. 9
Bottom-up DP	Base $\to$ topolojik for $\to$ relation $\to$ original	Böl. 10
Yerel kaba kuvvet	İlk öğenin seçeneklerini dene + max/min; reuse	Böl. 10

24.17 Builder ve OMSCS Bağlantıları

6 köprü

Bu ders, hazır algoritma uygulamaktan kendi algoritmanı tasarlamaya geçişin kapısıdır; SRTBOT disiplini ve memoization sezgisi, ML ve sistem mühendisliğindeki çok sayıda araca doğrudan bağlanır — köprülerin özeti:

DP → dizi hizalama (DNA/diff), Viterbi/DTW (ses, ML), metin akıllı-kırpma, knapsack, en kısa yol.
SRTBOT → algoritma tasarım disiplini; her DP’yi altı adımla yazma alışkanlığı (OMSCS CS 6515 — her DP probleminde “önce S/R/T/B/O/T çıkar” refleksi).
Memoization → caching/önbellekleme; saf hesaplamayı tekrar etmeden sakla.
Yerel kaba kuvvet → “her adımda sabit seçenek + reuse” → üstel aramayı polinoma indirme.
Alt-problem grafı = DAG → bağımlılık çözümü, build sistemi; DP içinde gizli DFS.
Optimal alt yapı → en kısa yol + DP köprüsü; alt-problem çözümlerini birleştirme.

Tek bir şey alıp gideceksen

Dinamik programlama = özyineleme + memoization. SRTBOT’la alt problemleri tanımla, bir recurrence ile ilişkilendir, topolojik sırada çöz, çözümleri bir memo tablosunda sakla. Sihir “yerel kaba kuvvettedir”: her adımda yalnız ilk öğenin sabit sayıda seçeneğini dener, en iyisini alırsın — alt problemleri yeniden kullandığından, üstel görünen arama polinom zamana iner. Tek soru: “çözümün hangi özelliğini bilsem işim biterdi?” Bu, kendi algoritmanı tasarlama bölümünün açılışıdır; sırada DP’yi string ve oyunlara taşıyan Ders 24 var.

--- title: "Dinamik Programlama 1: SRTBOT" subtitle: "Özyineleme + memoization: alt problemleri SRTBOT çerçevesiyle tanımla, bir recurrence ile ilişkilendir, topolojik sırada bir memo tablosunda sakla — Fibonacci üstelden polinoma iner, bowling ise suffix-DP'de yerel kaba kuvvetle O(n)'e; kursun yepyeni bölümünün, kendi algoritmanı tasarlama bölümünün açılış dersi" --- ::: {.callout-note title="Oturum bilgisi"} - **Demaine'in videosu:** [YouTube — Lecture 15: Dynamic Programming, Part 1](https://www.youtube.com/watch?v=r4-cftqTcdI) (≈57 dk) - **OCW sayfası:** [MIT 6.006 Lecture 15: Dynamic Programming, Part 1](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec15/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 23 (L15) - **Hoca:** Erik Demaine (dinamik programlama; **DP ünitesinin AÇILIŞ dersi** — 4 dersin 1.si) - **Okuma süresi:** ≈27 dk > Bu, kursun **yepyeni bölümünün** açılışıdır: hazır algoritma uygulamaktan **kendi algoritmanı tasarlamaya** geçiyoruz. Demaine ile başlayan bu blok, en güçlü algoritmik tasarım paradigmasını öğretir: **dinamik programlama (DP)**. Özü iki kelimedir — özyineleme + memoization — ve tasarımı bir akronime bağlanır: **SRTBOT**. ::: ## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d23} Kursun **yepyeni bölümü** başlıyor (Erik Demaine). Şimdiye dek hazır algoritmaları (sıralama, çizge, veri yapısı) *uyguluyorduk*; bundan sonra **kendi algoritmamızı sıfırdan tasarlayacağız** — özellikle **dinamik programlama (DP)**, en güçlü algoritmik tasarım paradigması. > *"dynamic programming... It's probably the most powerful algorithmic design paradigm."* — Demaine, 1:00 DP'nin özü iki kelimedir: **özyineleme + memoization**. Tasarım için bir akronim: **SRTBOT**. > *"when I say dynamic programming, I mean recursion with memoization."* — Demaine, 27:13 Üç ana fikir: 1. **SRTBOT** — özyinelemeli algoritma tasarımının 6 adımı: **S**ubproblems, **R**elations, **T**opological order, **B**ase case, **O**riginal problem, **T**ime. 2. **Memoization** — alt problem çözümlerini sakla/yeniden kullan; Fibonacci'yi üstelden **polinoma** indirir. 3. **Yerel kaba kuvvet (local brute force)** — "ilk öğeye ne yapabilirim?" sorusunun polinom seçeneği varsa, polinom bir DP elde edilir. ```{mermaid} %%| label: fig-concept-map %%| echo: false %%| fig-cap: "Ders 23'ün (L15) kavram haritası: kök = Dinamik Programlama 1 ve SRTBOT (Demaine) — DP ünitesinin açılış dersi; algoritma uygulamaktan algoritma TASARLAMAYA geçiş. Beş dal — (1) DP = özyineleme + memoization: en güçlü tasarım paradigması, iki kelimelik öz. (2) SRTBOT 6 adım: Subproblems, Relations, Topological order, Base case, Original problem, Time; en zoru S (doğru alt problemi bulmak). (3) Memoization: alt problem çözümünü sakla, yeniden kullan; Fibonacci üstelden (phi üzeri n) polinoma (n alt problem). (4) Süre formülü: alt problemler toplamı çarpı özyineleme-dışı iş; her alt problem en fazla bir kez. (5) Yerel kaba kuvvet: ilk öğenin sabit sayıda seçeneğini dene plus reuse; bowling suffix-DP B(i) = max(atla, tek, çift) O(n). Sonuç: DAG en kısa yol da bir DP'dir, memo gizli bir DFS'tir; dizi girdide önek/sonek/alt-dizi seç, alt-dizilim ASLA (2 üzeri n)." flowchart TD A["Ders 23 (L15): Dinamik Programlama 1 — SRTBOT"] --> D["DP = özyineleme + memoization"] D --> Da["en güçlü tasarım paradigması iki kelimelik öz (Demaine)"] A --> S["SRTBOT — 6 adım"] S --> Sa["Subproblems / Relations / Topological Base / Original / Time; en zoru S"] A --> M["Memoization"] M --> Ma["alt problem çözümünü sakla + yeniden kullan Fibonacci üstelden polinoma"] A --> T["Süre formülü"] T --> Ta["alt problemler toplamı çarpı özyineleme-dışı iş her alt problem en fazla bir kez"] A --> B["Yerel kaba kuvvet"] B --> Ba["ilk öğenin sabit seçeneklerini dene + reuse bowling B(i)=max(atla,tek,çift) O(n)"] classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937 classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937 classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937 class A root class D,S,M,T,B branch class Da,Sa,Ma,Ta,Ba leaf ``` ::: {.callout-tip title="Builder Notu — Memoization = caching"} DP'nin tek değiştirdiği şey, saf özyinelemeye "hesaplananı sakla, gerektiğinde yeniden kullan" cümlesini eklemektir. Bu desen gerçek sistemlerde **önbelleklemenin (caching)** ta kendisidir: pahalı bir hesap (HTTP isteği, veritabanı sorgusu, embedding çıkarımı) bir kez yapılır, sonucu bir tabloya yazılır, aynı girdi tekrar gelince tablodan döner. Fibonacci'nin üstelden polinoma inişi, bir memcache/Redis katmanının neden bu kadar büyük bir hız farkı yarattığının minyatür ispatıdır. - **İleriye → DP her yerde:** dizi hizalama (DNA, diff), Viterbi/DTW (ses/ML), en kısa yol, knapsack, metin akıllı-kırpma — hepsi DP. - **İleriye → memoization = caching:** "hesaplananı sakla/yeniden kullan" deseni, gerçek sistemde önbellekleme. - **Geriye → DAG shortest paths (Ders 16):** DAG relaxation aslında bir DP; SRTBOT içinde gizli bir DFS çalışır. - **İleriye → DP 2-4 (Ders 24-27):** string, ağaç, pseudopolinom alt problemler. Tek cümle: *DP = özyineleme + memoization; SRTBOT ile alt problemleri tanımla, bir recurrence ile ilişkilendir, topolojik sırada çöz, çözümleri bir memo tablosunda sakla — böylece "yerel kaba kuvvet" üstel aramayı polinom zamana indirir.* ::: ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 23 (L15) DP 1: SRTBOT motoru (_engine.py D23 bölümü: # fib_naive_counted / fib_memo_counted / fib_bottom_up → Fibonacci üstelden # polinoma; bowling_bottom_up / bowling_memo_counted / bowling_plan / # bowling_brute_pairs / build_bowling_example → bowling suffix-DP; # dag_sp_memoized + D16 bağımlılıkları INF / relax_edge / dag_relaxation / # build_weighted_dag_example → DAG-SP bir DP'dir, ÇAPRAZ TANIK). Slate+Amber # viz sabitleri (_viz.py COL_*). Bu hücre gizlidir (#| echo: false). # # Aşağıdaki TÜM figür hücreleri burada tanımlanan fonksiyonları IMPORT # ETMEDEN kullanır (dosyadan import YOK — brief: setup hücresine INLINE göm). # # Notion'daki öğretim içeriği (görünür ```python blokları) bu motorun tarif # seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar. # # NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama # backend'ini ezer (plt.show() 0 figür üretir). # ============================================================================ import math from collections import Counter import matplotlib.pyplot as plt from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch, Polygon # --------------------------------------------------------------------------- # _viz.py — Slate+Amber stil sabitleri (HEX birebir) # --------------------------------------------------------------------------- COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve COL_ACCENT = "#f59e0b" # amber-500 — vurgu COL_TEXT = "#1f2937" # slate-800 — metin COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast COL_AMBER_600 = "#d97706" # koyu amber COL_AMBER_300 = "#fcd34d" # açık amber COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu) COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara COL_WHITE = "#ffffff" INF = float("inf") # --------------------------------------------------------------------------- # _engine.py D23 (L15) §4-5 — Fibonacci: üstelden polinoma # --------------------------------------------------------------------------- def fib_naive_counted(n): """Memoization'suz Fibonacci (L15 §4): f(i)=f(i-1)+f(i-2), f1=f2=1. Özyineleme ağacında alt problemler DEFALARCA çözülür → çağrı sayısı yaklaşık phi^n (üstel tanık). Döndürür: (f_n, toplam çağrı sayısı).""" calls = [0] def f(i): calls[0] += 1 if i <= 2: return 1 return f(i - 1) + f(i - 2) return f(n), calls[0] def fib_memo_counted(n): """Memoized Fibonacci (L15 §5 generic DP yapısı BİREBİR: memo kontrolü → taban → recurrence → sakla). Her alt problem EN FAZLA BİR KEZ çözülür → n alt problem × O(1) = O(n). Döndürür: (f_n, çözülen alt problem sayısı).""" memo = {} def f(i): if i in memo: # daha önce çözüldü mü? return memo[i] # tekrar etme, döndür if i <= 2: # taban durum result = 1 else: # recurrence ile özyinele result = f(i - 1) + f(i - 2) memo[i] = result # sakla return result val = f(n) return val, len(memo) def fib_bottom_up(n): """Bottom-up Fibonacci (L15 Egzersiz 1): taban → artan i döngüsü → orijinal. Memoized ile aynı değer, açık tablo.""" F = [0, 1, 1] for i in range(3, n + 1): F.append(F[i - 1] + F[i - 2]) return F[n] # --------------------------------------------------------------------------- # _engine.py D23 (L15) §9-10 — Bowling: suffix-DP + yerel kaba kuvvet # --------------------------------------------------------------------------- def bowling_bottom_up(v): """Bowling bottom-up DP (L15 §10 Notion pseudocode BİREBİR): B[n] = 0 taban; i azalan (topolojik sıra); B[i] = max(atla B[i+1], tek B[i+1]+v_i, çift B[i+2]+v_i*v_{i+1} — yalnız >= 2 pin varsa). O(n). Döndürür: B tablosu (B[0] = orijinal problem; figür tablo için tam).""" n = len(v) B = [0] * (n + 1) # B[n] = 0 taban durum for i in range(n - 1, -1, -1): # topolojik sıra: i azalan B[i] = max(B[i + 1], B[i + 1] + v[i]) if i + 1 < n: # çift yalnızca >= 2 pin varsa B[i] = max(B[i], B[i + 2] + v[i] * v[i + 1]) return B def bowling_memo_counted(v): """Top-down memoized bowling (L15 §9 SRTBOT: S = sonek B(i), R = yerel kaba kuvvet 3 seçenek, T = i azalan, B = B(n)=0, O = B(0)). Döndürür: (skor, çözülen alt problem sayısı) — n+1 tanığı.""" n = len(v) memo = {} def B(i): if i in memo: return memo[i] if i >= n: r = 0 else: r = max(B(i + 1), B(i + 1) + v[i]) if i + 1 < n: r = max(r, B(i + 2) + v[i] * v[i + 1]) memo[i] = r return r val = B(0) return val, len(memo) def bowling_plan(v): """Plan geri-kurma (figür izi): B tablosundan i=0'dan ileri yürü; her adımda kazanan seçeneği (çift > tek > atla önceliğiyle) etiketle. Döndürür: [(i, seçim, katkı)] — toplam katkı == B[0].""" B = bowling_bottom_up(v) n = len(v) plan, i = [], 0 while i < n: if i + 1 < n and B[i] == B[i + 2] + v[i] * v[i + 1]: plan.append((i, "çift", v[i] * v[i + 1])) i += 2 elif B[i] == B[i + 1] + v[i]: plan.append((i, "tek", v[i])) i += 1 else: plan.append((i, "atla", 0)) i += 1 return plan def bowling_brute_pairs(v): """Bağımsız tanık (FARKLI ayrıştırma — recurrence'sız, memo'suz): tüm örtüşmesiz bitişik-çift yerleşimlerini bitmask ile say; çiftlerce kapsanmayan pinlerde tek vuruş yalnız değeri pozitifse kârlı (max(0, v_j) — atlamak serbest). Üstel; yalnız küçük n testi.""" n = len(v) best = 0 # hepsi-atla = 0 her zaman geçerli for mask in range(1 << max(0, n - 1)): if mask & (mask << 1): # çift başlangıçları örtüşemez continue covered, score = 0, 0 for i in range(n - 1): if mask >> i & 1: score += v[i] * v[i + 1] covered |= (1 << i) | (1 << (i + 1)) for j in range(n): if not covered >> j & 1 and v[j] > 0: score += v[j] best = max(best, score) return best def build_bowling_example(): """L15 Egzersiz 2 dizisi: v = [1, 9, 9, 2, -5, -5]. Optimal 109 = tek(1) + çift(9*9 = 81) + tek(2) + çift((-5)*(-5) = 25) — negatif çiftin çarpımla POZİTİFLEŞMESİ örneğin can alıcı noktası.""" return [1, 9, 9, 2, -5, -5] # --------------------------------------------------------------------------- # _engine.py D16 (L11) — relax_edge + dag_relaxation + örnek (D23 §7 köprüsü) # --------------------------------------------------------------------------- def relax_edge(d, weight, u, v): """Kenar gevşetme (L11 §8): üçgen eşitsizliği ihlali varsa tahmini düşür.""" if d[u] + weight[(u, v)] < d[v]: d[v] = d[u] + weight[(u, v)] return True return False def dag_relaxation(adj, weight, s, topo_order): """DAG relaxation (L11 §10): d=inf, d[s]=0; topolojik sırada her u'nun çıkış komşularını gevşet. O(V+E). D23 §7'de dag_sp_memoized'ın ÇAPRAZ TANIĞI (aynı delta, farklı mekanizma).""" d = {v: INF for v in adj} d[s] = 0 for u in topo_order: for v in adj[u]: relax_edge(d, weight, u, v) return d def build_weighted_dag_example(): """L11 §10 çalışılan örneğine uyumlu DAG (Notion anlatı sayıları birebir): topolojik sıra a, b, e, f, g, h, d, c; kaynak e. Beklenen delta(e,.): e=0, f=3, g=5, h=6, d=3, c=8; a=b=+inf.""" adj = {"a": ["b"], "b": [], "e": ["f"], "f": ["h", "g"], "g": ["h", "d"], "h": [], "d": ["c"], "c": []} weight = {("a", "b"): 1, ("e", "f"): 3, ("f", "h"): 8, ("f", "g"): 2, ("g", "h"): 1, ("g", "d"): -2, ("d", "c"): 5} topo = ["a", "b", "e", "f", "g", "h", "d", "c"] return adj, weight, topo # --------------------------------------------------------------------------- # _engine.py D23 (L15) §7 — DAG-SP'yi DP olarak çöz (gelen-kenar min recurrence) # Memo kontrolü 'ziyaret edildi mi' rolünü oynar → DP içinde GİZLİ DFS. # --------------------------------------------------------------------------- def dag_sp_memoized(adj, weight, s): """DAG-SP'yi DP olarak çöz (L15 §7): delta(s,v) = min({delta(s,u) + w(u,v) : (u,v) GELEN kenar} ∪ {inf}); taban delta(s,s) = 0; generic memo yapısı. Memo kontrolü 'ziyaret edildi mi' rolünü oynar → DP içinde GİZLİ DFS + topolojik sıra. D16 dag_relaxation ile ÇAPRAZ TANIK (aynı delta). Döndürür: (delta sözlüğü, çözülen alt problem sayısı).""" rev = {v: [] for v in adj} for u in adj: for v in adj[u]: rev[v].append(u) memo = {} def delta(v): if v in memo: return memo[v] if v == s: # taban durum r = 0 else: r = min((delta(u) + weight[(u, v)] for u in rev[v]), default=INF) memo[v] = r return r out = {v: delta(v) for v in adj} return out, len(memo) ``` ## 1. Yeni Bölüm: Algoritmik Tasarım ve DP {#sec-1-yeni-bolum-dp} Şimdiye dek "ver(il)en algoritmaya indirge" yaptık. Artık **sıfırdan polinom-zaman algoritma** tasarlıyoruz. DP, özyinelemeli bir tasarım türüdür ve tümevarımla kanıt tekniğimizle çok iyi uyuşur. > *"Today we start a totally new section of the class."* — Demaine, 0:18 DP'nin temeli: alt problemleri tanımla, aralarındaki ilişkiyi (recurrence) yaz, çevrimsiz (DAG) bir alt-problem grafı kur, çözümleri sakla. Tüm dersi tek bir disiplinde toparlayan akronim **SRTBOT**'tur. ## 2. SRTBOT Çerçevesi {#sec-2-srtbot-cercevesi} Özyinelemeli algoritma tasarımının altı adımı (akronim **SRTBOT**): > *"SRTBOT... sub-problems, relations, topological order, base case, original problem, and time."* — Demaine, 2:33 - **S — Subproblems (alt problemler):** problemi polinom sayıda alt probleme böl. *En zor adım* — doğru alt problemi bulmak. - **R — Relations (ilişki):** bir alt problemi daha küçüklerinden çöz (recurrence). - **T — Topological order:** alt-problem grafı **DAG** olmalı (çevrim = sonsuz döngü); topolojik sıra. - **B — Base case (taban durum):** özyinelemenin durağı. - **O — Original problem:** çözmek istediğin (genelde alt problemlerden biri). - **T — Time (süre):** $\sum$ (alt problemler) $\times$ özyineleme-dışı iş. DP = SRTBOT + **memoization**. @fig-srtbot-pipeline altı adımı tek bir yatay zincirde toplar; her kutuda adımın adı, Türkçe tek-satır açıklaması ve altında bu dersin **bowling** örneğindeki karşılığı yer alır (S: sonek $B(i)$, R: $\max$(atla, tek, çift), ..., O: $B(0) = 109$ — bu sayı motordan canlı hesaplanır, T: $7$ alt problem $\times\, O(1) = O(n)$). ```{python} #| label: fig-srtbot-pipeline #| fig-cap: "SRTBOT — özyinelemeli tasarımın 6 adımı yatay zincir (Demaine L15 §2): S→R→T→B→O→T. Her kutuda adım adı (İngilizce) + Türkçe tek-satır açıklama + altında BOWLING karşılığı (amber). S: Subproblems — B(i) = i'den sona sonek max skoru. R: Relations — max(atla, tek v_i, çift v_i·v_{i+1}). T: Topological — i azalan (n → 0). B: Base — B(n)=B(6)=0. O: Original — B(0)=109 (motordan canlı). T: Time — 7 alt problem × O(1) = O(n). Amber oklar zinciri kutudan kutuya bağlar. Alt not: Demaine 2:33 — her DP çözümü bu altı adımın bir örneğidir. DP = SRTBOT + memoization. Veri MOTORDAN: bowling_bottom_up([1,9,9,2,−5,−5])[0] == 109 (assert); B(n)=B(6)=0 taban (assert); n=6 → T kutusu '7 alt problem × O(1) = O(n)'." #| fig-width: 12.0 #| fig-height: 5.5 # fig-srtbot-pipeline (L15 §2): SRTBOT 6 adımı yatay zincir + bowling karşılığı. # Veri MOTORDAN (build_bowling_example + bowling_bottom_up). networkx YOK. _sp_v = build_bowling_example() assert _sp_v == [1, 9, 9, 2, -5, -5], _sp_v _sp_B = bowling_bottom_up(_sp_v) _sp_B0 = _sp_B[0] _sp_n = len(_sp_v) assert _sp_B0 == 109, _sp_B0 # O kutusu motordan assert _sp_B[_sp_n] == 0, _sp_B[_sp_n] # B kutusu taban _sp_nsub = _sp_n + 1 # Her adım: (harf, başlık, Türkçe açıklama, bowling karşılığı) _sp_steps = [ ("S", "Subproblems", "Alt problemleri\ntanımla (sonek...)", "B(i) = i'den sona\nsonek max skoru"), ("R", "Relations", "Alt problemi küçük\nalt problemlere bağla", "max(atla, tek v_i,\nçift v_i·v_{i+1})"), ("T", "Topological", "Bağımlılık DAG'ını\ndöngüsüz sırala", "i azalan\n(n → 0)"), ("B", "Base", "Taban alt problemi\ndoğrudan çöz", f"B(n) = B({_sp_n}) = 0"), ("O", "Original", "Orijinali alt\nproblemden oku", f"B(0) = {_sp_B0}"), ("T", "Time", "alt problem sayısı ×\nalt problem-başı iş", f"{_sp_nsub} alt problem × O(1)\n= O(n)"), ] assert len(_sp_steps) == 6 assert f"= {_sp_B0}" in _sp_steps[4][3] assert f"B({_sp_n})" in _sp_steps[3][3] fig, ax = plt.subplots(figsize=(12, 5.5)) fig.patch.set_facecolor(COL_WHITE) _sp_box_w, _sp_box_h = 1.72, 2.55 _sp_gap = 0.42 _sp_y0 = 0.0 _sp_xstarts = [k * (_sp_box_w + _sp_gap) for k in range(6)] _sp_cy = _sp_y0 + _sp_box_h / 2 for k, (letter, title, desc, bowl) in enumerate(_sp_steps): x = _sp_xstarts[k] ax.add_patch(FancyBboxPatch( (x, _sp_y0), _sp_box_w, _sp_box_h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2)) cx = x + _sp_box_w / 2 badge_w = 0.52 ax.add_patch(FancyBboxPatch( (cx - badge_w / 2, _sp_y0 + _sp_box_h - 0.62), badge_w, 0.46, boxstyle="round,pad=0.02,rounding_size=0.12", fc=COL_ACCENT, ec=COL_AMBER_700, linewidth=1.6, zorder=4)) ax.text(cx, _sp_y0 + _sp_box_h - 0.39, letter, ha="center", va="center", fontsize=15, color=COL_WHITE, weight="bold", zorder=5) ax.text(cx, _sp_y0 + _sp_box_h - 0.92, title, ha="center", va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=4) ax.text(cx, _sp_y0 + _sp_box_h - 1.45, desc, ha="center", va="center", fontsize=7.8, color=COL_SLATE_500, zorder=4, linespacing=1.25) ax.plot([x + 0.14, x + _sp_box_w - 0.14], [_sp_y0 + 0.92, _sp_y0 + 0.92], color=COL_SLATE_400, linewidth=0.9, zorder=3) ax.text(cx, _sp_y0 + 0.80, "BOWLING", ha="center", va="center", fontsize=6.6, color=COL_AMBER_700, weight="bold", zorder=4) ax.text(cx, _sp_y0 + 0.40, bowl, ha="center", va="center", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=4, linespacing=1.2) for k in range(5): x_from = _sp_xstarts[k] + _sp_box_w x_to = _sp_xstarts[k + 1] ax.add_patch(FancyArrowPatch( (x_from + 0.02, _sp_cy), (x_to - 0.02, _sp_cy), arrowstyle="-|>", mutation_scale=18, color=COL_ACCENT, linewidth=2.4, zorder=5)) _sp_total_w = _sp_xstarts[-1] + _sp_box_w ax.text(_sp_total_w / 2, _sp_box_h + 0.78, "SRTBOT — özyinelemeli tasarımın 6 adımı (DP = SRTBOT + memoization)", ha="center", va="center", fontsize=13.5, color=COL_TEXT, weight="bold") ax.text(_sp_total_w / 2, _sp_y0 - 0.55, "Demaine 2:33 — her dinamik programlama çözümü bu altı adımın bir örneğidir", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic") ax.set_xlim(-0.35, _sp_total_w + 0.35) ax.set_ylim(_sp_y0 - 1.0, _sp_box_h + 1.25) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## 3. Örnek: Merge Sort SRTBOT ile {#sec-3-merge-sort-srtbot} Bildiğimiz merge sort'u SRTBOT'a oturtalım. **S:** $S(i, j) = A[i..j-1]$'i sırala. **O:** $S(0, n)$. **R:** $S(i, j) = \mathrm{merge}(S(i, m), S(m, j))$ ($m$ = orta). **T:** $j - i$ artan sırada. **B:** boş dizi. **Time:** $O(n \log n)$. (Merge sort memoization'dan *yararlanmaz* — alt diziler ayrık, tekrar yok. Ama çerçeve uygulanabilir; SRTBOT yalnızca DP'ye değil, her özyinelemeli tasarıma uyar.) ## 4. Fibonacci: Memoization'sız Üstel {#sec-4-fibonacci-ustel} Fibonacci: $f_n = f_{n-1} + f_{n-2}$, $f_1 = f_2 = 1$. **S:** $f(i) = i$. Fibonacci. **R:** $f(i) = f(i-1) + f(i-2)$. Doğal özyineleme — ama özyineleme ağacı çizilince $f(n-3), f(n-2)$ gibi alt problemler **defalarca** hesaplanır. $T(n) = T(n-1) + T(n-2) + 1 \to$ çözüm yaklaşık $\varphi^n$ (altın oran, üstel). Üstel = kötü; yalnız çok küçük $n$ çözülür. @fig-fib-tree-vs-memo bu dersin imza karşılaştırmasını verir: solda $f(6)$'nın tam özyineleme ağacı (memoization YOK) — motordan sayılan tekrarlar amber tonlarıyla işaretli ($f(3)$ tam 3 kez, $f(2)$ 5 kez, $f(1)$ 3 kez; ağaç $15$ düğüm = naif $15$ çağrı); sağda aynı alt problemler memoization ile **tek kopya** zincir-DAG ($f(1) \ldots f(6)$) ve büyük sayılar paneli ($n = 20$: naif $13.529$ çağrı, memo TAM $20$ alt problem; oran $\mathrm{calls}(20)/\mathrm{calls}(15) = 11{,}10 \approx \varphi^5 = 11{,}09$ — büyüme $\approx \varphi^n$ üstel). ```{python} #| label: fig-fib-tree-vs-memo #| fig-cap: "Fibonacci: özyineleme ağacından memoization'a — üstelden polinoma (Demaine L15 §4-5 İMZA). SOL: f(6) tam özyineleme ağacı (memoization YOK); tekrarlanan alt problemler aynı amber tonuyla — f(3) 3 kez, f(2) 5 kez, f(1) 3 kez (motordan sayıldı); ağaç 15 düğüm = naif 15 çağrı. SAĞ: aynı düğümler memo ile TEK KOPYA zincir-DAG (f(1)..f(6)); her f(i)'den f(i−1) ve f(i−2)'ye geri-ok (bir kez hesapla, sonra oku); büyük sayılar paneli — n=20: naif 13.529 çağrı vs memo TAM 20 alt problem; oran(20/15) = 11.10 ≈ phi^5 = 11.09 → büyüme yaklaşık phi^n ÜSTEL. Veri MOTORDAN (assert): fib_naive_counted(20) = (6765, 13529); fib_naive_counted(15)[1] = 1219; fib_naive_counted(6) = (8, 15); fib_memo_counted(20) = (6765, 20); ratio 13529/1219 = 11.10 ≈ phi^5 = 11.09; f(6) ağaç düğüm 15, f(3) tekrar 3." #| fig-width: 12.0 #| fig-height: 6.2 # fig-fib-tree-vs-memo (L15 §4-5 İMZA): özyineleme ağacı vs memo zincir-DAG. # Veri MOTORDAN (fib_naive_counted + fib_memo_counted). networkx YOK. _ft_val20, _ft_calls20 = fib_naive_counted(20) _ft_val15, _ft_calls15 = fib_naive_counted(15) _ft_val6, _ft_calls6 = fib_naive_counted(6) _ft_mval20, _ft_msub20 = fib_memo_counted(20) assert (_ft_val20, _ft_calls20) == (6765, 13529), (_ft_val20, _ft_calls20) assert _ft_calls15 == 1219, _ft_calls15 assert (_ft_val6, _ft_calls6) == (8, 15), (_ft_val6, _ft_calls6) assert (_ft_mval20, _ft_msub20) == (6765, 20), (_ft_mval20, _ft_msub20) _ft_ratio = _ft_calls20 / _ft_calls15 _ft_phi = (1 + math.sqrt(5)) / 2 _ft_phi5 = _ft_phi ** 5 assert abs(_ft_ratio - 11.10) < 0.01, _ft_ratio assert abs(_ft_phi5 - 11.09) < 0.01, _ft_phi5 # f(6) özyineleme ağacını kur (her düğüm motorla aynı kuralla) + say _ft_nodes = [] _ft_edges = [] _ft_ctr = [0] def _ft_build(i, depth): nid = _ft_ctr[0] _ft_ctr[0] += 1 _ft_nodes.append({"id": nid, "val": i, "depth": depth}) if i > 2: c1 = _ft_build(i - 1, depth + 1) c2 = _ft_build(i - 2, depth + 1) _ft_edges.append((nid, c1)) _ft_edges.append((nid, c2)) return nid _ft_build(6, 0) assert len(_ft_nodes) == _ft_calls6 == 15, len(_ft_nodes) _ft_counts = Counter(nd["val"] for nd in _ft_nodes) assert _ft_counts[3] == 3, _ft_counts assert _ft_counts[2] == 5 and _ft_counts[1] == 3, _ft_counts assert _ft_counts[4] == 2 and _ft_counts[5] == 1 and _ft_counts[6] == 1 assert sum(1 for nd in _ft_nodes if nd["val"] <= 2) == _ft_val6 == 8 _ft_children = {nd["id"]: [] for nd in _ft_nodes} for p, c in _ft_edges: _ft_children[p].append(c) _ft_byid = {nd["id"]: nd for nd in _ft_nodes} _ft_leafx = [0.0] def _ft_assign_x(nid): nd = _ft_byid[nid] ch = _ft_children[nid] if not ch: nd["x"] = _ft_leafx[0] _ft_leafx[0] += 1.0 return nd["x"] xs = [_ft_assign_x(c) for c in ch] nd["x"] = sum(xs) / len(xs) return nd["x"] _ft_assign_x(0) _ft_maxd = max(nd["depth"] for nd in _ft_nodes) def _ft_xy(nd): return nd["x"], (_ft_maxd - nd["depth"]) fig, (axL, axR) = plt.subplots(1, 2, figsize=(12, 6.2)) fig.patch.set_facecolor(COL_WHITE) _FT_REPEAT = { 3: (COL_AMBER_100, COL_ACCENT), 2: (COL_AMBER_100, COL_AMBER_600), 1: (COL_AMBER_100, COL_AMBER_700), } def _ft_box(ax, x, y, label, fc, ec, lw, w=0.62, h=0.42, fs=8.5): ax.add_patch(FancyBboxPatch( (x - w / 2, y - h / 2), w, h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=fc, ec=ec, linewidth=lw, zorder=4)) ax.text(x, y, label, ha="center", va="center", fontsize=fs, color=COL_TEXT, weight="bold", zorder=5) # SOL: özyineleme ağacı for p, c in _ft_edges: px, py = _ft_xy(_ft_byid[p]) cx, cy = _ft_xy(_ft_byid[c]) axL.plot([px, cx], [py, cy], color=COL_SLATE_400, linewidth=1.1, zorder=1) for nd in _ft_nodes: x, y = _ft_xy(nd) vv = nd["val"] if vv in _FT_REPEAT and _ft_counts[vv] > 1: fc, ec = _FT_REPEAT[vv] lw = 2.2 else: fc, ec = COL_BG, COL_PRIMARY lw = 1.5 _ft_box(axL, x, y, f"f({vv})", fc, ec, lw) axL.set_title("memoization YOK: aynı alt problem DEFALARCA", color=COL_TEXT, fontsize=12.5, weight="bold") _ft_ly = _ft_maxd + 0.55 axL.text(0.0, _ft_ly + 0.55, "f(6) ağacı: 15 düğüm (= naif 15 çağrı)", ha="left", va="center", fontsize=9.5, color=COL_TEXT, weight="bold") _ft_bx = 0.0 for vv, cnt, col in [(3, _ft_counts[3], COL_ACCENT), (2, _ft_counts[2], COL_AMBER_600), (1, _ft_counts[1], COL_AMBER_700)]: axL.add_patch(FancyBboxPatch( (_ft_bx, _ft_ly - 0.18), 0.55, 0.36, boxstyle="round,pad=0.02,rounding_size=0.05", fc=COL_AMBER_100, ec=col, linewidth=2.0, zorder=4)) axL.text(_ft_bx + 0.275, _ft_ly, f"f({vv})", ha="center", va="center", fontsize=8, color=COL_TEXT, weight="bold", zorder=5) axL.text(_ft_bx + 0.85, _ft_ly, f"× {cnt} kez", ha="left", va="center", fontsize=9, color=col, weight="bold") _ft_bx += 2.35 axL.set_xlim(-0.7, _ft_leafx[0] - 0.3) axL.set_ylim(-0.7, _ft_ly + 1.0) axL.axis("off") # SAĞ: memo zincir-DAG + büyük sayılar paneli _ft_chain_y = 3.6 _ft_xc = {} for k, vv in enumerate(range(1, 7)): _ft_xc[vv] = k * 1.55 for vv in range(1, 7): x = _ft_xc[vv] if vv in _FT_REPEAT: fc, ec = _FT_REPEAT[vv] lw = 2.2 else: fc, ec = COL_BG, COL_PRIMARY lw = 1.6 axR.add_patch(FancyBboxPatch( (x - 0.42, _ft_chain_y - 0.30), 0.84, 0.60, boxstyle="round,pad=0.02,rounding_size=0.07", fc=fc, ec=ec, linewidth=lw, zorder=4)) axR.text(x, _ft_chain_y, f"f({vv})", ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5) for vv in range(3, 7): x = _ft_xc[vv] axR.add_patch(FancyArrowPatch( (x - 0.42, _ft_chain_y - 0.16), (_ft_xc[vv - 1] + 0.42, _ft_chain_y - 0.16), arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700, linewidth=1.7, zorder=3, connectionstyle="arc3,rad=0.30")) axR.add_patch(FancyArrowPatch( (x - 0.30, _ft_chain_y + 0.30), (_ft_xc[vv - 2] + 0.30, _ft_chain_y + 0.30), arrowstyle="-|>", mutation_scale=12, color=COL_SLATE_500, linewidth=1.5, zorder=3, connectionstyle="arc3,rad=-0.45")) axR.text((_ft_xc[1] + _ft_xc[6]) / 2, _ft_chain_y + 1.45, "memoization: sakla + yeniden kullan → O(n)", ha="center", va="center", fontsize=12.5, color=COL_TEXT, weight="bold") axR.text((_ft_xc[1] + _ft_xc[6]) / 2, _ft_chain_y - 0.95, "her alt problem TEK KOPYA · oklar = bir kez hesapla, sonra oku", ha="center", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic") axR.add_patch(FancyBboxPatch( (-0.80, 0.05), _ft_xc[6] + 1.60, 1.50, boxstyle="round,pad=0.02,rounding_size=0.10", fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=2)) _ft_midx = (_ft_xc[1] + _ft_xc[6]) / 2 axR.text(_ft_midx, 1.12, f"n=20: naif {_ft_calls20:,} çağrı".replace(",", ".") + f" vs memo TAM {_ft_msub20} alt problem", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold") axR.text(_ft_midx, 0.52, f"oran(20/15) = {_ft_ratio:.2f} ≈ phi^5 = {_ft_phi5:.2f} → büyüme ≈ phi^n ÜSTEL", ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold") axR.set_xlim(-0.9, _ft_xc[6] + 0.9) axR.set_ylim(-0.2, _ft_chain_y + 1.95) axR.axis("off") fig.suptitle("Fibonacci: özyineleme ağacından memoization'a — üstelden polinoma", fontsize=13.5, color=COL_TEXT, weight="bold", y=0.99) fig.tight_layout(rect=(0, 0, 1, 0.97)) plt.show() ``` ## 5. Memoization: Üstelden Polinoma {#sec-5-memoization-polinom} Küçük bir kurnazlık her şeyi değiştirir: **memoization** — alt problem çözümlerini bir "memo" tablosuna yaz, gerektiğinde yeniden kullan. > *"remember and reuse solutions to sub-problems."* — Demaine, 14:14 Generic DP yapısı (her DP böyledir): ```{python} #| eval: false #| echo: true memo = {} def f(subproblem): if subproblem in memo: # daha once cozuldu mu? return memo[subproblem] # tekrar etme, dondur if base_case(subproblem): # taban durum result = base_value else: # recurrence ile ozyinele result = relation(f, subproblem) memo[subproblem] = result # sakla return result ``` Memo tablosu genelde bir **doğrudan-erişim dizisi** veya hash tablosu. Fibonacci için: her alt problem en fazla bir kez çözülür $\to$ **n alt problem $\times\, O(1)$** $= O(n)$. (Bir DFS'in "ziyaret edildi mi" kontrolünü oynar memo tablosu.) @fig-memo-structure bu generic iskeleti bir akış diyagramı olarak çizer: çağrı $\to$ "alt problem memoda mı?" (EVET $\to$ tabloyu döndür, tekrar hesaplama YOK) $\to$ "taban durum mu?" (EVET $\to$ taban değer; HAYIR $\to$ recurrence ile özyinele) $\to$ sonucu **sakla** $\to$ döndür. Sağ alt köşede, memonun bir DFS'in "ziyaret edildi mi" kontrolünü oynadığı not edilir. Motor tanığı: $\mathrm{bowling\_memo\_counted}([1,9,9,2,-5,-5]) = (109, 7)$ — $n+1 = 7$ alt problem, her biri tam bir kez. ```{python} #| label: fig-memo-structure #| fig-cap: "Generic DP iskeleti — f(alt problem) akış diyagramı (Demaine L15 §5 pseudocode birebir): memo kontrolü → taban → recurrence → sakla. SOL DİKEY ANA AKIŞ: çağrı → karar 'ap ∈ memo?' → (HAYIR) karar 'taban durum?' → (EVET) result = taban değer / (HAYIR) result = relation(f, ap), özyinele → her iki dal SAKLA kutusunda birleşir (memo[ap] = result, amber). SAĞ: memo HIT kısa-devresi — 'ap ∈ memo?' EVET → memo[ap] döndür, TEKRAR HESAPLAMA YOK (amber kalın) → return result. SAĞ ALT KÖŞE: memo = bir DFS'in ziyaret-edildi-mi kontrolü; DP içinde GİZLİ DFS çalışır (Demaine §7). ALT NOT (motor tanıklı): her alt problem EN FAZLA BİR KEZ çözülür → T = Σ (alt problem) × (özyineleme-dışı iş); tanık bowling([1,9,9,2,−5,−5]) → skor 109, 7 alt problem (n+1). Veri MOTORDAN (assert): bowling_memo_counted([1,9,9,2,−5,−5]) == (109, 7); fib_memo_counted(10) == (55, 10); ikisi de AYNI iskelet." #| fig-width: 10.5 #| fig-height: 6.0 # fig-memo-structure (L15 §5): generic DP iskeleti akış diyagramı. # Veri MOTORDAN (build_bowling_example + bowling_memo_counted + fib_memo_counted). _ms_v = build_bowling_example() assert _ms_v == [1, 9, 9, 2, -5, -5], _ms_v _ms_bval, _ms_bsub = bowling_memo_counted(_ms_v) assert (_ms_bval, _ms_bsub) == (109, 7), (_ms_bval, _ms_bsub) _ms_n = len(_ms_v) assert _ms_bsub == _ms_n + 1, _ms_bsub _ms_fval, _ms_fsub = fib_memo_counted(10) assert (_ms_fval, _ms_fsub) == (55, 10), (_ms_fval, _ms_fsub) fig, ax = plt.subplots(figsize=(10.5, 6)) ax.set_xlim(0, 10.5) ax.set_ylim(0, 6) ax.axis("off") fig.patch.set_facecolor(COL_WHITE) ax.set_facecolor(COL_WHITE) def _ms_proc(x, y, w, h, text, fc=COL_BG, ec=COL_PRIMARY, lw=1.8, tcol=COL_TEXT, fs=9.5, weight="bold"): ax.add_patch(FancyBboxPatch( (x - w / 2, y - h / 2), w, h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=fc, ec=ec, linewidth=lw, zorder=3)) ax.text(x, y, text, ha="center", va="center", fontsize=fs, color=tcol, weight=weight, zorder=4, linespacing=1.25) def _ms_diamond(x, y, w, h, text, fc=COL_BG, ec=COL_PRIMARY, lw=1.9, fs=9.5): pts = [(x, y + h / 2), (x + w / 2, y), (x, y - h / 2), (x - w / 2, y)] ax.add_patch(Polygon(pts, closed=True, fc=fc, ec=ec, linewidth=lw, zorder=3)) ax.text(x, y, text, ha="center", va="center", fontsize=fs, color=COL_TEXT, weight="bold", zorder=4, linespacing=1.2) def _ms_arrow(p0, p1, color=COL_PRIMARY, lw=1.8, rad=0.0, ls="-"): ax.add_patch(FancyArrowPatch( p0, p1, arrowstyle="-|>", mutation_scale=15, color=color, linewidth=lw, zorder=2, linestyle=ls, connectionstyle=f"arc3,rad={rad}")) def _ms_elabel(x, y, text, color=COL_SLATE_500, fs=8.5): ax.text(x, y, text, ha="center", va="center", fontsize=fs, color=color, weight="bold", zorder=5, bbox=dict(boxstyle="round,pad=0.12", fc=COL_WHITE, ec="none", alpha=0.85)) ax.text(5.25, 5.78, "Generic DP iskeleti — f(alt problem)", ha="center", va="center", fontsize=13, color=COL_TEXT, weight="bold") ax.text(5.25, 5.46, "memo kontrolü → taban → recurrence → sakla (L15 §5 — fib_memo & bowling_memo aynı)", ha="center", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic") _ms_xL = 2.6 _ms_proc(_ms_xL, 5.0, 2.6, 0.52, "f(alt problem ap)\nÇAĞRI", fs=9.5) _ms_diamond(_ms_xL, 4.05, 2.5, 0.95, "ap ∈ memo ?") _ms_arrow((_ms_xL, 5.0 - 0.26), (_ms_xL, 4.05 + 0.50)) _ms_diamond(_ms_xL, 2.6, 2.5, 0.95, "taban durum ?") _ms_arrow((_ms_xL, 4.05 - 0.48), (_ms_xL, 2.6 + 0.50)) _ms_elabel(_ms_xL - 0.42, 3.35, "HAYIR") _ms_xBase = 0.92 _ms_proc(_ms_xBase, 1.6, 1.55, 0.78, "result =\ntaban değer", fs=9) _ms_arrow((_ms_xL - 1.25, 2.6), (_ms_xBase + 0.20, 1.6 + 0.40), rad=-0.18) _ms_elabel(_ms_xL - 1.55, 2.20, "EVET") _ms_xRec = 3.30 _ms_proc(_ms_xRec, 1.6, 2.75, 0.78, "result =\nrelation(f, ap) — özyinele\n(alt problemleri çağır)", fs=8.4) _ms_arrow((_ms_xL, 2.6 - 0.48), (_ms_xRec - 0.55, 1.6 + 0.40), rad=-0.10) _ms_elabel(_ms_xL + 0.45, 2.12, "HAYIR") _ms_xStore = 2.1 _ms_proc(_ms_xStore, 0.55, 3.6, 0.6, "memo[ap] = result (SAKLA)", fc=COL_AMBER_100, ec=COL_AMBER_600, lw=2.0, tcol=COL_AMBER_700, fs=9.2) _ms_arrow((_ms_xBase, 1.6 - 0.40), (_ms_xStore - 1.3, 0.55 + 0.30), rad=0.15) _ms_arrow((_ms_xRec, 1.6 - 0.40), (_ms_xStore + 1.0, 0.55 + 0.30), rad=-0.12) _ms_xHit = 7.0 _ms_proc(_ms_xHit, 4.05, 3.7, 0.72, "memo[ap] döndür\n(TEKRAR HESAPLAMA YOK)", fc=COL_AMBER_100, ec=COL_ACCENT, lw=2.4, tcol=COL_AMBER_700, fs=9.5) _ms_arrow((_ms_xL + 1.25, 4.05), (_ms_xHit - 1.85, 4.05), color=COL_ACCENT, lw=2.4) _ms_elabel(_ms_xL + 2.4, 4.35, "EVET") _ms_xOut = 7.0 _ms_proc(_ms_xOut, 0.55, 1.7, 0.56, "return result", fs=9.5) _ms_arrow((_ms_xHit + 1.85, 4.05), (9.6, 4.05), color=COL_ACCENT, lw=2.0) _ms_arrow((9.6, 4.05), (9.6, 0.55), color=COL_ACCENT, lw=2.0) _ms_arrow((9.6, 0.55), (_ms_xOut + 0.85, 0.55), color=COL_ACCENT, lw=2.0) _ms_arrow((_ms_xStore + 1.85, 0.55), (_ms_xOut - 0.85, 0.55), lw=1.8) ax.add_patch(FancyBboxPatch( (5.95, 1.18), 4.35, 1.55, boxstyle="round,pad=0.05,rounding_size=0.08", fc=COL_BG, ec=COL_SLATE_400, linewidth=1.3, zorder=1)) ax.text(8.12, 2.50, "memo = bir DFS'in", ha="center", va="center", fontsize=9, color=COL_TEXT, weight="bold") ax.text(8.12, 2.22, "ziyaret-edildi-mi kontrolü", ha="center", va="center", fontsize=9, color=COL_TEXT, weight="bold") ax.text(8.12, 1.88, "DP içinde GİZLİ DFS çalışır", ha="center", va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold") ax.text(8.12, 1.42, "(Demaine §7)", ha="center", va="center", fontsize=8, color=COL_SLATE_500, style="italic") _ms_note = (f"Her alt problem EN FAZLA BİR KEZ çözülür → " f"T = Σ (alt problem) × (özyineleme-dışı iş) · " f"tanık: bowling([1,9,9,2,−5,−5]) → skor {_ms_bval}, {_ms_bsub} alt problem (n+1)") ax.text(5.25, 0.12, _ms_note, ha="center", va="center", fontsize=8.4, color=COL_SLATE_500, weight="bold", linespacing=1.3) plt.tight_layout() plt.show() ``` ## 6. Çalışma Süresi Formülü {#sec-6-calisma-suresi-formulu} Memoization'lı bir DP'nin süresi: **T = Σ (tüm alt problemler) × (recurrence'ın özyineleme-dışı işi)** > *"the time it takes is at most the sum over all sub problems of the relation time."* — Demaine, 23:07 Çünkü her alt problem **en fazla bir kez** çözülür; özyinelemeli çağrılar zaten toplama dahildir. (Fibonacci: $n \times O(1) = O(n)$.) **Word-RAM inceliği.** Fibonacci sayıları $n$-bit büyüklüğüne ulaşır; bir $w$-bit makine sözcüğünde toplama, $\lceil n/w \rceil$ sözcük işine mal olur. Dolayısıyla daha hassas süre $O(n + n^2/w)$'dir — ama bu da $w$ sabitken **polinom** kalır. Asimptotik tablo değişmez: memoization, Fibonacci'yi üstelden polinoma indirir. ## 7. DAG En Kısa Yol DP Olarak {#sec-7-dagsp-dp-olarak} DAG tek-kaynak en kısa yol (Ders 16) aslında bir DP'dir. **S:** $\delta(s, v)$ tüm $v$. **O:** hepsi. **R:** $$\delta(s, v) = \min\bigl(\{\delta(s, u) + w(u, v) : (u, v) \text{ gelen kenar}\} \cup \{\infty\}\bigr)$$ **T:** alt-problem grafı = $G$'nin kendisi $\to$ $G$'nin topolojik sırası. **B:** $\delta(s, s) = 0$. **Time:** $\sum$ (gelen kenar sayısı $+ 1$) $= O(V + E)$. İlginç: generic DP algoritması (memo-kontrol $\to$ özyinele) **alt-problem grafının tersinde bir DFS** çalıştırır; memo tablosu "ziyaret edildi mi" kontrolüdür. Yani DP, içinde DFS + topolojik sıra barındırır — "bedavaya". @fig-dagsp-as-dp bu denkliği Ders 16 örneğiyle kanıtlar: solda $8$ düğümlü DAG (topolojik sıra $a, b, e, f, g, h, d, c$; kaynak $e$), her düğümün üstünde motordan hesaplanan $\delta$ rozeti ($e{:}0, f{:}3, g{:}5, h{:}6, d{:}3, c{:}8$; $a = b = \infty$ soluk, erişilmez), ve $h$ için gelen-kenar min recurrence'ı vurgulu ($\delta(h) = \min(\delta(f)+8, \delta(g)+1) = \min(11, 6) = 6$; kazanan $g \to h$ amber, kaybeden $f \to h$ kesikli + "11" üstü çizik); sağda recurrence kutusu, SRTBOT eşleme tablosu (S/R/T/B/O/T) ve alt tanık rozeti — memoized çağrı sayısı $= 8 = V$ (gizli DFS tanığı), $\mathrm{dag\_sp\_memoized}$ ile $\mathrm{dag\_relaxation}$ aynı $\delta$'yı BİREBİR verir (D16 çapraz tanık). ```{python} #| label: fig-dagsp-as-dp #| fig-cap: "DAG en kısa yol = Dinamik Programlama (Demaine L15 §7; D16 köprüsü): delta(s,v) = min{ gelen δ(s,u)+w(u,v) } ∪ {∞}. SOL: D16 çizgesi (8 düğüm; topo sırası a,b,e,f,g,h,d,c soldan sağa); her düğümün üstünde δ değeri rozetli (e=0 amber kaynak; a,b=∞ soluk erişilemez). h için GELEN-kenar min recurrence vurgulu: δ(h) = min(δ(f)+8, δ(g)+1) = min(11, 6) = 6 — kazanan g→h amber kalın, kaybeden f→h kesikli + '11' üstü çizik. SAĞ: recurrence kutusu + SRTBOT eşleme tablosu (S alt problem / R ilişki / T topo sıra / B taban / O orijinal / T süre = O(V+E)) + alt rozet (memoized çağrı sayısı = 8 = V gizli DFS tanığı; dag_relaxation ile BİREBİR). Veri MOTORDAN (assert): topo == [a,b,e,f,g,h,d,c]; delta == {a:∞,b:∞,e:0,f:3,g:5,h:6,d:3,c:8}; nsub == 8 == V; delta == dag_relaxation (D16 çapraz tanık); δ(f)+8=11, δ(g)+1=6, δ(h)=min(11,6)=6." #| fig-width: 12.0 #| fig-height: 6.0 # fig-dagsp-as-dp (L15 §7; D16 köprüsü): DAG-SP = DP, gelen-kenar min recurrence. # Veri MOTORDAN (build_weighted_dag_example + dag_sp_memoized + dag_relaxation). _dd_adj, _dd_w, _dd_topo = build_weighted_dag_example() _dd_src = "e" _dd_delta, _dd_nsub = dag_sp_memoized(_dd_adj, _dd_w, _dd_src) _dd_relax = dag_relaxation(_dd_adj, _dd_w, _dd_src, _dd_topo) _dd_V = len(_dd_adj) assert _dd_topo == ["a", "b", "e", "f", "g", "h", "d", "c"], _dd_topo assert _dd_delta == {"a": INF, "b": INF, "e": 0, "f": 3, "g": 5, "h": 6, "d": 3, "c": 8}, _dd_delta assert _dd_nsub == 8 == _dd_V, (_dd_nsub, _dd_V) assert _dd_delta == _dd_relax, (_dd_delta, _dd_relax) assert _dd_delta["f"] + _dd_w[("f", "h")] == 11 assert _dd_delta["g"] + _dd_w[("g", "h")] == 6 assert _dd_delta["h"] == min(11, 6) == 6, _dd_delta["h"] _dd_match = (_dd_delta == _dd_relax) _DD_POS = { "e": (0.00, 1.00), "f": (1.15, 1.00), "g": (2.30, 1.00), "h": (3.45, 1.60), "d": (3.45, 0.40), "c": (4.60, 0.40), "a": (0.00, 2.50), "b": (1.15, 2.50), } _DD_EDGES = [ ("e", "f", 3, False), ("f", "h", 8, False), ("f", "g", 2, False), ("g", "h", 1, False), ("g", "d", -2, True), ("d", "c", 5, False), ("a", "b", 1, False), ] _DD_UNREACH = {"a", "b"} _DD_R = 0.27 _DD_WIN = ("g", "h") _DD_LOSE = ("f", "h") def _dd_draw_graph(ax, delta, source): for u, v, wt, neg in _DD_EDGES: ux, uy = _DD_POS[u] vx, vy = _DD_POS[v] dim = (u in _DD_UNREACH or v in _DD_UNREACH) is_win = (u, v) == _DD_WIN is_lose = (u, v) == _DD_LOSE if dim: ecol, lw, ls, al = COL_SLATE_400, 1.8, "solid", 0.45 elif is_win: ecol, lw, ls, al = COL_ACCENT, 3.2, "solid", 1.0 elif is_lose: ecol, lw, ls, al = COL_SLATE_400, 2.0, "dashed", 0.85 elif neg: ecol, lw, ls, al = COL_AMBER_600, 2.4, "solid", 1.0 else: ecol, lw, ls, al = COL_PRIMARY, 2.0, "solid", 1.0 ax.add_patch(FancyArrowPatch( (ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15, color=ecol, linewidth=lw, linestyle=ls, shrinkA=_DD_R * 76, shrinkB=_DD_R * 76, alpha=al, zorder=3)) mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5 if is_win: bg, ec, tcol, blw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.2 elif neg: bg, ec, tcol, blw = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700, 1.7 else: bg, ec, tcol, blw = COL_WHITE, COL_SLATE_400, COL_TEXT, 1.1 ax.add_patch(FancyBboxPatch( (mx - 0.16, my - 0.135), 0.32, 0.27, boxstyle="round,pad=0.01,rounding_size=0.06", fc=bg, ec=ec, linewidth=blw, alpha=0.45 if dim else 1.0, zorder=6)) ax.text(mx, my, str(wt), ha="center", va="center", fontsize=8.5 if not (neg or is_win) else 9.5, color=tcol, weight="bold", alpha=0.5 if dim else 1.0, zorder=7) for v, (x, y) in _DD_POS.items(): dim = (v in _DD_UNREACH) is_src = (v == source) is_h = (v == "h") fc = COL_AMBER_100 if (is_src or is_h) else COL_BG ec = COL_ACCENT if (is_src or is_h) else (COL_SLATE_400 if dim else COL_PRIMARY) lw = 3.0 if is_src else (2.6 if is_h else (1.4 if dim else 2.0)) ax.add_patch(Circle((x, y), _DD_R, facecolor=fc, edgecolor=ec, linewidth=lw, alpha=0.5 if dim else 1.0, zorder=5)) tcol = COL_AMBER_700 if is_src else (COL_SLATE_400 if dim else COL_TEXT) ax.text(x, y, v, ha="center", va="center", fontsize=13, color=tcol, weight="bold", alpha=0.6 if dim else 1.0, zorder=6) dv = delta[v] dtxt = "∞" if dv == INF else str(dv) if is_src or is_h: rbg, rec, rtc = COL_AMBER_100, COL_ACCENT, COL_AMBER_700 elif dim: rbg, rec, rtc = COL_WHITE, COL_SLATE_400, COL_SLATE_400 else: rbg, rec, rtc = COL_BG, COL_PRIMARY, COL_TEXT by = y + _DD_R + 0.20 ax.add_patch(FancyBboxPatch( (x - 0.205, by - 0.135), 0.41, 0.27, boxstyle="round,pad=0.01,rounding_size=0.08", fc=rbg, ec=rec, linewidth=2.2 if (is_src or is_h) else 1.4, alpha=0.5 if dim else 1.0, zorder=7)) ax.text(x, by, f"δ={dtxt}", ha="center", va="center", fontsize=9, color=rtc, weight="bold", alpha=0.6 if dim else 1.0, zorder=8) sx, sy = _DD_POS[source] ax.text(sx - _DD_R - 0.08, sy - 0.42, "kaynak", ha="center", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6) ax.text(0.57, 2.95, "a, b — e'den erişilemez (δ = ∞)", ha="center", va="center", fontsize=8, color=COL_SLATE_400, style="italic", zorder=6) bx, by0 = 1.55, -0.62 ax.add_patch(FancyBboxPatch( (bx, by0), 3.30, 0.78, boxstyle="round,pad=0.04,rounding_size=0.08", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=4)) ax.text(bx + 0.16, by0 + 0.55, "δ(h) = min( δ(f)+8 , δ(g)+1 )", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) ymin = by0 + 0.22 ax.text(bx + 0.16, ymin, "= min(", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) x11 = bx + 1.18 ax.text(x11, ymin, "11", ha="center", va="center", fontsize=9.5, color=COL_SLATE_500, weight="bold", family="monospace", zorder=6) ax.plot([x11 - 0.12, x11 + 0.12], [ymin, ymin], color=COL_AMBER_700, linewidth=1.6, zorder=7) ax.text(bx + 1.42, ymin, ",", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) ax.text(bx + 1.66, ymin, "6", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) ax.text(bx + 1.84, ymin, ") = 6", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) ax.text(bx + 2.52, ymin + 0.30, "(g→h kazanır)", ha="left", va="center", fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=6) ax.set_title("DAG en kısa yol = GELEN kenarların min'i\n" "(topo sırası: a, b, e, f, g, h, d, c)", color=COL_PRIMARY, fontsize=11, weight="bold") ax.set_xlim(-0.70, 5.30) ax.set_ylim(-0.95, 3.40) ax.set_aspect("equal") ax.axis("off") def _dd_draw_srtbot(ax, delta, nsub, V, match): ax.set_xlim(0, 10) ax.set_ylim(0, 10) ax.axis("off") ax.add_patch(FancyBboxPatch( (0.25, 8.30), 9.5, 1.45, boxstyle="round,pad=0.06,rounding_size=0.10", fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2)) ax.text(5.0, 9.42, "Yineleme (recurrence)", ha="center", va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=4) ax.text(5.0, 8.92, "δ(s, v) = min{ δ(s, u) + w(u, v) : (u, v) gelen } ∪ {∞}", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=4) ax.text(5.0, 8.52, "taban: δ(s, s) = 0", ha="center", va="center", fontsize=9, color=COL_TEXT, style="italic", zorder=4) rows = [ ("S", "alt problem", "δ(s, v) — her v için kaynaktan en kısa mesafe"), ("R", "ilişki", "δ(s,v) = min{ δ(s,u)+w(u,v) : gelen (u,v) } ∪ {∞}"), ("T", "topo. sıra", "alt-problem grafı G'nin KENDİSİ (zaten DAG)"), ("B", "taban", "δ(s, s) = 0 (erişilemez → ∞)"), ("O", "orijinal", "δ(s, v) tüm v ∈ V (kaynak e)"), ("T", "süre", "Σ_v (gelen derece + 1) = O(V + E)"), ] top = 7.75 rh = 1.02 x_let, x_name, x_desc = 0.45, 1.55, 3.55 for i, (letter, name, desc) in enumerate(rows): y = top - i * rh is_time = (letter == "T" and "süre" in name) is_topo = (letter == "T" and "topo" in name) if is_time: rbg, rec = COL_AMBER_100, COL_ACCENT elif is_topo: rbg, rec = COL_AMBER_100, COL_AMBER_600 else: rbg, rec = COL_WHITE, COL_SLATE_400 ax.add_patch(FancyBboxPatch( (0.25, y - rh * 0.46), 9.5, rh * 0.90, boxstyle="round,pad=0.02,rounding_size=0.05", fc=rbg, ec=rec, linewidth=1.8 if (is_time or is_topo) else 1.0, zorder=2)) ax.add_patch(Circle((x_let, y), 0.27, facecolor=COL_PRIMARY if not is_time else COL_ACCENT, edgecolor="none", zorder=3)) ax.text(x_let, y, letter, ha="center", va="center", fontsize=11.5, color=COL_WHITE, weight="bold", zorder=4) ax.text(x_name, y, name, ha="left", va="center", fontsize=9, color=COL_TEXT, weight="bold", zorder=4) ax.text(x_desc, y, desc, ha="left", va="center", fontsize=8.6, color=COL_AMBER_700 if (is_time or is_topo) else COL_TEXT, zorder=4) by = 1.20 ax.add_patch(FancyBboxPatch( (0.25, by - 0.62), 9.5, 1.22, boxstyle="round,pad=0.05,rounding_size=0.10", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2)) ax.text(5.0, by + 0.36, f"★ memoized çağrı sayısı = {nsub} = V (gizli DFS + topolojik sıra tanığı)", ha="center", va="center", fontsize=9.8, color=COL_AMBER_700, weight="bold", zorder=4) chk = "✓ BİREBİR" if match else "✗ FARK" ax.text(5.0, -0.04, f"dag_sp_memoized δ = dag_relaxation δ → {chk} (D16 çapraz tanık)", ha="center", va="center", fontsize=9.2, color=COL_TEXT, weight="bold", zorder=4) ax.set_title("SRTBOT eşlemesi — DP olarak DAG-SP", color=COL_PRIMARY, fontsize=11, weight="bold") fig, (axL, axR) = plt.subplots(1, 2, figsize=(12.0, 6.0), gridspec_kw={"width_ratios": [1.05, 1.0]}) fig.patch.set_facecolor(COL_WHITE) _dd_draw_graph(axL, _dd_delta, _dd_src) _dd_draw_srtbot(axR, _dd_delta, _dd_nsub, _dd_V, _dd_match) fig.suptitle( "DAG en kısa yol = Dinamik Programlama — δ(s,v) = min{ gelen δ(s,u)+w(u,v) } ∪ {∞} (L15 §7; D16 köprüsü)", color=COL_TEXT, fontsize=12.5, weight="bold", y=0.99) plt.tight_layout(rect=(0, 0, 1, 0.95)) plt.show() ``` ::: {.callout-tip title="Builder Notu — DAG = build sistemi"} Alt-problem grafının çevrimsiz (DAG) olması bir tesadüf değil, bir zorunluluktur: çevrim olsaydı bir alt problem kendini beklerdi (sonsuz döngü). Bu yapı gerçek mühendislikte her gün karşına çıkar — **build sistemleri** (Make, Bazel, webpack), paket bağımlılık çözücüler, elektronik tablo hücre yeniden-hesaplaması ve görev zamanlayıcıları hep bir bağımlılık DAG'ını topolojik sırada işler. Memoization'lı DP'nin "her düğümü bir kez çöz, sonucu sakla" mantığı, Make'in "değişmemiş hedefi yeniden derleme" mantığının ta kendisidir; ikisi de aynı gizli DFS'i koşturur. ::: ## 8. Alt-Problem Tasarım Aracı: Prefix/Suffix/Substring {#sec-8-altproblem-araci} Girdi bir **dizi** ise, doğal alt problem adayları: > *"if your input is a sequence, here are some good sub-problems... prefixes... suffixes... substrings."* — Demaine, 43:03 - **Önekler (prefixes):** $x[:i]$, her $i$ için — **$\Theta(n)$** tane. - **Sonekler (suffixes):** $x[i:]$, her $i$ için — **$\Theta(n)$** tane. - **Alt diziler (substrings):** $x[i:j]$ — **$\Theta(n^2)$** tane. **Alt-dizilim (subsequence) KULLANMA** — $2^n$ tane (üstel). Önek/sonek genelde denktir ve yeterlidir; yetmezse substring'e geç. @fig-subproblem-kinds bu dört adayı $n = 6$ örnek dizide ("ABCDEF") yan yana sıralar: önek satırı soldan büyür (A, ABC, ABCDEF), sonek sağdan büyür (F, DEF, ABCDEF) — ikisi de yeşil "$\Theta(n)$ — 7 tane" rozetiyle; substring ortadan bir aralık seçer (CD, BCDE, ...) amber "$\Theta(n^2)$ — 28 tane"; subsequence atlamalı seçim (A_C_E, ...) kırmızı üstü-çizik "$2^n = 64$ — YASAK". Sayılar figür içinde gerçek enumerasyondan hesaplanır ($n+1 / n+1 / (n+1)(n+2)/2 / 2^n$). ```{python} #| label: fig-subproblem-kinds #| fig-cap: "Alt-problem tasarım aracı: dizi girdide hangi alt problemi seçeyim? (Demaine L15 §8, 43:03; n=6 'ABCDEF'). 4 satır: PREFIX (önekler x[:i]) soldan büyüyen A / ABC / ABCDEF + yeşil 'Θ(n) — 7 tane'; SUFFIX (sonekler x[i:]) sağdan büyüyen F / DEF / ABCDEF + yeşil 'Θ(n) — 7 tane'; SUBSTRING (alt diziler x[i:j]) ortadan CD / BCDE / D + amber 'Θ(n²) — 28 tane'; SUBSEQUENCE (alt dizilim, atlamalı) A C E / B D F / A F üstü-çizik kırmızı + '2ⁿ = 64 — YASAK'. ALT NOT: dizi girdide önce prefix/suffix dene → yetmezse substring → subsequence ASLA (Demaine 43:03); n+1 / n+1 / (n+1)(n+2)/2 polinom çözülebilir, 2ⁿ üstel DP tablosu patlar. Veri figür içinde GERÇEK enumerasyondan (assert): prefix = n+1 = 7; suffix = n+1 = 7; substring = (n+1)(n+2)/2 = 28; subsequence = 2ⁿ = 64; sıralama prefix=suffix < substring < subsequence." #| fig-width: 11.0 #| fig-height: 6.5 # fig-subproblem-kinds (L15 §8): prefix/suffix/substring/subsequence sayıları. # Sayılar GERÇEK enumerasyondan (formül DEĞİL) + formülle ASSERT. networkx YOK. _SK_GOOD = "#cfe8da" _SK_GOOD_EC = "#3f7d5e" _SK_BAD = "#fde2e0" _SK_BAD_EC = "#b91c1c" def _sk_counts(seq): n = len(seq) prefixes = [seq[:i] for i in range(n + 1)] suffixes = [seq[i:] for i in range(n + 1)] substrings = [seq[i:j] for i in range(n + 1) for j in range(i, n + 1)] return {"prefix": len(prefixes), "suffix": len(suffixes), "substring": len(substrings), "subsequence": 2 ** n, "n": n} def _sk_seq(ax, x0, y, chars, selected=None, ec_sel=COL_ACCENT, fc_sel=COL_AMBER_100, bracket=None, gaps=False, strike=False, cell_w=0.46, cell_h=0.46): selected = set(selected or []) for k, ch in enumerate(chars): x = x0 + k * cell_w hot = k in selected if hot: fc, ec, lw = fc_sel, ec_sel, 2.2 elif gaps: fc, ec, lw = COL_WHITE, COL_SLATE_400, 1.1 else: fc, ec, lw = COL_BG, COL_PRIMARY, 1.4 ax.add_patch(FancyBboxPatch( (x, y), cell_w * 0.9, cell_h * 0.9, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=3)) cx, cy = x + cell_w * 0.45, y + cell_h * 0.45 tcol = COL_TEXT if (hot or not gaps) else COL_SLATE_400 ax.text(cx, cy, ch, ha="center", va="center", fontsize=9.5, color=tcol, weight="bold", zorder=5) if bracket is not None: i, j = bracket xl = x0 + i * cell_w - cell_w * 0.05 xr = x0 + j * cell_w + cell_w * 0.9 + cell_w * 0.05 yb = y - cell_h * 0.22 ax.plot([xl, xl, xr, xr], [yb + cell_h * 0.12, yb, yb, yb + cell_h * 0.12], color=ec_sel, linewidth=1.8, zorder=6, solid_capstyle="round") if strike: xl = x0 - cell_w * 0.1 xr = x0 + len(chars) * cell_w yc = y + cell_h * 0.45 ax.plot([xl, xr], [yc, yc], color=_SK_BAD_EC, linewidth=2.6, zorder=8, solid_capstyle="round") def _sk_badge(ax, x, y, text, fc, ec, tcol, w=2.55, h=0.50, fontsize=9.5): ax.add_patch(FancyBboxPatch( (x, y - h / 2), w, h, boxstyle="round,pad=0.02,rounding_size=0.20", fc=fc, ec=ec, linewidth=2.2, zorder=5)) ax.text(x + w / 2, y, text, ha="center", va="center", fontsize=fontsize, color=tcol, weight="bold", zorder=6) _sk_seq_str = "ABCDEF" _sk_c = _sk_counts(_sk_seq_str) _sk_n = _sk_c["n"] assert _sk_n == 6 assert _sk_c["prefix"] == _sk_n + 1 == 7, _sk_c["prefix"] assert _sk_c["suffix"] == _sk_n + 1 == 7, _sk_c["suffix"] assert _sk_c["substring"] == (_sk_n + 1) * (_sk_n + 2) // 2 == 28, _sk_c["substring"] assert _sk_c["subsequence"] == 2 ** _sk_n == 64, _sk_c["subsequence"] assert _sk_c["prefix"] == _sk_c["suffix"] < _sk_c["substring"] < _sk_c["subsequence"] _sk_chars = list(_sk_seq_str) fig, ax = plt.subplots(figsize=(11.0, 6.5)) fig.patch.set_facecolor(COL_WHITE) _sk_row_y = [7.2, 5.4, 3.6, 1.8] _sk_ex_x = [2.3, 5.0, 7.7] _sk_label_x = 0.05 _sk_badge_x = 9.9 def _sk_row_label(y, name, sub): ax.text(_sk_label_x, y + 0.45, name, ha="left", va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold", zorder=6) ax.text(_sk_label_x, y + 0.10, sub, ha="left", va="center", fontsize=8.3, color=COL_SLATE_500, style="italic", zorder=6) # Satır 1 — PREFIX y = _sk_row_y[0] _sk_row_label(y, "prefix", "önekler x[:i]") for col, k in enumerate((0, 2, 5)): _sk_seq(ax, _sk_ex_x[col], y, _sk_chars, selected=set(range(k + 1)), bracket=(0, k)) ax.text(_sk_ex_x[col] + (k + 1) * 0.46 * 0.5, y - 0.42, _sk_seq_str[:k + 1], ha="center", va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold", zorder=6) _sk_badge(ax, _sk_badge_x, y + 0.23, f"Θ(n) — {_sk_c['prefix']} tane", _SK_GOOD, _SK_GOOD_EC, _SK_GOOD_EC) # Satır 2 — SUFFIX y = _sk_row_y[1] _sk_row_label(y, "suffix", "sonekler x[i:]") for col, i in enumerate((5, 3, 0)): _sk_seq(ax, _sk_ex_x[col], y, _sk_chars, selected=set(range(i, 6)), bracket=(i, 5)) ax.text(_sk_ex_x[col] + (i + 6) * 0.46 * 0.5, y - 0.42, _sk_seq_str[i:], ha="center", va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold", zorder=6) _sk_badge(ax, _sk_badge_x, y + 0.23, f"Θ(n) — {_sk_c['suffix']} tane", _SK_GOOD, _SK_GOOD_EC, _SK_GOOD_EC) # Satır 3 — SUBSTRING y = _sk_row_y[2] _sk_row_label(y, "substring", "alt diziler x[i:j]") for col, (i, j) in enumerate([(2, 3), (1, 4), (3, 3)]): _sk_seq(ax, _sk_ex_x[col], y, _sk_chars, selected=set(range(i, j + 1)), bracket=(i, j)) ax.text(_sk_ex_x[col] + (i + j + 1) * 0.46 * 0.5, y - 0.42, _sk_seq_str[i:j + 1], ha="center", va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold", zorder=6) _sk_badge(ax, _sk_badge_x, y + 0.23, f"Θ(n²) — {_sk_c['substring']} tane", COL_AMBER_100, COL_ACCENT, COL_AMBER_700) # Satır 4 — SUBSEQUENCE y = _sk_row_y[3] _sk_row_label(y, "subsequence", "alt dizilim (atlamalı)") for col, sel in enumerate([{0, 2, 4}, {1, 3, 5}, {0, 5}]): _sk_seq(ax, _sk_ex_x[col], y, _sk_chars, selected=sel, gaps=True, strike=True, ec_sel=_SK_BAD_EC, fc_sel=_SK_BAD) picked = "".join(_sk_seq_str[k] for k in sorted(sel)) ax.text(_sk_ex_x[col] + 6 * 0.46 * 0.5, y - 0.42, picked, ha="center", va="center", fontsize=7.8, color=_SK_BAD_EC, weight="bold", zorder=6) _sk_badge(ax, _sk_badge_x, y + 0.23, f"2ⁿ = {_sk_c['subsequence']} — YASAK", _SK_BAD, _SK_BAD_EC, _SK_BAD_EC, w=2.75) _sk_strip_y = 0.65 ax.add_patch(FancyBboxPatch( (_sk_label_x - 0.05, _sk_strip_y - 0.55), _sk_badge_x + 2.75 - _sk_label_x + 0.10, 0.92, boxstyle="round,pad=0.03,rounding_size=0.10", fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=1)) ax.text((_sk_label_x + _sk_badge_x + 2.75) * 0.5, _sk_strip_y + 0.10, "Dizi girdide önce prefix/suffix dene → yetmezse substring " "→ subsequence ASLA (Demaine 43:03)", ha="center", va="center", fontsize=10.0, color=COL_AMBER_700, weight="bold", zorder=4) ax.text((_sk_label_x + _sk_badge_x + 2.75) * 0.5, _sk_strip_y - 0.30, "n+1 / n+1 / (n+1)(n+2)/2 polinom — çözülebilir · 2ⁿ üstel — " "DP tablosu patlar, kullanma", ha="center", va="center", fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=4) fig.suptitle( 'Alt-problem tasarım aracı: dizi girdide hangi alt problemi seçeyim? ' '(n = 6, "ABCDEF")', color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975) ax.set_xlim(_sk_label_x - 0.3, _sk_badge_x + 2.75 + 0.3) ax.set_ylim(_sk_strip_y - 0.85, _sk_row_y[0] + 1.05) ax.axis("off") plt.tight_layout() plt.show() ``` ## 9. Bowling Problemi: SRTBOT Uygulaması {#sec-9-bowling-srtbot} **Problem.** $n$ pin, pin $i$ değeri $v_i$. Bir pin vurursan $v_i$ puan; bitişik iki pini ($i, i+1$) birlikte vurursan $v_i \cdot v_{i+1}$ puan. Skoru maksimize et (pinleri atlamak serbest). **Çalışılan Örnek — suffix DP.** **S:** $B(i) = $ pin $i \ldots n-1$ ile elde edilebilecek maksimum skor. **O:** $B(0)$. **R:** ilk pin $i$'ye üç şey yapabilirim — atla, tek vur, ya da $i+1$ ile çiftle: $$B(i) = \max\bigl(B(i+1),\; B(i+1) + v_i,\; B(i+2) + v_i \cdot v_{i+1}\bigr)$$ **T:** $i$ azalan (for $i = n-1 \ldots 0$). **B:** $B(n) = 0$. **Time:** $n$ alt problem $\times\, O(1) = $ **$O(n)$**. ## 10. Bottom-Up DP ve Yerel Kaba Kuvvet {#sec-10-bottomup-yerel-kabakuvvet} SRTBOT'u doğrudan bir **for-döngüsü** algoritmasına çevirebiliriz (bottom-up): taban durumu yaz, topolojik sırada döngü kur, recurrence'ı uygula, sonunda orijinali döndür. ```{python} #| eval: false #| echo: true def bowling(v, n): B = [0] * (n + 1) # B[n] = 0 taban durum for i in range(n - 1, -1, -1): # topolojik sira: i azalan B[i] = max(B[i + 1], B[i + 1] + v[i]) if i + 1 < n: # cift yalnizca >= 2 pin varsa B[i] = max(B[i], B[i + 2] + v[i] * v[i + 1]) return B[0] # orijinal problem ``` Bu, **yerel kaba kuvvettir (local brute force)**: pin $i$ için *tüm* seçenekleri (3 tane) dene, en iyisini al. Normalde $3 \times 3 \times \ldots$ üstel olurdu; ama alt problemleri yeniden kullandığımızdan **doğrusal**. > *"dp is essentially an idea of using local brute force."* — Demaine, 54:47 DP sezgisi: "**çözümün hangi özelliğini bilsem işim biterdi?**" Bu özelliğin seçenek sayısı polinomsa, polinom bir DP elde edersin. (Sonek $\to$ ilk öğeyi düşün; önek $\to$ son öğe; substring $\to$ ortadaki öğe.) > *"identify some feature of the solution that if we knew that feature we would be done."* — Demaine, 56:00 @fig-bowling-table bu dersin ikinci imza figürüdür ve bowling'i uçtan uca çözer: üstte pin dizisi $v = [1, 9, 9, 2, -5, -5]$ ve optimal plan izi (tek vuruşlar halka, çift kemerler amber yay; "$(-5) \cdot (-5) \to$ POZİTİFLEŞİR" rozeti) — toplam $1 + 81 + 2 + 25 = 109$; altta suffix-DP tablosu $B$ doldurma sırası $i = 6 \to 0$ (topolojik sıra, sağdan sola amber ok), her hücrede $B[i]$ değeri ve kazanan seçenek. Motor bunu üç bağımsız yoldan teyit eder: $\mathrm{bowling\_bottom\_up}(v) = [109, 108, 43, 27, 25, 0, 0]$, $\mathrm{bowling\_brute\_pairs}(v) = 109$ (bitmask-çift bağımsız tanık), $\mathrm{bowling\_memo\_counted}(v) = (109, 7)$ ($n+1$ alt problem). ```{python} #| label: fig-bowling-table #| fig-cap: "Bowling suffix-DP — pin dizisi + plan izi + B tablosu (Demaine L15 §9-10 İMZA): B[n]=0 taban; i azalan topolojik sıra; her pin 3 seçenek (atla / tek vuruş +v_i / çift kemer v_i·v_{i+1}); negatif çift çarpımla pozitifleşir. ÜST PANEL: pin dizisi v=[1,9,9,2,−5,−5] (negatifler slate dolgu); optimal plan izi — tek vuruşlar halka (✓ +1, +2), çift kemerler amber yay (9·9=81, (−5)·(−5)=25) + '(−5)·(−5) → POZİTİFLEŞİR' rozeti; sağ toplam kutusu 1 + 81 + 2 + 25 = 109. ALT PANEL: suffix-DP tablosu B 7 hücre i=0..6, doldurma yönü i=6→0 (topolojik sıra, sağdan sola amber ok); her hücre B[i] değeri + kazanan seçenek (← çift/tek/atla) + formül; B[0]=109 CEVAP amber vurgu, B[6]=0 taban (boş sonek). ALT NOT: her pin 3 seçenek, alt problemler YENİDEN KULLANILIR → 3ⁿ kaba kuvvet yerine O(n); yerel kaba kuvvet sabit ≤3 seçenek/pin (Demaine 54:47). Veri MOTORDAN (assert): v=[1,9,9,2,−5,−5]; bowling_bottom_up(v)=[109,108,43,27,25,0,0]; plan=[(0,tek,1),(1,çift,81),(3,tek,2),(4,çift,25)]; bowling_brute_pairs(v)=109 (bağımsız); bowling_memo_counted(v)=(109,7); plan toplam=B[0]=109." #| fig-width: 11.5 #| fig-height: 7.0 # fig-bowling-table (L15 §9-10 İMZA): pin dizisi + plan izi + B suffix-DP tablosu. # Veri MOTORDAN (build_bowling_example + bowling_bottom_up + bowling_plan + # bowling_brute_pairs + bowling_memo_counted). networkx YOK. _bt_v = build_bowling_example() assert _bt_v == [1, 9, 9, 2, -5, -5], _bt_v _bt_B = bowling_bottom_up(_bt_v) assert _bt_B == [109, 108, 43, 27, 25, 0, 0], _bt_B _bt_plan = bowling_plan(_bt_v) assert _bt_plan == [(0, "tek", 1), (1, "çift", 81), (3, "tek", 2), (4, "çift", 25)], _bt_plan _bt_brute = bowling_brute_pairs(_bt_v) assert _bt_brute == 109, _bt_brute _bt_mval, _bt_msub = bowling_memo_counted(_bt_v) assert (_bt_mval, _bt_msub) == (109, 7), (_bt_mval, _bt_msub) _bt_n = len(_bt_v) assert len(_bt_B) == _bt_n + 1 _bt_plan_total = sum(c for (_, _, c) in _bt_plan) assert _bt_plan_total == _bt_B[0] == 109 _bt_winners = {} for i in range(_bt_n): skip = _bt_B[i + 1] one = _bt_B[i + 1] + _bt_v[i] two = (_bt_B[i + 2] + _bt_v[i] * _bt_v[i + 1]) if i + 1 < _bt_n else None if two is not None and _bt_B[i] == two: _bt_winners[i] = ("çift", f"B[{i+2}]+{_bt_v[i]}·{_bt_v[i+1]}", two) elif _bt_B[i] == one: _bt_winners[i] = ("tek", f"B[{i+1}]+{_bt_v[i]}", one) else: _bt_winners[i] = ("atla", f"B[{i+1}]", skip) _bt_winners[_bt_n] = ("taban", "0", 0) assert _bt_winners[0] == ("tek", "B[1]+1", 109) assert _bt_winners[1] == ("çift", "B[3]+9·9", 108) assert _bt_winners[4] == ("çift", "B[6]+-5·-5", 25) fig, (axU, axL) = plt.subplots( 2, 1, figsize=(11.5, 7), gridspec_kw={"height_ratios": [1.0, 1.15], "hspace": 0.18}) fig.patch.set_facecolor(COL_WHITE) for ax in (axU, axL): ax.set_facecolor(COL_WHITE) ax.axis("off") # ÜST PANEL — pin dizisi + plan izi axU.set_xlim(0, 11.5) axU.set_ylim(0, 3.85) axU.text(0.15, 3.68, "Pin dizisi v + optimal plan izi", ha="left", va="center", fontsize=12.5, color=COL_TEXT, weight="bold") axU.text(0.15, 3.40, "her pinde 3 seçenek: atla · tek vuruş (+v_i) · çift kemer (v_i·v_{i+1})", ha="left", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic") _bt_pin_w, _bt_pin_h = 1.05, 0.86 _bt_x0 = 0.55 _bt_y_pin = 0.80 _bt_centers = [] for k, val in enumerate(_bt_v): x = _bt_x0 + k * (_bt_pin_w + 0.18) neg = val < 0 fc = COL_SLATE_400 if neg else COL_BG axU.add_patch(FancyBboxPatch( (x, _bt_y_pin), _bt_pin_w, _bt_pin_h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=fc, ec=COL_PRIMARY, linewidth=1.9, zorder=2)) cx, cy = x + _bt_pin_w * 0.5, _bt_y_pin + _bt_pin_h * 0.5 _bt_centers.append((cx, cy)) axU.text(cx, cy, str(val), ha="center", va="center", fontsize=15, color=(COL_WHITE if neg else COL_TEXT), weight="bold", zorder=4) axU.text(cx, _bt_y_pin - 0.22, f"v[{k}]", ha="center", va="center", fontsize=8, color=COL_SLATE_500, zorder=4) for (i, typ, c) in _bt_plan: cx, cy = _bt_centers[i] if typ == "tek": axU.add_patch(Circle((cx, cy + _bt_pin_h * 0.5 + 0.34), 0.20, fill=False, ec=COL_AMBER_700, linewidth=2.4, zorder=5)) axU.text(cx, cy + _bt_pin_h * 0.5 + 0.34, "✓", ha="center", va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6) axU.text(cx, cy + _bt_pin_h * 0.5 + 0.72, f"tek +{c}", ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=6) for (i, typ, c) in _bt_plan: if typ != "çift": continue cx0, cy0 = _bt_centers[i] cx1, cy1 = _bt_centers[i + 1] ytop = cy0 + _bt_pin_h * 0.5 + 0.30 axU.add_patch(FancyArrowPatch( (cx0, ytop), (cx1, ytop), arrowstyle="-", mutation_scale=1, color=COL_ACCENT, linewidth=4.2, zorder=4, connectionstyle="arc3,rad=-0.55")) midx = (cx0 + cx1) / 2.0 a_disp = str(_bt_v[i]).replace("-", "−") b_disp = str(_bt_v[i + 1]).replace("-", "−") axU.text(midx, ytop + 0.62, f"çift {a_disp}·{b_disp} = {c}", ha="center", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6, bbox=dict(boxstyle="round,pad=0.18", fc=COL_AMBER_100, ec=COL_ACCENT, lw=1.5)) _bt_cx4, _ = _bt_centers[4] _bt_cx5, _ = _bt_centers[5] axU.text((_bt_cx4 + _bt_cx5) / 2.0, _bt_y_pin - 0.62, "(−5)·(−5) → POZİTİFLEŞİR", ha="center", va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=6, bbox=dict(boxstyle="round,pad=0.16", fc=COL_AMBER_100, ec=COL_AMBER_600, lw=1.4)) _bt_x_tot = _bt_x0 + _bt_n * (_bt_pin_w + 0.18) + 0.30 axU.add_patch(FancyBboxPatch( (_bt_x_tot, 0.70), 1.95, 1.55, boxstyle="round,pad=0.04,rounding_size=0.08", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=3)) axU.text(_bt_x_tot + 0.975, 1.97, "Optimal", ha="center", va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=5) axU.text(_bt_x_tot + 0.975, 1.58, "1 + 81 + 2 + 25", ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5) axU.text(_bt_x_tot + 0.975, 0.96, "= 109", ha="center", va="center", fontsize=18, color=COL_AMBER_700, weight="bold", zorder=5) # ALT PANEL — B suffix-DP tablosu axL.set_xlim(0, 11.5) axL.set_ylim(0, 4.05) axL.text(0.15, 3.88, "Suffix-DP tablosu B — doldurma i = 6 → 0 (topolojik sıra)", ha="left", va="center", fontsize=12.5, color=COL_TEXT, weight="bold") axL.text(0.15, 3.58, "B[i] = en iyi skor (pin i'den sona) · B[n]=0 taban · her hücre kazanan seçeneği gösterir", ha="left", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic") _bt_cell_w, _bt_cell_h = 1.30, 0.92 _bt_cx0 = 0.95 _bt_y_tab = 1.35 _bt_tab_centers = [] for i in range(_bt_n + 1): x = _bt_cx0 + i * (_bt_cell_w + 0.18) is_base = (i == _bt_n) is_answer = (i == 0) if is_base: fc, ec, lw = COL_BG, COL_SLATE_400, 1.6 elif is_answer: fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.8 else: fc, ec, lw = COL_BG, COL_PRIMARY, 1.8 axL.add_patch(FancyBboxPatch( (x, _bt_y_tab), _bt_cell_w, _bt_cell_h, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2)) cx, cy = x + _bt_cell_w * 0.5, _bt_y_tab + _bt_cell_h * 0.5 _bt_tab_centers.append((cx, cy)) axL.text(cx, cy + 0.13, str(_bt_B[i]), ha="center", va="center", fontsize=15, color=COL_TEXT, weight="bold", zorder=4) axL.text(cx, _bt_y_tab + _bt_cell_h + 0.16, f"B[{i}]", ha="center", va="center", fontsize=9, color=COL_SLATE_500, weight="bold", zorder=4) wlbl, wform, _ = _bt_winners[i] if is_base: cap, ccol = "taban = 0", COL_SLATE_500 else: cap, ccol = f"← {wlbl}", COL_AMBER_700 axL.text(cx, cy - 0.24, cap, ha="center", va="center", fontsize=8.5, color=ccol, weight="bold", zorder=4) for i in range(_bt_n): cx, cy = _bt_tab_centers[i] wlbl, wform, _ = _bt_winners[i] axL.text(cx, _bt_y_tab - 0.30, wform.replace("-", "−"), ha="center", va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold", zorder=4) _bt_cx_ans, _ = _bt_tab_centers[0] axL.text(_bt_cx_ans, _bt_y_tab - 0.66, "CEVAP", ha="center", va="center", fontsize=8.5, color=COL_ACCENT, weight="bold", zorder=5) _bt_cx_base, _ = _bt_tab_centers[_bt_n] axL.text(_bt_cx_base, _bt_y_tab - 0.42, "(boş sonek)", ha="center", va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5) _bt_y_topo = _bt_y_tab + _bt_cell_h + 0.50 _bt_x_right = _bt_tab_centers[_bt_n][0] _bt_x_left = _bt_tab_centers[0][0] axL.add_patch(FancyArrowPatch( (_bt_x_right, _bt_y_topo), (_bt_x_left, _bt_y_topo), arrowstyle="-|>", mutation_scale=18, color=COL_ACCENT, linewidth=2.6, zorder=3, connectionstyle="arc3,rad=0.05")) axL.text((_bt_x_right + _bt_x_left) / 2.0, _bt_y_topo + 0.30, "doldurma yönü: i = 6 → 0 (her B[i] sağındaki çözülmüş hücrelere bakar)", ha="center", va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=4) axL.text(5.75, 0.30, "her pin 3 seçenek (atla / tek / çift) · alt problemler YENİDEN KULLANILIR → " "3ⁿ kaba kuvvet yerine O(n)", ha="center", va="center", fontsize=9.5, color=COL_TEXT, weight="bold") axL.text(5.75, 0.05, "yerel kaba kuvvet sabit (≤3 seçenek/pin) — Demaine 54:47", ha="center", va="center", fontsize=8.2, color=COL_SLATE_500, style="italic") plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — DP → Viterbi / DTW / diff"} "İlk öğeye ne yapabilirim?" + memoization şablonu, bowling'in çok ötesine geçer. Aynı yerel-kaba-kuvvet refleksi gerçek ML ve sistem araçlarının çekirdeğidir: **Viterbi** (gizli Markov modellerinde en olası durum dizisi — her adımda "bu gözlem hangi durumdan geldi?"), **DTW** (dynamic time warping — ses/zaman serisi hizalama), **diff** ve **git merge** (en uzun ortak alt-dizilim üzerinden satır eşleme), **sequence alignment** (Needleman-Wunsch, Smith-Waterman — DNA/protein). Hepsi bir dizide ilk/son öğenin sabit sayıda seçeneğini deneyip alt problem çözümlerini yeniden kullanır. Bu dersin bir sonraki adımı (Ders 24, LCS/LIS) tam da bu köprünün ilk taşıdır. ::: ## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d23} 1. **DP = özyineleme + memoization**; en güçlü tasarım paradigması. 2. **SRTBOT**: Subproblems / Relations / Topological / Base / Original / Time. 3. **Memoization**: alt problem çözümünü sakla $\to$ her biri bir kez $\to$ Fibonacci $O(n)$. 4. **Süre formülü**: $\sum$ alt problemler $\times$ özyineleme-dışı iş. 5. **DAG shortest path** = DP; içinde DFS + topolojik sıra gizli. 6. **Alt-problem aracı**: prefix/suffix $\Theta(n)$, substring $\Theta(n^2)$; subsequence ($2^n$) YASAK. 7. **Bowling**: suffix DP, $B(i)$ = max(atla, tek, çift) → $O(n)$; yerel kaba kuvvet. ::: {.callout-important title="Tek Bir Cümle"} DP, "ilk öğeye ne yapabilirim?" sorusunu polinom sayıda alt problem üzerinde memoization'la çözer: SRTBOT ile alt problemleri tanımla, recurrence ile ilişkilendir, topolojik sırada sakla — yerel kaba kuvvet üstel aramayı polinom zamana indirir. ::: ## Kontrol Soruları {#sec-kontrol-sorulari-d23} ::: {.callout-note collapse="true" title="Soru 1: Fibonacci'nin saf özyinelemesi neden üstel, memoization neden polinom yapar?"} **Cevap:** Saf özyinelemede $f(n)$, $f(n-1)$ ve $f(n-2)$'yi çağırır; bunlar da kendi alt çağrılarını yapar — özyineleme ağacında $f(n-3), f(n-2)$ gibi alt problemler **defalarca** yeniden hesaplanır. $T(n) = T(n-1) + T(n-2) + 1 \approx \varphi^n$ (üstel). Memoization, her alt problemi çözünce bir memo tablosuna yazar; aynı alt problem ikinci kez istendiğinde **yeniden hesaplanmaz**, tablodan döner. Böylece yalnız $n$ farklı alt problem, her biri $O(1)$ $\to$ **$O(n)$**. Tek değişiklik "hesaplananı sakla/yeniden kullan"dır. ::: ::: {.callout-note collapse="true" title="Soru 2: SRTBOT'un altı adımı nedir, ve hangisi en zordur?"} **Cevap:** **S**ubproblems (alt problemleri tanımla), **R**elations (recurrence ile ilişkilendir), **T**opological order (DAG + çözüm sırası), **B**ase case (taban durum), **O**riginal problem (çözmek istediğin), **T**ime ($\sum$ alt problem $\times$ özyineleme-dışı iş). En zoru genelde **S** (ve onunla bağlı R): doğru alt problemleri bulmak. Demaine'in sezgisi: "çözümün hangi özelliğini bilsem işim biterdi?" — o özelliğin polinom seçeneği varsa, alt problemler doğru kurulur. ::: ::: {.callout-note collapse="true" title="Soru 3: Neden dizi problemlerinde alt-dizilim (subsequence) alt problem olarak seçilmez?"} **Cevap:** $n$ öğeli bir dizinin **$2^n$** alt-dizilimi vardır (her öğe ya alınır ya alınmaz) — üstel. Alt problemleri alt-dizilimlerle parametreleştirirsek, alt problem sayısı garantili üstel olur $\to$ DP'nin tüm avantajı kaybolur. Oysa **önek** ($\Theta(n)$), **sonek** ($\Theta(n)$) ve **alt dizi/substring** ($\Theta(n^2)$) polinom sayıdadır. DP'nin işe yaraması için alt problem sayısı polinom olmalı; bu yüzden dizilerde prefix/suffix/substring tercih edilir, subsequence asla. ::: ::: {.callout-note collapse="true" title="Soru 4: Bowling'de B(i) = max(B(i+1), B(i+1)+v_i, B(i+2)+v_i·v_{i+1}) neden doğru? 'Yerel kaba kuvvet' ne demek?"} **Cevap:** İlk pin $i$'ye yapılabilecek **tüm** şeyler: (1) atla $\to$ kalan sonek $B(i+1)$; (2) tek vur $\to$ $B(i+1) + v_i$; (3) $i+1$ ile çiftle $\to$ $B(i+2) + v_i \cdot v_{i+1}$. Bu üç seçenek tüm olasılıkları kapsar; max alarak en iyisini seçeriz. Geri kalan her durumda kalan **bir sonektir** (daha küçük alt problem) $\to$ özyineleme geçerli. "Yerel kaba kuvvet": her adımda yalnız ilk öğenin seçeneklerini (sabit sayıda) dene; alt problemler yeniden kullanıldığından, normalde $3^n$ olacak arama **$O(n)$**'e iner. ::: ## Egzersizler {#sec-egzersizler-d23} **Egzersiz 1.** Fibonacci'yi hem memoizasyonlu (top-down) hem bottom-up Python'da yaz; her ikisinin de $O(n)$ toplama yaptığını doğrula. **Egzersiz 2.** Bowling'i verilen bir örnek dizide (örn. $[1, 9, 9, 2, -5, -5]$) elle $B(i)$ tablosuyla çöz; optimal stratejiyi göster. **Egzersiz 3.** DAG en kısa yolu SRTBOT olarak yaz (S/R/T/B/O/T); recurrence'ın gelen kenarlar üzerinden min olduğunu açıkla. **Egzersiz 4.** Bir dizi problemi için prefix, suffix ve substring alt problem sayılarını ($\Theta(n), \Theta(n), \Theta(n^2)$) ve subsequence'in neden $2^n$ olduğunu yaz. **Egzersiz 5.** Bowling kuralını değiştir (örn. üç bitişik pin de vurulabilsin); recurrence'a yeni seçeneği ekle ve sürenin hâlâ $O(n)$ kaldığını göster. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d23} ::: {.callout-warning title="Sonraki: Ders 24 (L16) — Dinamik Programlama 2 (Erik Demaine)"} **Ders 24 (L16): Dinamik Programlama 2** (string alt problemleri, Erik Demaine). DP'yi **dizi/string** problemlerine uyguluyoruz: en uzun ortak alt-dizilim (LCS), en uzun artan alt-dizilim (LIS) gibi klasikler, ve oyun ağaçları. SRTBOT aynı kalır; alt problemler önek/sonek/substring olur, recurrence "son karakteri eşleştir/eşleştirme" gibi yerel kaba kuvvetle kurulur. DP ünitesi burada devam eder (Ders 24-27 = L16-L18; araya **Ders 25 = PS8** girer); blok, Quiz 3 kapsamının (DP) belkemiğidir ve **Ders 30 = PS10/Quiz 3 Gözden Geçirme** ile özetlenir. **Ders 24 Öncesi Yapılacak:** - Bu dersin egzersizlerini, özellikle Egzersiz 1 (Fibonacci iki yöntem) ve 2 (bowling) çöz. - SRTBOT'un altı adımını ezberden say; her birine bowling'den örnek ver. - Ana cümleyi tekrar oku: *"Çözümün hangi özelliğini bilsem işim biterdi? — polinom seçenek → polinom DP."* ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d23} | Kavram | Tanım | Sayfada | |---|---|---| | **Dinamik programlama** | Özyineleme + memoization; polinom tasarım | Böl. 1 | | **SRTBOT** | Subproblems/Relations/Topological/Base/Original/Time | Böl. 2 | | **Memoization** | Alt problem çözümünü sakla/yeniden kullan | Böl. 5 | | **Süre formülü** | $\sum$ alt problem $\times$ özyineleme-dışı iş | Böl. 6 | | **Alt-problem aracı** | prefix/suffix $\Theta(n)$, substring $\Theta(n^2)$; subsequence $2^n$ YASAK | Böl. 8 | | **Bowling recurrence** | $B(i)$ = max(atla, tek $v_i$, çift $v_i \cdot v_{i+1}$) | Böl. 9 | | **Bottom-up DP** | Base $\to$ topolojik for $\to$ relation $\to$ original | Böl. 10 | | **Yerel kaba kuvvet** | İlk öğenin seçeneklerini dene + max/min; reuse | Böl. 10 | ## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d23} ::: {.callout-tip title="6 köprü"} Bu ders, hazır algoritma uygulamaktan kendi algoritmanı tasarlamaya geçişin kapısıdır; SRTBOT disiplini ve memoization sezgisi, ML ve sistem mühendisliğindeki çok sayıda araca doğrudan bağlanır — köprülerin özeti: 1. **DP** → dizi hizalama (DNA/diff), Viterbi/DTW (ses, ML), metin akıllı-kırpma, knapsack, en kısa yol. 2. **SRTBOT** → algoritma tasarım disiplini; her DP'yi altı adımla yazma alışkanlığı (OMSCS CS 6515 — her DP probleminde "önce S/R/T/B/O/T çıkar" refleksi). 3. **Memoization** → caching/önbellekleme; saf hesaplamayı tekrar etmeden sakla. 4. **Yerel kaba kuvvet** → "her adımda sabit seçenek + reuse" → üstel aramayı polinoma indirme. 5. **Alt-problem grafı = DAG** → bağımlılık çözümü, build sistemi; DP içinde gizli DFS. 6. **Optimal alt yapı** → en kısa yol + DP köprüsü; alt-problem çözümlerini birleştirme. ::: --- ::: {.callout-important title="Tek bir şey alıp gideceksen"} Dinamik programlama = özyineleme + memoization. SRTBOT'la alt problemleri tanımla, bir recurrence ile ilişkilendir, topolojik sırada çöz, çözümleri bir memo tablosunda sakla. Sihir "yerel kaba kuvvettedir": her adımda yalnız ilk öğenin sabit sayıda seçeneğini dener, en iyisini alırsın — alt problemleri yeniden kullandığından, üstel görünen arama polinom zamana iner. Tek soru: "çözümün hangi özelliğini bilsem işim biterdi?" Bu, kendi algoritmanı tasarlama bölümünün açılışıdır; sırada DP'yi string ve oyunlara taşıyan Ders 24 var. :::