---
title: "Problem Oturumu 9"
subtitle: "Pseudopolinom DP oturumu — 0/1 ve sınırsız knapsack, precomputation sinyali ve adversarial minimax"
---
::: {.callout-note title="Oturum bilgisi"}
- **Solomon'un videosu:** [YouTube — Problem Session 9](https://www.youtube.com/watch?v=KPkOkiwAlbY) (≈85 dk)
- **OCW sayfası:** [MIT 6.006 Problem Session 9](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_prob9/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 29 (PS9)
- **Hoca:** Justin Solomon
- **Okuma süresi:** ≈24 dk
- DP problem oturumlarının **İKİNCİSİ**; pseudopolinom dili "liberating" (Solomon 0:26).
:::
## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d29}
Dokuzuncu problem oturumu (Justin Solomon), **dinamik programlama** üzerine iki oturumun ikincisi; bu kez **pseudopolinom** DP odakta dört problemi **SRTBOT** çerçevesiyle çözer (@fig-concept-map). Solomon "bu set öncekinden kolaydı" der — çünkü pseudopolinom, runtime'da "kullanmaman gereken" sayısal parametreleri ($k$, $b$) kullanmaya izin verir, bu da recurrence kurmayı kolaylaştırır.
> *"we learned in class about pseudo polynomial time style dynamic programs. Somehow, that language is a little bit liberating."* — Solomon, 0:26
Beş problem planlanmıştı; Solomon **dördünü** işledi (9-5 "duvar örme" zaman yetmediği için atlandı — bkz. @sec-sonraki-d29 öncesi son not). Her problem "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir. Yeni temalar: **0/1 vs sınırsız knapsack**, **zaman ekseninin topolojik sıra vermesi**, **toplam-terimli runtime → precomputation sinyali**, ve **minimax (adversarial) DP**.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Problem Oturumu 9'un kavram haritası: kök (PS9) dört probleme dallanır ve ortadaki ortak tema düğümü dördünü birden yönlendirir. Problem 1 Coin-Crafting'i 0/1 knapsack ile çözer — her nesneden en fazla bir tane, j−1'e geçerek nesneyi tüketir, (n+1)² hücre × O(1) = O(n²) polinom. Problem 2 Tim the Beaver kariyer fuarını SINIRSIZ knapsack + çanta boşaltma ile çözer — aynı stant tekrar tekrar alınır, çanta dolunca eve gidip boşaltılır, zaman hep ileri aktığı için topolojik sırayı zaman verir, kb hücre × O(n) = O(nbk) pseudopolinom. Problem 3 Protein Parsing'i naif v1'den (string-karşılaştırma her adımda, O(|S|·|P|·k) iki dev çarpım) precompute v2'ye (hash + m üyelik tablosu) indirger; runtime'da çarpım değil TOPLAM görmek precomputation sinyalidir, O(k·|P| + k²·|S|). Problem 4 Lazy Egg Drop'u minimax DP ile çözer — yumurta adversarial, min içinde max; topolojik sıra harcanan kaynaktan değil belirsizliğin DARALMASINDAN gelir, O(n³k). Ortak tema — istenen runtime'ın şekli (toplam mı çarpım mı, hangi parametreler) çözümün yapısını ele verir — Solomon'un dört probleme de aynı kapıdan girmesini sağlar."
flowchart TD
R["Problem Oturumu 9<br/>(DP problem oturumlarının İKİNCİSİ — pseudopolinom)"] --> P1["Problem 1<br/>Coin-Crafting<br/>(0/1 knapsack, O(n²))"]
R --> P2["Problem 2<br/>Tim kariyer fuarı<br/>(sınırsız + boşaltma, O(nbk))"]
R --> P3["Problem 3<br/>Protein parsing<br/>(naif → precompute)"]
R --> P4["Problem 4<br/>Lazy egg drop<br/>(minimax / adversarial)"]
CORE["Ortak tema:<br/>runtime'ın ŞEKLİ çözümü ele verir<br/>(toplam mı çarpım mı, hangi parametreler)<br/>— pseudopolinom dili 'liberating'"]
CORE -.-> P1
CORE -.-> P2
CORE -.-> P3
CORE -.-> P4
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:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937
class R root
class P1,P2,P3,P4 branch
class CORE leaf
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 29 (PS9) motoru (_engine_PS9.py) + INF + Slate+Amber
# sabitleri (_viz.py). Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür
# hücreleri bu hücrede tanımlanan fonksiyonları (coin_craft, brute_coin_craft,
# career_fair, brute_career_fair, protein_v1/v2, brute_protein, egg_drop,
# egg_policy_sim, build_* ...) + COL_* globallerini + apply_style'ı IMPORT
# ETMEDEN kullanır. Notion'daki öğretim içeriği (görünür display python blokları)
# bu motorun tarif seviyesidir; burada tam, deterministik, test edilmiş sürüm
# yaşar (_smoke_PS9: 11/11 PASS).
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Standalone testte savefig
# kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
#
# Dosyadan import YOK: tüm DP motoru + INF burada self-contained INLINE →
# render dizininden bağımsız (kurs paritesi: PS6/PS8 emsali, düz INLINE).
# ============================================================================
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch
from matplotlib.gridspec import GridSpec
# ---------------------------------------------------------------------------
# _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 (aktif seçenek / kazanan zincir)
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu
# Türev amber tonları
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)
# Türev slate tonları
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# Naif/yavaş vurgu için soluk kırmızı (palet dışı, sadece "kötü yol" işareti)
COL_RED_FILL = "#fde2e2"
COL_RED_EC = "#c0504d"
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
# ===========================================================================
# _engine_PS9.py — PS9 problem motoru (4 problem, hepsi SRTBOT; INLINE).
# ===========================================================================
INF = float("inf")
# --- Problem 1: Coin-Crafting — 0/1 knapsack ---
def coin_craft(P, K, budget=None):
"""x(i, j) = i para ve İLK j nesneyle max gelir. R (2 seçenek): j'yi yapma
→ x(i, j−1); yap (i ≥ Kⱼ) → Pⱼ + x(i−Kⱼ, j−1). B: x(0, j) = x(i, 0) = 0.
O: x(n, n). (n+1)² × O(1) = O(n²). Döndürür: (max gelir, x tablosu)."""
n = len(P)
if budget is None:
budget = n
x = {}
for i in range(budget + 1):
x[(i, 0)] = 0
for j in range(1, n + 1):
for i in range(budget + 1):
best = x[(i, j - 1)] # j'yi yapma
if K[j - 1] <= i: # j'yi yap
best = max(best, P[j - 1] + x[(i - K[j - 1], j - 1)])
x[(i, j)] = best
return x[(budget, n)], x
def brute_coin_craft(P, K, budget=None):
"""Bağımsız tanık (2ⁿ bitmask): ΣK ≤ bütçe alt kümelerinde max ΣP."""
n = len(P)
if budget is None:
budget = n
best = 0
for mask in range(1 << n):
cost = sum(K[m] for m in range(n) if mask >> m & 1)
if cost <= budget:
best = max(best, sum(P[m] for m in range(n) if mask >> m & 1))
return best
def build_coin_craft_example():
return [8, 5, 11, 6, 3], [2, 1, 3, 2, 1]
# --- Problem 2: Kariyer Fuarı — sınırsız knapsack + çanta boşaltma ---
def career_fair(C, W, t, b, h, k):
"""x(i, j) = i dakika ve çantada j ağırlık-yeri kalmışken max havalılık.
R (max, 3 tip): pes → 0; stant m → Cₘ + x(i−tₘ−1, j−Wₘ) (uygunsa);
eve git → x(i−h−1, b) (yer b'ye SIFIRLANIR). T: zaman hep ileri akar.
B: x(0, j) = 0. O: x(k, b). kb × O(n) = O(nbk). Döndürür: (max, x)."""
n = len(C)
x = {}
for j in range(b + 1):
x[(0, j)] = 0
for i in range(1, k + 1):
for j in range(b + 1):
best = 0 # pes et
for m in range(n): # stant m'ye gir
ii, jj = i - t[m] - 1, j - W[m]
if ii >= 0 and jj >= 0 and C[m] + x[(ii, jj)] > best:
best = C[m] + x[(ii, jj)]
if i - h - 1 >= 0 and x[(i - h - 1, b)] > best:
best = x[(i - h - 1, b)] # eve git, boşalt
x[(i, j)] = best
return x[(k, b)], x
def brute_career_fair(C, W, t, b, h, k):
"""Bağımsız tanık (eylem-dizisi DFS): kalan süre/yer ile tüm eylem
dizilerini ileri-simülasyonla gez. Üstel; küçük k testi."""
n = len(C)
def rec(time_left, room):
best = 0
for m in range(n):
if t[m] + 1 <= time_left and W[m] <= room:
cand = C[m] + rec(time_left - t[m] - 1, room - W[m])
if cand > best:
best = cand
if h + 1 <= time_left and room < b: # boşaltmak anlamlıysa
cand = rec(time_left - h - 1, b)
if cand > best:
best = cand
return best
return rec(k, b)
def build_career_example():
return [10, 4], [2, 1], [1, 0], 2, 1, 9
# --- Problem 3: Protein Parsing — precomputation ---
def protein_v1(S, P):
"""Naif DP (v1): x(i) = S[i:] max marker sayısı. R: karakteri atla x(i+1)
VEYA uyan her marker m için 1 + x(i+|m|). String karşılaştırma her
seferinde → O(|S|·|P|·k) iki-dev-çarpım (yavaş)."""
n = len(S)
x = [0] * (n + 1)
for i in range(n - 1, -1, -1):
best = x[i + 1] # atla (değersiz parça)
for m in P:
if S.startswith(m, i) and 1 + x[i + len(m)] > best:
best = 1 + x[i + len(m)]
x[i] = best
return x[0]
def protein_v2(S, P, kmax):
"""Precompute DP (v2, Solomon 56:30): (1) P'yi hash kümesine al —
O(k·|P|); (2) m[i][j] = S[i:i+j] ∈ P tablosu — O(k²·|S|); (3) DP:
x(i) = max_{j=1..k} m[i][j] + x(i+j) — O(|S|·k). Toplam O(k·|P| + k²·|S|).
Döndürür: (değer, m tablosu)."""
n = len(S)
pset = set(P) # (1) hash
m = [[0] * (kmax + 1) for _ in range(n + 1)] # (2) üyelik tablosu
for i in range(n):
for j in range(1, min(kmax, n - i) + 1):
if S[i:i + j] in pset:
m[i][j] = 1
x = [0] * (n + 1) # (3) küçük DP
for i in range(n - 1, -1, -1):
best = 0
for j in range(1, min(kmax, n - i) + 1):
if m[i][j] + x[i + j] > best:
best = m[i][j] + x[i + j]
x[i] = best
return x[0], m
def brute_protein(S, P):
"""Bağımsız tanık (2^(|S|−1) kesim): tüm bölünmeler; değer = P'de olan
parça sayısı; max."""
n = len(S)
pset = set(P)
best = 0
for mask in range(1 << max(0, n - 1)):
cuts = [0] + [q + 1 for q in range(n - 1) if mask >> q & 1] + [n]
val = sum(1 for a, bnd in zip(cuts, cuts[1:]) if S[a:bnd] in pset)
best = max(best, val)
return best
def build_protein_example():
return "ACTGACTGA", ["ACT", "GA", "TGA", "CT"], 3
# --- Problem 4: Lazy Egg Drop — minimax DP ---
def egg_drop(h, k):
"""x(i, j, e) = belirsiz katlar [i..j] ve e yumurta kalmışken min TOPLAM
yükseklik (en kötü durum). R (MINIMAX): x = min_{f∈[i,j]} h[f] +
max( x(i, f−1, e−1) [kırıldı], x(f+1, j, e) [kırılmadı] ). T: belirsizlik
j−i KESİN azalır. B: j < i → 0; e = 0 ∧ j ≥ i → ∞. O: x(1, n, k).
n²k × O(n) = O(n³k). h 1-indeksli. Döndürür: (cevap, memo, choice)."""
n = len(h) - 1
memo, choice = {}, {}
def x(i, j, e):
if j < i:
return 0
if e == 0:
return INF
if (i, j, e) in memo:
return memo[(i, j, e)]
best, bf = INF, None
for f in range(i, j + 1):
cand = h[f] + max(x(i, f - 1, e - 1), x(f + 1, j, e))
if cand < best:
best, bf = cand, f
memo[(i, j, e)] = best
choice[(i, j, e)] = bf
return best
ans = x(1, n, k)
return ans, memo, choice
def egg_policy_sim(h, k):
"""BAĞIMSIZ TANIK (politika simülasyonu): DP politikasını (choice) HER
gerçek eşik t için oynat; biriken h[f] maliyetlerinin MAKSİMUMU ==
x(1, n, k) olmalı (adversarial = en kötü gerçek eşik). Döndürür:
(max maliyet, hepsi-doğru-buldu bool)."""
n = len(h) - 1
ans, memo, choice = egg_drop(h, k)
worst, all_correct = 0, True
for t in range(n + 1):
i, j, e, cost = 1, n, k, 0
while i <= j:
f = choice[(i, j, e)]
cost += h[f]
if f > t: # kırıldı
j, e = f - 1, e - 1
else: # kırılmadı
i = f + 1
found = j # daralan aralık → eşik
all_correct = all_correct and found == t
worst = max(worst, cost)
return worst, all_correct
def build_egg_example():
return [0, 1, 2, 3, 4, 5, 6], 2
```
::: {.callout-tip title="Yaklaşım — ortak strateji: istenen runtime'ın şeklini hocanın ipucu gibi oku"}
Dört problemin tamamı aynı refleksle başlar: önce alt problemi (Subproblem) tanımla, sonra "bu alt problemde hangi yerel kararı versem geri kalanı bir küçük alt probleme iner?" diye **yerel kaba kuvvet** uygula; bu recurrence'ı (Relation) verir. Pseudopolinom dili bu oturumda işi kolaylaştırır: runtime'da $k$ ve $b$ gibi sayısal parametreleri kullanmaya izin verince recurrence doğal akar. İncelik istenen runtime'ı bir teşhis aracı gibi okumakta: $O(nbk)$ gibi bir **çarpım** doğrudan tablo boyutu × hücre işidir; $O(k \lvert P \rvert + k^2 \lvert S \rvert)$ gibi bir **toplam** ise "DP dışında ön-işleme var" der; bir **min içinde max** ise adversarial bir minimax kurar. Bu oturum, DP kasını bu dört SRTBOT'la pseudopolinom yönünde çalıştırır.
:::
@fig-knapsack-pair iki knapsack varyantını yan yana motordan **gerçek** verilerle gösterir: solda Problem 1 (0/1, $O(n^2)$ polinom), sağda Problem 2 (sınırsız + çanta boşaltma, $O(nbk)$ pseudopolinom). Tek bir "kapasite içinde max değer" çekirdeği iki farklı kısıtla karşı karşıya gelir; figür her ikisini birden kapsar ve aşağıdaki iki problemin köprüsüdür.
```{python}
#| label: fig-knapsack-pair
#| fig-cap: "İki knapsack yan yana — Problem 1 ve Problem 2 İMZA. Veri MOTORDAN (P1: P=[8,5,11,6,3] K=[2,1,3,2,1] bütçe 5 → 19 = bitmask; P2: C=[10,4] W=[2,1] t=[1,0] b=2 h=1 k=9 → 24 = eylem-DFS). SOL P1 — 0/1 knapsack (her nesne ≤ 1 kez): 5 nesne kartı (P fiyat üst, K eritme alt), seçilenler (11+5+3) amber yıldızlı; bütçe çubuğu 5 para → 3+1+1 dolu; x(i,j) recurrence kutusu (yap → j−1'e GEÇ / yapma → j−1, her iki dalda nesne tüketilir); sonuç 19 rozeti; '(n+1)² × O(1) = O(n²) POLİNOM'. SAĞ P2 — SINIRSIZ + çanta boşaltma: zaman çizgisi 9 dk + motor-optimal eylem dizisi (stant0→eve→stant0→eve→stant1, aynı stant tekrar); çanta doluluk basamak grafiği (b=2'ye dayanınca EVE GİT → b'ye sıfırlanır amber ok); 'zaman HEP İLERİ → topolojik sıra (Solomon 30:00)'; sonuç 24 rozeti; 'kb × O(n) = O(nbk) PSEUDOpolinom (k, b runtime'da)'."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-knapsack-pair — PS9 P1/P2 İMZA: iki knapsack (0/1 vs sınırsız + boşaltma).
# Veri MOTORDAN (elle kopya YOK): build_coin_craft_example / coin_craft /
# brute_coin_craft (P1); build_career_example / career_fair / brute_career_fair (P2).
# Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, COL_*.
def _build_p2_timeline(C, W, t, b, h, k):
"""Motor-optimal senaryoyu ileri-simüle eder; zaman-çizgisi olaylarını döndürür.
stant0 → eve → stant0 → eve → stant1 (toplam 24, zaman 9). events =
[(label, t0, t1, room_before, room_after, award, kind)]."""
actions = [("stant", 0), ("eve", None), ("stant", 0), ("eve", None), ("stant", 1)]
events = []
time_now, room, total = 0, b, 0
for kind, mm in actions:
if kind == "stant":
dur = t[mm] + 1
room_after = room - W[mm]
assert room_after >= 0 and time_now + dur <= k
events.append((f"stant {mm}", time_now, time_now + dur, room,
room_after, C[mm], "stant"))
total += C[mm]
room = room_after
time_now += dur
else: # eve git → yer b'ye sıfırlanır
dur = h + 1
assert time_now + dur <= k
events.append(("EVE GİT", time_now, time_now + dur, room,
b, 0, "eve"))
room = b
time_now += dur
return events, total, time_now
def _draw_p1(ax, P, K, value):
"""5 nesne kartı (P / K), seçilenler amber, bütçe çubuğu, x(i,j) recurrence
kutusu, sonuç rozeti, karmaşıklık etiketi."""
n = len(P)
selected = {1, 2, 4} # 11 (idx2), 5 (idx1), 3 (idx4) — seçilen nesneler
sel_K = [K[i] for i in (2, 1, 4)] # 3, 1, 1 (bütçe çubuğu dolu hücreleri)
ax.text(2.6, 6.55, "P1 — 0/1 knapsack (her nesne ≤ 1 kez)", ha="center",
va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold")
card_w, card_h, gap, y0 = 0.92, 1.35, 0.18, 4.55
x_start = 0.10
for j in range(n):
x = x_start + j * (card_w + gap)
hot = j in selected
ax.add_patch(FancyBboxPatch(
(x, y0), card_w, card_h, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.6 if hot else 1.7, zorder=3))
cx = x + card_w * 0.5
ax.text(cx, y0 + card_h * 0.70, f"P={P[j]}", ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700 if hot else COL_TEXT,
weight="bold", zorder=5)
ax.text(cx, y0 + card_h * 0.30, f"K={K[j]}", ha="center", va="center",
fontsize=9.5, color=COL_SLATE_500, zorder=5)
ax.text(cx, y0 - 0.22, f"nesne {j}", ha="center", va="center",
fontsize=7.6, color=COL_SLATE_400, zorder=5)
if hot:
ax.scatter([cx], [y0 + card_h + 0.16], marker="*", s=130,
color=COL_ACCENT, edgecolor=COL_AMBER_700, linewidth=0.8,
zorder=6)
ax.text(2.6, y0 + card_h + 0.50, "seçilen ✶ : 11 + 5 + 3 = 19", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold")
bud = sum(sel_K) # 5 para tüketildi
total_budget = n # bütçe = n özdeş para = 5
by, bh = 3.55, 0.46
coin_w, cgap = 0.62, 0.10
bx0 = 0.55
ax.text(bx0 - 0.05, by + bh + 0.30, "bütçe: 5 para → 3 + 1 + 1 = 5 harcandı",
ha="left", va="center", fontsize=9, color=COL_TEXT, weight="bold")
for c in range(total_budget):
x = bx0 + c * (coin_w + cgap)
full = c < bud
ax.add_patch(FancyBboxPatch(
(x, by), coin_w, bh, boxstyle="round,pad=0.01,rounding_size=0.06",
fc=COL_AMBER_300 if full else COL_WHITE,
ec=COL_AMBER_700 if full else COL_SLATE_400,
linewidth=2.0 if full else 1.2, zorder=3))
assert bud == total_budget == 5
rx, ry, rw, rh = 0.20, 0.95, 5.0, 2.05
ax.add_patch(FancyBboxPatch(
(rx, ry), rw, rh, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.text(rx + rw * 0.5, ry + rh - 0.25,
"x(i, j) = i para + İLK j nesneyle max gelir", ha="center",
va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(rx + 0.25, ry + rh - 0.72,
"• j'yi YAPMA → x(i, j−1)", ha="left", va="center",
fontsize=9.2, color=COL_TEXT, zorder=4)
ax.text(rx + 0.25, ry + rh - 1.12,
"• j'yi YAP (i ≥ Kⱼ) → Pⱼ + x(i − Kⱼ, j−1)", ha="left",
va="center", fontsize=9.2, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(rx + rw * 0.5, ry + 0.42,
"her iki dalda da j → j−1 : nesne TÜKETİLDİ (tekrar alınamaz)",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic", zorder=4)
ax.add_patch(FancyBboxPatch(
(0.20, 0.10), 2.45, 0.62, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3))
ax.text(1.42, 0.41, f"max gelir = {value}", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(4.45, 0.41, "(n+1)² × O(1) = O(n²)\nPOLİNOM", ha="center",
va="center", fontsize=9.2, color=COL_PRIMARY, weight="bold", zorder=5)
ax.set_xlim(-0.1, 5.35)
ax.set_ylim(-0.1, 7.0)
ax.set_aspect("equal")
ax.axis("off")
def _draw_p2(ax, events, b, k, value):
"""Zaman çizgisi (9 dk) + eylem dizisi + çanta doluluk grafiği (eve git →
b'ye sıfırlanır) + topolojik-sıra notu + sonuç rozeti + pseudopolinom."""
ax.text(3.0, 6.55, "P2 — SINIRSIZ knapsack + çanta boşaltma", ha="center",
va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold")
tl_y = 5.35
x_left, x_right = 0.30, 5.70
span = x_right - x_left
def tx(minute):
return x_left + span * (minute / k)
ax.add_patch(FancyArrowPatch(
(x_left, tl_y), (x_right + 0.18, tl_y), arrowstyle="-|>",
mutation_scale=16, color=COL_PRIMARY, linewidth=2.2, zorder=3))
for minute in range(k + 1):
x = tx(minute)
ax.plot([x, x], [tl_y - 0.07, tl_y + 0.07], color=COL_SLATE_400,
linewidth=1.0, zorder=3)
ax.text(x, tl_y - 0.24, str(minute), ha="center", va="center",
fontsize=7.2, color=COL_SLATE_500, zorder=3)
ax.text(x_right + 0.30, tl_y - 0.24, "dk", ha="left", va="center",
fontsize=8, color=COL_SLATE_500, zorder=3)
blk_h = 0.50
for label, t0, t1, room0, room1, award, kind in events:
x0, x1 = tx(t0), tx(t1)
is_eve = (kind == "eve")
ax.add_patch(FancyBboxPatch(
(x0 + 0.02, tl_y + 0.14), max(0.0, x1 - x0 - 0.04), blk_h,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_BG if is_eve else COL_AMBER_100,
ec=COL_AMBER_600 if is_eve else COL_ACCENT,
linewidth=2.0, zorder=4))
cx = (x0 + x1) * 0.5
ax.text(cx, tl_y + 0.14 + blk_h * 0.62, label, ha="center", va="center",
fontsize=7.6, color=COL_AMBER_700 if not is_eve else COL_AMBER_600,
weight="bold", zorder=5)
if award > 0:
ax.text(cx, tl_y + 0.14 + blk_h * 0.22, f"+{award}", ha="center",
va="center", fontsize=7.4, color=COL_AMBER_700, zorder=5)
ax.text(x_left, tl_y + 1.02,
"zaman HEP İLERİ akar → topolojik sıra (Solomon 30:00)",
ha="left", va="center", fontsize=9, color=COL_PRIMARY, weight="bold")
gx_y0 = 2.40 # grafik tabanı (room = 0)
unit = 0.52 # room birimi yüksekliği
ax.text(x_left, gx_y0 + b * unit + 0.42,
f"çanta doluluğu (kapasite b = {b})", ha="left", va="center",
fontsize=9, color=COL_TEXT, weight="bold")
for lvl in range(b + 1):
yy = gx_y0 + lvl * unit
ax.plot([x_left, x_right], [yy, yy], color=COL_SLATE_400,
linewidth=0.7, alpha=0.5, zorder=2)
ax.text(x_left - 0.12, yy, str(lvl), ha="right", va="center",
fontsize=7, color=COL_SLATE_500, zorder=2)
ax.text(x_left - 0.42, gx_y0 + b * unit * 0.5, "kullanılan\nyer",
ha="center", va="center", fontsize=7.2, color=COL_SLATE_500,
rotation=90, zorder=2)
def used(room):
return b - room
for label, t0, t1, room0, room1, award, kind in events:
x0, x1 = tx(t0), tx(t1)
y_before = gx_y0 + used(room0) * unit
y_after = gx_y0 + used(room1) * unit
ax.plot([x0, x1], [y_before, y_before], color=COL_ACCENT,
linewidth=2.6, zorder=4)
if abs(y_after - y_before) > 1e-9:
if kind == "eve":
ax.add_patch(FancyArrowPatch(
(x1, y_before), (x1, y_after), arrowstyle="-|>",
mutation_scale=14, color=COL_AMBER_700, linewidth=2.4,
zorder=6))
ax.text(x1 + 0.06, (y_before + y_after) * 0.5, "boşalt",
ha="left", va="center", fontsize=7, color=COL_AMBER_700,
weight="bold", zorder=6)
else:
ax.plot([x1, x1], [y_before, y_after], color=COL_ACCENT,
linewidth=2.6, zorder=4)
ax.text(x_right, gx_y0 + b * unit + 0.10,
"b'ye dayanınca → EVE GİT → b'ye sıfırlanır", ha="right", va="center",
fontsize=7.6, color=COL_AMBER_700, style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(0.20, 0.95), 2.35, 0.62, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3))
ax.text(1.37, 1.26, f"max havalılık = {value}", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(1.37, 0.62, "10 + 10 + 4 (aynı stant tekrar)", ha="center",
va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(3.00, 0.55), 2.85, 1.05, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=3))
ax.text(4.42, 1.28, "kb hücre × O(n) = O(nbk)", ha="center", va="center",
fontsize=9.8, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(4.42, 0.88, "PSEUDOpolinom", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(4.42, 0.62, "(k, b runtime'da — girdi boyutunda değil)",
ha="center", va="center", fontsize=6.8, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.55, 6.15)
ax.set_ylim(-0.1, 7.0)
ax.set_aspect("equal")
ax.axis("off")
# --- motor verisi + iç tutarlılık (uydurma sayı YASAK) ---
P, K = build_coin_craft_example()
assert P == [8, 5, 11, 6, 3] and K == [2, 1, 3, 2, 1], (P, K)
v1, _ = coin_craft(P, K)
assert v1 == 19 == brute_coin_craft(P, K), v1
assert P[2] + P[1] + P[4] == 19
assert K[2] + K[1] + K[4] == 5 == len(P)
C, W, t, b, h, k = build_career_example()
assert (C, W, t, b, h, k) == ([10, 4], [2, 1], [1, 0], 2, 1, 9)
v2, _ = career_fair(C, W, t, b, h, k)
assert v2 == 24 == brute_career_fair(C, W, t, b, h, k), v2
events, scenario_total, time_used = _build_p2_timeline(C, W, t, b, h, k)
assert scenario_total == 24 == v2, scenario_total
assert time_used == 9 == k, time_used
fig, axes = plt.subplots(1, 2, figsize=(12.0, 6.0),
gridspec_kw={"width_ratios": [1.0, 1.12]})
fig.patch.set_facecolor(COL_WHITE)
_draw_p1(axes[0], P, K, v1)
_draw_p2(axes[1], events, b, k, v2)
fig.suptitle(
"İki knapsack: 0/1 (her nesne ≤ 1 kez, O(n²)) vs SINIRSIZ + boşaltma "
"(zaman = topolojik sıra, O(nbk) pseudopolinom)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.98)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## Problem 1: Coin-Crafting — 0/1 Knapsack {#sec-problem-1-d29}
**İfade.** Bir hırsızın $n$ özdeş altın parası var; bunları eritip $n$ nesneden bazılarını üretip alıcıya satacak. Nesne $i$: fiyat $P_i$, eritme sayısı $K_i$ (üretmek için gereken para). Her nesneden **en fazla bir** tane (0/1). Toplam para bütçesiyle geliri maksimize et.
::: {.callout-tip title="Yaklaşım — iki doğal parametre: hangi nesneyi yaptım + kaç para harcadım"}
İki doğal parametre var: hangi nesneyi yaptım (nesne indeksi) + kaç para harcadım (kalan bütçe). Bu klasik **0/1 knapsack**. Nesne sırası önemsiz olduğu için topolojik sırayı nesne indeksi verir; her nesne için yerel kaba kuvvet ikiye iner — yap ya da yapma. "Her nesneden en fazla bir tane" kısıtı recurrence'ın yapısına gömülür: her iki seçenekte de $j \to j-1$ ilerler, yani bir kez bakılan nesne tüketilir.
:::
> *"the two variables here, when I make a new object, is what object did I make? And how many coins did I spend?"* — Solomon, 14:30
@fig-knapsack-pair (sol panel) bu 0/1 knapsack'i motordan **gerçek** verilerle gösterir: örnek fiyatlar $P = [8, 5, 11, 6, 3]$ ve eritmeler $K = [2, 1, 3, 2, 1]$, bütçe $5$ para için optimal gelir $19$ — nesneler $11 + 5 + 3$ seçilir ($K$ toplamı $3 + 1 + 1 = 5$, tam bütçe). Bağımsız bitmask tanığı da aynı $19$'u verir.
**Çözüm.** **S:** $x(i, j) = i$ para ve ilk $j$ nesneyle elde edilebilen maksimum gelir. **R:** iki seçenek — $j$'yi yapma $\to x(i, j-1)$; $j$'yi yap (yalnız $i \ge K_j$ ise) $\to P_j + x(i - K_j, j-1)$; ikisinin max'ı. **T:** ikinci indeks ($j$) azalır. **B:** $x(0, j) = 0$ (para yok), $x(i, 0) = 0$ (nesne yok). **O:** $x(n, n)$.
```python
def coin_craft(P, K, budget=None): # (n+1)² × O(1) = O(n²)
n = len(P)
budget = n if budget is None else budget # bütçe = n özdeş para
x = {(i, 0): 0 for i in range(budget + 1)} # taban: nesne yok → 0
for j in range(1, n + 1):
for i in range(budget + 1):
best = x[(i, j - 1)] # j'yi YAPMA → j−1
if K[j - 1] <= i: # j'yi YAP (para yeterli)
best = max(best, P[j - 1] + x[(i - K[j - 1], j - 1)])
x[(i, j)] = best # her iki dalda da j → j−1
return x[(budget, n)], x
```
**Karmaşıklık.** $(n+1)^2$ alt problem $\times\ O(1)$ iş = $O(n^2)$.
::: {.callout-note title="Bonus — SRTBOT'u koda çevirmenin iki yolu"}
Solomon SRTBOT'u koda çevirmenin iki yolunu gösterdi: **memoization** (yukarıdan-aşağıya; "zaten hesapladıysam tabloya bak, döndür" — DP'nin sihri tek satırda) ve **bottom-up** (aşağıdan-yukarıya; $j$ sütunlarını sırayla doldur, recursion yok). İkisi sabit-çarpan farkıyla eşdeğer; pratikte bottom-up (yığın yükü yok + netlik) tercih edilir. Yukarıdaki kod bottom-up sürümdür.
:::
## Problem 2: Tim the Beaver Kariyer Fuarı — Sınırsız Knapsack + Çanta Boşaltma {#sec-problem-2-d29}
**İfade.** $n$ stant; nesne $i$: havalılık $C_i$, ağırlık $W_i$, sıra-bekleme $t_i$; her sıraya girmek $+1$ dk. Çanta kapasitesi $b$; eve gidip çanta boşaltma $h$ dk (sonra $+1$). Toplam süre $k$. Aynı nesneden **birden çok** alınabilir (sınırsız). $k$ dakikada maksimum toplam havalılığı bul; hedef $O(nbk)$.
::: {.callout-tip title="Yaklaşım — iki kısıt: süre ve ağırlık; topolojik sırayı zaman verir"}
İki kısıt var: süre ve çanta ağırlığı. **Kilit:** çanta boşaltılabildiği için ağırlık monotonik azalmaz — ama boşaltmak da süre harcar. Yine de **zaman hep ileri akar** → bir adım atan her seçenek ya işi bitirir ya kalan süreyi kesin azaltır; bu da topolojik sırayı zamandan doğurur (boşaltmak ağırlığı geri yükselttiğinde bile). Aynı stant tekrar tekrar alınabildiği için bu **sınırsız** knapsack'tir: nesne indeksinde ileri geçmek yerine her seçenekte tüm stantlar yeniden taranır.
:::
> *"time always moves forward for Tim the Beaver... that's what's going to give us our topological order."* — Solomon, 30:00
@fig-knapsack-pair (sağ panel) bu sınırsız knapsack'i motordan **gerçek** verilerle gösterir: iki stant $(C, W, t) = (10, 2, 1)$ ve $(4, 1, 0)$, çanta $b = 2$, ev $h = 1$, süre $k = 9$ için optimal havalılık $24$ — motor-optimal senaryo stant 0 → eve → stant 0 → eve → stant 1 ($10 + 10 + 4$, aynı stant tekrar), tam $9$ dakikayı kullanır. Bağımsız eylem-dizisi DFS tanığı da $24$ verir.
**Çözüm.** **S:** $x(i, j) = i$ dakika ve çantada $j$ ağırlık-yeri kalmışken maksimum havalılık. **R:** üç tip seçeneğin max'ı — (1) pes et $\to 0$; (2) her stant $\bar{m}$ için: $C_{\bar{m}} + x(i - t_{\bar{m}} - 1,\ j - W_{\bar{m}})$ (uygunsa: $i - t_{\bar{m}} - 1 \ge 0 \wedge j - W_{\bar{m}} \ge 0$); (3) eve git: $x(i - h - 1,\ b)$ (havalılık yok, ağırlık-yeri $b$'ye sıfırlanır; $i - h - 1 \ge 0$ ise). **T:** her seçenek ya biter ya süreyi azaltır. **B:** $x(0, j) = 0$. **O:** $x(k, b)$.
```python
def career_fair(C, W, t, b, h, k): # kb × O(n) = O(nbk)
n = len(C)
x = {(0, j): 0 for j in range(b + 1)} # taban: süre yok → 0
for i in range(1, k + 1): # zaman artan (topolojik)
for j in range(b + 1):
best = 0 # (1) pes et
for m in range(n): # (2) stant m (SINIRSIZ tekrar)
ii, jj = i - t[m] - 1, j - W[m]
if ii >= 0 and jj >= 0:
best = max(best, C[m] + x[(ii, jj)])
if i - h - 1 >= 0: # (3) eve git → yer b'ye SIFIRLANIR
best = max(best, x[(i - h - 1, b)])
x[(i, j)] = best
return x[(k, b)], x
```
**Karmaşıklık.** $kb$ alt problem $\times\ O(n)$ iş (stantlar üzerinde döngü) = $O(nbk)$. Pseudopolinom: $k$ ve $b$ runtime'da görünür — girdi boyutunda değil, sayısal değerlerinde.
## Problem 3: Protein Parsing — Precomputation ile Hızlandırma {#sec-problem-3-d29}
**İfade.** ACTG'den oluşan DNA dizisi $S$; uzunluğu $\le k$ olan marker listesi $P$. $S$'yi alt-dizilere böl (division); değer = $P$'de olan parça sayısı. Maksimum değeri bul; hedef $O(k \lvert P \rvert + k^2 \lvert S \rvert)$.
::: {.callout-tip title="Yaklaşım — toplam-terimli runtime precomputation sinyalidir"}
Önce naif DP kurulur, sonra runtime düzeltilir. Asıl ipucu istenen runtime'ın **şeklinde**: $O(k \lvert P \rvert + k^2 \lvert S \rvert)$ bir **toplam**, klasik "alt problem × iş" formülünün verdiği **çarpım** değil. Çoğu DP bir tablo doldurur ve runtime bir çarpımdır; bir toplam görünce "DP dışında ön-işleme (precomputation) var" diye okumak gerekir. Burada ön-işleme, $P$ marker'larını hash'lemek ve $S$'nin her aralığının markerlığını bir $m$ tablosuna doldurmaktır; DP kısmı ondan sonra tabloyu $O(1)$ okur.
:::
> *"I see two terms. Most of our dynamic programming things involve filling in a table, where you would expect there to be a product. So... maybe I have to do some pre-computation."* — Solomon, 56:30
@fig-protein-precompute bu iki aşamayı motordan **gerçek** verilerle gösterir: $S = $ ACTGACTGA ve $P = \{$ACT, GA, TGA, CT$\}$ için maksimum değer $4$ — optimal bölünme ACT $\mid$ GA $\mid$ CT $\mid$ GA, dört markerla dokuz harfi tam döşer. Üç bağımsız tanık (naif v1, precompute v2, tüm-bölünmeler brute) birebir $4$ verir.
**Çözüm — v1 (naif, yavaş).** **S:** $x(i) = S[i{:}]$ sonekinin maksimum değeri. **R:** $x(i) = \max($ $x(i+1)$ [karakteri atla, değer yok], her marker için: marker $S$'ye $i$'de uyuyorsa $1 + x(i + \lvert \text{marker} \rvert)$ $)$. **T:** $i$ artar. **B:** $x(\lvert S \rvert) = 0$. **O:** $x(0)$. Süre: $\lvert S \rvert$ alt problem $\times \lvert P \rvert$ marker $\times\ O(k)$ string-karşılaştırma = $O(\lvert S \rvert \cdot \lvert P \rvert \cdot k)$ — iki büyük sayının çarpımı, çok yavaş.
**Çözüm — v2 (precomputation).** $m[i, j] = 1$ eğer $S[i{:}j] \in P$, yoksa $0$. (1) $P$'deki tüm string'leri hash'le $\to O(k \lvert P \rvert)$ (birinci terim). (2) $m$'i doldur: her $i$ için $j = i+1 \dots i+k$ (uzunluk $\le k$), $S[i{:}j]$'yi hash'le $O(k)$ + $P$-hash'te ara $\to O(k^2 \lvert S \rvert)$ (ikinci terim). Revize **R′:** $x(i) = \max_{j \in 1 \dots k} ($ $m[i, i+j] + x(i+j)$ $)$. DP kısmı $O(\lvert S \rvert \cdot k)$ — diğer terimlerden küçük.
*(İndeks köprüsü: prose, kaynaktaki gibi $m$'in ikinci indeksini bitiş konumu olarak kullanır — $m[i, j]$, parça $S[i{:}j]$. Aşağıdaki kod ve figür ise ikinci indeksi parça uzunluğu alır: kodun $m[i][j]$'si, prose'un $m[i, i+j]$'sine denktir.)*
```python
def protein_v2(S, P, kmax): # O(k·|P| + k²·|S|)
n = len(S)
pset = set(P) # (1) P'yi hash'le — O(k·|P|)
m = [[0] * (kmax + 1) for _ in range(n + 1)] # (2) m[i][j] üyelik tablosu
for i in range(n): # — O(k²·|S|)
for j in range(1, min(kmax, n - i) + 1):
if S[i:i + j] in pset:
m[i][j] = 1
x = [0] * (n + 1) # (3) küçük DP — O(|S|·k)
for i in range(n - 1, -1, -1):
best = 0
for j in range(1, min(kmax, n - i) + 1):
best = max(best, m[i][j] + x[i + j]) # yalnız TABLOYU okur
x[i] = best
return x[0], m
```
**Karmaşıklık.** $O(k \lvert P \rvert + k^2 \lvert S \rvert)$. İlginç: tüm precomputation'dan sonra DP kısmı runtime'da **önemsiz** kalır.
```{python}
#| label: fig-protein-precompute
#| fig-cap: "Protein parsing: naif tekrar-hesap vs PRECOMPUTE — Problem 3. Veri MOTORDAN (S=ACTGACTGA, P={ACT,GA,TGA,CT}, k=3, üç tanık v1==v2==brute==4, m tablosunda 8 adet 1). ÜST: DNA şeridi 9 harf kutu + optimal bölünme ACT|GA|CT|GA (4 amber marker bloğu) + sağda P marker listesi (kullanılanlar ✓). ALT: iki-aşamalı boru hattı — v1 naif (soluk kırmızı, O(|S|·|P|·k) iki dev çarpım YAVAŞ) → 'önce HESAPLA' oku → v2 üç precompute kutusu: (1) P → hash O(k·|P|), (2) m[i][j] üyelik tablosu mini görsel (1'ler amber) O(k²·|S|), (3) küçük DP O(|S|·k); toplam runtime O(k·|P| + k²·|S|) rozeti; 'runtime'da TOPLAM görüyorsan precompute sinyali (Solomon 56:30)'."
#| fig-width: 11.5
#| fig-height: 6.5
# fig-protein-precompute — PS9 P3: toplam-terimli runtime → precompute sinyali.
# Veri MOTORDAN: build_protein_example / protein_v1 / protein_v2 / brute_protein.
# Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, COL_*, COL_RED_*.
S, Pmark, kmax = build_protein_example()
assert S == "ACTGACTGA", S
assert Pmark == ["ACT", "GA", "TGA", "CT"], Pmark
assert kmax == 3, kmax
n = len(S)
assert n == 9, n
pset = set(Pmark)
val_v1 = protein_v1(S, Pmark)
val_v2, m = protein_v2(S, Pmark, kmax)
val_brute = brute_protein(S, Pmark)
assert val_v1 == val_v2 == val_brute == 4, (val_v1, val_v2, val_brute)
assert m[0][3] == 1 and m[3][2] == 1 and m[0][2] == 0
# optimal bölünmeyi DFS ile bul (motorla aynı kmax kuralı) ve assert et
_sols = []
def _dfs(i, parts):
if i == n:
if sum(1 for a, bb in parts if S[a:bb] in pset) == val_v2:
_sols.append(list(parts))
return
for j in range(1, min(kmax, n - i) + 1):
parts.append((i, i + j))
_dfs(i + j, parts)
parts.pop()
_dfs(0, [])
_sols.sort(key=lambda ps: (sum(1 for a, bb in ps if S[a:bb] not in pset), len(ps)))
split = _sols[0]
split_pieces = [S[a:bb] for a, bb in split]
assert split == [(0, 3), (3, 5), (5, 7), (7, 9)], split
assert split_pieces == ["ACT", "GA", "CT", "GA"], split_pieces
n_markers = sum(1 for a, bb in split if S[a:bb] in pset)
assert n_markers == 4
ones = [(i, j) for i in range(len(m)) for j in range(len(m[0])) if m[i][j] == 1]
n_ones = len(ones)
assert n_ones == 8, n_ones
naive_cost = "O(|S|·|P|·k)"
cost_hash = "O(k·|P|)"
cost_table = "O(k²·|S|)"
cost_dp = "O(|S|·k)"
total_cost = "O(k·|P| + k²·|S|)"
def rbox(ax, x, y, w, hh, fc, ec, lw=1.8, rounding=0.06):
ax.add_patch(FancyBboxPatch(
(x, y), w, hh, boxstyle=f"round,pad=0.02,rounding_size={rounding}",
fc=fc, ec=ec, linewidth=lw, zorder=2))
fig, (axT, axB) = plt.subplots(2, 1, figsize=(11.5, 6.5))
fig.patch.set_facecolor(COL_WHITE)
# ÜST PANEL — DNA şeridi + optimal bölünme + P marker listesi
axT.set_title("Protein ayrıştırma: en çok markeri kapsayan bölünme",
fontsize=12.5, color=COL_TEXT, weight="bold")
cell_w, cell_h = 0.92, 0.92
y_strip = 1.55
x0 = 0.30
char_part = [None] * n
for pidx, (a, bb) in enumerate(split):
for c in range(a, bb):
char_part[c] = pidx
for c in range(n):
x = x0 + c * cell_w
pidx = char_part[c]
a, bb = split[pidx]
is_marker = S[a:bb] in pset
fc = COL_AMBER_100 if is_marker else COL_WHITE
ec = COL_ACCENT if is_marker else COL_SLATE_400
rbox(axT, x, y_strip, cell_w * 0.94, cell_h * 0.94, fc, ec,
lw=2.4 if is_marker else 1.4, rounding=0.04)
cx = x + cell_w * 0.47
axT.text(cx, y_strip + cell_h * 0.47, S[c], ha="center", va="center",
fontsize=14, color=COL_TEXT, weight="bold", zorder=4)
axT.text(cx, y_strip - 0.24, str(c), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=4)
axT.text(x0 - 0.55, y_strip + cell_h * 0.47, "S =", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
for pidx, (a, bb) in enumerate(split):
xa = x0 + a * cell_w - 0.04
xb = x0 + bb * cell_w + 0.04
w = xb - xa - cell_w * 0.02
rbox(axT, xa, y_strip - 0.06, w, cell_h + 0.12, "none", COL_AMBER_600,
lw=2.2, rounding=0.05)
mx = (xa + xb) / 2
axT.text(mx, y_strip + cell_h + 0.34, S[a:bb], ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=5)
axT.text((x0 + n * cell_w * 0.5), y_strip + cell_h + 0.78,
f"optimal bölünme: {' · '.join(split_pieces)} → {n_markers} marker",
ha="center", va="center", fontsize=10, color=COL_TEXT, weight="bold")
px0 = x0 + n * cell_w + 0.75
pw, ph = 2.55, 2.95
pby = y_strip - 0.75
rbox(axT, px0, pby, pw, ph, COL_BG, COL_PRIMARY, lw=1.8, rounding=0.08)
axT.text(px0 + pw * 0.5, pby + ph - 0.30, "marker kümesi P",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
for idx, mk in enumerate(Pmark):
my = pby + ph - 0.80 - idx * 0.48
used = mk in split_pieces
chip_fc = COL_AMBER_100 if used else COL_WHITE
chip_ec = COL_ACCENT if used else COL_SLATE_400
rbox(axT, px0 + 0.45, my - 0.17, 1.05, 0.36, chip_fc, chip_ec,
lw=2.0 if used else 1.3, rounding=0.08)
axT.text(px0 + 0.97, my, mk, ha="center", va="center", fontsize=10,
color=COL_TEXT, weight="bold")
if used:
axT.text(px0 + 1.75, my, "✓", ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold")
axT.text(px0 + pw * 0.5, pby + 0.20,
f"|P| = {len(Pmark)}, k = {kmax}", ha="center", va="center",
fontsize=8.4, color=COL_SLATE_500, style="italic")
axT.set_xlim(-0.9, px0 + pw + 0.4)
axT.set_ylim(min(pby - 0.15, y_strip - 0.95), y_strip + cell_h + 1.15)
axT.set_aspect("equal")
axT.axis("off")
# ALT PANEL — iki-aşamalı boru hattı (naif vs precompute)
axB.set_title("Naif tekrar-hesap vs PRECOMPUTE: runtime'da TOPLAM = sinyal",
fontsize=12.5, color=COL_TEXT, weight="bold")
v1x, v1y, v1w, v1h = 0.20, 1.95, 2.55, 1.55
rbox(axB, v1x, v1y, v1w, v1h, COL_RED_FILL, COL_RED_EC, lw=2.0, rounding=0.06)
axB.text(v1x + v1w * 0.5, v1y + v1h - 0.30, "v1 — naif", ha="center",
va="center", fontsize=11, color=COL_RED_EC, weight="bold")
axB.text(v1x + v1w * 0.5, v1y + v1h - 0.68,
"DP içinde her adımda\nstring-karşılaştırma", ha="center", va="center",
fontsize=8.4, color=COL_TEXT)
axB.text(v1x + v1w * 0.5, v1y + 0.50, naive_cost, ha="center", va="center",
fontsize=12.5, color=COL_RED_EC, weight="bold")
axB.text(v1x + v1w * 0.5, v1y + 0.14, "iki dev çarpım · YAVAŞ", ha="center",
va="center", fontsize=8.0, color=COL_RED_EC, style="italic")
axB.add_patch(FancyArrowPatch(
(v1x + v1w + 0.06, v1y + v1h * 0.5), (v1x + v1w + 0.72, v1y + v1h * 0.5),
arrowstyle="-|>", mutation_scale=20, color=COL_AMBER_600,
linewidth=2.4, zorder=3))
axB.text(v1x + v1w + 0.39, v1y + v1h * 0.5 + 0.28, "önce\nHESAPLA",
ha="center", va="center", fontsize=7.8, color=COL_AMBER_700,
weight="bold")
stage_x0 = v1x + v1w + 0.85
gap = 0.30
sw, sh = 2.55, 1.55
s1x = stage_x0
rbox(axB, s1x, v1y, sw, sh, COL_BG, COL_PRIMARY, lw=1.7, rounding=0.06)
axB.text(s1x + sw * 0.5, v1y + sh - 0.28, "(1) P → hash", ha="center",
va="center", fontsize=10, color=COL_TEXT, weight="bold")
for idx, mk in enumerate(Pmark):
cxh = s1x + 0.55 + (idx % 2) * 1.15
cyh = v1y + sh - 0.68 - (idx // 2) * 0.42
rbox(axB, cxh - 0.32, cyh - 0.16, 0.78, 0.32, COL_WHITE, COL_SLATE_400,
lw=1.2, rounding=0.08)
axB.text(cxh + 0.07, cyh, mk, ha="center", va="center", fontsize=7.8,
color=COL_TEXT, weight="bold")
axB.text(s1x + sw * 0.5, v1y + 0.16, cost_hash, ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold")
axB.add_patch(FancyArrowPatch(
(s1x + sw + 0.02, v1y + sh * 0.5), (s1x + sw + gap - 0.02, v1y + sh * 0.5),
arrowstyle="-|>", mutation_scale=13, color=COL_SLATE_400,
linewidth=1.6, zorder=3))
s2x = s1x + sw + gap
mw, mh = 2.55, 1.55
rbox(axB, s2x, v1y, mw, mh, COL_BG, COL_PRIMARY, lw=1.7, rounding=0.06)
axB.text(s2x + mw * 0.5, v1y + mh - 0.24, "(2) m[i][j] tablosu", ha="center",
va="center", fontsize=9.5, color=COL_TEXT, weight="bold")
mini_i = list(range(n))
mini_j = [1, 2, 3]
gx0 = s2x + 0.58
gy0 = v1y + mh - 0.62
gcw, gch = 0.155, 0.105
for ri, i in enumerate(mini_i):
for cj, j in enumerate(mini_j):
gx = gx0 + cj * gcw
gy = gy0 - ri * gch
on = (m[i][j] == 1)
axB.add_patch(FancyBboxPatch(
(gx, gy - gch * 0.92), gcw * 0.9, gch * 0.9,
boxstyle="square,pad=0.0",
fc=COL_AMBER_300 if on else COL_WHITE,
ec=COL_AMBER_700 if on else COL_SLATE_400,
linewidth=1.1 if on else 0.6, zorder=4))
for cj, j in enumerate(mini_j):
axB.text(gx0 + cj * gcw + gcw * 0.45, gy0 + 0.07, str(j),
ha="center", va="bottom", fontsize=5.6, color=COL_SLATE_500)
axB.text(gx0 + gcw * 1.4, gy0 + 0.20, "j", ha="center", va="bottom",
fontsize=6.0, color=COL_SLATE_500, style="italic")
axB.text(gx0 - 0.14, gy0 - (n - 1) * gch * 0.5, "i", ha="center", va="center",
fontsize=6.5, color=COL_SLATE_500, style="italic")
axB.text(s2x + mw - 0.62, v1y + mh - 0.62,
"1 ⟺\nS[i:i+j]∈P", ha="center", va="center", fontsize=6.6,
color=COL_AMBER_700, weight="bold")
axB.text(s2x + mw - 0.62, v1y + mh - 1.10, f"{n_ones} adet 1", ha="center",
va="center", fontsize=6.8, color=COL_AMBER_700, style="italic")
axB.text(s2x + mw * 0.5, v1y + 0.16, cost_table, ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold")
axB.add_patch(FancyArrowPatch(
(s2x + mw + 0.02, v1y + mh * 0.5), (s2x + mw + gap - 0.02, v1y + mh * 0.5),
arrowstyle="-|>", mutation_scale=13, color=COL_SLATE_400,
linewidth=1.6, zorder=3))
s3x = s2x + mw + gap
dw = 2.45
rbox(axB, s3x, v1y, dw, sh, COL_AMBER_100, COL_ACCENT, lw=2.2, rounding=0.06)
axB.text(s3x + dw * 0.5, v1y + sh - 0.28, "(3) küçük DP", ha="center",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold")
axB.text(s3x + dw * 0.5, v1y + sh - 0.78,
"x(i)=max_{j} m[i][j]+x(i+j)\nyalnız TABLOYU okur", ha="center",
va="center", fontsize=7.4, color=COL_TEXT)
axB.text(s3x + dw * 0.5, v1y + 0.42, f"cevap = {val_v2}", ha="center",
va="center", fontsize=11, color=COL_AMBER_700, weight="bold")
axB.text(s3x + dw * 0.5, v1y + 0.12, cost_dp, ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold")
tot_w = 5.0
tot_x = (s1x + s3x + dw) / 2 - tot_w / 2
rbox(axB, tot_x, 0.95, tot_w, 0.66, COL_AMBER_100, COL_ACCENT, lw=2.6,
rounding=0.10)
axB.text(tot_x + tot_w * 0.5, 0.95 + 0.33,
f"toplam runtime = {total_cost}", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold")
axB.text((s1x + s3x + dw) / 2, 0.42,
"runtime'da TOPLAM görüyorsan precompute sinyali (Solomon 56:30)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", style="italic")
axB.text(v1x + 0.05, 0.42,
f"v1 = v2 = brute = {val_v2}", ha="left", va="center",
fontsize=8.4, color=COL_SLATE_500, style="italic")
axB.set_xlim(-0.1, s3x + dw + 0.35)
axB.set_ylim(0.20, v1y + sh + 0.85)
axB.set_aspect("equal")
axB.axis("off")
fig.tight_layout()
plt.show()
```
## Problem 4: Lazy Egg Drop — Minimax DP {#sec-problem-4-d29}
**İfade.** $n$ katlı bina (kat yükseklikleri $h(i)$, sıralı), $k$ yumurta. Yumurtanın kırılmadan atılabildiği **en yüksek katı** bul. Her atış maliyeti = inilen kat yüksekliği (merdiven inip kontrol). Yumurta kırılırsa üst sınır $+$ bir yumurta gider; kırılmazsa geri alınır (yeniden kullanılır), alt sınır. **Toplam yüksekliği** (en kötü durumda) minimize et; hedef $O(n^3 k)$.
::: {.callout-tip title="Yaklaşım — adversarial yumurta: belirsizlik aralığını izle, min içinde max kur"}
Bu bir deney tasarımı problemi. Belirsiz kat aralığı hep **bağlantılıdır** (bir kat kırılırsa üstündeki tüm katlar da kırılır), bu yüzden durumu bir aralık $[i, j]$ olarak izlemek yeterli. Yumurta **adversarial** kabul edilir: kırılır/kırılmaz seçimini en çok işi yaptıracak şekilde yapar, çünkü en kötü durumu sınırlamaya çalışıyoruz. Bu da recurrence'ı bir **minimax** yapar — biz hangi kattan atacağımızı seçerek maliyeti minimize ederiz, yumurta sonucu seçerek maliyeti maksimize eder (min içinde max).
:::
> *"the egg might be an adversarial egg... we're trying to upper bound the amount of work... and I'm trying to design a procedure that minimizes my work."* — Solomon, 1:15:15
@fig-egg-minimax bu minimax'ı motordan **gerçek** verilerle gösterir: $n = 6$ kat, $h[f] = f$, $k = 2$ yumurta için minimum en-kötü maliyet $14$ — DP'nin ilk atışı kat $f = 2$, kırılırsa $[1, 1]$'e $1$ yumurta, kırılmazsa $[3, 6]$'ya $2$ yumurta düşer. Bağımsız politika-simülasyonu tanığı yedi gerçek eşiğin hepsinde doğru eşiği bulur ve en kötü maliyetini tam $14$ (adversarial = en kötü gerçek eşik) verir. $k = 1$ tek-yumurta hâli zorunlu aşağıdan-yukarı tarama yapar ($\Sigma h = 21$); yumurta arttıkça maliyet $[21, 14, 12, 12]$ doymaya gider.
**Çözüm.** **S:** $x(i, j, e) = $ belirsiz katlar $[i, j]$ ve $e$ yumurta kalmışken minimum toplam yükseklik. **R (minimax):** $x(i, j, e) = \min_{f \in [i, j]} [\ h(f) + \max(\ x(i, f-1, e-1)$ [kırıldı], $x(f+1, j, e)$ [kırılmadı]\ )\ ]$. **T:** belirsizlik genişliği $j - i$ **kesin azalır** (yumurta harcaması değil!) → topolojik. **B:** $x(i, j, 0) = \infty$ (yumurta bitti ama kat belirsiz — min'de asla seçilmez); $x(i, i-1, e) = 0$ (aralık tek kata indi). **O:** $x(1, n, k)$.
```python
def egg_drop(h, k): # n²k × O(n) = O(n³k)
n = len(h) - 1
memo, choice = {}, {}
def x(i, j, e):
if j < i: return 0 # aralık çözüldü
if e == 0: return INF # yumurtasız belirsizlik
if (i, j, e) in memo: return memo[(i, j, e)]
best, bf = INF, None
for f in range(i, j + 1): # hangi kattan atayım? (MIN)
cand = h[f] + max(x(i, f - 1, e - 1), # kırıldı (yumurta -1) ┐ adversarial
x(f + 1, j, e)) # kırılmadı (aralık üstü) ┘ (MAX)
if cand < best:
best, bf = cand, f
memo[(i, j, e)] = best; choice[(i, j, e)] = bf
return best
return x(1, n, k), memo, choice
```
**Karmaşıklık.** $n^2$ (iki kat indeksi) $\times\ k$ (yumurta) alt problem $\times\ O(n)$ ($f$ döngüsü) = $O(n^3 k)$.
```{python}
#| label: fig-egg-minimax
#| fig-cap: "Lazy egg drop: minimax DP + politika simülasyonu — Problem 4 İMZA. Veri MOTORDAN (h=[0,1,2,3,4,5,6], k=2 → x(1,6,2)=14; politika-sim 7 eşik HEPSİ doğru + max maliyet 14; ilk atış f=choice[(1,6,2)]=2; k=1 → Σh=21; doyma [21,14,12,12]). SOL: 6 katlı bina, DP'nin ilk atışı f=2 amber vurgu; kırıldı dalı (amber, [1,1] e=1) ve kırılmadı dalı (slate, [3,6] e=2); minimax kutusu x(i,j,e)=min_f[h(f)+max(kırıldı,kırılmadı)] + 'yumurta ADVERSARIAL (Solomon 1:15:15)'; topolojik-sıra rozeti 'belirsizlik j−i DARALIR (yumurtadan değil)'. SAĞ ÜST: politika-simülasyon tablosu — 7 gerçek eşik t=0..6 için DP maliyeti [3,3,10,14,14,13,13], max=14 amber; 'DP politikası HER eşikte doğru eşiği bulur, en kötü == x(1,n,k)=14 adversarial tanık'. SAĞ ALT: doyma eğrisi k=1..4 → [21,14,12,12], 4. yumurta işe yaramaz (belirsizlik-daralması baskın)."
#| fig-width: 12.0
#| fig-height: 6.3
# fig-egg-minimax — PS9 P4 İMZA: minimax DP + politika simülasyonu tanığı.
# Veri MOTORDAN: build_egg_example / egg_drop / egg_policy_sim.
# Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, GridSpec, COL_*, apply_style, INF.
heights, kk = build_egg_example()
assert heights == [0, 1, 2, 3, 4, 5, 6], heights
assert kk == 2, kk
nfloors = len(heights) - 1
assert nfloors == 6
ans, memo, choice = egg_drop(heights, kk)
assert ans == 14, ans
worst, all_correct = egg_policy_sim(heights, kk)
assert worst == 14 and all_correct is True
assert worst == ans
f0 = choice[(1, nfloors, kk)]
assert f0 == 2, f0
brk_lo, brk_hi, brk_e = 1, f0 - 1, kk - 1 # [1,1] e=1
nbrk_lo, nbrk_hi, nbrk_e = f0 + 1, nfloors, kk # [3,6] e=2
assert (brk_lo, brk_hi, brk_e) == (1, 1, 1)
assert (nbrk_lo, nbrk_hi, nbrk_e) == (3, 6, 2)
ans1, _, _ = egg_drop(heights, 1)
assert ans1 == sum(heights) == 21
saturation = []
for kx in range(1, 5):
a_kx, _, _ = egg_drop(heights, kx)
saturation.append(a_kx)
assert saturation == [21, 14, 12, 12], saturation
def _per_threshold_costs(h, k, choice):
nn = len(h) - 1
costs, founds = [], []
for t in range(nn + 1):
i, j, e, cost = 1, nn, k, 0
while i <= j:
f = choice[(i, j, e)]
cost += h[f]
if f > t:
j, e = f - 1, e - 1
else:
i = f + 1
costs.append(cost)
founds.append(j)
return costs, founds
t_costs, t_founds = _per_threshold_costs(heights, kk, choice)
assert t_founds == list(range(nfloors + 1)), t_founds
assert t_costs == [3, 3, 10, 14, 14, 13, 13], t_costs
assert max(t_costs) == worst == 14
worst_t = t_costs.index(max(t_costs))
def rbox(ax, x, y, w, h_, fc, ec, lw=1.8):
ax.add_patch(FancyBboxPatch(
(x, y), w, h_, boxstyle="round,pad=0.02,rounding_size=0.05",
fc=fc, ec=ec, linewidth=lw, zorder=2))
fig = plt.figure(figsize=(12, 6.3))
fig.patch.set_facecolor(COL_WHITE)
gs = GridSpec(2, 2, width_ratios=[1.08, 1.0], height_ratios=[1.12, 1.0],
hspace=0.42, wspace=0.18, figure=fig)
axL = fig.add_subplot(gs[:, 0])
axRT = fig.add_subplot(gs[0, 1])
axRB = fig.add_subplot(gs[1, 1])
# SOL — bina + ilk atış + iki dal + minimax kutusu
axL.set_title("Lazy egg drop: DP'nin ilk atışı f=2 (minimax)",
fontsize=12.3, color=COL_TEXT, weight="bold")
bx0, bw = 0.55, 1.5
floor_h = 0.62
base_y = 0.7
for f in range(1, nfloors + 1):
fy = base_y + (f - 1) * floor_h
is_throw = (f == f0)
rbox(axL, bx0, fy, bw, floor_h * 0.9,
COL_AMBER_100 if is_throw else COL_BG,
COL_ACCENT if is_throw else COL_PRIMARY,
lw=2.6 if is_throw else 1.5)
axL.text(bx0 + 0.30, fy + floor_h * 0.42, f"{f}", ha="center", va="center",
fontsize=10, color=COL_SLATE_500, weight="bold", zorder=4)
if is_throw:
axL.text(bx0 + bw * 0.66, fy + floor_h * 0.42,
"← ilk atış f = 2", ha="left", va="center",
fontsize=9.6, color=COL_AMBER_700, weight="bold", zorder=4)
axL.text(bx0 + bw * 0.5, base_y + nfloors * floor_h + 0.22,
"6 katlı bina · h[f] = f", ha="center", va="center",
fontsize=9.3, color=COL_SLATE_500, style="italic")
axL.text(bx0 - 0.18, base_y - 0.30, "kat f:", ha="left", va="center",
fontsize=8.6, color=COL_SLATE_500)
throw_y = base_y + (f0 - 1) * floor_h + floor_h * 0.42
split_x = bx0 + bw + 0.55
axL.add_patch(FancyArrowPatch((bx0 + bw, throw_y), (split_x, throw_y),
arrowstyle="-", color=COL_SLATE_400, linewidth=1.3, zorder=1))
brk_x, brk_y = 3.55, throw_y + 1.70
axL.add_patch(FancyArrowPatch((split_x, throw_y), (brk_x - 0.05, brk_y),
arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT,
linewidth=2.3, zorder=3, connectionstyle="arc3,rad=0.18"))
rbox(axL, brk_x, brk_y - 0.46, 2.85, 0.92, COL_AMBER_100, COL_ACCENT, lw=2.2)
axL.text(brk_x + 1.42, brk_y + 0.18, "KIRILDI", ha="center", va="center",
fontsize=9.8, color=COL_AMBER_700, weight="bold")
axL.text(brk_x + 1.42, brk_y - 0.20,
f"[1, {brk_hi}] · {brk_e} yumurta\nx(1,1,1)", ha="center", va="center",
fontsize=8.6, color=COL_TEXT)
nbrk_x, nbrk_y = 3.55, throw_y - 0.05
axL.add_patch(FancyArrowPatch((split_x, throw_y), (nbrk_x - 0.05, nbrk_y),
arrowstyle="-|>", mutation_scale=14, color=COL_SLATE_400,
linewidth=1.8, zorder=2, connectionstyle="arc3,rad=-0.18"))
rbox(axL, nbrk_x, nbrk_y - 0.46, 2.85, 0.92, COL_BG, COL_PRIMARY, lw=1.7)
axL.text(nbrk_x + 1.42, nbrk_y + 0.18, "KIRILMADI", ha="center", va="center",
fontsize=9.8, color=COL_SLATE_500, weight="bold")
axL.text(nbrk_x + 1.42, nbrk_y - 0.20,
f"[{nbrk_lo}, 6] · {nbrk_e} yumurta\nx(3,6,2)", ha="center", va="center",
fontsize=8.6, color=COL_TEXT)
rbox(axL, 0.35, -1.30, 6.15, 1.05, COL_WHITE, COL_AMBER_600, lw=2.0)
axL.text(3.42, -0.62,
"x(i,j,e) = min_f [ h(f) + max(kırıldı, kırılmadı) ]",
ha="center", va="center", fontsize=10.2, color=COL_TEXT, weight="bold")
axL.text(3.42, -1.03,
"yumurta ADVERSARIAL — en kötü sonucu varsay (Solomon 1:15:15)",
ha="center", va="center", fontsize=8.4, color=COL_AMBER_700,
style="italic")
rbox(axL, 0.35, -2.30, 6.15, 0.72, COL_BG, COL_PRIMARY, lw=1.6)
axL.text(3.42, -1.94,
"topolojik sıra: belirsizlik j−i DARALIR (yumurtadan değil)",
ha="center", va="center", fontsize=8.8, color=COL_PRIMARY, weight="bold")
axL.set_xlim(-0.1, 6.7)
axL.set_ylim(-2.50, base_y + nfloors * floor_h + 0.55)
axL.axis("off")
# SAĞ ÜST — politika-simülasyon tablosu (7 gerçek eşik)
axRT.set_title("Politika simülasyonu — her gerçek eşik için maliyet",
fontsize=10.8, color=COL_TEXT, weight="bold")
cw, ch = 0.96, 0.66
tx0, ty0 = 1.65, 1.55
axRT.text(tx0 - 0.20, ty0 + ch + 0.34, "gerçek eşik t:", ha="right", va="center",
fontsize=8.6, color=COL_SLATE_500, weight="bold")
axRT.text(tx0 - 0.20, ty0 + ch * 0.5, "DP maliyeti:", ha="right", va="center",
fontsize=8.6, color=COL_SLATE_500, weight="bold")
for t in range(nfloors + 1):
x = tx0 + t * cw
is_worst = (t_costs[t] == max(t_costs))
axRT.text(x + cw * 0.45, ty0 + ch + 0.34, f"{t}", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold")
rbox(axRT, x, ty0, cw * 0.9, ch,
COL_AMBER_100 if is_worst else COL_BG,
COL_ACCENT if is_worst else COL_PRIMARY,
lw=2.6 if is_worst else 1.5)
axRT.text(x + cw * 0.45, ty0 + ch * 0.5, f"{t_costs[t]}",
ha="center", va="center",
fontsize=11 if is_worst else 10,
color=COL_AMBER_700 if is_worst else COL_TEXT, weight="bold")
axRT.text(tx0 + (worst_t + 0.45) * cw, ty0 + ch + 0.78, "max = 14",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700,
weight="bold")
rbox(axRT, tx0, -0.30, (nfloors + 1) * cw - 0.06, 0.95, COL_WHITE, COL_AMBER_600, lw=1.9)
axRT.text(tx0 + (nfloors + 1) * cw * 0.5, 0.37,
"DP politikası HER eşikte doğru eşiği bulur",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700,
weight="bold")
axRT.text(tx0 + (nfloors + 1) * cw * 0.5, -0.05,
"en kötü maliyet == x(1,n,k) = 14 (adversarial tanık)",
ha="center", va="center", fontsize=8.6, color=COL_TEXT)
axRT.set_xlim(0, tx0 + (nfloors + 1) * cw + 0.45)
axRT.set_ylim(-0.55, ty0 + ch + 1.05)
axRT.axis("off")
# SAĞ ALT — doyma eğrisi k=1..4 → [21,14,12,12]
apply_style(axRB)
ks = list(range(1, 5))
axRB.plot(ks, saturation, color=COL_PRIMARY, linewidth=2.2,
marker="o", markersize=7, markerfacecolor=COL_ACCENT,
markeredgecolor=COL_AMBER_700, zorder=4)
for kx, val in zip(ks, saturation):
axRB.annotate(f"{val}", (kx, val), textcoords="offset points",
xytext=(0, 9), ha="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold")
axRB.annotate("", xy=(4, saturation[3]), xytext=(3, saturation[2]),
arrowprops=dict(arrowstyle="-", color=COL_AMBER_600,
linewidth=2.4, linestyle=(0, (3, 2))), zorder=3)
axRB.text(3.5, saturation[2] + 4.4,
"4. yumurta işe yaramaz\n(belirsizlik-daralması baskın)",
ha="center", va="center", fontsize=8.4, color=COL_AMBER_700,
weight="bold")
axRB.set_xticks(ks)
axRB.set_xlim(0.7, 4.4)
axRB.set_ylim(9.5, 24)
axRB.set_xlabel("yumurta sayısı k", fontsize=9.5, color=COL_TEXT)
axRB.set_ylabel("min en-kötü maliyet", fontsize=9.5, color=COL_TEXT)
axRB.set_title("Doyma eğrisi — x(1,6,k)", fontsize=10.5, color=COL_TEXT, weight="bold")
axRB.tick_params(labelsize=8.5)
fig.suptitle("Lazy egg drop (PS9 P4) — minimax DP + politika-simülasyon tanığı",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.99)
plt.show()
```
> **Atlanan 5. problem (duvar örme):** Karo dizerek duvar örme; runtime **üstel** ama problem buna izin verir — "küçük parametrelerde üstel" kabul, yasak olan **iki dev üstelin çarpımı**. Solomon zaman yetmediği için işlemedi (transkript 1:24:34).
## Ne Öğrendik? {#sec-ne-ogrendik-d29}
::: {.callout-important title="Altı Taşınabilir Araç"}
Bu oturum, DP problem oturumlarının ikincisiydi ve SRTBOT çerçevesini dört pseudopolinom problemde uyguladı:
1. **0/1 vs sınırsız knapsack (P1 vs P2):** "her nesneden bir tane" ($j-1$'e geç) $\leftrightarrow$ "sınırsız" (aynı indekste kal / her seçeneği tara). İkisi de iki-parametreli (bütçe + nesne/zaman).
2. **Zaman = topolojik sıra (P2):** ağırlık geri artsa bile (çanta boşaltma), zaman hep ilerlediği için sıra garanti. "$t$ hem zaman hem topological order".
3. **SRTBOT → kod (P1):** memoization (top-down, "zaten hesapladıysam döndür") vs bottom-up (tabloyu sırayla doldur); sabit-çarpan eşdeğer, genelde bottom-up tercih.
4. **Toplam-terimli runtime → precomputation (P3):** runtime'da çarpım değil **toplam** görürsen, DP dışında ön-işleme (hash + tablo) yap; DP kısmı küçülür.
5. **Minimax DP (P4):** adversarial sonuç (yumurta kırılır/kırılmaz) → min içinde max; topolojik sıra "harcanan kaynak"tan değil **belirsizlik daralmasından** gelebilir.
6. **"Hocayı teşhis et":** istenen runtime'ın şekli (toplam mı çarpım mı, hangi parametreler) çözümün yapısını ele verir.
:::
## Sonraki {#sec-sonraki-d29}
::: {.callout-warning title="Ders 30 (PS10): Problem Oturumu 10 (Quiz 3 Tekrarı) — Jason Ku"}
Sırada **Ders 30 (PS10): Problem Oturumu 10 (Quiz 3 Tekrarı)** var — bu kez hoca değişir, Jason Ku ile DP ve karmaşıklık bloğunun kapanış tekrarını yaparız. Bu oturumdaki pseudopolinom + minimax sezgileri ve "runtime'ı teşhis et" refleksi, Quiz 3 hazırlığının çekirdeğidir.
:::
