---
title: "Dinamik Programlama 3: Floyd-Warshall, Parantezleme"
subtitle: "Subproblem expansion derinliği: alt probleme bir koordinat ekleyerek geçmişi/state'i hatırlamak — Floyd-Warshall vertex-prefix APSP ile ilk k düğümü kullan ve E terimini V'ye çevir O(V³), parantezlemede son işlemi (kök) tahmin et ve negatifler için min/max genişlet O(n³), parmaklamada hangi parmakla başladığını state olarak taşı O(n·F²)"
---
::: {.callout-note title="Oturum bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 17: Dynamic Programming, Part 3](https://www.youtube.com/watch?v=TDo3r5M1LNo) (≈63 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 17: Dynamic Programming, Part 3](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec17/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 26 (L17)
- **Hoca:** Erik Demaine (dinamik programlama; **DP serisinin 3/4'ü**)
- **Okuma süresi:** ≈27 dk
> Bu, DP ünitesinin **üçüncü dersidir**. Ders 24 çoklu girdi, alt problem kısıtı ve genişletmeyi tanıttı; bu ders **subproblem expansion**'ı derinleştirir: alt probleme bir kısıt/koordinat ekleyerek geçmişi/state'i hatırlamak. Dört örnek — Bellman-Ford (DP olarak), **Floyd-Warshall** (yeni APSP, $O(V^3)$), aritmetik parantezleme (kök tahmini + min/max), piyano parmaklama (state = parmak). **Tarihsel not:** DP'yi 1950'lerde Bellman icat etti; "programming" eski anlamıyla **optimizasyon**, "dynamic" ise her aşamada farklı davranan yerel kaba kuvvet.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d26}
DP serisinin **3/4'ü** (Erik Demaine). Tema: **subproblem expansion** (alt problem genişletme) — alt probleme bir kısıt/durum koordinatı ekleyerek "geçmişi/state'i hatırlamak".
> *"we can always add subproblems to make the next step easier."* — Demaine, 2:55
Üç ana fikir:
1. **Floyd-Warshall** — alt problemi "yalnız ilk $k$ düğümü kullanarak" kısıtla → $O(V^3)$ ($E$ faktörünü $V$'ye çevirir).
2. **Kökü tahmin et** — parantezleme/ifade ağacında **son işlem (kök)** en kolay tahmin edilebilir özelliktir → substring alt problemleri.
3. **State = koordinat** — piyano parmaklamada "hangi parmakla başladım" durumunu alt problem koordinatına taşı.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 26'nın (L17) kavram haritası: kök = Dinamik Programlama 3 (Demaine) — DP serisinin 3/4'ü; tek tema SUBPROBLEM EXPANSION, yani alt probleme küçük bir koordinat/kısıt ekleyerek geçmişi ve state'i hatırlamak. Dört dal — (1) Bellman-Ford DP olarak: δ-alt-k aslında en fazla k kenar kısıtlı bir DP'dir, k indeksi çevrimli grafı çevrimsize çevirir, son kenarı tahmin et, O eşittir V çarpı E; bu k_edge_distances motorunun ta kendisidir. (2) Floyd-Warshall vertex-prefix APSP: alt problem d(u,v,k) yalnız ilk k düğümü ara-düğüm kullanır, k. düğümü ekleyince yol ya geçmez ya BİR KEZ geçer yani min İKİ terim O(1) iş, V küp alt problem çarpı O(1) eşittir O(V küp), negatif çevrim tanığı köşegen d(v,v) sıfırdan küçük. (3) FW karşı Johnson: yoğun grafta FW basit beş satır kod, seyrek grafta Johnson V kare log V kazanır, ikisi de negatif çevrimde AYNI tanığı verir. (4) Parantezleme kök tahmini: son yapılan işlem en kolay tahmin edilen özellik, kökü seç sol ve sağ substring ayrışır; negatif sayılarda iki yanı maksimize çöker çünkü negatif çarpı negatif eşittir büyük pozitif, çözüm her substring için HEM min HEM max sakla, n küp. (5) Piyano parmaklama state eşittir parmak: zorluk d dört parametreli, alt problemi başlangıç parmağıyla kısıtla, sonraki parmağı tahmin et, n F kare. Birleştirici tema: küçük state'i alt problem sayısıyla çarp, geçişleri yerel kaba kuvvetle tara — neredeyse her problemin her yönünü yakalarsın."
flowchart TD
A["Ders 26 (L17): Dinamik Programlama 3 — Floyd-Warshall, Parantezleme"] --> BF["Bellman-Ford = DP"]
BF --> BFa["δ-alt-k: en fazla k kenar kısıtı<br/>k indeksi çevrimliyi çevrimsize çevirir; O(V·E)"]
A --> FW["Floyd-Warshall — vertex-prefix APSP"]
FW --> FWa["d(u,v,k) = yalnız ilk k düğüm<br/>min İKİ terim O(1) → O(V³); köşegen<0 tanığı"]
A --> VS["FW vs Johnson"]
VS --> VSa["yoğun → FW (5 satır); seyrek → Johnson (V² log V)<br/>negatif çevrimde ikisi de AYNI tanık"]
A --> PR["Parantezleme — kök tahmini"]
PR --> PRa["son işlem (kök) tahmin et → substring<br/>negatif için HEM min HEM max; O(n³)"]
A --> PI["Piyano parmaklama — state = parmak"]
PI --> PIa["zorluk d dört parametreli; başlangıç parmağı koordinatı<br/>sonraki parmağı tahmin et; O(n·F²)"]
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 BF,FW,VS,PR,PI branch
class BFa,FWa,VSa,PRa,PIa leaf
```
::: {.callout-tip title="Builder Notu — Floyd-Warshall = transitif kapanış / ağ analizi"}
Floyd-Warshall yalnız APSP mesafe matrisi vermez; ağırlıkları "var/yok" boole'e indirgersen aynı $O(V^3)$ üçlü döngü **transitif kapanışı** (reachability — "hangi düğümden hangi düğüme ulaşılır?") hesaplar. Bu yüzden ağ analizi, sosyal-ağ erişilebilirliği ve derleyici veri-akışı analizinde temel araçtır: dense çizgede 5 satır kod, in-place, basit. Asimptotik olarak Johnson kadar iyi değildir ($V \cdot E$ seyrek çizgede kazanır), ama dense ($E \sim V^2$) veya küçük çizgede pratik üstünlük FW'dedir.
- **İleriye → Floyd-Warshall:** APSP mesafe matrisi, transitif kapanış (reachability), ağ analizi; dense çizgede pratik.
- **İleriye → parantezleme:** derleyici ifade optimizasyonu, **matris-zincir çarpımı** (matrix chain), sözdizimi ağacı.
- **İleriye → parmaklama:** MIDI/müzik teknolojisi, dizilim hizalama, **durum-makinesi DP'leri**.
- **Geriye → Bellman-Ford (Ders 18):** $\delta_k$ aslında bir DP alt-problem kısıtıdır.
Tek cümle: *Alt probleme bir koordinat ekleyerek "state" hatırlarsın: Floyd-Warshall "ilk $k$ düğümü kullan" der ($O(V^3)$), parantezleme "son işlem hangisi?" diye kökü tahmin eder (negatifler için min+max), parmaklama "hangi parmak" durumunu taşır — hepsi subproblem expansion.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 26 (L17) DP 3: Floyd-Warshall / Parantezleme / Parmaklama
# motoru (_engine.py D26 bölümü + bağımlılıkları INLINE GÖMÜLÜ — import YOK,
# brief: setup hücresine göm). Fonksiyonlar:
# floyd_warshall / floyd_warshall_steps / fw_negative_cycle / build_fw_example
# → vertex-prefix APSP DP (min iki terim) + figür izi + negatif çevrim tanığı.
# parenthesize / paren_reconstruct / brute_paren_values
# + build_paren_example / build_paren_negative_example → kök-tahmini min/max DP.
# default_difficulty / piano_fingering / brute_fingering / build_piano_example
# → state=parmak DP + Fⁿ bağımsız tanık.
# k_edge_distances / bellman_ford_classic / relax_edge / _reachable_from
# → Bellman-Ford-DP köprüsü (δₖ tablosu).
# ChangeablePQ / dijkstra / add_supernode / reweight / johnson / brute_apsp
# / build_johnson_example → FW çapraz tanığı (FW == johnson == V×BF).
# Slate+Amber viz sabitleri (_viz.py COL_*) + apply_style. Bu hücre gizli
# (#| echo: false).
#
# Aşağıdaki TÜM figür hücreleri burada tanımlanan fonksiyonları IMPORT ETMEDEN
# kullanır (dosyadan import YOK). Notion'daki öğretim içeriği (görünür pseudocode)
# 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
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle, Arc
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
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"
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py — kenar gevşetme + erişilebilirlik (D16/D18 bağımlılıkları)
# ---------------------------------------------------------------------------
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 _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (tanık → −∞ yayma)."""
seen = set(start)
stack = list(start)
while stack:
u = stack.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
return seen
def k_edge_distances(adj, weight, s, kmax):
"""δₖ(s,v) tablosu (L12 §4): k = 0..kmax için en fazla k kenarlı en kısa
mesafeler. Bellman-Ford-DP köprüsü. Döndürür: liste[k][v]."""
d0 = {v: INF for v in adj}
d0[s] = 0
table = [d0]
for _ in range(kmax):
prev = table[-1]
cur = dict(prev) # "kalma" kenarı: δₖ ≤ δₖ₋₁
for u in adj:
if prev[u] == INF:
continue
for v in adj[u]:
if prev[u] + weight[(u, v)] < cur[v]:
cur[v] = prev[u] + weight[(u, v)]
table.append(cur)
return table
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford (L12): V−1 tur kenar gevşetme; V. turda hâlâ
gevşeyen düğümler TANIK → erişilenlere −∞ yay. O(V·E)."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1): # V−1 tur (δ_{V−1})
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
relax_edge(d, weight, u, v)
witnesses = set()
for u in adj: # V. tur: tanık tespiti
if d[u] == INF:
continue
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
witnesses.add(v)
for v in _reachable_from(adj, witnesses):
d[v] = -INF
return d
def build_bf_example():
"""L12 §8 Notion örneği: a,b,c,d; çevrim b→c→d→b = (−4)+3+(−1) = −2
(negatif); a→b(−5) girişi. δ(a,·): a=0, b=c=d=−∞ (çevrimden erişilir)."""
adj = {"a": ["b"], "b": ["c"], "c": ["d"], "d": ["b"]}
weight = {("a", "b"): -5, ("b", "c"): -4, ("c", "d"): 3, ("d", "b"): -1}
return adj, weight
# ---------------------------------------------------------------------------
# _engine.py — D19 Dijkstra (ChangeablePQ) + D21 Johnson (FW çapraz tanığı)
# ---------------------------------------------------------------------------
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü (cross-link). build O(n), delete_min / decrease_key
O(log n)."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (cross-link ile O(1) konum). O(log n)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6): en yakını çıkar, kenarlarını gevşet, decrease_key
ile güncelle. Ağırlıklar ≥ 0 ŞART."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
def add_supernode(adj, weight):
"""Süpernode (L14 §8): s* → her düğüme 0-ağırlık; GELEN kenarı yok."""
s = ("super", "*")
adj2 = {s: list(adj.keys())}
for u in adj:
adj2[u] = list(adj[u])
w2 = dict(weight)
for v in adj:
w2[(s, v)] = 0
return adj2, w2, s
def reweight(adj, weight, h):
"""Potansiyel dönüşümü (L14 §6): w′(u,v) = w(u,v) + h(u) − h(v)."""
return {(u, v): weight[(u, v)] + h[u] - h[v] for u in adj for v in adj[u]}
def johnson(adj, weight):
"""Johnson APSP (L14 §9): süpernode → BF potansiyeli → reweight → V×Dijkstra
→ geri çevir. Döndürür: {u: {v: δ(u,v)}} ya da None (negatif çevrim)."""
adj_s, w_s, s = add_supernode(adj, weight) # 1. süpernode
h = bellman_ford_classic(adj_s, w_s, s) # 2. h = δ(s,·)
if any(h[v] == -INF for v in adj):
return None # negatif çevrim
w_prime = reweight(adj, weight, h) # 3. w′ ≥ 0
delta = {}
for u in adj: # 4. V × Dijkstra
dp = dijkstra(adj, w_prime, u)
# 5. geri çevir: δ(u,v) = δ′(u,v) − h(u) + h(v)
delta[u] = {v: (dp[v] - h[u] + h[v]) if dp[v] != INF else INF
for v in adj}
return delta
def brute_apsp(adj, weight):
"""Bağımsız tanık: her düğümden bellman_ford_classic (V×BF — Johnson'dan
FARKLI yol; negatif çevrimsiz çizgede sonlu/INF birebir)."""
return {u: bellman_ford_classic(adj, weight, u) for u in adj}
def build_johnson_example():
"""L14/L17 deterministik negatif-kenarlı (negatif-çevrimsiz) çizge:
a→b(−2), b→c(3), a→c(4), c→d(−1), b→d(2)."""
adj = {"a": ["b", "c"], "b": ["c", "d"], "c": ["d"], "d": []}
weight = {("a", "b"): -2, ("b", "c"): 3, ("a", "c"): 4,
("c", "d"): -1, ("b", "d"): 2}
return adj, weight
# ---------------------------------------------------------------------------
# _engine.py D26 (L17) §3-4 — Floyd-Warshall: vertex-prefix APSP DP
# ---------------------------------------------------------------------------
def floyd_warshall(adj, weight):
"""Floyd-Warshall (L17 §3-4): d(u,v,k) = yalnız {u,v} ∪ {ilk k düğüm}
ara-düğümlü en kısa yol; R = min(d(u,v,k−1), d(u,k,k−1) + d(k,v,k−1))
— yol k'dan ya geçmez ya BİR KEZ geçer → min İKİ terim O(1) iş →
V³ × O(1) = O(V³). Taban: 0 (u=v) / w(u,v) / ∞. Negatif çevrim tanığı:
d(v,v) < 0. Döndürür: {u: {v: d}} (johnson / brute_apsp formatı)."""
nodes = list(adj)
d = {u: {v: (0 if u == v else weight.get((u, v), INF)) for v in nodes}
for u in nodes}
for k in nodes: # k artan: izinli ara-düğüm büyür
for u in nodes:
duk = d[u][k]
if duk == INF:
continue
for v in nodes:
if duk + d[k][v] < d[u][v]:
d[u][v] = duk + d[k][v]
return d
def fw_negative_cycle(d):
"""FW çıktısında negatif çevrim tanığı: d(v,v) < 0 olan düğümler."""
return sorted(v for v in d if d[v][v] < 0)
def floyd_warshall_steps(adj, weight):
"""Figür izi (Egzersiz 1): taban (k=0) dahil her k'dan sonra d matrisi
kopyası. Döndürür: [(etiket, {u: {v: d}})]."""
nodes = list(adj)
d = {u: {v: (0 if u == v else weight.get((u, v), INF)) for v in nodes}
for u in nodes}
steps = [("taban", {u: dict(d[u]) for u in nodes})]
for k in nodes:
for u in nodes:
if d[u][k] == INF:
continue
for v in nodes:
if d[u][k] + d[k][v] < d[u][v]:
d[u][v] = d[u][k] + d[k][v]
steps.append(("k=" + str(k), {u: dict(d[u]) for u in nodes}))
return steps
def build_fw_example():
"""L17 FW örneği = D21 johnson örneği (a,b,c,d; negatif kenarlı,
negatif-çevrimsiz) — FW == johnson çapraz tanığı AYNI çizgede kapanır."""
return build_johnson_example()
# ---------------------------------------------------------------------------
# _engine.py D26 (L17) §6-8 — Aritmetik parantezleme: kök tahmini + min/max
# ---------------------------------------------------------------------------
def parenthesize(values, ops):
"""Aritmetik parantezleme DP (L17 §6-8): x(i,j,opt) = a[i..j) alt-
ifadesinin opt ∈ {min, max} değeri. Kökü (SON işlem ⋆ₖ) tahmin et →
sol/sağ substring; negatif sayılar için HEM min HEM max sakla
(negatif × negatif = büyük pozitif — Demaine 34:50); kombinasyon 4.
Taban x(i,i+1) = aᵢ. n² substring × 2 × O(n) kök = O(n³).
Döndürür: (xmin, xmax, choice) — choice[(i,j,opt)] = (k, optL, optR)."""
n = len(values)
xmin, xmax, choice = {}, {}, {}
for i in range(n):
xmin[(i, i + 1)] = xmax[(i, i + 1)] = values[i]
for span in range(2, n + 1):
for i in range(0, n - span + 1):
j = i + span
best_min, best_max = INF, -INF
for k in range(i + 1, j):
op = ops[k - 1]
for vl, ol in ((xmin[(i, k)], "min"), (xmax[(i, k)], "max")):
for vr, om in ((xmin[(k, j)], "min"),
(xmax[(k, j)], "max")):
val = vl + vr if op == "+" else vl * vr
if val < best_min:
best_min = val
choice[(i, j, "min")] = (k, ol, om)
if val > best_max:
best_max = val
choice[(i, j, "max")] = (k, ol, om)
xmin[(i, j)], xmax[(i, j)] = best_min, best_max
return xmin, xmax, choice
def paren_reconstruct(values, ops, opt="max"):
"""Ebeveyn izinden parantezli ifade string'i (D24 §5 emsali).
Döndürür: (ifade, değer) — ifade eval ile sağlanabilir (× → *)."""
xmin, xmax, choice = parenthesize(values, ops)
def rec(i, j, o):
if j == i + 1:
v = values[i]
return str(v) if v >= 0 else "(" + str(v) + ")"
k, ol, om = choice[(i, j, o)]
sym = "+" if ops[k - 1] == "+" else "×"
return "(" + rec(i, k, ol) + " " + sym + " " + rec(k, j, om) + ")"
table = xmax if opt == "max" else xmin
return rec(0, len(values), opt), table[(0, len(values))]
def brute_paren_values(values, ops):
"""Bağımsız tanık (Catalan-üstel, DP'siz): TÜM parantezlemelerin
ulaşılabilir değer KÜMESİ — max'ı x(max), min'i x(min) ile kıyaslanır."""
def rec(i, j):
if j == i + 1:
return {values[i]}
out = set()
for k in range(i + 1, j):
op = ops[k - 1]
for lv in rec(i, k):
for rv in rec(k, j):
out.add(lv + rv if op == "+" else lv * rv)
return out
return rec(0, len(values))
def build_paren_example():
"""L17 §6 örneği: 7 + 4 × 3 + 5 → ((7+4) × (3+5)) = 88."""
return [7, 4, 3, 5], ["+", "*", "+"]
def build_paren_negative_example():
"""L17 §7 örneği: 7 + (−4) × 3 + (−5) → 7 + ((−4) × (3+(−5))) = 15
(negatif alt-ifadeyi MİNİMİZE etmek genel max'ı artırır)."""
return [7, -4, 3, -5], ["+", "*", "+"]
# ---------------------------------------------------------------------------
# _engine.py D26 (L17) §9 — Piyano parmaklama: state = parmak DP
# ---------------------------------------------------------------------------
def default_difficulty(t, f, t2, f2):
"""Sentetik geçiş zorluğu d(t,f,t2,f2) (L17 §9 figür/test): el kayması
|Δnota − Δparmak| + ters-yön cezası 2 (nota yukarı, parmak aşağı vb.).
NOT: bu SENTETİK bir örnek-fonksiyondur; dersin gerçek d'si soyuttur."""
base = abs((t2 - t) - (f2 - f))
cross = 2 if (t2 - t) * (f2 - f) < 0 else 0
return base + cross
def piano_fingering(notes, F, d=default_difficulty):
"""Piyano parmaklama DP (L17 §9): x(i,f) = tᵢ'yi f parmağıyla BAŞLAYARAK
soneki çalmanın min toplam zorluğu (state = parmak; alt problem ×F
genişletmesi). R: sonraki parmak kaba kuvvet: x(i,f) = min_{f2}
x(i+1,f2) + d(tᵢ,f,tᵢ₊₁,f2). O = min_f x(0,f). n·F × O(F) = O(n·F²).
Döndürür: (min zorluk, parmak ataması listesi) — ebeveyn iziyle."""
n = len(notes)
if n == 0:
return 0, []
x = {(n - 1, f): 0 for f in range(F)}
nxt = {}
for i in range(n - 2, -1, -1):
for f in range(F):
best, bf = INF, None
for f2 in range(F):
c = x[(i + 1, f2)] + d(notes[i], f, notes[i + 1], f2)
if c < best:
best, bf = c, f2
x[(i, f)] = best
nxt[(i, f)] = bf
f0 = min(range(F), key=lambda f: x[(0, f)])
assign = [f0]
for i in range(n - 1):
assign.append(nxt[(i, assign[-1])])
return x[(0, f0)], assign
def brute_fingering(notes, F, d=default_difficulty):
"""Bağımsız tanık (Fⁿ tüm atamalar, DP'siz): min toplam zorluk."""
from itertools import product
n = len(notes)
if n == 0:
return 0
best = INF
for assign in product(range(F), repeat=n):
tot = sum(d(notes[i], assign[i], notes[i + 1], assign[i + 1])
for i in range(n - 1))
best = min(best, tot)
return best
def build_piano_example():
"""L17 §9 figür örneği: 6 notalık melodi (MIDI benzeri), F = 5 parmak."""
return [60, 64, 62, 67, 65, 60], 5
```
## 1. DP 3/4: Subproblem Expansion {#sec-1-dp-3-4-subproblem-expansion}
DP 2'de para oyununda alt problemi 2 katına (kim başlıyor) çıkarmıştık. Bu ders, bu fikri derinleştirir: **alt probleme kısıt/koordinat ekleyerek geçmişi hatırlamak**. Hatırlatma: alt problemleri tanımla (prefix/suffix/substring; çoklu girdide çarpım), "çözümün hangi özelliğini bilsem işim biterdi?" sorusunu kaba kuvvetle dene, DAG + topolojik sıra, taban, orijinal, süre.
> *"we can always add subproblems to make the next step easier."* — Demaine, 2:55
Bu derste bu refleksi dört kez izleriz: Bellman-Ford'u bir DP olarak yeniden okuruz; Floyd-Warshall'da "yalnız ilk $k$ düğüm" kısıtını ekleriz; parantezlemede "son işlem hangisi?" diye kökü tahmin ederiz; parmaklamada "hangi parmak" durumunu taşırız. Her seferinde alt problem sayısını küçük bir faktörle çarpar, recurrence'ı sadeleştiririz.
## 2. Bellman-Ford DP Olarak {#sec-2-bellman-ford-dp-olarak}
Bellman-Ford (Ders 18) aslında bir **DP**'dir. **S:** $\delta_k(s, v) = $ en fazla $k$ kenarlı en kısa $s \to v$ yol (kısıt: $k$). **R:**
$$\delta_k(s, v) = \min\bigl( \delta_{k-1}(s, v),\; \min\{\, \delta_{k-1}(s, u) + w(u, v) : (u,v) \text{ gelen kenar} \,\} \bigr)$$
Son kenar $(u, v)$'yi tahmin et; yol $\le k$ kenarsa, kalanı $\le k-1$ kenar → $\delta_{k-1}$. **$k$ indeksi** çevrimli grafı ($G$) çevrimsize çevirir: $k$ artan sırada referanslar hep $k-1$'e → acyclic. **O:** $\delta_{V-1}(s, v)$. **Süre:** $\sum_k \sum_v (\text{gelen kenar}) = O(V \cdot E)$.
@fig-bf-dp-bridge bu DP'yi motor üzerinde somutlaştırır: D21 örneğinin (a,b,c,d) $\delta_k(a, v)$ tablosu — satırlar $k = 0 \ldots 3$, sütunlar $v$. Satırdan satıra **düşen** hücreler (amber ok) "bir kenar daha eklendi" demektir; son satır $\delta_3$ tam olarak klasik Bellman-Ford sonucudur ($\{a{:}0, b{:}{-2}, c{:}1, d{:}0\}$). Kritik gözlem: motorun `k_edge_distances` fonksiyonu **bu tablonun ta kendisidir** — Bellman-Ford'un DP iskeleti.
```{python}
#| label: fig-bf-dp-bridge
#| fig-cap: "Bellman-Ford bir DP'dir — δₖ(a, v) alt-problem tablosu (L17 §2 + D18 köprüsü). Sol bölge: satırlar k=0..3, sütunlar v=a,b,c,d; her hücre δₖ (∞ soluk). Satırdan satıra DÜŞEN hücreler amber ok ('δₖ < δₖ₋₁ → bir kenar daha eklendi, yeni gevşeme'). Son satır δ₃ amber kesik çerçeve = klasik Bellman-Ford sonucu (sonlu). Sağ kutu: SRTBOT eşlemesi (S = δₖ en fazla k kenar kısıtı = k koordinatı; R = kal ya da bir kenar gevşet; T = k artan çevrimliyi acyclic yapar; O = δ_{V−1} SSSP cevabı). Alt rozet: alt-problem genişletmesi ×V → O(V·E); motor k_edge_distances BU tablonun ta kendisi. Veri MOTORDAN (assert): k_edge_distances(build_fw_example, 'a', 3); son satır == bellman_ford_classic; tab[0..3] birebir; düşüşler k=1 {b,c}, k=2 {c,d}, k=3 yok."
#| fig-width: 11.0
#| fig-height: 5.5
# fig-bf-dp-bridge (L17 §2): Bellman-Ford = DP; δₖ tablosu. Veri MOTORDAN.
adj, w = build_fw_example()
src = list(adj.keys())[0]
assert src == "a", src
nodes = list(adj.keys())
n = len(adj)
assert nodes == ["a", "b", "c", "d"] and n == 4
tab = k_edge_distances(adj, w, src, n - 1) # k = 0..3
assert len(tab) == n
bf = bellman_ford_classic(adj, w, src)
assert all(tab[-1][v] == bf[v] for v in nodes), (tab[-1], bf)
assert tab[0] == {"a": 0, "b": INF, "c": INF, "d": INF}, tab[0]
assert tab[1] == {"a": 0, "b": -2, "c": 4, "d": INF}, tab[1]
assert tab[2] == {"a": 0, "b": -2, "c": 1, "d": 0}, tab[2]
assert tab[3] == {"a": 0, "b": -2, "c": 1, "d": 0}, tab[3]
assert bf == {"a": 0, "b": -2, "c": 1, "d": 0}, bf
def _fmt(val):
return "∞" if val == INF else str(val)
def _dropped_cells(table):
drops = []
for k in range(1, len(table)):
for v in nodes:
if table[k][v] < table[k - 1][v]:
drops.append((k, v))
return drops
drops = _dropped_cells(tab)
assert set(drops) == {(1, "b"), (1, "c"), (2, "c"), (2, "d")}, drops
fig, ax = plt.subplots(figsize=(11, 5.5))
ax.set_facecolor(COL_WHITE)
cell_w, cell_h = 1.15, 0.95
x0 = 1.55
y_top = 0.0
row_gap = cell_h + 0.30
col_x = {v: x0 + j * cell_w for j, v in enumerate(nodes)}
row_y = {k: y_top - k * row_gap for k in range(n)}
ax.text(x0 + (n * cell_w) / 2.0, y_top + cell_h + 0.62,
"Bellman-Ford bir DP'dir — δₖ(a, v) alt-problem tablosu",
ha="center", va="center", fontsize=13.5, color=COL_TEXT, weight="bold")
ax.text(x0 - 0.30, y_top + cell_h + 0.10, "k \\ v", ha="right", va="center",
fontsize=10.5, color=COL_SLATE_500, weight="bold", style="italic")
for v in nodes:
cx = col_x[v] + cell_w * 0.5
ax.text(cx, y_top + cell_h + 0.18, v, ha="center", va="center",
fontsize=12.5, color=COL_PRIMARY, weight="bold")
center = {}
for k in range(n):
yk = row_y[k]
ax.text(x0 - 0.30, yk + cell_h * 0.5, f"k={k}", ha="right", va="center",
fontsize=11, color=COL_AMBER_700 if k == n - 1 else COL_TEXT,
weight="bold")
for v in nodes:
x = col_x[v]
val = tab[k][v]
is_inf = (val == INF)
is_drop = (k, v) in drops
if is_drop:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.6
ax.add_patch(FancyBboxPatch(
(x, yk), cell_w * 0.93, cell_h * 0.90, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=2))
cx, cy = x + cell_w * 0.465, yk + cell_h * 0.45
center[(k, v)] = (cx, cy)
txt_color = COL_SLATE_400 if is_inf else COL_TEXT
ax.text(cx, cy, _fmt(val), ha="center", va="center",
fontsize=13 if not is_inf else 14,
color=txt_color, weight="bold", zorder=4)
kl = n - 1
band_x = col_x[nodes[0]] - 0.05
band_w = n * cell_w - 0.07
ax.add_patch(FancyBboxPatch(
(band_x, row_y[kl] - 0.06), band_w, cell_h * 0.90 + 0.12,
boxstyle="round,pad=0.0,rounding_size=0.06",
fc="none", ec=COL_AMBER_700, linewidth=2.2, linestyle=(0, (5, 3)),
zorder=6))
ax.text(band_x + band_w + 0.18, row_y[kl] + cell_h * 0.45,
"δ₃ = Bellman-Ford\nsonucu (sonlu)", ha="left", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold")
for (k, v) in drops:
cx_prev, cy_prev = center[(k - 1, v)]
cx_cur, cy_cur = center[(k, v)]
ax.add_patch(FancyArrowPatch(
(cx_prev, cy_prev - cell_h * 0.42),
(cx_cur, cy_cur + cell_h * 0.44),
arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT,
linewidth=2.2, zorder=5, shrinkA=2, shrinkB=2))
ax.text(x0 + (n * cell_w) / 2.0, row_y[n - 1] - 0.55,
"amber ok: δₖ < δₖ₋₁ → bir kenar daha eklendi (yeni gevşeme)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", style="italic")
bx = x0 + n * cell_w + 1.45
bw = 5.05
by_top = y_top + cell_h + 0.30
by_bot = row_y[n - 1] - 0.20
bh = by_top - by_bot
ax.add_patch(FancyBboxPatch(
(bx, by_bot), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=1))
srtbot = [
("S", "δₖ(s, v) = en fazla k kenarlı en kısa mesafe",
"KISIT = k koordinatı (kenar bütçesi)"),
("R", "δₖ(v) = min( δₖ₋₁(v), min_{u→v} δₖ₋₁(u) + w(u,v) )",
"kal ya da bir kenar daha gevşet"),
("T", "k artan (0 → V−1)",
"k boyutu çevrimli grafı ACYCLIC yapar"),
("O", "δ_{V−1}(s, v) = SSSP cevabı",
"(negatif çevrim yoksa)"),
]
txt_x = bx + 0.30
head_y = by_top - 0.30
ax.text(txt_x, head_y, "SRTBOT eşlemesi", ha="left", va="center",
fontsize=12, color=COL_PRIMARY, weight="bold")
line_y = head_y - 0.55
dy = (line_y - (by_bot + 0.30)) / (len(srtbot) - 0.0)
for letter, main, sub in srtbot:
ax.add_patch(FancyBboxPatch(
(txt_x, line_y - 0.22), 0.40, 0.44,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=3))
ax.text(txt_x + 0.20, line_y, letter, ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(txt_x + 0.58, line_y + 0.085, main, ha="left", va="center",
fontsize=9.3, color=COL_TEXT, weight="bold", zorder=4)
ax.text(txt_x + 0.58, line_y - 0.175, sub, ha="left", va="center",
fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=4)
line_y -= dy
badge_cx = (x0 + bx + bw) / 2.0
badge_y = min(row_y[n - 1] - 1.15, by_bot - 0.50)
badge_w, badge_h = (bx + bw) - x0 + 0.10, 0.78
ax.add_patch(FancyBboxPatch(
(x0 - 0.05, badge_y - badge_h * 0.5), badge_w, badge_h,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_AMBER_700, linewidth=2.0, zorder=2))
ax.text(badge_cx, badge_y + 0.13,
"alt-problem genişletmesi ×V → O(V·E)",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(badge_cx, badge_y - 0.17,
"D18 motoru k_edge_distances BU tablonun ta kendisi",
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=4)
ax.set_xlim(x0 - 1.05, bx + bw + 0.35)
ax.set_ylim(badge_y - badge_h * 0.5 - 0.30, y_top + cell_h + 1.05)
ax.set_aspect("equal")
ax.axis("off")
fig.tight_layout()
plt.show()
```
## 3. Floyd-Warshall: Vertex-Prefix APSP {#sec-3-floyd-warshall-vertex-prefix}
Yeni bir **tüm-çiftler en kısa yol** (APSP) algoritması. Johnson kadar asimptotik iyi değil ama **çok basit** ve dense çizgede mükemmel: $O(V^3)$. Fikir — farklı bir subproblem expansion.
Düğümleri $1 \ldots V$ numarala. **S:** $d(u, v, k) = u \to v$ en kısa yol, **yalnız $\{u, v, 1 \ldots k\}$ düğümlerini ara-düğüm olarak kullanarak**.
Bu, "en fazla $k$ kenar" kısıtından farklı bir kısıt: "yalnız ilk $k$ düğüm". Bu, pahalı "tüm gelen düğümler üzerinde döngü"yü ($E$ terimi) ortadan kaldırır.
## 4. Floyd-Warshall Recurrence ve O(V³) {#sec-4-floyd-warshall-recurrence}
**Çalışılan Örnek.** $d(u, v, k)$'yı hesapla: $k$. düğümü ekleyince iki seçenek — yol $k$'dan **geçmez** ya da **geçer**:
$$d(u, v, k) = \min\bigl( d(u, v, k-1),\; d(u, k, k-1) + d(k, v, k-1) \bigr)$$
İlk terim: $k$'yı kullanma. İkinci: $u \to k$ (ilk $k-1$ ile) $+ \; k \to v$ (ilk $k-1$ ile) — basit yol olduğundan $k$ bir kez geçilir. **Min yalnız iki terim** → $O(1)$ iş! **T:** $k$ artan (üçlü iç içe döngü $k, u, v$). **B:** $d(u, v, 0) = 0$ ($u=v$) / $w(u, v)$ (kenar varsa) / $\infty$ (yoksa). **O:** $d(u, v, V)$. **Süre:** $V^3$ alt problem $\times\, O(1) = O(V^3)$.
@fig-fw-steps recurrence'ı motorun $5$ ardışık $d$-matrisi üzerinde gösterir (taban $\to k = a, b, c, d$): her adımda bir önceki matrise göre **değişen** hücreler amber vurgulanır. Örneğin $k = b$ adımında $(a, c){:}\,4 \to 1$ ve $(a, d){:}\,\infty \to 0$ — çünkü artık $a \to b \to c$ ve $a \to b \to d$ yolları açılır. Son matris üç bağımsız yoldan doğrulanır: $\text{FW} = \text{johnson} = V \times \text{Bellman-Ford}$ (üç-yol tanığı, 60 rastgele çizgede de tutar), ve köşegen $d(v,v) = 0$ (negatif çevrim yok).
```{python}
#| label: fig-fw-steps
#| fig-cap: "Floyd-Warshall: d(u, v, k) evrimi — taban → k = a, b, c, d (Demaine L17 §3-4 İMZA). 5 mini-matris dizisi (4×4 d matrisi); her adımda bir önceki adıma göre DEĞİŞEN hücreler amber vurgulu + sağ-üst köşede 'k yoluyla' rozeti, köşegen 0 koyu, ∞ soluk; matrisler arası 'k yoluyla' okları. k=b adımında (a,c):4→1 ve (a,d):∞→0 (yol b'den geçer). Altta recurrence kutusu d(u,v,k) = min(d(u,v,k−1), d(u,k,k−1)+d(k,v,k−1)) — İKİ terim, yol k'dan ya geçmez ya BİR KEZ geçer → hücre başına O(1). Sağ rozet: V³ × O(1) = O(V³); FW == johnson == V × BF (üç-yol tanığı). Veri MOTORDAN (assert): floyd_warshall_steps(build_fw_example); 5 adım (taban + k=a..d); steps[2] (a,c)=1, (a,d)=0; final == floyd_warshall == johnson == brute_apsp; fw_negative_cycle(final) == []."
#| fig-width: 12.5
#| fig-height: 5.5
# fig-fw-steps (L17 §3-4 İMZA): d(u,v,k) evrimi. Veri MOTORDAN.
adj, w = build_fw_example()
nodes = list(adj)
assert nodes == ["a", "b", "c", "d"], nodes
assert w == {("a", "b"): -2, ("b", "c"): 3, ("a", "c"): 4,
("c", "d"): -1, ("b", "d"): 2}, w
steps = floyd_warshall_steps(adj, w)
assert len(steps) == 5, len(steps)
labels = [s[0] for s in steps]
assert labels == ["taban", "k=a", "k=b", "k=c", "k=d"], labels
final = steps[-1][1]
fw = floyd_warshall(adj, w)
assert final == fw, "steps son != floyd_warshall"
assert fw == johnson(adj, w), "FW != johnson"
assert fw == brute_apsp(adj, w), "FW != brute_apsp"
assert fw_negative_cycle(final) == [], fw_negative_cycle(final)
assert steps[0][1]["a"]["c"] == 4 and steps[0][1]["a"]["d"] == INF
assert steps[2][1]["a"]["c"] == 1 and steps[2][1]["a"]["d"] == 0
assert final["a"]["c"] == 1 and final["a"]["d"] == 0
def _fmt(x):
return "∞" if x == INF else str(int(x))
changed = [set()]
for s_idx in range(1, len(steps)):
prev = steps[s_idx - 1][1]
cur = steps[s_idx][1]
ch = set()
for u in nodes:
for v in nodes:
if prev[u][v] != cur[u][v]:
ch.add((u, v))
changed.append(ch)
k_of_step = [None, "a", "b", "c", "d"]
fig, ax = plt.subplots(figsize=(12.5, 5.5))
CELL = 0.74
GAP_LABEL = 0.34
MAT_W = 4 * CELL + GAP_LABEL
BLOCK_GAP = 0.95
TOP_Y = 0.0
def _draw_matrix(x0, step_idx):
lbl, mat = steps[step_idx]
ch = changed[step_idx]
k = k_of_step[step_idx]
k_idx = nodes.index(k) if k is not None else None
title = "taban w" if lbl == "taban" else "k = " + lbl.split("=")[1]
ax.text(x0 + GAP_LABEL + 2 * CELL, TOP_Y + 0.42, title,
ha="center", va="center", fontsize=11.5,
color=COL_AMBER_700 if k is not None else COL_PRIMARY,
weight="bold")
for j, v in enumerate(nodes):
cx = x0 + GAP_LABEL + (j + 0.5) * CELL
is_k = (k_idx is not None and j == k_idx)
ax.text(cx, TOP_Y + 0.10, v, ha="center", va="center",
fontsize=9, color=COL_ACCENT if is_k else COL_SLATE_500,
weight="bold" if is_k else "normal")
for i, u in enumerate(nodes):
cy = TOP_Y - GAP_LABEL - (i + 0.5) * CELL
is_k = (k_idx is not None and i == k_idx)
ax.text(x0 + GAP_LABEL * 0.5, cy, u, ha="center", va="center",
fontsize=9, color=COL_ACCENT if is_k else COL_SLATE_500,
weight="bold" if is_k else "normal")
for i, u in enumerate(nodes):
for j, v in enumerate(nodes):
x = x0 + GAP_LABEL + j * CELL
y = TOP_Y - GAP_LABEL - (i + 1) * CELL
val = mat[u][v]
is_diag = (u == v)
is_inf = (val == INF)
is_changed = (u, v) in ch
on_k_line = (k_idx is not None and (i == k_idx or j == k_idx))
if is_changed:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6
elif is_diag:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.6
elif on_k_line:
fc, ec, lw = COL_WHITE, COL_AMBER_600, 1.4
else:
fc, ec, lw = COL_WHITE, COL_SLATE_400, 1.2
ax.add_patch(FancyBboxPatch(
(x, y), CELL * 0.93, CELL * 0.93, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=2))
cx, cy = x + CELL * 0.465, y + CELL * 0.465
txt = _fmt(val)
if is_changed:
tc, tw = COL_AMBER_700, "bold"
elif is_inf:
tc, tw = COL_SLATE_400, "normal"
elif is_diag:
tc, tw = COL_PRIMARY, "bold"
else:
tc, tw = COL_TEXT, "normal"
ax.text(cx, cy, txt, ha="center", va="center",
fontsize=11.5 if is_changed else 10.5,
color=tc, weight=tw, zorder=4)
for (u, v) in ch:
i, j = nodes.index(u), nodes.index(v)
cx = x0 + GAP_LABEL + (j + 0.5) * CELL
cy = TOP_Y - GAP_LABEL - (i + 0.5) * CELL
ax.text(cx + CELL * 0.34, cy + CELL * 0.34, k,
ha="center", va="center", fontsize=7.5,
color=COL_WHITE, weight="bold", zorder=6,
bbox=dict(boxstyle="circle,pad=0.12", fc=COL_ACCENT,
ec=COL_AMBER_700, linewidth=0.8))
return x0 + MAT_W
x_cursor = 0.0
block_x0 = []
for s_idx in range(len(steps)):
block_x0.append(x_cursor)
x_end = _draw_matrix(x_cursor, s_idx)
x_cursor = x_end + BLOCK_GAP
for s_idx in range(len(steps) - 1):
x_from = block_x0[s_idx] + MAT_W
y_mid = TOP_Y - GAP_LABEL - 2 * CELL
ax.add_patch(FancyArrowPatch(
(x_from + 0.10, y_mid), (x_from + BLOCK_GAP - 0.10, y_mid),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.0, zorder=3))
k_next = k_of_step[s_idx + 1]
ax.text(x_from + BLOCK_GAP * 0.5, y_mid + 0.30, k_next + " yoluyla",
ha="center", va="center", fontsize=8, color=COL_AMBER_700,
weight="bold", zorder=3)
total_w = x_cursor - BLOCK_GAP
mat_bottom = TOP_Y - GAP_LABEL - 4 * CELL - GAP_LABEL
rec_y = mat_bottom - 0.55
ax.add_patch(FancyBboxPatch(
(0.0, rec_y - 0.62), total_w * 0.625, 0.92,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=2))
ax.text(total_w * 0.31, rec_y - 0.02,
"d(u, v, k) = min( d(u, v, k−1), d(u, k, k−1) + d(k, v, k−1) )",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=4)
ax.text(total_w * 0.31, rec_y - 0.40,
"İKİ terim — yol k'dan ya geçmez ya BİR KEZ geçer → hücre başına O(1) iş",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
style="italic", zorder=4)
badge_x = total_w * 0.655
ax.add_patch(FancyBboxPatch(
(badge_x, rec_y - 0.62), total_w - badge_x, 0.92,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=2))
ax.text((badge_x + total_w) * 0.5, rec_y - 0.02,
"V³ × O(1) = O(V³)",
ha="center", va="center", fontsize=12.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text((badge_x + total_w) * 0.5, rec_y - 0.40,
"FW == johnson == V × BF (üç-yol tanığı)",
ha="center", va="center", fontsize=9, color=COL_TEXT,
weight="bold", zorder=4)
ax.set_xlim(-0.3, total_w + 0.3)
ax.set_ylim(rec_y - 0.95, TOP_Y + 0.75)
ax.set_aspect("equal")
ax.axis("off")
fig.suptitle("Floyd-Warshall: d(u, v, k) evrimi — taban → k = a, b, c, d",
fontsize=13.5, color=COL_TEXT, weight="bold", y=0.985)
fig.tight_layout(rect=(0, 0, 1, 0.96))
plt.show()
```
## 5. Floyd-Warshall vs Johnson {#sec-5-floyd-warshall-vs-johnson}
- **Floyd-Warshall:** her zaman $O(V^3)$. Dense çizgede ($E \sim V^2$) Johnson ile aynı ($V \cdot E \sim V^3$), ama daha **basit** (5 satır).
- **Johnson:** $O(V^2 \log V + V \cdot E)$. **Seyrek** çizgede çok daha iyi ($V^2 \log V$).
Kural: çizgenin **dense olduğunu önceden biliyorsan** (veya küçükse) Floyd-Warshall; seyrek/karışıksa Johnson (seyreklikten kazanır). Negatif olmayan ağırlıkta $V \times$ Dijkstra da bir seçenektir.
İki algoritma **negatif çevrim** karşısında da **aynı tanığı** verir: APSP, negatif çevrimi olan bir çizgede tanımsızdır (mesafe $-\infty$'a düşer). Floyd-Warshall bunu köşegende yakalar ($d(v, v) < 0$); Johnson süpernode-Bellman-Ford adımında $-\infty$ görür ve `None` döndürerek iptal eder. @fig-fw-vs-johnson hem seçim haritasını (yatay FW $O(V^3)$ vs artan Johnson eğrisi) hem de bu ortak teşhisi gösterir: `build_bf_example` çizgesinde ($b \to c \to d \to b = -2$ çevrim) FW köşegeni $\{b, c, d\}$ düğümlerini negatif işaretler, Johnson `None` döner — **köşegen $< 0 \Leftrightarrow$ Johnson iptali**, 60 rastgele çizgede de birebir.
```{python}
#| label: fig-fw-vs-johnson
#| fig-cap: "APSP seçim: seyrek → Johnson, yoğun → FW (5 satır), negatif çevrimde ikisi de AYNI tanık (Demaine L17 §5; Johnson algoritmasının kendisi Ders 21/L14, Ku). SOL panel seçim haritası: x = kenar yoğunluğu E (seyrek V'den yoğun V²'ye), y = süre; Floyd-Warshall yatay O(V³) (amber, E'den bağımsız), Johnson eğri O(V² log V + V·E) (slate, E ile artar); kesişim E ≈ V²; seyrek bölge 'Johnson KAZANIR', yoğun bölge '~eşit'; 'FW = 5 satır kod' rozeti. SAĞ panel negatif-çevrim teşhisi: build_bf_example çizgesi (çevrim b→c→d→b = (−4)+3+(−1) = −2), çevrim düğümleri {b,c,d} amber 'd(v,v)<0' rozetli; iki teşhis kutusu — Floyd-Warshall köşegen d(v,v)<0 → {b,c,d}; Johnson Bellman-Ford → −∞ → None (APSP İPTAL); ⟺ köprüsü 'köşegen < 0 ⟺ Johnson iptali' (60 rastgele çizgede çapraz tanık). Veri MOTORDAN (assert): floyd_warshall(build_fw_example) == johnson == brute_apsp; fw_negative_cycle == []; floyd_warshall(build_bf_example) köşegen<0 düğümleri == fw_negative_cycle == ['b','c','d']; johnson(build_bf_example) is None."
#| fig-width: 12.0
#| fig-height: 5.8
# fig-fw-vs-johnson (L17 §5): APSP seçim haritası + negatif-çevrim teşhisi.
# Veri MOTORDAN (floyd_warshall + johnson + brute_apsp + fw_negative_cycle).
adj1, w1 = build_fw_example()
fw1 = floyd_warshall(adj1, w1)
jh1 = johnson(adj1, w1)
bf1 = brute_apsp(adj1, w1)
assert jh1 is not None
assert all(fw1[u][v] == jh1[u][v] for u in adj1 for v in adj1), (fw1, jh1)
assert all(fw1[u][v] == bf1[u][v] for u in adj1 for v in adj1), (fw1, bf1)
assert fw_negative_cycle(fw1) == [], fw_negative_cycle(fw1)
adj2, w2 = build_bf_example()
fw2 = floyd_warshall(adj2, w2)
cyc = fw_negative_cycle(fw2)
assert cyc == ["b", "c", "d"], cyc
assert johnson(adj2, w2) is None
diag_neg = sorted(v for v in fw2 if fw2[v][v] < 0)
assert diag_neg == cyc == ["b", "c", "d"], (diag_neg, cyc)
fig, (axL, axR) = plt.subplots(
1, 2, figsize=(12.0, 5.8), gridspec_kw={"width_ratios": [1.05, 1.0]})
fig.patch.set_facecolor(COL_WHITE)
# ---- SOL: seçim haritası ----
apply_style(axL)
V = 80.0
e_lo = V
e_hi = V * V
Es = [e_lo + (e_hi - e_lo) * t / 400.0 for t in range(401)]
c = 1.0 / (V * V * V)
fw_y = [c * (V ** 3) for _ in Es]
jo_y = [c * (V * V * math.log2(V) + V * e) for e in Es]
xs = [(e - e_lo) / (e_hi - e_lo) for e in Es]
e_star = V * V - V * math.log2(V)
x_star = (e_star - e_lo) / (e_hi - e_lo)
axL.axvspan(0.0, x_star, color=COL_AMBER_100, alpha=0.55, zorder=0)
axL.axvspan(x_star, 1.0, color=COL_BG, alpha=0.7, zorder=0)
axL.plot(xs, fw_y, color=COL_ACCENT, linewidth=3.0, zorder=4,
label="Floyd-Warshall O(V³)")
axL.plot(xs, jo_y, color=COL_PRIMARY, linewidth=2.6, zorder=4,
label="Johnson O(V² log V + V·E)")
y_star = c * (V ** 3)
axL.plot([x_star], [y_star], marker="o", markersize=8,
markerfacecolor=COL_WHITE, markeredgecolor=COL_AMBER_700,
markeredgewidth=2.2, zorder=6)
axL.annotate("kesişim:\nE ≈ V²",
xy=(x_star, y_star), xytext=(x_star - 0.06, y_star + 0.34),
ha="center", va="bottom", fontsize=8.5, color=COL_AMBER_700,
weight="bold",
arrowprops=dict(arrowstyle="-|>", color=COL_AMBER_700, lw=1.6),
zorder=7)
axL.text(x_star * 0.48, 0.18,
"seyrek graf\nJohnson KAZANIR\n(E ≪ V²)", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5)
axL.text(x_star + (1.0 - x_star) * 0.5, 1.18,
"yoğun graf\n~eşit\n(E → V²)", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", zorder=5)
axL.set_xlim(0.0, 1.0)
axL.set_ylim(0.0, 1.45)
axL.set_xticks([0.0, x_star, 1.0])
axL.set_xticklabels(["E ≈ V\n(seyrek)", "E ≈ V²", "E ≈ V²\n(yoğun)"],
fontsize=8.5)
axL.set_yticks([])
axL.set_xlabel("kenar yoğunluğu E →", fontsize=10, color=COL_TEXT)
axL.set_ylabel("çalışma süresi →", fontsize=10, color=COL_TEXT)
axL.set_title("APSP seçim haritası — hangi algoritma ne zaman?",
color=COL_TEXT, fontsize=11.5, weight="bold")
axL.legend(loc="upper left", fontsize=8.8, framealpha=0.95)
bx, by, bw, bh = 0.60, 0.30, 0.375, 0.30
axL.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.012,rounding_size=0.03",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=8,
transform=axL.transData))
axL.text(bx + bw * 0.5, by + bh * 0.66, "FW = 5 satır kod",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=9)
axL.text(bx + bw * 0.5, by + bh * 0.28,
"üçlü döngü · basit · in-place", ha="center", va="center",
fontsize=7.3, color=COL_AMBER_700, style="italic", zorder=9)
# ---- SAĞ: negatif-çevrim teşhisi ----
axR.set_facecolor(COL_WHITE)
_POS = {"a": (0.0, 2.05), "b": (1.05, 2.05), "c": (1.95, 1.30), "d": (1.05, 0.55)}
_BF_EDGES = [
("a", "b", -5, False),
("b", "c", -4, True),
("c", "d", 3, True),
("d", "b", -1, True),
]
_R = 0.18
ox_g, oy_g = 0.25, 2.05
cyc_set = set(cyc)
def _P(v):
x, y = _POS[v]
return (ox_g + x, oy_g + y)
for u, v, wt, on_cyc in _BF_EDGES:
ux, uy = _P(u)
vx, vy = _P(v)
ecol = COL_ACCENT if on_cyc else COL_SLATE_500
rad = 0.25 if (u, v) == ("d", "b") else 0.0
axR.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=12,
color=ecol, linewidth=2.6 if on_cyc else 1.9,
shrinkA=_R * 95, shrinkB=_R * 95, zorder=2,
connectionstyle=f"arc3,rad={rad}"))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("d", "b"):
mx -= 0.30
bg = COL_AMBER_100 if on_cyc else COL_WHITE
ec = COL_ACCENT if on_cyc else COL_SLATE_400
tcol = COL_AMBER_700 if on_cyc else COL_TEXT
axR.add_patch(FancyBboxPatch(
(mx - 0.14, my - 0.115), 0.28, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=bg, ec=ec, linewidth=1.6 if on_cyc else 1.0, zorder=6))
axR.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5, color=tcol, weight="bold", zorder=7)
for v in _POS:
px, py = _P(v)
hot = v in cyc_set
axR.add_patch(Circle(
(px, py), _R, facecolor=COL_AMBER_100 if hot else COL_BG,
edgecolor=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.4 if hot else 1.9, zorder=5))
axR.text(px, py, v, ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if hot else COL_TEXT, weight="bold", zorder=6)
if hot:
axR.text(px + _R + 0.02, py + _R - 0.02, "d(v,v)<0",
ha="left", va="bottom", fontsize=6.6, color=COL_AMBER_700,
weight="bold", zorder=7)
axR.text(ox_g + 1.0, oy_g - 0.10,
"çevrim b→c→d→b = (−4)+3+(−1) = −2 (negatif)",
ha="center", va="center", fontsize=7.8, color=COL_AMBER_700,
style="italic", zorder=6)
axR.text(ox_g + 1.0, oy_g + 2.55,
"Teşhis çizgesi (build_bf_example)", ha="center", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6)
# iki teşhis kutusu (alt)
ox_d, oy_d = 0.10, 0.70
bw2, bh2, gap2 = 2.30, 1.05, 0.40
x1 = ox_d
axR.add_patch(FancyBboxPatch(
(x1, oy_d), bw2, bh2, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3))
axR.text(x1 + 0.14, oy_d + bh2 - 0.20, "Floyd-Warshall", ha="left", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5)
axR.text(x1 + 0.14, oy_d + bh2 - 0.45, "köşegen d(v,v) < 0 ?", ha="left",
va="center", fontsize=8.2, color=COL_AMBER_700, zorder=5)
nodes_str = "{ " + ", ".join(cyc) + " }"
axR.text(x1 + bw2 * 0.5, oy_d + 0.42, nodes_str, ha="center", va="center",
fontsize=12.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
axR.text(x1 + bw2 * 0.5, oy_d + 0.16, "negatif-çevrim tanığı", ha="center",
va="center", fontsize=7.4, color=COL_AMBER_700, style="italic",
zorder=5)
x2 = ox_d + bw2 + gap2
axR.add_patch(FancyBboxPatch(
(x2, oy_d), bw2, bh2, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_SLATE_400, linewidth=2.0, zorder=3))
axR.text(x2 + 0.14, oy_d + bh2 - 0.20, "Johnson", ha="left", va="center",
fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=5)
axR.text(x2 + 0.14, oy_d + bh2 - 0.45, "Bellman-Ford → −∞ ?", ha="left",
va="center", fontsize=8.2, color=COL_SLATE_500, zorder=5)
axR.text(x2 + bw2 * 0.5, oy_d + 0.42, "None", ha="center", va="center",
fontsize=14, color=COL_PRIMARY, weight="bold",
family="monospace", zorder=5)
axR.text(x2 + bw2 * 0.5, oy_d + 0.16, "APSP İPTAL", ha="center", va="center",
fontsize=7.8, color=COL_SLATE_500, weight="bold", zorder=5)
midx = x2 - gap2 * 0.5
axR.text(midx, oy_d + bh2 * 0.5, "⟺", ha="center", va="center",
fontsize=16, color=COL_AMBER_700, weight="bold", zorder=6)
axR.text(ox_d + (2 * bw2 + gap2) * 0.5, oy_d - 0.32,
"iki algoritma AYNI tanığı verir: köşegen < 0 ⟺ Johnson iptali",
ha="center", va="center", fontsize=8.6, color=COL_TEXT,
weight="bold", zorder=5)
axR.text(ox_d + (2 * bw2 + gap2) * 0.5, oy_d - 0.58,
"(60 rastgele çizgede doğrulandı — çapraz tanık BİREBİR)",
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=5)
axR.set_title("Negatif çevrim → APSP tanımsız: AYNI teşhis",
color=COL_TEXT, fontsize=11.5, weight="bold")
axR.set_xlim(-0.20, 5.20)
axR.set_ylim(0.00, 4.95)
axR.set_aspect("equal")
axR.axis("off")
fig.suptitle(
"APSP seçim: seyrek → Johnson · yoğun → FW (5 satır) · negatif çevrimde "
"ikisi de AYNI tanığı verir (L17 §5)",
color=COL_TEXT, fontsize=12.0, weight="bold", y=0.99)
plt.tight_layout(rect=(0, 0, 1, 0.96))
plt.show()
```
## 6. Aritmetik Parantezleme: Kökü Tahmin Et {#sec-6-parantezleme-koku-tahmin}
**Problem.** Formül $a_0 \star_1 a_1 \star_2 \ldots a_{n-1}$ ($\star = +$ veya $\times$, $a_i$ tamsayı). Parantezleri istediğin gibi yerleştirip sonucu **maksimize** et. Örnek: $7 + 4 \times 3 + 5 \to ((7+4) \times (3+5)) = 88$.
İfade bir **ağaçtır**; en kolay tanımlanabilir özellik **kök** $=$ **son yapılan işlem**.
> *"guess which operation, star i, is evaluated last — or, in other words, at the root."* — Demaine, 30:51
Kök $\star_k$'yı tahmin et → solu (prefix) ve sağı (suffix) ayrışır; ama prefix-of-suffix gerektiğinden alt problem **substring** olmalı (prefix+suffix karışımı → daima substring).
@fig-paren-tree bu fikri motor üzerinde gösterir: kazanan ağaç $((7 + 4) \times (3 + 5)) = 88$ — kök $k = 2$ (yani $\times$), sol substring $(7+4) = 11$, sağ substring $(3+5) = 8$, $11 \times 8 = 88$ (Demaine'le birebir). Soldan-sağa naif değerlendirme ($((7+4) \times 3) + 5 = 38$) sub-optimaldir. Sağdaki substring tablosu $x(i, j, \max)$ üçgenini ($10$ hücre) ve kök-seçim oklarını gösterir; brute-force $4$ farklı parantezleme değeri ($\{24, 38, 39, 88\}$) verir, max $= 88$.
```{python}
#| label: fig-paren-tree
#| fig-cap: "Parantezleme: kök-tahmini (SON işlem) → O(n³) DP (Demaine L17 §6 İMZA, 30:51). SOL panel kazanan ifade ağacı: kök × (amber, 'kök = SON işlem'), sol + = (7+4)=11, sağ + = (3+5)=8, üst rozet 11 × 8 = 88; alt köşede alternatif KÖTÜ ağaç (((7+4)×3)+5) üstü çizik 'soldan-sağa = 38 ✗ sub-optimal'. SAĞ panel substring tablosu x(i,j,max): üçgen yerleşim 10 hücre (satır = başlangıç i, sütun = uzunluk j−i, taban x(i,i+1)=aᵢ), (0,4)=88 amber hedef; kök-seçim okları (0,4) ← (0,2) ve (2,4) (son işlem k=2 bölünmesi); alt rozet 4² substring × 2 opt × O(4) kök = O(n³), 4ⁿ olası parantezleme polinomda taranır (brute: 4 farklı değer, max=88). Veri MOTORDAN (assert): build_paren_example == ([7,4,3,5],[+,*,+]); paren_reconstruct == ('((7 + 4) × (3 + 5))', 88); choice[(0,4,max)] kök k=2 (×); xmax[(0,2)]=11, xmax[(2,4)]=8, 11×8=88; brute_paren_values max=88, 4 farklı değer; soldan-sağa=38 brute kümesinde."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-paren-tree (L17 §6 İMZA): kök-tahmini ifade ağacı + substring tablosu.
# Veri MOTORDAN (build_paren_example + paren_reconstruct + parenthesize + brute).
vals, ops = build_paren_example()
assert vals == [7, 4, 3, 5] and ops == ["+", "*", "+"]
expr, val = paren_reconstruct(vals, ops, opt="max")
assert val == 88 and expr == "((7 + 4) × (3 + 5))", expr
brute_set = brute_paren_values(vals, ops)
assert max(brute_set) == 88, brute_set
n_distinct = len(brute_set)
xmin, xmax, choice = parenthesize(vals, ops)
n = len(vals)
root_k, root_ol, root_om = choice[(0, n, "max")]
assert root_k == 2 and ops[root_k - 1] == "*"
left_val = xmax[(0, root_k)]
right_val = xmax[(root_k, n)]
assert left_val == 11 and right_val == 8 and left_val * right_val == 88
bad_val = ((vals[0] + vals[1]) * vals[2]) + vals[3]
assert bad_val == 38 and bad_val in brute_set
substrings = []
for i in range(n):
for j in range(i + 1, n + 1):
substrings.append((i, j, xmax[(i, j)]))
assert len(substrings) == 10
assert xmax[(0, 2)] == 11 and xmax[(2, 4)] == 8 and xmax[(0, 4)] == 88
fig = plt.figure(figsize=(12, 6))
gs = fig.add_gridspec(1, 2, width_ratios=[1.05, 1.0], wspace=0.14)
ax_tree = fig.add_subplot(gs[0, 0])
ax_tab = fig.add_subplot(gs[0, 1])
def _leaf(ax, x, y, label, hot=False):
wb, hb = 0.62, 0.5
ax.add_patch(FancyBboxPatch(
(x - wb / 2, y - hb / 2), wb, hb,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.0 if hot else 1.6, zorder=4))
ax.text(x, y, str(label), ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold", zorder=5)
def _opnode(ax, x, y, sym, r=0.42, big=False, sub=None):
circ = Circle((x, y), r, fc=COL_AMBER_300 if big else COL_BG,
ec=COL_ACCENT if big else COL_PRIMARY,
linewidth=3.0 if big else 1.8, zorder=4)
ax.add_patch(circ)
ax.text(x, y, sym, ha="center", va="center",
fontsize=18 if big else 14, color=COL_TEXT, weight="bold", zorder=5)
if sub is not None:
ax.text(x + r + 0.30, y, sub, ha="left", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5,
style="italic")
def _edge(ax, x0, y0, x1, y1, hot=False):
ax.plot([x0, x1], [y0, y1],
color=COL_AMBER_600 if hot else COL_SLATE_500,
linewidth=2.4 if hot else 1.6, zorder=2, solid_capstyle="round")
root_xy = (2.5, 5.4)
lplus_xy = (1.3, 4.0)
rplus_xy = (3.7, 4.0)
l7, l4, l3, l5 = (0.8, 2.7), (1.8, 2.7), (3.2, 2.7), (4.2, 2.7)
_edge(ax_tree, *root_xy, *lplus_xy, hot=True)
_edge(ax_tree, *root_xy, *rplus_xy, hot=True)
_edge(ax_tree, *lplus_xy, *l7)
_edge(ax_tree, *lplus_xy, *l4)
_edge(ax_tree, *rplus_xy, *l3)
_edge(ax_tree, *rplus_xy, *l5)
_opnode(ax_tree, *root_xy, "×", r=0.46, big=True, sub="kök = SON işlem")
_opnode(ax_tree, *lplus_xy, "+")
_opnode(ax_tree, *rplus_xy, "+")
_leaf(ax_tree, *l7, 7, hot=True)
_leaf(ax_tree, *l4, 4, hot=True)
_leaf(ax_tree, *l3, 3, hot=True)
_leaf(ax_tree, *l5, 5, hot=True)
def _value_badge(ax, x, y, text):
ax.add_patch(FancyBboxPatch(
(x - 0.55, y - 0.24), 1.10, 0.48,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=6))
ax.text(x, y, text, ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=7)
_value_badge(ax_tree, lplus_xy[0] - 0.05, 3.35, f"(7+4)={left_val}")
_value_badge(ax_tree, rplus_xy[0] + 0.05, 3.35, f"(3+5)={right_val}")
ax_tree.add_patch(FancyBboxPatch(
(root_xy[0] - 1.05, 5.95), 2.10, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.12",
fc=COL_ACCENT, ec=COL_AMBER_700, linewidth=2.2, zorder=6))
ax_tree.text(root_xy[0], 6.26, f"{left_val} × {right_val} = {val}",
ha="center", va="center", fontsize=14, color=COL_TEXT,
weight="bold", zorder=7)
ax_tree.text(2.5, 1.95,
"kök = SON yapılan işlem — en kolay tahmin edilen özellik\n"
"(Demaine 30:51): sol/sağ substring bağımsız alt problem",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=5)
ax_tree.text(2.5, 6.95, "Kazanan ağaç: " + expr + f" = {val}",
ha="center", va="center", fontsize=11.5, color=COL_PRIMARY,
weight="bold")
bx, by = 0.55, 0.10
ax_tree.add_patch(FancyBboxPatch(
(bx - 0.45, by - 0.30), 3.55, 1.55,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.2, zorder=1))
m_root = (bx + 1.55, by + 0.95)
m_x = (bx + 0.85, by + 0.50)
m_5 = (bx + 2.45, by + 0.50)
m_711 = (bx + 0.35, by + 0.08)
m_3 = (bx + 1.35, by + 0.08)
_edge(ax_tree, *m_root, *m_x)
_edge(ax_tree, *m_root, *m_5)
_edge(ax_tree, *m_x, *m_711)
_edge(ax_tree, *m_x, *m_3)
_opnode(ax_tree, *m_root, "+", r=0.22)
_opnode(ax_tree, *m_x, "×", r=0.22)
for (mx, my), lbl in ((m_5, "5"), (m_711, "(7+4)"), (m_3, "3")):
ax_tree.text(mx, my, lbl, ha="center", va="center", fontsize=8,
color=COL_SLATE_500, weight="bold", zorder=5,
bbox=dict(boxstyle="round,pad=0.15", fc=COL_BG,
ec=COL_SLATE_400, linewidth=1.0))
ax_tree.plot([bx - 0.30, bx + 2.85], [by + 0.55, by + 0.55],
color=COL_AMBER_700, linewidth=2.4, zorder=8)
ax_tree.text(bx + 1.30, by - 0.12,
f"soldan-sağa = {bad_val} ✗ (sub-optimal)",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=8)
ax_tree.set_xlim(-0.2, 5.2)
ax_tree.set_ylim(-0.4, 7.4)
ax_tree.set_aspect("equal")
ax_tree.axis("off")
cell_w, cell_h = 1.18, 0.92
x_org, y_org = 0.4, 3.85
cell_pos = {}
for (i, j, xv) in substrings:
length = j - i
col = length - 1
row = i
x = x_org + col * cell_w
y = y_org - row * cell_h
cx, cy = x + cell_w * 0.5, y + cell_h * 0.5
cell_pos[(i, j)] = (x, y, cx, cy)
is_root = (i == 0 and j == n)
base = (length == 1)
if is_root:
fc, ec, lw = COL_ACCENT, COL_AMBER_700, 2.8
elif base:
fc, ec, lw = COL_BG, COL_SLATE_400, 1.4
else:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 1.8
ax_tab.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.92, cell_h * 0.88, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax_tab.text(cx - cell_w * 0.02, y + cell_h * 0.62,
f"x({i},{j})", ha="center", va="center",
fontsize=8.0, color=COL_SLATE_500, zorder=5)
ax_tab.text(cx - cell_w * 0.02, y + cell_h * 0.26, str(xv),
ha="center", va="center", fontsize=12.5,
color=COL_TEXT, weight="bold", zorder=5)
def _cell_arrow(src, dst, rad):
_, _, sx, sy = cell_pos[src]
_, _, dx, dy = cell_pos[dst]
ax_tab.add_patch(FancyArrowPatch(
(dx, dy), (sx, sy), arrowstyle="-|>", mutation_scale=15,
color=COL_AMBER_700, linewidth=2.2, zorder=6,
shrinkA=24, shrinkB=24, connectionstyle=f"arc3,rad={rad}"))
_cell_arrow((0, 4), (0, 2), 0.32)
_cell_arrow((0, 4), (2, 4), -0.32)
_, _, rcx, rcy = cell_pos[(0, n)]
ax_tab.text(rcx, y_org + cell_h * 0.88 + 0.55,
f"kök: son işlem k={root_k} (×)\n→ x(0,2) · x(2,4)",
ha="center", va="center", fontsize=8.4, color=COL_AMBER_700,
weight="bold", zorder=6)
ax_tab.text((x_org + 1.9), y_org + cell_h + 1.50,
"Substring tablosu x(i, j, max) — her hücre bir alt-ifadenin max'ı",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold")
ax_tab.text((x_org + 1.9), y_org + cell_h + 1.18,
"satır = başlangıç i · sütun = uzunluk (j−i) · taban: x(i,i+1)=aᵢ",
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500,
style="italic")
ax_tab.text((x_org + 1.9), y_org - 3.55,
f"{n}² substring × 2 opt (min,max) × O({n}) kök = O(n³)\n"
f"4ⁿ olası parantezleme → polinomda taranır "
f"(brute: {n_distinct} farklı değer, max={max(brute_set)})",
ha="center", va="center", fontsize=9.2, color=COL_AMBER_700,
weight="bold",
bbox=dict(boxstyle="round,pad=0.5", fc=COL_BG,
ec=COL_ACCENT, linewidth=1.6))
ax_tab.set_xlim(-0.1, x_org + n * cell_w + 0.5)
ax_tab.set_ylim(y_org - 4.2, y_org + cell_h + 1.9)
ax_tab.set_aspect("equal")
ax_tab.axis("off")
fig.suptitle("Parantezleme: kök-tahmini (SON işlem) → O(n³) DP",
fontsize=13, color=COL_TEXT, weight="bold", y=0.99)
plt.show()
```
## 7. Negatif Sayılar: Min/Max Genişletmesi {#sec-7-negatif-min-max}
**Çalışılan Örnek — neden min de gerek.** Sayılar negatif olabilirse, "maksimize için iki yanı maksimize et" çöker: iki **negatif** sayının çarpımı **pozitif büyük** olur. Örn. $7 + (-4) \times 3 + (-5)$.
> *"when we take a product of two negative numbers, we get a positive number."* — Demaine, 34:50
Çözüm: **subproblem expansion** — hem **min** hem **max** sakla. **S:** $x(i, j, \mathrm{opt})$, $\mathrm{opt} \in \{\min, \max\} = a[i..j)$ alt-ifadesinin opt değeri.
> *"If I can solve max and min, I'll know the entire range that I could get."* — Demaine, 35:38
@fig-paren-minmax bu işaret-çevirme mantığını motor üzerinde gösterir: kazanan ağaç $(7 + ((-4) \times (3 + (-5)))) = 15$. Kritik adım, sağ alt-ifade $(3 + (-5)) = -2$'nin **minimize** edilmesidir; çünkü $(-4) \times (-2) = +8$ büyük pozitif verir ve $7 + 8 = 15$. "İki yanı da maksimize et" stratejisi burada çöker — onun yerine her substring için $[\min, \max]$ çifti (aralık aritmetiği) saklanır, çarpımda dört kombinasyon denenir.
```{python}
#| label: fig-paren-minmax
#| fig-cap: "Negatif sayılar: min/max genişletmesi (Demaine L17 §7-8, 34:50). Kazanan ağaç (7 + ((−4) × (3 + (−5)))) = 15: kök +, sol yaprak 7, sağ alt-ağaç × ('işaret çevirme', amber, (−4)·(−2) = +8), onun sağı + 'min' rozetli ((3+(−5)) = −2 MİNİMİZE edildi). KRİTİK SEZGİ: max'ı büyütmek için sağ alt-ifadeyi minimize et çünkü negatif × negatif = pozitif büyük; '7 + 8 = 15'. Sağ kutu 'Neden HEM min HEM max?': iki yanı da maksimize ÇÖKER (Demaine 34:50), pozitif büyük için EN KÜÇÜK (en negatif) çarpan gerekir → her substring için HEM min HEM max sakla (×2 expansion), çarpımda 4 kombinasyon (min·min, min·max, max·min, max·max). Alt not: aralık aritmetiği [min, max] çifti substring'in TÜM ulaşılabilir değerlerini sınırlar. Veri MOTORDAN (assert): build_paren_negative_example == ([7,−4,3,−5],[+,*,+]); paren_reconstruct == ('(7 + ((-4) × (3 + (-5))))', 15); xmin[(2,4)] == −2; (−4)·(−2) = 8; 7+8 = 15; choice[(0,4,max)]=(1,min,max); choice[(1,4,max)]=(2,min,min); brute_paren_values max=15."
#| fig-width: 11.5
#| fig-height: 6.0
# fig-paren-minmax (L17 §7-8): negatif → min/max genişletmesi. Veri MOTORDAN.
nv, no = build_paren_negative_example()
assert nv == [7, -4, 3, -5] and no == ["+", "*", "+"]
expr, val = paren_reconstruct(nv, no, "max")
assert expr == "(7 + ((-4) × (3 + (-5))))", repr(expr)
assert val == 15, val
brute = brute_paren_values(nv, no)
assert max(brute) == 15, max(brute)
xmin, xmax, choice = parenthesize(nv, no)
assert xmin[(2, 4)] == -2 and xmax[(2, 4)] == -2
sub_val = xmin[(2, 4)]
prod = nv[1] * sub_val
assert prod == 8 and 7 + prod == val == 15
assert choice[(0, 4, "max")] == (1, "min", "max"), choice[(0, 4, "max")]
assert choice[(1, 4, "max")] == (2, "min", "min"), choice[(1, 4, "max")]
assert xmax[(1, 4)] == 8
fig, ax = plt.subplots(figsize=(11.5, 6.0))
def _node(x, y, label, *, kind="op", wb=0.78, hb=0.66, badge=None,
badge_color=COL_SLATE_500, badge_fc=COL_BG, val_label=None,
val_color=COL_SLATE_500):
if kind == "leaf":
fc, ec, lw, tc = COL_WHITE, COL_PRIMARY, 1.7, COL_TEXT
elif kind == "min":
fc, ec, lw, tc = COL_BG, COL_PRIMARY, 2.6, COL_TEXT
elif kind == "flip":
fc, ec, lw, tc = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
else:
fc, ec, lw, tc = COL_BG, COL_PRIMARY, 2.0, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x - wb / 2, y - hb / 2), wb, hb,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=4))
ax.text(x, y, label, ha="center", va="center", fontsize=15,
color=tc, weight="bold", zorder=6)
if val_label is not None:
ax.text(x, y - hb / 2 - 0.20, val_label, ha="center", va="center",
fontsize=10, color=val_color, weight="bold", zorder=6)
if badge is not None:
bw = 0.30 + 0.115 * len(badge)
ax.add_patch(FancyBboxPatch(
(x + wb / 2 - 0.05, y + hb / 2 - 0.10), bw, 0.34,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=badge_fc, ec=badge_color, linewidth=1.8, zorder=7))
ax.text(x + wb / 2 - 0.05 + bw / 2, y + hb / 2 + 0.07, badge,
ha="center", va="center", fontsize=8.5, color=badge_color,
weight="bold", zorder=8)
def _edge2(x0, y0, x1, y1, *, hot=False):
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-", mutation_scale=10,
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.6 if hot else 1.6,
shrinkA=16, shrinkB=16, zorder=2))
xr, yr = 3.0, 5.0
x7, y7 = 1.4, 3.6
xm, ym = 4.6, 3.6
xn4, yn4 = 3.5, 2.1
xp, yp = 5.7, 2.1
x3, y3 = 4.9, 0.6
xn5, yn5 = 6.5, 0.6
_edge2(xr, yr, x7, y7)
_edge2(xr, yr, xm, ym, hot=True)
_edge2(xm, ym, xn4, yn4, hot=True)
_edge2(xm, ym, xp, yp, hot=True)
_edge2(xp, yp, x3, y3)
_edge2(xp, yp, xn5, yn5)
_node(xr, yr, "+", kind="op", val_label="= 15", val_color=COL_AMBER_700)
_node(x7, y7, "7", kind="leaf")
_node(xm, ym, "×", kind="flip",
badge="işaret çevirme", badge_color=COL_AMBER_700, badge_fc=COL_AMBER_100,
val_label="(-4)·(-2) = +8", val_color=COL_AMBER_700)
_node(xn4, yn4, "-4", kind="leaf")
_node(xp, yp, "+", kind="min",
badge="min", badge_color=COL_PRIMARY, badge_fc=COL_BG,
val_label="(3+(-5)) = -2", val_color=COL_PRIMARY)
_node(x3, y3, "3", kind="leaf")
_node(xn5, yn5, "-5", kind="leaf")
ax.text(xr - 1.05, yr + 0.05, "7 + 8 = 15", ha="right", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(3.0, 6.45, "Kazanan ağaç: (7 + ((-4) × (3 + (-5)))) = 15",
ha="center", va="center", fontsize=14, color=COL_TEXT, weight="bold")
ax.text(3.0, 6.02,
"max'ı büyütmek için sağ alt-ifadeyi MİNİMİZE et: negatif × negatif = pozitif büyük",
ha="center", va="center", fontsize=10, color=COL_SLATE_500, style="italic")
bx, by, bw, bh = 8.05, 2.05, 3.30, 4.25
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=3))
ax.text(bx + bw / 2, by + bh - 0.32, "Neden HEM min HEM max?",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold")
box_lines = [
"\"Maksimize için iki yanı da",
"maksimize et\" → ÇÖKER",
"(Demaine 34:50).",
"",
"Çünkü negatif çarpan işareti",
"ters çevirir: pozitif büyük",
"için EN KÜÇÜK (en negatif)",
"çarpan gerekir.",
"",
"→ her substring için HEM min",
" HEM max sakla (×2 expansion)",
"→ çarpımda 4 kombinasyon:",
" min·min, min·max,",
" max·min, max·max",
]
ty = by + bh - 0.82
for ln in box_lines:
weight = "bold" if ("ÇÖKER" in ln or "×2" in ln or "4 kombinasyon" in ln) else "normal"
col = COL_AMBER_700 if ("ÇÖKER" in ln or "×2" in ln or "4 kombinasyon" in ln) else COL_TEXT
ax.text(bx + 0.18, ty, ln, ha="left", va="center", fontsize=9.0,
color=col, weight=weight, zorder=5)
ty -= 0.235
ax.add_patch(FancyBboxPatch(
(0.6, -0.55), 10.7, 0.62, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.6, zorder=3))
ax.text(5.95, -0.24,
"Aralık aritmetiği: her alt-ifade için [min, max] çifti, o substring'in TÜM "
"ulaşılabilir değerlerini sınırlar.",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.set_xlim(0.3, 11.6)
ax.set_ylim(-0.85, 6.75)
ax.set_aspect("equal")
ax.axis("off")
fig.tight_layout()
plt.show()
```
## 8. Parantezleme Recurrence ve O(n³) {#sec-8-parantezleme-recurrence}
**R:** kök $k$'yı + sol/sağ için $\mathrm{opt}_L, \mathrm{opt}_R$'yi kaba kuvvetle dene:
$$x(i, j, \mathrm{opt}) = \mathrm{opt} \text{ over } \{\, x(i, k, \mathrm{opt}_L) \star_k x(k, j, \mathrm{opt}_R) : i < k < j,\; \mathrm{opt}_L, \mathrm{opt}_R \in \{\min, \max\} \,\}$$
(Min/max için $4$ kombinasyon — çarpımda işaretler karışık, hepsini dene; toplamda yalnız min-min/max-max gerekir.) **T:** $j - i$ artan (substring). **B:** $x(i, i+1, \mathrm{opt}) = a_i$. **O:** $x(0, n, \max)$. **Süre:** $n^2$ substring $\times\, 2$ (opt) $\times\, O(n)$ ($k$) $= O(n^3)$. ($4^n$ parantezlemeyi polinomda tarıyoruz — subproblem expansion sayesinde.)
Bu, @fig-paren-tree ve @fig-paren-minmax'in formel özetidir: kökü tahmin etmek substring alt problemlerini doğurur ($O(n^2)$ tane), her birinde $\min/\max$ ikilemesi ($\times 2$) ve $k$ taraması ($O(n)$) vardır.
## 9. Piyano Parmaklama: State = Parmak {#sec-9-piyano-state-parmak}
**Problem.** Nota dizisi $t_0 \ldots t_{n-1}$, $F$ parmak. Geçiş zorluğu $d(t, f, t', f')$ (notayı $t$'yi $f$ parmağıyla, sonra $t'$'yü $f'$ ile çalmanın zorluğu). Toplam zorluğu minimize edip her notaya parmak ata.
**Çalışılan Örnek — state expansion.** Naif suffix yetmez: $d$ dört parametreli, "şu anki parmağı" bilmeden iki nota arası zorluğu hesaplayamayız. Çözüm: alt problemi **başlangıç parmağıyla** kısıtla.
**S:** $x(i, f) = t_i$'yi **$f$ parmağıyla** başlayarak sonek $t_i \ldots t_{n-1}$'i çalmanın min toplam zorluğu (alt problem $\times F$ genişletmesi). **R:** bir sonraki parmak $f'$'yü tahmin et:
$$x(i, f) = \min \text{ over } f' \;\{\, x(i+1, f') + d(t_i, f, t_{i+1}, f') \,\}$$
**O:** $\min_f x(0, f)$. **Süre:** $n \cdot F$ alt problem $\times\, O(F) = O(n \cdot F^2)$ ($F$ sabit → doğrusal).
@fig-piano-state örneği motor üzerinde çözer: $6$ notalık melodi $[60, 64, 62, 67, 65, 60]$, $F = 5$. Min toplam zorluk $6$, optimal atama $[0, 2, 0, 4, 2, 0]$ ($0$-indeksli; $1$-indeksli gösterimde $1./3./1./5./3./1.$ parmak), $F^n$ kaba kuvvet de $6$ verir. Alt panel $x(i, f)$ tablosunu ($6 \times 5$) ve kazanan zincir oklarını gösterir. Bu örnek **sentetik** bir zorluk fonksiyonu kullanır (`default_difficulty` $= |\Delta\text{nota} - \Delta\text{parmak}| + $ ters-yön cezası $2$); dersin gerçek $d$'si soyuttur — buradaki amaç state-genişletmesini somutlaştırmaktır, gerçek parmaklama tavsiyesi değil.
```{python}
#| label: fig-piano-state
#| fig-cap: "Piyano parmaklama: state = parmak DP (Demaine L17 §9 İMZA, 1:03:09). ÜST panel: 6 nota zaman-çizgisi (y = perde 60-67) + seçilen parmak rozetleri (motor assign'dan, 0-indeksli +1 gösterim, yani 1./3./1./5./3./1. parmak) + ardışık geçiş maliyetleri d (sentetik default_difficulty), Σd = 2+0+1+0+3 = 6. ALT panel: x(i,f) tablosu (6 nota × 5 parmak) motor değerleriyle; kazanan hücre zinciri amber oklar; O = min_f x(0,f) = 6 işareti; recurrence kutusu x(i,f) = min_{f₂} [x(i+1,f₂) + d(tᵢ,f,tᵢ₊₁,f₂)], taban x(n−1,f)=0; O(n·F²) rozeti (state = parmak ×F genişletme); Demaine 1:03:09 'state sayısı küçükse alt problemi state ile ÇARP'. NOT: d SENTETİK örnek-fonksiyon (dersin d'si soyut). Veri MOTORDAN (assert): build_piano_example == ([60,64,62,67,65,60], 5); piano_fingering → (6, [0,2,0,4,2,0]); brute_fingering == 6; geçiş maliyetleri trans == [2,0,1,0,3], Σ=6; tablo satırları motordan birebir."
#| fig-width: 11.5
#| fig-height: 6.5
# fig-piano-state (L17 §9 İMZA): parmaklama state-DP. Veri MOTORDAN.
notes, F = build_piano_example()
assert notes == [60, 64, 62, 67, 65, 60] and F == 5
d_total, assign = piano_fingering(notes, F)
assert d_total == 6 and assign == [0, 2, 0, 4, 2, 0]
assert brute_fingering(notes, F) == 6
n = len(notes)
trans = [
default_difficulty(notes[i], assign[i], notes[i + 1], assign[i + 1])
for i in range(n - 1)
]
assert sum(trans) == 6 and trans == [2, 0, 1, 0, 3], trans
x = {(n - 1, f): 0 for f in range(F)}
nxt = {}
for i in range(n - 2, -1, -1):
for f in range(F):
best, bf = INF, None
for f2 in range(F):
cc = x[(i + 1, f2)] + default_difficulty(notes[i], f, notes[i + 1], f2)
if cc < best:
best, bf = cc, f2
x[(i, f)] = best
nxt[(i, f)] = bf
f0 = min(range(F), key=lambda f: x[(0, f)])
assert f0 == assign[0] and x[(0, f0)] == 6
expected_table = {
0: [6, 7, 8, 9, 10],
1: [6, 5, 4, 5, 6],
2: [4, 5, 6, 7, 8],
3: [7, 6, 5, 4, 3],
4: [5, 4, 3, 2, 1],
5: [0, 0, 0, 0, 0],
}
for i in range(n):
assert [x[(i, f)] for f in range(F)] == expected_table[i], i
chain = [(i, assign[i]) for i in range(n)]
fig = plt.figure(figsize=(11.5, 6.5))
gs = fig.add_gridspec(2, 1, height_ratios=[1.0, 1.35], hspace=0.34)
ax_top = fig.add_subplot(gs[0])
ax_bot = fig.add_subplot(gs[1])
PITCH_MIN, PITCH_MAX = 60, 67
x_step = 1.0
xs = [k * x_step for k in range(n)]
def _pitch_to_y(p):
return (p - PITCH_MIN) / (PITCH_MAX - PITCH_MIN) * 2.2
for p in range(PITCH_MIN, PITCH_MAX + 1):
yy = _pitch_to_y(p)
ax_top.plot([xs[0] - 0.55, xs[-1] + 0.55], [yy, yy],
color=COL_SLATE_400, linewidth=0.6, alpha=0.35, zorder=0)
ax_top.text(xs[0] - 0.62, _pitch_to_y(PITCH_MAX), "perde 67",
ha="right", va="center", fontsize=7.5, color=COL_SLATE_500)
ax_top.text(xs[0] - 0.62, _pitch_to_y(PITCH_MIN), "perde 60",
ha="right", va="center", fontsize=7.5, color=COL_SLATE_500)
note_y = [_pitch_to_y(p) for p in notes]
ax_top.plot(xs, note_y, color=COL_PRIMARY, linewidth=1.4, alpha=0.55,
zorder=2, linestyle="-")
for i in range(n - 1):
xm = (xs[i] + xs[i + 1]) / 2.0
ym = (note_y[i] + note_y[i + 1]) / 2.0
cost = trans[i]
hot = cost > 0
ax_top.text(xm, ym + 0.30, f"d={cost}", ha="center", va="center",
fontsize=8.5,
color=COL_AMBER_700 if hot else COL_SLATE_500,
weight="bold" if hot else "normal", zorder=4,
bbox=dict(boxstyle="round,pad=0.16", fc=COL_WHITE,
ec=COL_AMBER_300 if hot else COL_SLATE_400,
linewidth=0.9, alpha=0.92))
for k in range(n):
xk, yk = xs[k], note_y[k]
ax_top.add_patch(FancyBboxPatch(
(xk - 0.18, yk - 0.16), 0.36, 0.32,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=5))
ax_top.text(xk, yk, str(notes[k]), ha="center", va="center",
fontsize=8.5, color=COL_TEXT, weight="bold", zorder=6)
ax_top.text(xk, 2.62, f"t{k}", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, zorder=4)
finger_display = assign[k] + 1
byp = -0.62
ax_top.add_patch(FancyBboxPatch(
(xk - 0.20, byp - 0.20), 0.40, 0.40,
boxstyle="circle,pad=0.02",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=5))
ax_top.text(xk, byp, str(finger_display), ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=6)
ax_top.add_patch(FancyArrowPatch(
(xk, yk - 0.18), (xk, byp + 0.22), arrowstyle="-", mutation_scale=1,
color=COL_SLATE_400, linewidth=1.0, zorder=3, linestyle=":"))
ax_top.text(xs[0] - 0.62, -0.62, "parmak", ha="right", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold")
ax_top.set_title("Melodi + optimum parmaklama — toplam zorluk = 6 "
"(parmak rozetleri 1-indeksli gösterim)",
color=COL_TEXT, fontsize=11.5, weight="bold")
ax_top.text((xs[0] + xs[-1]) * 0.5, -1.18,
f"Σ d = {' + '.join(str(c) for c in trans)} = {sum(trans)}",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold",
bbox=dict(boxstyle="round,pad=0.3", fc=COL_AMBER_100, ec=COL_ACCENT,
linewidth=1.4))
ax_top.set_xlim(xs[0] - 1.3, xs[-1] + 1.4)
ax_top.set_ylim(-1.45, 2.95)
ax_top.axis("off")
cell_w, cell_h = 1.15, 0.66
tbl_x0, tbl_y0 = 0.0, 0.0
chain_set = set(chain)
for i in range(n):
cx = tbl_x0 + i * cell_w + cell_w * 0.5
ax_bot.text(cx, tbl_y0 + F * cell_h + 0.30,
f"t{i}\n(nota {notes[i]})", ha="center", va="center",
fontsize=8.5, color=COL_TEXT, weight="bold")
for f in range(F):
ry = tbl_y0 + (F - 1 - f) * cell_h + cell_h * 0.5
ax_bot.text(tbl_x0 - 0.30, ry, f"parmak {f+1}", ha="right", va="center",
fontsize=8.5, color=COL_TEXT, weight="bold")
for i in range(n):
for f in range(F):
cx = tbl_x0 + i * cell_w
cy = tbl_y0 + (F - 1 - f) * cell_h
is_chain = (i, f) in chain_set
ax_bot.add_patch(FancyBboxPatch(
(cx, cy), cell_w * 0.93, cell_h * 0.90, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if is_chain else COL_BG,
ec=COL_ACCENT if is_chain else COL_SLATE_400,
linewidth=2.6 if is_chain else 1.2, zorder=2))
ax_bot.text(cx + cell_w * 0.46, cy + cell_h * 0.45, str(x[(i, f)]),
ha="center", va="center",
fontsize=11 if is_chain else 10,
color=COL_AMBER_700 if is_chain else COL_TEXT,
weight="bold" if is_chain else "normal", zorder=4)
for idx in range(n - 1):
i, f = chain[idx]
i2, f2 = chain[idx + 1]
x_a = tbl_x0 + i * cell_w + cell_w * 0.46
y_a = tbl_y0 + (F - 1 - f) * cell_h + cell_h * 0.45
x_b = tbl_x0 + i2 * cell_w + cell_w * 0.46
y_b = tbl_y0 + (F - 1 - f2) * cell_h + cell_h * 0.45
ax_bot.add_patch(FancyArrowPatch(
(x_a + cell_w * 0.30, y_a), (x_b - cell_w * 0.30, y_b),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_600,
linewidth=2.0, zorder=5, connectionstyle="arc3,rad=-0.12"))
i0, f0c = chain[0]
oxp = tbl_x0 + i0 * cell_w + cell_w * 0.46
oy_cell = tbl_y0 + (F - 1 - f0c) * cell_h + cell_h * 0.45
ax_bot.add_patch(FancyArrowPatch(
(oxp, oy_cell + cell_h * 0.95), (oxp, oy_cell + cell_h * 0.50),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700,
linewidth=1.8, zorder=6))
table_right = tbl_x0 + n * cell_w
table_top = tbl_y0 + F * cell_h
ax_bot.text(tbl_x0 - 0.30, table_top + 0.30,
"O = min_f x(0, f) = 6", ha="right", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold")
rec_text = ("x(i, f) = min_{f₂} [ x(i+1, f₂) + d(tᵢ, f, tᵢ₊₁, f₂) ]\n"
"taban: x(n−1, f) = 0 · cevap: O = min_f x(0, f)")
ax_bot.text(table_right + 0.40, table_top - 0.05, rec_text,
ha="left", va="top", fontsize=9, color=COL_TEXT,
bbox=dict(boxstyle="round,pad=0.4", fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.4), zorder=6)
ax_bot.text(table_right + 0.40, table_top - 1.45,
"state = parmak (×F genişletme)\n"
"n·F alt problem × O(F) geçiş = O(n·F²)",
ha="left", va="top", fontsize=9, color=COL_AMBER_700, weight="bold",
bbox=dict(boxstyle="round,pad=0.35", fc=COL_AMBER_100, ec=COL_ACCENT,
linewidth=1.6), zorder=6)
ax_bot.text(table_right + 0.40, table_top - 2.75,
"Demaine 1:03:09 — \"state sayısı küçükse\nalt problemi state ile ÇARP\"",
ha="left", va="top", fontsize=8, color=COL_SLATE_500, style="italic",
zorder=6)
ax_bot.set_title("x(i, f) tablosu — sonek-min zorluk (amber zincir = optimum çözüm)",
color=COL_TEXT, fontsize=11.5, weight="bold")
ax_bot.set_xlim(tbl_x0 - 2.4, table_right + 5.0)
ax_bot.set_ylim(tbl_y0 - 0.5, table_top + 0.75)
ax_bot.set_aspect("equal")
ax_bot.axis("off")
plt.show()
```
## 10. Genelleme: Çoklu Nota, Gitar {#sec-10-genelleme-coklu-nota-gitar}
State'i istediğin kadar zenginleştirebilirsin — yeter ki **state sayısı küçük** olsun.
> *"with subproblem expansion, I can capture almost any aspect of a problem that I want."* — Demaine, 1:03:03
Aynı anda çoklu nota → $t^F$ state ($t = $ anlık maks nota); gitar → ayrıca "hangi tel" seçimi. Her durumda: state'i alt problem koordinatına ekle, geçişleri $d$ ile yakala.
> *"As long as the number of states... is small, I can just multiply the number of subproblems by that state."* — Demaine, 1:03:09
(Bu, çizge çarpımıyla da yapılabilir ama DP metodik bir yol verir.) @fig-piano-state'in tek parmaklı state'i bu genelin en sade hâlidir: $F$ küçük olduğundan $\times F$ genişletme doğrusal kalır; çoklu nota/gitar eklenince state çarpan büyür ama yine polinom kaldığı sürece DP çalışır.
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d26}
1. **Subproblem expansion** $=$ alt probleme kısıt/koordinat ekleyip "state" hatırlamak.
2. **Bellman-Ford DP**: $\delta_k$ (en fazla $k$ kenar) kısıtı → çevrimliyi çevrimsize çevirir; $O(V \cdot E)$.
3. **Floyd-Warshall**: $d(u,v,k) = $ yalnız ilk $k$ düğüm; min iki terim → $O(V^3)$ (dense'te iyi).
4. **Floyd-Warshall vs Johnson**: dense → FW (basit); sparse → Johnson (hızlı).
5. **Parantezleme**: kökü (son işlem) tahmin et → substring; negatif için min+max; $O(n^3)$.
6. **Piyano parmaklama**: state = başlangıç parmağı; $\times F$ genişletme; $O(n \cdot F^2)$.
7. **Genel ilke**: küçük state'i alt problem koordinatına ekle, geçişleri kaba kuvvetle tara.
::: {.callout-important title="Tek Bir Cümle"}
Subproblem expansion, alt probleme bir koordinat ekleyerek geçmişi/state'i hatırlatır: Floyd-Warshall "ilk $k$ düğümü kullan" ($O(V^3)$), parantezleme "son işlem hangisi?" (min+max, $O(n^3)$), parmaklama "hangi parmak" ($O(n \cdot F^2)$) — küçük state'i çoğalt, geçişleri tara.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d26}
::: {.callout-note collapse="true" title="Soru 1: Floyd-Warshall'ın d(u,v,k) kısıtı nedir, ve neden recurrence yalnız iki terim (O(1)) olur?"}
**Cevap:**
$d(u, v, k) = $ "$u \to v$ en kısa yol, yalnız $\{u, v, 1 \ldots k\}$ düğümlerini ara-düğüm olarak kullanarak". $k$. düğümü eklerken yol ya **$k$'dan geçmez** ($= d(u, v, k-1)$) ya da **geçer** ($= d(u, k, k-1) + d(k, v, k-1)$, çünkü basit yolda $k$ bir kez kullanılır ve iki parça da yalnız ilk $k-1$ düğümü kullanır). Bu iki olasılık tüm durumları kapsar → min **iki terimli** → $O(1)$ özyineleme-dışı iş. $V^3$ alt problem $\times\, O(1) = O(V^3)$. (Bellman-Ford'da "tüm gelen kenarlar üzerinde döngü" $E$ terimi getirirdi; "ilk $k$ düğüm" kısıtı bunu $V$'ye çevirir.)
:::
::: {.callout-note collapse="true" title="Soru 2: Floyd-Warshall ne zaman Johnson'a tercih edilir, ne zaman edilmez?"}
**Cevap:**
Floyd-Warshall her zaman **$O(V^3)$**; Johnson **$O(V^2 \log V + V \cdot E)$**. **Dense** çizgede ($E \sim V^2$) ikisi de $\sim V^3$ ama Floyd-Warshall çok daha **basit** (5 satır) — onu tercih et (veya çizge küçükse). **Seyrek** çizgede ($E \sim V$) Johnson $V^2 \log V$'ye iner, Floyd-Warshall hâlâ $V^3$ harcar → Johnson çok daha iyi. Kural: dense/küçük biliyorsan FW; seyrek/karışıksa Johnson (seyreklikten kazanır).
:::
::: {.callout-note collapse="true" title="Soru 3: Parantezleme'de neden 'kökü tahmin et', ve negatif sayılar için neden hem min hem max gerekir?"}
**Cevap:**
İfade bir ağaçtır; "ilk işlem" karmaşık (ortada çarpım yapınca üç parça kalır) ama **kök = son işlem** kolayca tahmin edilir — kökü seçmek soldaki ve sağdaki alt-ifadeleri (substring'ler) doğal ayırır. Negatif sayılar için "maksimize $=$ iki yanı maksimize" çöker: iki büyük **negatif** sayının çarpımı büyük **pozitif** olur. Yani bazen alt-ifadeyi *minimize* etmek (çok negatif yapmak) genel maksimumu artırır. Çözüm: her substring için hem **min** hem **max** sakla (subproblem expansion $\times 2$); çarpımda dört min/max kombinasyonunu dene.
:::
::: {.callout-note collapse="true" title="Soru 4: Piyano parmaklamada neden alt problemi 'başlangıç parmağı f' ile genişletiyoruz?"}
**Cevap:**
Zorluk fonksiyonu $d(t, f, t', f')$ **dört** parametreli — iki nota arası geçişin zorluğu, hem şu anki parmağa ($f$) hem sonraki parmağa ($f'$) bağlı. Naif $x(i) = $ "sonek $t_i \ldots$'i en az zorlukla çal" tanımında, recurse ederken **şu anki parmağı** bilmediğimizden $d$'yi hesaplayamayız. Çözüm: alt problemi başlangıç parmağıyla kısıtla — $x(i, f) = $ "$t_i$'yi $f$ ile başlayarak…". Artık $f$ bilinir; sonraki parmak $f'$'yü kaba kuvvetle dener, $d(t_i, f, t_{i+1}, f')$'yi hesaplayabiliriz. Alt problem sayısı $\times F$ (sabit) → $O(n \cdot F^2)$, $F$ sabitse doğrusal.
:::
## Egzersizler {#sec-egzersizler-d26}
**Egzersiz 1.** Floyd-Warshall'ı küçük bir ağırlıklı çizgede elle çalıştır: $d(u,v,k)$ tablosunu $k = 0 \ldots V$ için doldur.
**Egzersiz 2.** Floyd-Warshall'ı Python'da yaz (üçlü iç içe döngü); $O(V^3)$ olduğunu ve dense'te $V \cdot E$'ye denk geldiğini göster.
**Egzersiz 3.** Aritmetik parantezlemeyi $7 + (-4) \times 3 + (-5)$ üzerinde $x(i,j,\min/\max)$ tablosuyla elle çöz; en büyük sonucu bul.
**Egzersiz 4.** Parantezleme recurrence'ında neden min/max'in $4$ kombinasyonunu denemenin yeterli olduğunu (aralık aritmetiği) açıkla.
**Egzersiz 5.** Piyano parmaklamayı iki notalık akorlara genişlet: state'in $t^F$'ye çıktığını ve sürenin $O(n \cdot t^{2F})$ olduğunu göster.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d26}
::: {.callout-warning title="Sonraki: Ders 27 (L18) — Dinamik Programlama 4 (pseudopolinom, DP FİNALİ)"}
**Ders 27 (L18): Dinamik Programlama 4** (pseudopolinom). Erik Demaine ile, DP serisinin **finali**: **integer alt problemler** ve **pseudopolinom zaman**. Rod cutting ve subset sum örnekleriyle, $n \cdot T$ gibi sürelerin neden "polinom değil ama yeterince iyi" olduğunu görür, tüm DP tekniklerini diagonal bir bakışla toparlarız. DP ünitesi Ders 24-27 (L16-L18) boyunca sürer ve **Ders 30 = Quiz 3 Gözden Geçirme** ile özetlenir.
**Ders 27 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 1 (Floyd-Warshall) ve 3 (parantezleme) çöz.
- Floyd-Warshall, parantezleme ve parmaklamanın SRTBOT'unu ezberden yaz.
- Ana cümleyi tekrar oku: *"Küçük state'i alt problem koordinatına ekle; geçişleri kaba kuvvetle tara."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d26}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Subproblem expansion** | Alt probleme kısıt/koordinat ekle; state hatırla | Böl. 1 |
| **Bellman-Ford DP** | $\delta_k$ (en fazla $k$ kenar); çevrimli → çevrimsiz; $O(V \cdot E)$ | Böl. 2 |
| **Floyd-Warshall** | $d(u,v,k) = $ ilk $k$ düğüm; min 2 terim; $O(V^3)$ | Böl. 3-4 |
| **FW vs Johnson** | dense → FW (basit); sparse → Johnson | Böl. 5 |
| **Parantezleme** | Kökü (son işlem) tahmin et → substring | Böl. 6 |
| **Min/max genişletme** | Negatif çarpım için hem min hem max sakla | Böl. 7-8 |
| **Parmaklama** | $x(i,f)$; state = parmak; $O(n \cdot F^2)$ | Böl. 9 |
| **Genel ilke** | Küçük state → koordinat; geçişleri tara | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d26}
::: {.callout-tip title="6 köprü"}
Bu dersin üç tekniği — vertex-prefix APSP, kök tahmini + min/max, state genişletmesi — ML, derleyici ve sistem mühendisliğindeki çok sayıda araca bağlanır; köprülerin özeti:
1. **Floyd-Warshall** → APSP mesafe matrisi, **transitif kapanış** (reachability), ağ analizi; ağırlıkları boole'e indirgersen aynı üçlü döngü erişilebilirliği verir.
2. **Parantezleme** → derleyici ifade optimizasyonu, **matris-zincir çarpımı** (matrix chain multiplication — hangi sırada çarpınca en az skaler çarpma?), sözdizimi ağacı kurma.
3. **Min/max genişletme** → **aralık aritmetiği**; optimizasyonda alt sınır + üst sınır birlikte; soyut-yorumlama (abstract interpretation) ve sağlamlık (robustness) analizleri.
4. **Piyano/gitar parmaklama** → **MIDI/müzik teknolojisi**, dizilim hizalama, **durum-makinesi DP'leri** (her geçişte küçük bir state taşı).
5. **State = koordinat** → durum-augmentasyonu; **OMSCS CS 6515'te DP tasarımının kalbi** — "bariz alt problem yetmiyorsa hangi koordinatı eklerim?" refleksi (state = koordinat).
6. **DP = Bellman icadı** → optimizasyon tarihi; "programming" $=$ optimizasyon (LP/IP ile aynı kök); "dynamic" $=$ aşama-aşama yerel kaba kuvvet.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Subproblem expansion, DP'nin en güçlü silahıdır: alt probleme küçük bir koordinat ekleyerek geçmişi/state'i hatırlarsın. Floyd-Warshall "yalnız ilk $k$ düğümü kullan" der ve $E$ terimini $V$'ye çevirip $O(V^3)$ verir. Parantezleme "son işlem (kök) hangisi?" diye sorar ve negatifler için hem min hem max saklar. Parmaklama "hangi parmakla başladım" durumunu taşır. Tek formül: küçük state'i alt problem sayısıyla çarp, geçişleri yerel kaba kuvvetle tara — neredeyse her problemin her yönünü yakalarsın.
:::
