---
title: "Dinamik Programlama 2: LCS, LIS, Oyunlar"
subtitle: "DP'yi tek diziden ötesine taşıyan üç teknik: çoklu girdide alt problem uzaylarını çarp (LCS), naif tanım çökerse bir kısıt ekleyip alt problemi genişlet (LIS), oyunlarda durumu koordinata taşı ve ben max rakip min oyna (para oyunu) — hepsi yerel kaba kuvvetle ve ebeveyn işaretçileriyle çözümün kendisini de kurtararak O(n²)"
---
::: {.callout-note title="Oturum bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 16: Dynamic Programming, Part 2](https://www.youtube.com/watch?v=KLBCUx1is2c) (≈58 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 16: Dynamic Programming, Part 2](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec16/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 24 (L16)
- **Hoca:** Erik Demaine (dinamik programlama; **DP serisinin 2/4'ü**)
- **Okuma süresi:** ≈27 dk
> Bu, DP ünitesinin **ikinci dersidir**. Ders 23 SRTBOT + memoization'ı tek dizide kurdu; bu ders çerçeveyi zorlayan üç klasik problemle yeni teknikleri tanıtır: **LCS** (en uzun ortak alt-dizilim), **LIS** (en uzun artan alt-dizilim) ve **değişen para oyunu** (alternating coin game). Temel sezgi sabit kalır: "çözümün hangi özelliğini bilsem işim biterdi?" — o özelliği **yerel kaba kuvvetle** dene.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d24}
DP serisinin **2/4'ü** (Erik Demaine). Üç klasik örnekle dört yeni DP fikri tanıtılır: **çoklu dizi** (tek değil), **substring** alt problemleri, **ebeveyn işaretçileri** (çözümü kurtarmak) ve **alt problem kısıtı/genişletmesi** (subproblem constraint/expansion).
> *"We're now in step two out of four."* — Demaine, 0:19
Üç ana fikir:
1. **Çoklu girdi → alt problem çarpımı** — iki dizi varsa, alt problem uzaylarını çarp (A'nın sonekleri × B'nin sonekleri).
2. **Alt problem kısıtı** — naif tanım recurrence vermiyorsa, alt probleme bir koşul ekle (örn. "A[i] ile başla").
3. **Subproblem expansion** — kısıt için alt problem sayısını çoğalt (polinom kalmak şartıyla); oyunlarda max ile min yer değiştirir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 24'ün (L16) kavram haritası: kök = Dinamik Programlama 2 (Demaine) — DP serisinin 2/4'ü; DP'yi tek diziden çoklu girdiye, string'e ve oyunlara taşır. Dört dal — (1) LCS = çoklu girdi: iki dizi varsa alt problem uzaylarını ÇARP, her alt problem bir sonek çifti L(i,j); eşit harf 1 artı çapraz değiştirme argümanıyla, farklı harf max iki seçenek; O(n kare). (2) Ebeveyn işaretçileri: her alt problemde seçilen yönü sakla, L(0,0)'dan tabana yürü, çapraz adımlarda topla; DEĞER değil çözümün KENDİSİ; BFS Dijkstra ebeveyn ağacının DP karşılığı. (3) LIS = alt problem kısıtı: naif tanım çöker çünkü artan kısıtı yerel kontrol edilemez; kısıt ekle L(i) eşittir A[i] ile başlayan en uzun artan, O eşittir max i L(i); O(n kare). (4) Para oyunu = subproblem expansion: substring alt problemleri artı kim başlıyor koordinatı; ben max rakip min minimax; O(n kare). Birleştirici tema: bariz alt problemler yetmezse uzayı polinom kaldığı sürece çoğalt — daha çok alt problem eşittir daha çok kısıt eşittir daha kolay recurrence."
flowchart TD
A["Ders 24 (L16): Dinamik Programlama 2 — LCS, LIS, Oyunlar"] --> L["LCS — çoklu girdi"]
L --> La["alt problem uzaylarını ÇARP<br/>sonek çifti L(i,j); eşit→1+çapraz, farklı→max"]
A --> P["Ebeveyn işaretçileri"]
P --> Pa["seçilen yönü sakla → çözümün KENDİSİ<br/>BFS/Dijkstra ebeveyn ağacının DP karşılığı"]
A --> I["LIS — alt problem kısıtı"]
I --> Ia["naif çöker (artan yerel kontrol edilemez)<br/>kısıt: A[i] ile başlayan; O=max_i L(i)"]
A --> G["Para oyunu — expansion"]
G --> Ga["substring + kim-başlıyor koordinatı<br/>ben max, rakip min (minimax)"]
A --> E["Subproblem expansion"]
E --> Ea["polinom kaldığı sürece çoğalt<br/>daha çok alt problem = daha kolay recurrence"]
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 L,P,I,G,E branch
class La,Pa,Ia,Ga,Ea leaf
```
::: {.callout-tip title="Builder Notu — LCS = diff / git'in kalbi"}
LCS soyut bir bulmaca değil; her gün kullandığın araçların çekirdeğidir. `diff` ve `git merge`, iki dosyayı satır dizileri olarak alıp **en uzun ortak alt-dizilimi** bulur — eşleşen satırlar "ortak", eşleşmeyenler "eklendi/silindi" olur. Aynı recurrence, **DNA/protein hizalamasında** (Needleman-Wunsch, Smith-Waterman), **sürüm karşılaştırmasında** ve **plagiarism tespitinde** yaşar. "Eşit harf → eşleştir, farklı harf → birini dışarıda bırakmayı dene" sezgisi, üç-yol birleştirmenin (three-way merge) ve edit-script üretiminin temelidir.
- **İleriye → LCS:** `diff`/git üç-yol birleştirme, DNA/protein hizalama, sürüm karşılaştırma.
- **İleriye → LIS:** patience sorting, zamanlama, kayıt-defteri analizi.
- **İleriye → minimax:** değişen para oyunu = iki-oyunculu minimax; oyun yapay zekâsı (satranç, alpha-beta budama).
- **Geriye → parent pointers (BFS/Dijkstra):** DP'de de çözümü ebeveyn işaretçileriyle geri kur.
Tek cümle: *İki dizi varsa alt problem uzaylarını çarp; naif tanım recurrence vermiyorsa bir kısıt ekleyip alt problem sayısını genişlet (polinom kalsın); oyunlarda "ben max, rakip min" — hepsi SRTBOT + yerel kaba kuvvetle O(n²).*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 24 (L16) DP 2: LCS / LIS / Oyunlar motoru (_engine.py D24
# bölümü INLINE GÖMÜLÜ — import YOK, brief: setup hücresine göm). Fonksiyonlar:
# lcs_table / lcs_reconstruct / is_subsequence / brute_lcs_length → LCS sonek
# çifti DP + ebeveyn işaretçisi + bağımsız tanık.
# lis_table / lis_reconstruct / brute_lis_length → LIS kısıtlı alt problem DP.
# coin_game / coin_game_diff_witness / build_coin_example → değişen para oyunu
# (minimax) + fark-formülasyonu bağımsız tanık.
# Slate+Amber viz sabitleri (_viz.py COL_*). Bu hücre gizlidir (#| echo: false).
#
# Aşağıdaki TÜM figür hücreleri burada tanımlanan fonksiyonları IMPORT ETMEDEN
# kullanır (dosyadan import YOK). 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 matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ---------------------------------------------------------------------------
# _engine.py D24 (L16) §3-5 — LCS: sonek çifti DP + ebeveyn işaretçisi
# ---------------------------------------------------------------------------
def lcs_table(A, B):
"""LCS sonek-çifti DP (L16 §3-4): L(i,j) = A[i:] ile B[j:] LCS uzunluğu.
İki durum: A[i] == B[j] → 1 + çapraz (değiştirme argümanı: eşleştirmek
hep güvenli); farklı → max(aşağı, sağ) (en az biri dışarıda).
Ebeveyn işaretçisi kaydedilir (L16 §5). Θ(|A|·|B|).
Döndürür: (L, parent) — parent[(i,j)] ∈ {'çapraz', 'aşağı', 'sağ'}."""
na, nb = len(A), len(B)
L, parent = {}, {}
for i in range(na, -1, -1):
for j in range(nb, -1, -1):
if i == na or j == nb:
L[(i, j)] = 0 # taban: bir dizi tükendi
elif A[i] == B[j]:
L[(i, j)] = 1 + L[(i + 1, j + 1)]
parent[(i, j)] = "çapraz"
elif L[(i + 1, j)] >= L[(i, j + 1)]:
L[(i, j)] = L[(i + 1, j)]
parent[(i, j)] = "aşağı" # A[i] dışarıda
else:
L[(i, j)] = L[(i, j + 1)]
parent[(i, j)] = "sağ" # B[j] dışarıda
return L, parent
def lcs_reconstruct(A, B):
"""Ebeveyn izi (L16 §5, Demaine 21:08): L(0,0)'dan tabana yürü; çapraz
adımlarda harfi topla → LCS'in KENDİSİ. Döndürür: (lcs_str, uzunluk)."""
L, parent = lcs_table(A, B)
out, i, j = [], 0, 0
while (i, j) in parent:
p = parent[(i, j)]
if p == "çapraz":
out.append(A[i])
i += 1
j += 1
elif p == "aşağı":
i += 1
else:
j += 1
return "".join(out), L[(0, 0)]
def is_subsequence(s, t):
"""s, t'nin alt-dizilimi mi? İki işaretçi (iterator 'in' ilerletir)."""
it = iter(t)
return all(ch in it for ch in s)
def brute_lcs_length(A, B):
"""Bağımsız tanık (üstel, küçük girdi): A'nın TÜM alt-dizilimleri
(bitmask) × B'ye is_subsequence — recurrence'sız ikinci yol."""
best = 0
for mask in range(1 << len(A)):
s = "".join(A[k] for k in range(len(A)) if mask >> k & 1)
if len(s) > best and is_subsequence(s, B):
best = len(s)
return best
# ---------------------------------------------------------------------------
# _engine.py D24 (L16) §6-7 — LIS: kısıtlı alt problem DP
# ---------------------------------------------------------------------------
def lis_table(A):
"""LIS kısıtlı alt problem DP (L16 §7): naif tanım çöker ('artan' yerel
kontrol edilemez); kısıt ekle → L(i) = A[i] İLE BAŞLAYAN en uzun kesin
artan alt-dizilim. R = 1 + max({L(j) : i < j, A[i] < A[j]} ∪ {0})
(ikinci öğe j'yi yerel kaba kuvvetle dene). O = max_i L(i). O(n²).
Döndürür: (L listesi, parent listesi)."""
n = len(A)
L = [1] * n
parent = [None] * n
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if A[i] < A[j] and 1 + L[j] > L[i]:
L[i] = 1 + L[j]
parent[i] = j
return L, parent
def lis_reconstruct(A):
"""O = max_i L(i); kazanan i'den ebeveyn iziyle LIS'in kendisi.
Döndürür: (öğeler listesi, uzunluk)."""
if not A:
return [], 0
L, parent = lis_table(A)
i = max(range(len(A)), key=lambda k: L[k])
out = []
while i is not None:
out.append(A[i])
i = parent[i]
return out, max(L)
def brute_lis_length(A):
"""Bağımsız tanık (üstel): tüm alt-dizilimler (bitmask); kesin artan
olanların en uzunu — DP'siz."""
best, n = 0, len(A)
for mask in range(1 << n):
seq = [A[k] for k in range(n) if mask >> k & 1]
if len(seq) > best and \
all(seq[x] < seq[x + 1] for x in range(len(seq) - 1)):
best = len(seq)
return best
# ---------------------------------------------------------------------------
# _engine.py D24 (L16) §8-9 — Değişen para oyunu: minimax + expansion
# ---------------------------------------------------------------------------
def coin_game(v):
"""Değişen para oyunu DP (L16 §9, subproblem expansion): x(i, j, p) =
vᵢ..vⱼ kala p başlarsa BENİM alacağım max toplam. p = ben → parayı ben
alır, max; p = sen → sıfır-toplam, rakip benim skorumu MİNİMİZE eder
(Demaine 53:04). Substring alt problemleri, j−i artan; 2n² → O(n²).
Döndürür: (x sözlüğü, ilk optimal hamle 'baş'/'son')."""
n = len(v)
x = {}
for i in range(n):
x[(i, i, "ben")] = v[i] # taban: tek para — ben alırım
x[(i, i, "sen")] = 0 # taban: tek para — sen alırsın
for span in range(2, n + 1):
for i in range(0, n - span + 1):
j = i + span - 1
x[(i, j, "ben")] = max(v[i] + x[(i + 1, j, "sen")],
v[j] + x[(i, j - 1, "sen")])
x[(i, j, "sen")] = min(x[(i + 1, j, "ben")],
x[(i, j - 1, "ben")])
first = None
if n == 1:
first = "baş"
elif n > 1:
front = v[0] + x[(1, n - 1, "sen")]
first = "baş" if x[(0, n - 1, "ben")] == front else "son"
return x, first
def coin_game_diff_witness(v):
"""Bağımsız tanık (FARKLI formülasyon — üçüncü koordinatsız): d(i, j) =
sıradaki oyuncunun skor FARKI maksimumu, d = max(vᵢ − d(i+1, j),
vⱼ − d(i, j−1)); benim toplamım = (Σv + d(0, n−1)) / 2 (sıfır-toplam
cebiri). Aynı cevabı bambaşka yoldan verir."""
n = len(v)
if n == 0:
return 0
d = {}
for i in range(n):
d[(i, i)] = v[i]
for span in range(2, n + 1):
for i in range(0, n - span + 1):
j = i + span - 1
d[(i, j)] = max(v[i] - d[(i + 1, j)], v[j] - d[(i, j - 1)])
return (sum(v) + d[(0, n - 1)]) // 2
def build_coin_example():
"""L16 §8 örneği: [5, 10, 100, 25]. 25'i hemen almak hata (rakip 100'ü
kapar); doğrusu 5 ile başla → 100 sonunda bende: ben 105, rakip 35."""
return [5, 10, 100, 25]
```
## 1. DP 2/4: Üç Örnek ve Yeni Fikirler {#sec-1-dp-2-4}
İlk DP dersi SRTBOT + memoization'ı kurdu. Bu ders, çerçeveyi zorlayan üç problemle yeni teknikleri tanıtır: **çoklu dizi**, **substring**, **ebeveyn işaretçileri** ve **alt problem kısıtı/genişletmesi**. Temel sezgi sabit kalır: "çözümün hangi özelliğini bilsem işim biterdi?" — o özelliği **yerel kaba kuvvetle** dene.
> *"Whenever there's something I don't know, I'll just brute force it."* — Demaine, 31:58
Her problemde aynı refleks işler: bir alt problemde bilmediğin küçük bir şey varsa (hangi harf eşleşir, ikinci öğe ne, sıra kimde), o şeyin **sabit veya polinom sayıda** seçeneği varsa hepsini dener, alt problem çözümlerini yeniden kullanırsın.
## 2. SRTBOT Hatırlatma {#sec-2-srtbot-hatirlatma}
Her DP aynı altı adımı izler: alt problemleri (dizi için prefix/suffix/substring) **tanımla**, bir recurrence ile **ilişkilendir** (alt-problem grafı **DAG** olmalı), **topolojik** sırada çöz, **taban** durumu ekle, **orijinali** kur, **süreyi** ($\sum$ alt problem $\times$ özyineleme-dışı iş) hesapla. Yeni bir alt problem türüne ihtiyaç doğdukça **genişlet** — polinom kaldığı sürece.
Bu derste S adımı her seferinde sınanır: tek dizinin prefix/suffix/substring'i yetmediğinde, alt problem uzayını ya **çarparız** (LCS), ya **kısıtlarız** (LIS), ya da bir **koordinatla genişletiriz** (para oyunu).
## 3. LCS: Çoklu Girdi → Alt Problem Çarpımı {#sec-3-lcs-coklu-girdi}
**Problem.** İki dizi A, B verilir; ikisinin de **alt-dizilimi** olan en uzun diziyi bul (substring değil — aradan öğe atlanabilir). Klasik örnek: "hieroglyphology" ve "Michelangelo".
Bowling'de tek dizi vardı; burada **iki**. Çözüm — çoklu girdi için genel numara:
> *"subproblems for multiple inputs... We just take the product, multiply the subproblem spaces."* — Demaine, 7:04
**S:** $L(i, j) = A[i:]$ ve $B[j:]$ soneklerinin LCS'i (her alt problem bir **sonek çifti**); $0 \le i \le |A|$, $0 \le j \le |B|$. Alt problem sayısı $(|A|+1) \cdot (|B|+1)$ — iki dizi için polinom; ama **n dizi** olsaydı $n^n$ (üstel) olurdu.
@fig-lcs-bignums ders örneğini motor üzerinde gösterir: $\mathrm{LCS}(\text{hieroglyphology}, \text{Michelangelo})$ uzunluğu **5**'tir, ama optimal çözüm **tekil değildir** — motorun tie-break izi "iello" iken Demaine'in derste verdiği "hello" da geçerli bir ortak alt-dizilimdir (ikisi de uzunluk 5, `is_subsequence` ile doğrulanır). Bu önemli bir CS nüansıdır: DP'nin pin'lediği şey **değerdir** (uzunluk 5), tek bir temsilci dizgi değil; çözüm kümesi birden çok elemanlı olabilir.
```{python}
#| label: fig-lcs-bignums
#| fig-cap: "LCS('hieroglyphology', 'Michelangelo') — optimal TEKİL değil, pin'lenen DEĞER (Demaine L16 §3). ÜST blok: A=hieroglyphology ve B=Michelangelo büyük harf kutuları arası 'iello' eşleşmeleri (motor tie-break izi, amber bağlantı çizgileri, soldan-açgözlü konumlar). ALT blok: aynı kelimeler arası 'hello' eşleşmeleri (Demaine'in derste verdiği ALTERNATİF optimal, soluk slate kesik çizgiler). SAĞ kutu: LCS uzunluğu = 5; optimal tekil değil — motor 'iello', ders 'hello', ikisi de geçerli ortak alt-dizilim. ALT NOT: çözüm kümesi geniş olunca pin'lenen şey DEĞER (uzunluk 5), temsilci dizgi değil. Veri MOTORDAN (assert): lcs_reconstruct('hieroglyphology','Michelangelo') == ('iello', 5); is_subsequence('hello', her ikisi) True; brute_lcs_length == 5; 'iello' != 'hello' ama eşit uzunluk."
#| fig-width: 11.5
#| fig-height: 5.0
# fig-lcs-bignums (L16 §3): LCS çoklu girdi — optimal tekil değil.
# Veri MOTORDAN (lcs_reconstruct + is_subsequence + brute_lcs_length). networkx YOK.
A = "hieroglyphology"
B = "Michelangelo"
lcs_str, lcs_len = lcs_reconstruct(A, B)
assert lcs_str == "iello", lcs_str
assert lcs_len == 5, lcs_len
assert is_subsequence("hello", A) and is_subsequence("hello", B)
assert is_subsequence("iello", A) and is_subsequence("iello", B)
assert brute_lcs_length(A, B) == 5, brute_lcs_length(A, B)
assert lcs_str != "hello" and len(lcs_str) == len("hello")
def _greedy_left(sub, word):
"""sub karakterlerini word içinde soldan-açgözlü eşleştir → konumlar."""
pos, start = [], 0
for ch in sub:
idx = word.index(ch, start)
pos.append(idx)
start = idx + 1
return pos
pos_iello_A = _greedy_left("iello", A)
pos_iello_B = _greedy_left("iello", B)
pos_hello_A = _greedy_left("hello", A)
pos_hello_B = _greedy_left("hello", B)
assert pos_iello_A == [1, 2, 6, 11, 12]
assert pos_iello_B == [1, 4, 5, 10, 11]
assert pos_hello_A == [0, 2, 6, 11, 12]
assert pos_hello_B == [3, 4, 5, 10, 11]
fig, ax = plt.subplots(figsize=(11.5, 5.0))
fig.patch.set_facecolor(COL_WHITE)
cell_w, cell_h = 0.62, 0.62
x0 = 0.0
yA, yB = 4.0, 2.6
def _draw_word(word, y, hot_positions, hot_color, hot_fc):
centers = []
hotset = set(hot_positions)
for k, ch in enumerate(word):
x = x0 + k * cell_w
hot = k in hotset
ax.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.92, cell_h * 0.92, boxstyle="square,pad=0.0",
fc=hot_fc if hot else COL_BG,
ec=hot_color if hot else COL_SLATE_400,
linewidth=2.4 if hot else 1.3, zorder=3))
cx, cy = x + cell_w * 0.46, y + cell_h * 0.46
centers.append((cx, cy))
ax.text(cx, cy, ch, ha="center", va="center",
fontsize=13, color=COL_TEXT, weight="bold", zorder=5)
return centers
cA = _draw_word(A, yA, pos_iello_A, COL_ACCENT, COL_AMBER_100)
cB = _draw_word(B, yB, pos_iello_B, COL_ACCENT, COL_AMBER_100)
ax.text(x0 - 0.35, yA + cell_h * 0.46, "A", ha="right", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
ax.text(x0 - 0.35, yB + cell_h * 0.46, "B", ha="right", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
for (ia, ib), ch in zip(zip(pos_iello_A, pos_iello_B), "iello"):
xa, ya0 = cA[ia][0], yA
xb, yb0 = cB[ib][0], yB + cell_h * 0.92
ax.plot([xa, xb], [ya0, yb0], color=COL_ACCENT,
linewidth=2.4, zorder=2, alpha=0.95)
mx, my = (xa + xb) / 2.0, (ya0 + yb0) / 2.0
ax.text(mx, my, ch, ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=6,
bbox=dict(boxstyle="circle,pad=0.12", fc=COL_WHITE,
ec=COL_ACCENT, linewidth=1.2))
ax.text(x0 + len(A) * cell_w * 0.5, yA + cell_h + 0.30,
'Motor izi (tie-break): LCS = "iello"', ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold")
yA2, yB2 = 1.15, -0.25
cA2 = _draw_word(A, yA2, pos_hello_A, COL_SLATE_500, COL_BG)
cB2 = _draw_word(B, yB2, pos_hello_B, COL_SLATE_500, COL_BG)
ax.text(x0 - 0.35, yA2 + cell_h * 0.46, "A", ha="right", va="center",
fontsize=12, color=COL_SLATE_500, weight="bold")
ax.text(x0 - 0.35, yB2 + cell_h * 0.46, "B", ha="right", va="center",
fontsize=12, color=COL_SLATE_500, weight="bold")
for (ia, ib), ch in zip(zip(pos_hello_A, pos_hello_B), "hello"):
xa, ya0 = cA2[ia][0], yA2
xb, yb0 = cB2[ib][0], yB2 + cell_h * 0.92
ax.plot([xa, xb], [ya0, yb0], color=COL_SLATE_400,
linewidth=1.6, zorder=2, alpha=0.85, linestyle=(0, (4, 2)))
ax.text(x0 + len(A) * cell_w * 0.5, yA2 + cell_h + 0.28,
'Demaine örneği: "hello" — ALTERNATİF optimal',
ha="center", va="center", fontsize=10.5, color=COL_SLATE_500,
weight="bold")
box_x = x0 + len(A) * cell_w + 0.55
box_y = 2.35
box_w, box_h = 4.05, 2.35
ax.add_patch(FancyBboxPatch(
(box_x, box_y), box_w, box_h,
boxstyle="round,pad=0.04,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=4))
ax.text(box_x + box_w * 0.5, box_y + box_h - 0.34,
f"LCS uzunluğu = {lcs_len}", ha="center", va="center",
fontsize=14, color=COL_AMBER_700, weight="bold", zorder=6)
msg = ("Optimal TEKİL DEĞİL:\n"
'motor tie-break "iello",\n'
'ders "hello".\n'
"İkisi de geçerli ortak\n"
"alt-dizilim (assert'li).")
ax.text(box_x + 0.22, box_y + box_h - 0.78, msg, ha="left", va="top",
fontsize=9.5, color=COL_TEXT, zorder=6, linespacing=1.35)
ax.text(x0 + (len(A) * cell_w + box_w) * 0.42, -1.25,
"Çözüm kümesi geniş olunca pin'lenen şey DEĞER (uzunluk 5), "
"temsilci dizgi değil.",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic")
ax.set_xlim(x0 - 0.85, box_x + box_w + 0.3)
ax.set_ylim(-1.7, yA + cell_h + 0.85)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 4. LCS Recurrence: Eşit / Farklı Durumlar {#sec-4-lcs-recurrence}
**Çalışılan Örnek — iki durum.** İlk harflere $A[i]$ ve $B[j]$ bakarız:
- **Farklı ($A[i] \neq B[j]$):** ikisi birden LCS'in ilk harfi olamaz; **en az biri** dışarıda. Hangisi bilinmez, ikisini de dene:
$$L(i, j) = \max\bigl( L(i+1, j),\; L(i, j+1) \bigr)$$
> *"at least one of Ai and Bj is not in the LCS."* — Demaine, 11:24
- **Eşit ($A[i] = B[j]$):** bu harfi **eşleştirmek** her zaman optimaldir (değiştirme argümanı: çaprazlamayan bir eşleştirmede $i$'yi $j$ ile eşlemek kaybettirmez), 1 puan al ve ikisinden de ilerle:
$$L(i, j) = 1 + L(i+1, j+1)$$
**T:** $i, j$ azalan. **B:** bir dizi tükenirse $L = 0$. **O:** $L(0, 0)$. **Süre:** $\Theta(|A| \cdot |B|)$ alt problem $\times\, O(1) = O(n^2)$.
@fig-lcs-grid bu recurrence'ı küçük bir örnek üzerinde tam DP-grid olarak gösterir ($A = \text{their}$, $B = \text{habit}$): her hücre $L(i, j)$ değerini taşır; **çapraz** (amber) oklar eşit-harf eşleşmesini ($1 + $ çapraz), **aşağı/sağ** (slate) oklar farklı-harf max seçimini gösterir. $L(0, 0) = 2$ ve ebeveyn izi LCS'in kendisini — "hi" — verir; bu §5'in konusu olan ebeveyn işaretçilerinin somut hâlidir.
```{python}
#| label: fig-lcs-grid
#| fig-cap: "LCS sonek-çifti DP tablosu + ebeveyn izi (Demaine L16 §4-5 İMZA). A='their' (satır), B='habit' (sütun); her hücre L(i,j) = A[i:] ile B[j:] LCS uzunluğu. ÇAPRAZ amber ok = eşit harf (1+çapraz, değiştirme argümanı: eşleştirmek hep güvenli); AŞAĞI/SAĞ slate ok = farklı harf max(A[i] dışarıda ↓ / B[j] dışarıda →). Amber yol L(0,0)'dan tabana ebeveyn izi; çapraz adımların harf rozetleri (amber daireler) LCS karakterleridir. Sağ üst: LCS uzunluğu = L(0,0) = 2, iz 'h → i', LCS('their','habit') = 'hi'. Veri MOTORDAN (assert): lcs_table + lcs_reconstruct; L(0,0) == 2; lcs_str == 'hi'; is_subsequence('hi', her ikisi); brute_lcs_length == 2; izden toplanan == lcs_str. Alt not: ≠ → max(2 seçenek), = → 1+çapraz; Θ(|A|·|B|)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-lcs-grid (L16 §4-5 İMZA): LCS DP grid + ebeveyn izi. Veri MOTORDAN.
A = "their"
B = "habit"
L, parent = lcs_table(A, B)
s, n = lcs_reconstruct(A, B)
na, nb = len(A), len(B)
assert L[(0, 0)] == n, L[(0, 0)]
assert n == 2 and s == "hi", (n, s)
assert is_subsequence(s, A) and is_subsequence(s, B)
assert brute_lcs_length(A, B) == n
# Ebeveyn izini yürü (yolda hangi hücreler, çapraz harfler)
path_cells = []
diag_cells = set()
diag_letters = {}
i, j = 0, 0
path_cells.append((i, j))
while (i, j) in parent:
p = parent[(i, j)]
if p == "çapraz":
diag_cells.add((i, j))
diag_letters[(i, j)] = A[i]
i += 1
j += 1
elif p == "aşağı":
i += 1
else:
j += 1
path_cells.append((i, j))
collected = "".join(diag_letters[c] for c in path_cells if c in diag_letters)
assert collected == s, (collected, s)
path_set = set(path_cells)
CELL = 1.0
fig, ax = plt.subplots(figsize=(11, 7))
def _cx(jj):
return jj * CELL + CELL * 0.5
def _cy(ii):
return (na - ii) * CELL + CELL * 0.5
for i in range(na + 1):
for j in range(nb + 1):
x = j * CELL
y = (na - i) * CELL
on_path = (i, j) in path_set
is_base = (i == na or j == nb)
if is_base:
fc, ec, lw = COL_WHITE, COL_SLATE_400, 1.0
elif on_path:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.2
ax.add_patch(FancyBboxPatch(
(x, y), CELL * 0.96, CELL * 0.96, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=2))
val = L[(i, j)]
ax.text(_cx(j), _cy(i) + CELL * 0.10, str(val),
ha="center", va="center", fontsize=14,
color=COL_AMBER_700 if on_path else COL_TEXT,
weight="bold", zorder=5)
for i in range(na):
ax.text(-0.55, _cy(i), A[i], ha="center", va="center",
fontsize=15, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(-0.55, _cy(na), "∅", ha="center", va="center",
fontsize=13, color=COL_SLATE_500, zorder=5)
for j in range(nb):
ax.text(_cx(j), (na + 1) * CELL + CELL * 0.5, B[j], ha="center", va="center",
fontsize=15, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(_cx(nb), (na + 1) * CELL + CELL * 0.5, "∅", ha="center", va="center",
fontsize=13, color=COL_SLATE_500, zorder=5)
for i in range(na):
for j in range(nb):
p = parent.get((i, j))
on_path = (i, j) in path_set and (i, j) in parent
if p == "çapraz":
x0, y0 = _cx(j) + CELL * 0.20, _cy(i) - CELL * 0.20
x1, y1 = _cx(j + 1) - CELL * 0.20, _cy(i + 1) + CELL * 0.20
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>",
mutation_scale=15 if on_path else 11,
color=COL_ACCENT if on_path else COL_AMBER_600,
linewidth=3.0 if on_path else 1.6, zorder=4))
elif p == "aşağı":
x0 = _cx(j)
y0 = _cy(i) - CELL * 0.30
y1 = _cy(i + 1) + CELL * 0.30
win = on_path
ax.add_patch(FancyArrowPatch(
(x0, y0), (x0, y1), arrowstyle="-|>",
mutation_scale=14 if win else 9,
color=COL_ACCENT if win else COL_SLATE_400,
linewidth=3.0 if win else 1.3, zorder=4))
elif p == "sağ":
y0 = _cy(i)
x0 = _cx(j) + CELL * 0.30
x1 = _cx(j + 1) - CELL * 0.30
win = on_path
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y0), arrowstyle="-|>",
mutation_scale=14 if win else 9,
color=COL_ACCENT if win else COL_SLATE_400,
linewidth=3.0 if win else 1.3, zorder=4))
for (ci, cj) in diag_cells:
bx = _cx(cj) - CELL * 0.32
by = _cy(ci) + CELL * 0.30
ax.add_patch(Circle((bx, by), CELL * 0.16, fc=COL_AMBER_600,
ec=COL_WHITE, linewidth=1.5, zorder=6))
ax.text(bx, by, diag_letters[(ci, cj)], ha="center", va="center",
fontsize=11, color=COL_WHITE, weight="bold", zorder=7)
ax.text(_cx(0), _cy(0) - CELL * 0.34, "başla", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=6)
info_x = (nb + 1) * CELL + 0.55
info_y = (na + 0.3) * CELL + CELL * 0.5
ax.text(info_x, info_y, f"LCS uzunluğu = L(0,0) = {n}", ha="left", va="center",
fontsize=13.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(info_x, info_y - 0.55, f"iz: {' → '.join(s)}", ha="left", va="center",
fontsize=12, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(info_x, info_y - 1.05, f"LCS(“{A}”, “{B}”) = “{s}”",
ha="left", va="center", fontsize=11, color=COL_TEXT, zorder=6)
leg_y = info_y - 1.85
ax.add_patch(FancyArrowPatch((info_x, leg_y), (info_x + 0.55, leg_y),
arrowstyle="-|>", mutation_scale=12, color=COL_ACCENT,
linewidth=2.4, zorder=6))
ax.text(info_x + 0.75, leg_y, "eşit harf → 1 + çapraz",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, zorder=6)
ax.add_patch(FancyArrowPatch((info_x, leg_y - 0.5), (info_x + 0.55, leg_y - 0.5),
arrowstyle="-|>", mutation_scale=10, color=COL_SLATE_400,
linewidth=1.5, zorder=6))
ax.text(info_x + 0.75, leg_y - 0.5, "farklı harf → max(aşağı, sağ)",
ha="left", va="center", fontsize=9.5, color=COL_SLATE_500, zorder=6)
ax.text((nb + 1) * CELL * 0.5, -0.9,
"≠ → max(2 seçenek: A[i] dışarıda ↓ / B[j] dışarıda →) "
"= → 1 + çapraz (değiştirme argümanı: eşleştirmek hep güvenli) "
"Θ(|A|·|B|)",
ha="center", va="center", fontsize=10, color=COL_TEXT,
weight="bold", zorder=6)
ax.set_xlim(-1.3, (nb + 1) * CELL + 4.6)
ax.set_ylim(-1.35, (na + 2) * CELL + 0.4)
ax.set_aspect("equal")
ax.axis("off")
fig.tight_layout()
plt.show()
```
## 5. Parent Pointers ile Çözüm Kurtarma {#sec-5-parent-pointers}
DP yalnız **uzunluğu** değil, **LCS'in kendisini** de verir. Her alt problemde "hangi seçeneği aldım?" yönünde bir **ebeveyn işaretçisi** (kırmızı/amber ok) çiz; sonda $L(0,0)$'dan tabana izleyip **çapraz kenarları** (harf eşleşmeleri) toplarsan LCS çıkar.
> *"we just follow these pointers backward... and we get our answer."* — Demaine, 21:08
Bu, BFS/Dijkstra'daki ebeveyn ağacının DP karşılığıdır; bugünkü tüm DP'lerde kullanılabilir. Kritik fark: ebeveyn işaretçisi **değeri** (uzunluk) değil, **çözümün kendisini** (dizinin/yolun kendisini) geri kurar.
@fig-parent-pointers fikri iki seviyede gösterir: solda kavramsal bir $3 \times 3$ DP-şeması (amber çapraz = topla, slate aşağı/sağ = atla; "geriye yürü, çapraz adımlarda topla"); sağda **iki gerçek iz** motordan — LCS "their"×"habit"in çapraz harfleri "hi"yi, LIS "carbohydrate"in ebeveyn zinciri (indeks 1→3→4→8→10) "abort"u verir. Rozet altını çizer: kaydedilen yön DEĞER değil, çözümün KENDİSİDİR.
```{python}
#| label: fig-parent-pointers
#| fig-cap: "Ebeveyn işaretçisi: çözümü geri kurma (Demaine L16 §5, 21:08). SOL panel KAVRAM: küçük 3×3 DP-tablo şeması; her hücrede seçilen yönün ebeveyn oku (amber çapraz = TOPLA, slate aşağı/sağ = atla); L(0,0)'dan tabana iz 'geriye yürü, çapraz adımlarda topla'. SAĞ panel İKİ GERÇEK İZ (motordan): (a) LCS 'their'×'habit' çapraz-adım harfleri → 'hi'; (b) LIS 'carbohydrate' ebeveyn zinciri indeksleri 1→3→4→8→10 → 'abort'. Rozet: BFS/Dijkstra ebeveyn ağacının DP karşılığı — kaydedilen yön DEĞER değil, çözümün KENDİSİ. Veri MOTORDAN (assert): lcs_reconstruct('their','habit') == ('hi', 2); çapraz harfleri 'hi'; lis_reconstruct('carbohydrate') == (['a','b','o','r','t'], 5); zincir indeksleri [1,3,4,8,10]."
#| fig-width: 11.0
#| fig-height: 5.5
# fig-parent-pointers (L16 §5 İMZA): ebeveyn işaretçisi → çözümün kendisi.
# Veri MOTORDAN (lcs_table/lcs_reconstruct + lis_table/lis_reconstruct).
A_l, B_l = "their", "habit"
L_l, parent_l = lcs_table(A_l, B_l)
lcs_str_l, lcs_len_l = lcs_reconstruct(A_l, B_l)
i, j = 0, 0
lcs_trail = []
while (i, j) in parent_l:
p = parent_l[(i, j)]
ch = A_l[i] if p == "çapraz" else None
lcs_trail.append((i, j, p, ch))
if p == "çapraz":
i += 1
j += 1
elif p == "aşağı":
i += 1
else:
j += 1
diag_letters_l = [t[3] for t in lcs_trail if t[3] is not None]
assert L_l[(0, 0)] == 2 and lcs_str_l == "hi" and lcs_len_l == 2
assert "".join(diag_letters_l) == "hi"
S_l = "carbohydrate"
Ll, par = lis_table(S_l)
lis_seq, lis_len = lis_reconstruct(S_l)
imax = max(range(len(S_l)), key=lambda k: Ll[k])
chain = []
k = imax
while k is not None:
chain.append((k, S_l[k]))
k = par[k]
chain_idx = [c[0] for c in chain]
chain_chars = [c[1] for c in chain]
assert lis_seq == ["a", "b", "o", "r", "t"] and lis_len == 5
assert chain_idx == [1, 3, 4, 8, 10]
assert chain_chars == ["a", "b", "o", "r", "t"]
def _dir_arrow(ax, fcx, fcy, r, c, cell, d, color, lw, scale,
alpha=1.0, label=None, lab_dx=0.0, lab_dy=0.0):
x, y = fcx(c), fcy(r)
off = cell * 0.42
if d == "diag":
tx, ty = x + off, y - off
elif d == "down":
tx, ty = x, y - off
else:
tx, ty = x + off, y
sx = x + (tx - x) * 0.30
sy = y + (ty - y) * 0.30
ax.add_patch(FancyArrowPatch(
(sx, sy), (tx, ty), arrowstyle="-|>", mutation_scale=scale,
color=color, linewidth=lw, alpha=alpha, zorder=5))
if label is not None:
ax.text(tx + lab_dx, ty + lab_dy, label, ha="center", va="center",
fontsize=7.0, color=color, weight="bold", zorder=6)
fig, (axL, axR) = plt.subplots(
1, 2, figsize=(11.0, 5.5), gridspec_kw={"width_ratios": [1.0, 1.35]})
# --- SOL: kavramsal 3×3 DP şeması ---
cell = 1.0
x0c, y0c = 0.0, 0.0
def _ccx(c):
return x0c + c * cell + cell * 0.5
def _ccy(r):
return y0c - r * cell - cell * 0.5
on_trail = {(0, 0), (1, 1), (2, 1)}
for r in range(3):
for c in range(3):
x = x0c + c * cell
y = y0c - r * cell - cell
hot = (r, c) in on_trail
axL.add_patch(FancyBboxPatch(
(x, y), cell * 0.96, cell * 0.96, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.2 if hot else 1.2, zorder=2))
axL.text(_ccx(c), _ccy(r) + cell * 0.20, f"L({r},{c})",
ha="center", va="center", fontsize=8.0,
color=COL_SLATE_500, zorder=4)
faint_dirs = {(0, 1): "down", (0, 2): "down", (1, 0): "right",
(1, 2): "down", (2, 0): "right", (2, 2): "diag"}
for (r, c), d in faint_dirs.items():
_dir_arrow(axL, _ccx, _ccy, r, c, cell, d, color=COL_SLATE_400,
lw=1.3, scale=11, alpha=0.7)
_dir_arrow(axL, _ccx, _ccy, 0, 0, cell, "diag", color=COL_ACCENT, lw=2.6,
scale=16, label="çapraz: TOPLA", lab_dx=0.0, lab_dy=0.30)
_dir_arrow(axL, _ccx, _ccy, 1, 1, cell, "down", color=COL_AMBER_700, lw=2.4,
scale=15, label="aşağı: atla", lab_dx=0.62, lab_dy=0.0)
_dir_arrow(axL, _ccx, _ccy, 2, 1, cell, "diag", color=COL_ACCENT, lw=2.6,
scale=16, label="çapraz: TOPLA", lab_dx=0.0, lab_dy=-0.30)
axL.text(_ccx(0), _ccy(0) - cell * 0.30, "başla\nL(0,0)", ha="center",
va="center", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=5)
axL.text(_ccx(2) + cell * 0.30, _ccy(2) - cell * 0.62, "taban ⊥",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=4)
axL.text(_ccx(1), y0c + 0.55, "çapraz adımlarda toplanan = optimal dizi",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=5)
axL.text(_ccx(1), y0c - 3 * cell - 0.72, "“geriye yürü; çapraz adımlarda topla”",
ha="center", va="center", fontsize=8.5, color=COL_TEXT,
style="italic", zorder=5)
axL.text(_ccx(1), y0c - 3 * cell - 1.06,
"— Demaine 21:08 (ebeveyn işaretçisi → çözümün kendisi)",
ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=5)
axL.set_title("Kavram: ebeveyn izi (3×3 DP şeması)",
color=COL_TEXT, fontsize=11.5, weight="bold")
axL.set_xlim(x0c - 1.0, x0c + 3 * cell + 1.3)
axL.set_ylim(y0c - 3 * cell - 1.5, y0c + 1.0)
axL.set_aspect("equal")
axL.axis("off")
# --- SAĞ: iki gerçek iz (LCS harfleri + LIS zincir indeksleri) ---
y_lcs = 5.0
used_i = {t[0] for t in lcs_trail if t[3] is not None}
cw = 0.78
axR.text(0.0, y_lcs + 1.05, "LCS “their” × “habit” — çapraz-adım harfleri",
ha="left", va="center", fontsize=10.0, color=COL_PRIMARY, weight="bold")
for k, ch in enumerate(A_l):
x = k * cw
hot = k in used_i
axR.add_patch(FancyBboxPatch(
(x, y_lcs), cw * 0.9, 0.62, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.2 if hot else 1.2, zorder=2))
axR.text(x + cw * 0.45, y_lcs + 0.31, ch, ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold", zorder=4)
axR.text(x + cw * 0.45, y_lcs - 0.22, str(k), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=4)
ty = y_lcs - 0.78
xx = 0.0
axR.text(xx, ty, "iz: ", ha="left", va="center", fontsize=8.0,
color=COL_TEXT, weight="bold")
xx += 0.40
for (ii, jj, p, ch) in lcs_trail:
if p == "çapraz":
txt, hot = "(%d,%d) çapraz → '%s'" % (ii, jj, ch), True
elif p == "aşağı":
txt, hot = "(%d,%d) aşağı" % (ii, jj), False
else:
txt, hot = "(%d,%d) sağ" % (ii, jj), False
col = COL_AMBER_700 if hot else COL_SLATE_500
axR.text(xx, ty, txt + " ", ha="left", va="center", fontsize=7.6,
color=col, weight="bold" if hot else "normal")
xx += 0.105 * (len(txt) + 2)
axR.text(0.0, ty - 0.55, "→ LCS = “%s” (uzunluk %d)" % (lcs_str_l, lcs_len_l),
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold")
y_lis = 1.30
chain_set = set(chain_idx)
cw2 = 0.72
axR.text(0.0, y_lis + 1.30, "LIS “carbohydrate” — ebeveyn zinciri (indeksler)",
ha="left", va="center", fontsize=10.0, color=COL_PRIMARY, weight="bold")
centers = []
for k, ch in enumerate(S_l):
x = k * cw2
hot = k in chain_set
axR.add_patch(FancyBboxPatch(
(x, y_lis), cw2 * 0.9, 0.60, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.2 if hot else 1.1, zorder=2))
axR.text(x + cw2 * 0.45, y_lis + 0.30, ch, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4)
axR.text(x + cw2 * 0.45, y_lis - 0.20, str(k), ha="center", va="center",
fontsize=7.0, color=COL_SLATE_500, zorder=4)
centers.append((x + cw2 * 0.45, y_lis))
for m in range(len(chain_idx) - 1):
x0a, _ = centers[chain_idx[m]]
x1a, _ = centers[chain_idx[m + 1]]
ytop = y_lis + 0.60
axR.add_patch(FancyArrowPatch(
(x0a, ytop), (x1a, ytop), arrowstyle="-|>", mutation_scale=12,
color=COL_ACCENT, linewidth=2.0, zorder=5,
connectionstyle="arc3,rad=-0.34"))
chain_lbl = " → ".join("'%s'(idx %d)" % (c, ix) for ix, c in chain)
axR.text(0.0, y_lis - 0.70, "zincir: " + chain_lbl, ha="left", va="center",
fontsize=8.2, color=COL_AMBER_700, weight="bold")
axR.text(0.0, y_lis - 1.10, "→ LIS = “%s” (uzunluk %d)"
% ("".join(chain_chars), lis_len),
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold")
bx, by, bw, bh = -0.15, -1.55, 8.9, 0.95
axR.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_600, linewidth=1.8, zorder=2))
axR.text(bx + bw * 0.5, by + bh * 0.62,
"BFS / Dijkstra ebeveyn ağacının DP karşılığı",
ha="center", va="center", fontsize=9.5, color=COL_TEXT,
weight="bold", zorder=4)
axR.text(bx + bw * 0.5, by + bh * 0.24,
"kaydedilen yön = DEĞER değil, çözümün KENDİSİ",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
style="italic", zorder=4)
axR.set_title("İki gerçek iz (motordan)", color=COL_TEXT,
fontsize=11.5, weight="bold")
axR.set_xlim(-0.4, 9.2)
axR.set_ylim(-1.75, 6.4)
axR.axis("off")
fig.suptitle(
"Ebeveyn işaretçisi: çözümü geri kurma (L16 §5) — DP'de değer değil dizinin kendisi",
color=COL_TEXT, fontsize=12.5, y=0.99, weight="bold")
plt.tight_layout(rect=(0, 0, 1, 0.96))
plt.show()
```
## 6. LIS: Naif Tanım Neden Çöker {#sec-6-lis-naif-cokus}
**Problem.** Tek dizi; en uzun **kesin artan** alt-dizilim. Örnek: "carbohydrate" → "abort".
Naif **S:** $L(i) = A[i:]$'nin en uzun artan alt-dizilimi. **R denemesi:** $L(i) = \max\bigl(L(i+1),\; 1 + L(i+1)\bigr)$ — **çöker**, çünkü "artan" kısıtı hiç uygulanmıyor; $A[i]$'yi eklediğimde $L(i+1)$ zincirinin **ikinci öğesinin** ne olduğunu ($A[i]$'den büyük mü?) bilmiyoruz. "Artan" koşulunu yerel olarak kontrol edemediğimiz için recurrence yazılamaz.
@fig-lis-constraint bu çöküşü ve §7'deki çözümü tek figürde toplar: üst panel naif tanımın neden recurrence vermediğini (üstü çizik deneme + "ikinci öğeyi bilmiyoruz") gösterir; alt panel kısıtlı tanımın "carbohydrate" üzerinde nasıl çalıştığını — her harfin altında $L(i)$ değeri ve kazanan zincir a→b→o→r→t (motordan) — verir.
## 7. LIS: Alt Problem Kısıtı {#sec-7-lis-alt-problem-kisiti}
**Çalışılan Örnek — kısıt ekleme.** Çözüm: alt probleme bir **koşul** ekle.
> *"this is the idea of subproblem constraints or conditions."* — Demaine, 28:25
**S (kısıtlı):** $L(i) = A[i]$ **ile başlayan** (yani $A[i]$'yi içeren) en uzun artan alt-dizilim. **O:** $\max_i L(i)$ (LIS nerede başlar bilmediğimizden hepsinin maksimumu). **R:** $A[i]$ kesin var; ikinci öğe $j$'yi bilmiyoruz, kaba kuvvetle dene ($i < j$ ve $A[i] < A[j]$ olan tüm $j$):
$$L(i) = 1 + \max\bigl( \{\, L(j) : i < j,\; A[i] < A[j] \,\} \cup \{0\} \bigr)$$
**T:** $i$ azalan. **B:** $L(|A|) = 0$. **Süre:** $n$ alt problem $\times\, O(n)$ özyineleme-dışı iş $= O(n^2)$. Artan kısıtı, $j$ seçimindeki $A[i] < A[j]$ koşuluyla **yerel** olarak garanti edilir; gerisi tümevarımla artan kalır.
```{python}
#| label: fig-lis-constraint
#| fig-cap: "LIS — naif tanım çöker, kısıtlı alt problem kurtarır (Demaine L16 §6-7 İMZA, 28:25). ÜST panel: naif tanım çöküşü — x(i)=A[i:] LIS'i deseydik denenen R = max(L(i+1), 1+L(i+1)) ÜSTÜ ÇİZİK; çünkü ikinci öğenin A[i]'den büyük mü olduğunu BİLMİYORUZ, 'artan' yerel kontrol edilemez. ALT panel: kısıtlı tanım — 'carbohydrate' 12 harf, her harf altında L(i) (motordan: [4,5,2,4,3,3,1,3,2,2,1,1]); kazanan zincir a→b→o→r→t amber oklarla (ebeveyn izi idx 1→3→4→8→10), O = max_i L(i) = 5 rozeti (i=1). Kısıt kutusu: L(i)=A[i] İLE BAŞLAYAN en uzun artan; R = 1 + max({L(j):i<j, A[i]<A[j]} ∪ {0}); n alt problem × O(n) yerel tarama = O(n²). Veri MOTORDAN (assert): lis_table('carbohydrate') L birebir; lis_reconstruct == (['a','b','o','r','t'], 5); brute_lis_length == 5; zincir [1,3,4,8,10]."
#| fig-width: 11.5
#| fig-height: 7.0
# fig-lis-constraint (L16 §6-7 İMZA): LIS naif çöküş + kısıtlı alt problem.
# Veri MOTORDAN (lis_table + lis_reconstruct + brute_lis_length).
A_lis = "carbohydrate"
L_lis, parent_lis = lis_table(A_lis)
items_lis, n_len = lis_reconstruct(A_lis)
brute = brute_lis_length(A_lis)
start_idx = max(range(len(A_lis)), key=lambda k: L_lis[k])
chain_idx = []
i = start_idx
while i is not None:
chain_idx.append(i)
i = parent_lis[i]
chain_chars = [A_lis[k] for k in chain_idx]
O = max(L_lis)
assert len(A_lis) == 12
assert items_lis == ["a", "b", "o", "r", "t"] and n_len == 5
assert brute == 5 and O == 5 and O == n_len
assert L_lis == [4, 5, 2, 4, 3, 3, 1, 3, 2, 2, 1, 1], L_lis
assert start_idx == 1 and chain_idx == [1, 3, 4, 8, 10]
assert chain_chars == ["a", "b", "o", "r", "t"]
assert is_subsequence("".join(chain_chars), A_lis)
fig = plt.figure(figsize=(11.5, 7.0))
gs = fig.add_gridspec(2, 1, height_ratios=[1.0, 1.32], hspace=0.28)
ax_top = fig.add_subplot(gs[0])
ax_bot = fig.add_subplot(gs[1])
# ÜST PANEL: naif çöküş
ax_top.set_xlim(0, 11.5)
ax_top.set_ylim(0, 3.2)
ax_top.axis("off")
ax_top.text(0.15, 2.92, "Naif tanım çöker", ha="left", va="center",
fontsize=13.5, color=COL_TEXT, weight="bold")
ax_top.text(0.15, 2.52, "x(i) = A[i:]'in LIS'i deseydik...", ha="left",
va="center", fontsize=11, color=COL_PRIMARY, style="italic")
ax_top.add_patch(FancyBboxPatch(
(0.15, 0.30), 11.05, 1.92, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=1))
rec_y = 1.74
ax_top.text(0.55, rec_y, "denenen yineleme:", ha="left", va="center",
fontsize=10.5, color=COL_TEXT)
ax_top.text(3.15, rec_y, "R = max( L(i+1), 1 + L(i+1) )", ha="left",
va="center", fontsize=12, color=COL_SLATE_500, weight="bold",
family="monospace")
ax_top.plot([3.10, 8.45], [rec_y, rec_y], color=COL_ACCENT, linewidth=2.2,
zorder=4)
ax_top.text(8.85, rec_y, "?", ha="center", va="center", fontsize=22,
color="#dc2626", weight="bold", zorder=5)
ax_top.text(0.55, 1.04, "ikinci öğenin A[i]'den büyük mü olduğunu BİLMİYORUZ:",
ha="left", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
ax_top.text(0.55, 0.66,
"L(i+1)'in zinciri A[i]'den küçük bir öğeyle başlayabilir →"
" 'artan' yerel olarak kontrol edilemez.",
ha="left", va="center", fontsize=10, color=COL_SLATE_500)
# ALT PANEL: kısıtlı tanım
ax_bot.axis("off")
cell_w, cell_h = 0.84, 0.84
x0 = 0.30
y_cells = 1.55
n = len(A_lis)
chain_set = set(chain_idx)
centers = []
for k, ch in enumerate(A_lis):
x = x0 + k * cell_w
on_chain = k in chain_set
ax_bot.add_patch(FancyBboxPatch(
(x, y_cells), cell_w * 0.92, cell_h * 0.92, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if on_chain else COL_BG,
ec=COL_ACCENT if on_chain else COL_PRIMARY,
linewidth=2.6 if on_chain else 1.6, zorder=3))
cx = x + cell_w * 0.46
cy = y_cells + cell_h * 0.46
centers.append((cx, cy))
ax_bot.text(cx, cy, ch, ha="center", va="center", fontsize=14,
color=COL_TEXT, weight="bold", zorder=5)
ax_bot.text(cx, y_cells - 0.20, str(k), ha="center", va="center",
fontsize=8, color=COL_SLATE_400, zorder=5)
li_hot = on_chain
ax_bot.text(cx, y_cells - 0.56, f"L={L_lis[k]}", ha="center", va="center",
fontsize=10 if li_hot else 9.2,
color=COL_AMBER_700 if li_hot else COL_SLATE_500,
weight="bold" if li_hot else "normal", zorder=5)
ax_bot.text(x0 - 0.20, y_cells - 0.56, "L(i):", ha="right", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold")
for a, b in zip(chain_idx, chain_idx[1:]):
cax, cay = centers[a]
cbx, cby = centers[b]
ax_bot.add_patch(FancyArrowPatch(
(cax, cay + cell_h * 0.52), (cbx, cby + cell_h * 0.52),
arrowstyle="-|>", mutation_scale=15, color=COL_ACCENT,
linewidth=2.3, zorder=6, connectionstyle="arc3,rad=-0.32"))
chain_label = " → ".join(chain_chars)
top_arrow_y = y_cells + cell_h + 0.66
ax_bot.text(x0 + (chain_idx[0] + chain_idx[-1]) / 2 * cell_w + cell_w * 0.46,
top_arrow_y, f"kazanan zincir: {chain_label}", ha="center",
va="center", fontsize=11.5, color=COL_AMBER_700, weight="bold",
zorder=6)
sx, sy = centers[start_idx]
badge_y = y_cells + cell_h + 0.18
ax_bot.add_patch(FancyArrowPatch(
(sx, badge_y + 0.10), (sx, sy + cell_h * 0.50), arrowstyle="-|>",
mutation_scale=13, color=COL_AMBER_700, linewidth=2.0, zorder=6))
ax_bot.add_patch(FancyBboxPatch(
(sx - 1.55, badge_y + 0.04), 3.10, 0.50,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.8, zorder=5))
ax_bot.text(sx, badge_y + 0.29, f"O = max_i L(i) = {O} (i={start_idx})",
ha="center", va="center", fontsize=10.5, color=COL_TEXT,
weight="bold", zorder=7)
ax_bot.text(x0, y_cells + cell_h + 1.30,
"Kısıtlı tanım — alt problem genişletmesi", ha="left", va="center",
fontsize=13.5, color=COL_TEXT, weight="bold")
kbox_y = -0.92
ax_bot.add_patch(FancyBboxPatch(
(x0, kbox_y), n * cell_w + 0.05, 1.42,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_WHITE, ec=COL_ACCENT, linewidth=1.8, zorder=1))
kx = x0 + 0.30
ax_bot.text(kx, kbox_y + 1.16,
"L(i) = A[i] İLE BAŞLAYAN en uzun kesin artan alt-dizilim",
ha="left", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
ax_bot.text(kx, kbox_y + 0.74,
"R: L(i) = 1 + max( { L(j) : i < j, A[i] < A[j] } ∪ {0} )",
ha="left", va="center", fontsize=10.5, color=COL_PRIMARY,
family="monospace")
ax_bot.text(kx, kbox_y + 0.30, "n alt problem × O(n) yerel tarama = O(n²)",
ha="left", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold")
ax_bot.set_xlim(-0.7, x0 + n * cell_w + 0.6)
ax_bot.set_ylim(kbox_y - 0.35, y_cells + cell_h + 1.75)
fig.suptitle("LIS — naif tanım çöker, kısıtlı alt problem kurtarır",
fontsize=15, color=COL_TEXT, weight="bold", y=0.985)
plt.show()
```
## 8. Değişen Para Oyunu: Substring + Genişletme {#sec-8-para-oyunu-substring}
**Problem.** $v_0 \ldots v_{n-1}$ değerli paralar dizisi; iki oyuncu sırayla **baştaki veya sondaki** parayı alır. Ben (önce başlarım) toplam değerimi maksimize etmek istiyorum. Örnek: $[5, 10, 100, 25]$ — 25'i hemen almak hata (rakip 100'ü kapar); doğrusu 5 ile başlamak, 100'ün sonunda bende kalmasını sağlamaktır.
İki uçtan silme → **substring** alt problemi (prefix de suffix de yetmez; iki uç da değişiyorsa neredeyse her zaman substring gerekir).
@fig-coin-game oyunu motor üzerinde çözer: ilk hamle **baş** ($v_0 = 5$) almaktır; bu durumda toplam payım $5 + x(1,3,\text{sen}) = 5 + 100 = 105$, oysa son (25) almak yalnız $25 + x(0,2,\text{sen}) = 25 + 10 = 35$ verir. Bağımsız bir tanık — üçüncü koordinatsız **fark formülasyonu** — aynı 105'i bambaşka yoldan doğrular: $(\Sigma v + d)/2 = (140 + 70)/2 = 105$.
## 9. İki Oyuncu: Max/Min Recurrence {#sec-9-max-min-recurrence}
**Çalışılan Örnek — subproblem expansion.** Alt probleme **üçüncü** bir koordinat ekle: $x(i, j, p) = $ "paralar $v_i \ldots v_j$ üzerinde, **$p$ oyuncusu başlarsa** benim alacağım maksimum toplam değer" ($p \in \{\text{ben}, \text{sen}\}$). Bir hamle yapınca sıra döner — bu yüzden iki oyuncu durumunu izlemeliyiz.
- **$x(i, j, \text{ben})$:** baştaki ($i$) veya sondaki ($j$) parayı al, sonra sıra sende → **max**:
$$x(i, j, \text{ben}) = \max\bigl( v_i + x(i+1, j, \text{sen}),\; v_j + x(i, j-1, \text{sen}) \bigr)$$
- **$x(i, j, \text{sen})$:** sen alırsın (ben puan almam, sıfır-toplam); rakip benim skorumu **minimize** eder:
$$x(i, j, \text{sen}) = \min\bigl( x(i+1, j, \text{ben}),\; x(i, j-1, \text{ben}) \bigr)$$
> *"when you choose, we end up minimizing, because that's the saddest thing that could happen to us."* — Demaine, 53:04
**T:** $j - i$ artan. **B:** $x(i, i, \text{ben}) = v_i$; $x(i, i, \text{sen}) = 0$. **O:** $x(0, n-1, \text{ben})$. **Süre:** $\Theta(n^2)$ substring $\times\, O(1) = O(n^2)$ (üçüncü koordinat alt problem sayısını yalnız 2 katına çıkarır).
```{python}
#| label: fig-coin-game
#| fig-cap: "Değişen para oyunu: minimax (Demaine L16 §8-9 İMZA, 53:04). SOL panel karar ağacı: v=[5,10,100,25]; ilk hamle BAŞ al (5) → 5 + x(1,3,sen)=100 = 105 KAZANAN (amber); SON al (25) → 25 + x(0,2,sen)=10 = 35 HATA (rakip 100'ü kapar, slate). SAĞ panel recurrence kutuları: x(i,j,ben) = max(vᵢ + x(i+1,j,sen), vⱼ + x(i,j−1,sen)) parayı ben alır MAKSİMİZE; x(i,j,sen) = min(x(i+1,j,ben), x(i,j−1,ben)) sıfır-toplam rakip MİNİMİZE. Bağımsız tanık — fark formülasyonu d(i,j)=max(vᵢ−d(i+1,j), vⱼ−d(i,j−1)); (Σv+d)/2 = (140+70)/2 = 105 BİREBİR. Alt rozet: ben 105 + rakip 35 = 140 (sıfır-toplam sağlaması). substring · j−i artan · 2n² durum → O(n²). Veri MOTORDAN (assert): coin_game([5,10,100,25]) → x(0,3,ben)=105, first='baş'; x(1,3,sen)=100; x(0,2,sen)=10; coin_game_diff_witness == 105 BİREBİR; d(0,3)=70."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-coin-game (L16 §8-9 İMZA): değişen para oyunu minimax + fark-tanık.
# Veri MOTORDAN (build_coin_example + coin_game + coin_game_diff_witness).
v = build_coin_example()
assert v == [5, 10, 100, 25], v
n = len(v)
x, first = coin_game(v)
ben_total = x[(0, n - 1, "ben")]
assert ben_total == 105 and first == "baş"
x_1_3_sen = x[(1, n - 1, "sen")]
x_0_2_sen = x[(0, n - 2, "sen")]
assert x_1_3_sen == 100 and x_0_2_sen == 10
front_branch = v[0] + x_1_3_sen
back_branch = v[-1] + x_0_2_sen
assert front_branch == 105 and back_branch == 35 and front_branch > back_branch
total_pot = sum(v)
assert total_pot == 140
rakip = total_pot - ben_total
assert rakip == 35
witness = coin_game_diff_witness(v)
assert witness == 105 and witness == ben_total
d_root = 2 * ben_total - total_pot
assert d_root == 70
fig, (axL, axR) = plt.subplots(1, 2, figsize=(12, 6))
def _medallion(ax, ccx, ccy, r, val, fc, ec, lw=2.2, txt_col=None):
ax.add_patch(Circle((ccx, ccy), r, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=3))
ax.text(ccx, ccy, str(val), ha="center", va="center",
fontsize=12.5, color=txt_col or COL_TEXT, weight="bold", zorder=4)
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.06",
fc=fc, ec=ec, linewidth=lw, zorder=2))
# SOL PANEL — karar ağacı
axL.set_title("Değişen para oyunu: ilk hamleyi seç",
fontsize=12.5, color=COL_TEXT, weight="bold")
coin_y = 5.3
coin_xs = [1.2, 2.55, 3.9, 5.25]
coin_r = 0.5
for ccx, val in zip(coin_xs, v):
_medallion(axL, ccx, coin_y, coin_r, val, COL_BG, COL_PRIMARY)
axL.text(coin_xs[0], coin_y + 0.78, "baş", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", style="italic")
axL.text(coin_xs[-1], coin_y + 0.78, "son", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", style="italic")
axL.text(0.25, coin_y, "v =", ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold")
split_x, split_y = 3.2, 4.55
axL.add_patch(FancyArrowPatch((3.2, coin_y - coin_r - 0.05), (split_x, split_y + 0.15),
arrowstyle="-", color=COL_SLATE_400, linewidth=1.4, zorder=1))
axL.add_patch(FancyArrowPatch((split_x, split_y), (1.55, 3.55),
arrowstyle="-|>", mutation_scale=15, color=COL_ACCENT,
linewidth=2.6, zorder=3))
axL.add_patch(FancyArrowPatch((split_x, split_y), (4.85, 3.55),
arrowstyle="-|>", mutation_scale=15, color=COL_SLATE_400,
linewidth=1.8, zorder=2))
axL.text(split_x, split_y + 0.30, "ben seçerim (max)", ha="center", va="bottom",
fontsize=9.5, color=COL_TEXT, weight="bold")
bx = 1.55
axL.text(bx, 3.30, "BAŞ al (5)", ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold")
for ccx, val in zip([bx - 0.7, bx, bx + 0.7], v[1:]):
_medallion(axL, ccx, 2.55, 0.30, val, COL_WHITE, COL_SLATE_400, lw=1.4)
axL.text(bx, 2.05, 'kalan [10,100,25] · "sen"', ha="center", va="center",
fontsize=8.3, color=COL_SLATE_500)
axL.text(bx, 1.62, f"gelecek payım x(1,3,sen)={x_1_3_sen}", ha="center",
va="center", fontsize=8.6, color=COL_TEXT)
_rbox(axL, bx - 1.05, 0.55, 2.1, 0.72, COL_AMBER_100, COL_ACCENT, lw=2.6)
axL.text(bx, 0.91, f"5 + {x_1_3_sen} = {front_branch}", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold")
axL.text(bx, 0.20, "✓ KAZANAN", ha="center", va="center", fontsize=10,
color=COL_AMBER_700, weight="bold")
sx = 4.85
axL.text(sx, 3.30, "SON al (25)", ha="center", va="center",
fontsize=10.5, color=COL_SLATE_500, weight="bold")
for ccx, val in zip([sx - 0.7, sx, sx + 0.7], v[:-1]):
_medallion(axL, ccx, 2.55, 0.30, val, COL_WHITE, COL_SLATE_400, lw=1.4)
axL.text(sx, 2.05, 'kalan [5,10,100] · "sen"', ha="center", va="center",
fontsize=8.3, color=COL_SLATE_500)
axL.text(sx, 1.62, f"gelecek payım x(0,2,sen)={x_0_2_sen}", ha="center",
va="center", fontsize=8.6, color=COL_TEXT)
_rbox(axL, sx - 1.05, 0.55, 2.1, 0.72, COL_BG, COL_SLATE_400, lw=1.8)
axL.text(sx, 0.91, f"25 + {x_0_2_sen} = {back_branch}", ha="center", va="center",
fontsize=12, color=COL_SLATE_500, weight="bold")
axL.text(sx, 0.20, "✗ rakip 100'ü kapar", ha="center", va="center", fontsize=9,
color=COL_SLATE_500, weight="bold")
axL.set_xlim(-0.1, 6.4)
axL.set_ylim(-0.15, 6.35)
axL.set_aspect("equal")
axL.axis("off")
# SAĞ PANEL — recurrence + tanık
axR.set_title("Minimax yinelemesi (Demaine 53:04)",
fontsize=12.5, color=COL_TEXT, weight="bold")
_rbox(axR, 0.3, 5.05, 9.0, 1.05, COL_AMBER_100, COL_ACCENT, lw=2.4)
axR.text(4.8, 5.78, "x(i,j,ben) = max( vᵢ + x(i+1,j,sen), vⱼ + x(i,j−1,sen) )",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700, weight="bold")
axR.text(4.8, 5.30, "parayı ben alırım → kendi payımı MAKSİMİZE ederim",
ha="center", va="center", fontsize=8.6, color=COL_TEXT)
_rbox(axR, 0.3, 3.75, 9.0, 1.05, COL_BG, COL_PRIMARY, lw=1.9)
axR.text(4.8, 4.48, "x(i,j,sen) = min( x(i+1,j,ben), x(i,j−1,ben) )",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
axR.text(4.8, 4.00, "sıfır-toplam: rakip BENİM skorumu MİNİMİZE eder",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500)
axR.text(4.8, 3.42,
"substring alt problemleri · j−i artan · 2n² durum → O(n²)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic")
_rbox(axR, 0.3, 1.85, 9.0, 1.30, COL_WHITE, COL_AMBER_600, lw=2.0)
axR.text(4.8, 2.83, "Bağımsız tanık — fark formülasyonu (tek koordinatsız ikinci yol)",
ha="center", va="center", fontsize=9.8, color=COL_AMBER_700, weight="bold")
axR.text(4.8, 2.43, "d(i,j) = max( vᵢ − d(i+1,j), vⱼ − d(i,j−1) )",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
axR.text(4.8, 2.05,
f"(Σv + d)/2 = ({total_pot} + {d_root})/2 = {witness} BİREBİR",
ha="center", va="center", fontsize=10, color=COL_AMBER_700, weight="bold")
_rbox(axR, 1.3, 0.45, 3.3, 1.05, COL_AMBER_100, COL_ACCENT, lw=2.4)
axR.text(2.95, 1.18, "ben", ha="center", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold")
axR.text(2.95, 0.78, f"{ben_total}", ha="center", va="center", fontsize=18,
color=COL_AMBER_700, weight="bold")
_rbox(axR, 5.0, 0.45, 3.3, 1.05, COL_BG, COL_PRIMARY, lw=1.9)
axR.text(6.65, 1.18, "rakip", ha="center", va="center", fontsize=9.5,
color=COL_SLATE_500, weight="bold")
axR.text(6.65, 0.78, f"{rakip}", ha="center", va="center", fontsize=18,
color=COL_SLATE_500, weight="bold")
axR.text(4.8, 0.12, f"{ben_total} + {rakip} = {total_pot} (sıfır-toplam sağlaması)",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic")
axR.set_xlim(0, 9.6)
axR.set_ylim(-0.05, 6.35)
axR.axis("off")
fig.tight_layout()
plt.show()
```
## 10. Subproblem Expansion İlkesi {#sec-10-subproblem-expansion}
> *"What we're really doing is subproblem expansion."* — Demaine, 57:00
Bariz alt problemler (prefix/suffix/substring) yetmezse, **alt problem sayısını çoğalt** (polinom kaldığı sürece): bir kısıt veya durum koordinatı ekle. Para oyununda "kim başlıyor"u ekleyerek alt problemi 2 katına çıkardık; LIS'te "A[i] ile başla" kısıtını ekledik.
> *"The more subproblems we have, we can consider more constraints."* — Demaine, 58:25
Daha fazla alt problem = daha fazla kısıt = daha kolay recurrence. (Bir bonus: çoğu DP, bir DAG kurup üzerinde en kısa/en uzun yol çalıştırarak da çözülebilir — *en uzun yol = ağırlıkları negate et + en kısa yol* — ama recurrence yazmak çok daha basittir.)
@fig-subproblem-expansion dersin birleştirici temasını tek panelde toplar: solda bariz alt problemlerin (prefix/suffix/substring) recurrence vermeye yetmediği; ortada iki çözüm yolu — **kısıt ekle** (LIS: "A[i] ile başlayan"; alt problem sayısı $n = 12$ DEĞİŞMEZ) ve **expansion** (para: kim-başlıyor koordinatı; 10 substring × 2 = 20 giriş, motordan); sağda kural rozeti ("polinom kaldığı sürece çoğalt") ve en uzun yol bonus köprüsü.
```{python}
#| label: fig-subproblem-expansion
#| fig-cap: "Alt problem EXPANSION — dersin birleştirici teması (Demaine L16 §10, 57:00 + 58:25). SÜTUN 1 'bariz alt problemler YETMEZ': prefix/suffix/substring üç mini ikon + büyük soru işareti (recurrence kapanmıyor). SÜTUN 2 iki çözüm yolu: ÜST (slate) KISIT EKLE → LIS 'carbohydrate', naif L(i)=A[:i] yerel kontrol edilemez, kısıt 'A[i] ile başlayan'; alt problem sayısı n=12 DEĞİŞMEZ → LIS='abort'(5). ALT (amber) EXPANSION → para oyunu [5,10,100,25], substring (i,j) yetmez sıra kimde belli değil, 'kim başlıyor' koordinatı ben/sen ×2; 10 substring × 2 = 20 giriş. SÜTUN 3 kural rozeti: POLİNOM kaldığı sürece ÇOĞALT — daha çok alt problem = daha çok kısıt = daha kolay recurrence; bonus köprü: en uzun yol = ağırlıkları NEGATE et + en kısa yol. Veri MOTORDAN (assert): len(lis_table('carbohydrate')[0])==12; lis_reconstruct=='abort'(5); len(coin_game([5,10,100,25]))==20; distinct (i,j)==10; 10×2==20."
#| fig-width: 11.5
#| fig-height: 5.5
# fig-subproblem-expansion (L16 §10 İMZA): bariz alt problemler yetmezse çoğalt.
# Veri MOTORDAN (lis_table + lis_reconstruct + coin_game + build_coin_example).
word = "carbohydrate"
L_se, _p = lis_table(list(word))
lis_n = len(L_se)
lis_items, lis_len_se = lis_reconstruct(list(word))
lis_seq = "".join(lis_items)
assert lis_n == 12
assert lis_len_se == 5 and lis_seq == "abort"
ex = build_coin_example()
coin_x, _f = coin_game(ex)
coin_entries = len(coin_x)
n_coin = len(ex)
distinct_subs = len({(i, j) for (i, j, _pp) in coin_x.keys()})
assert n_coin == 4 and distinct_subs == 10 and coin_entries == 20
assert distinct_subs * 2 == coin_entries
def _mini_cells(ax, x0, y, ncell, mark, cell=0.20, label=""):
mark = set(mark)
for k in range(ncell):
x = x0 + k * cell
hot = k in mark
ax.add_patch(FancyBboxPatch(
(x, y), cell * 0.86, cell * 0.86, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=1.6 if hot else 1.1, zorder=4))
if label:
ax.text(x0 + ncell * cell * 0.5 - cell * 0.07, y - 0.16, label,
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=5)
def _solution_box(ax, x, y, w, h, accent, title, badge, lines, foot):
if accent:
fc, ec, tc = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tc = COL_BG, COL_PRIMARY, COL_PRIMARY
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.05",
fc=fc, ec=ec, linewidth=2.4, zorder=2))
ax.add_patch(FancyBboxPatch(
(x + 0.12, y + h - 0.40), 1.05, 0.30,
boxstyle="round,pad=0.01,rounding_size=0.04",
fc=ec, ec=ec, linewidth=1.0, zorder=4))
ax.text(x + 0.12 + 1.05 * 0.5, y + h - 0.25, badge, ha="center",
va="center", fontsize=7.8, color=COL_WHITE, weight="bold", zorder=5)
ax.text(x + 1.32, y + h - 0.25, title, ha="left", va="center",
fontsize=10.5, color=tc, weight="bold", zorder=5)
ty = y + h - 0.58
n_lines = len(lines)
for idx, (ln, big) in enumerate(lines):
if idx == n_lines - 1:
ax.plot([x + 0.22, x + w - 0.22], [ty + 0.18, ty + 0.18],
color=ec, linewidth=1.0, alpha=0.45, zorder=4)
ax.text(x + 0.22, ty, ln, ha="left", va="center",
fontsize=9.2 if big else 8.4, color=COL_TEXT,
weight="bold" if big else "normal", zorder=5)
ty -= 0.33 if big else 0.28
ax.text(x + w * 0.5, y + 0.20, foot, ha="center", va="center",
fontsize=8.0, color=tc, weight="bold", style="italic", zorder=5)
fig, ax = plt.subplots(figsize=(11.5, 5.5))
fig.patch.set_facecolor(COL_WHITE)
# SÜTUN 1
col1_cx = 1.55
ax.text(col1_cx, 4.55, "① bariz alt problemler", ha="center", va="center",
fontsize=10.2, color=COL_PRIMARY, weight="bold", zorder=5)
nmini = 7
cellm = 0.20
x0m = col1_cx - nmini * cellm * 0.5
_mini_cells(ax, x0m, 4.05, nmini, mark=range(0, 3), cell=cellm,
label="önek (prefix) A[:i]")
_mini_cells(ax, x0m, 4.05 - 0.62, nmini, mark=range(4, 7), cell=cellm,
label="sonek (suffix) A[i:]")
_mini_cells(ax, x0m, 4.05 - 1.24, nmini, mark=range(2, 5), cell=cellm,
label="alt-dizi (substring) A[i:j]")
ax.text(col1_cx, 4.05 - 2.12, "?", ha="center", va="center", fontsize=38,
color=COL_AMBER_600, weight="bold", zorder=5)
ax.text(col1_cx, 4.05 - 2.70, "bariz alt problemler\nrecurrence VERMEYE YETMEZ",
ha="center", va="center", fontsize=8.6, color=COL_TEXT, weight="bold",
zorder=5)
ax.add_patch(FancyArrowPatch(
(3.05, 2.28), (3.70, 2.28), arrowstyle="-|>", mutation_scale=20,
color=COL_AMBER_700, linewidth=2.6, zorder=4))
ax.text(3.38, 2.58, "ÇOĞALT", ha="center", va="center", fontsize=8.2,
color=COL_AMBER_700, weight="bold", zorder=5)
# SÜTUN 2
col2_x = 3.85
col2_w = 4.05
ax.text(col2_x + col2_w * 0.5, 4.55, "② iki yol — ikisi de uzayı çoğaltır",
ha="center", va="center", fontsize=10.2, color=COL_PRIMARY,
weight="bold", zorder=5)
_solution_box(
ax, col2_x, 2.42, col2_w, 1.92, accent=False,
title="alt problemin TANIMINI daralt", badge="KISIT",
lines=[
("LIS — 'carbohydrate'", True),
("naif L(i)=A[:i] artan → yerel kontrol edilemez", False),
("kısıt: L(i) = 'A[i] İLE BAŞLAYAN en uzun artan'", False),
(f"alt problem sayısı n = {lis_n} — DEĞİŞMEZ", True),
],
foot=f"kısıtlı DP → LIS = '{lis_seq}' (uzunluk {lis_len_se})")
_solution_box(
ax, col2_x, 0.22, col2_w, 1.92, accent=True,
title="yeni KOORDİNAT ekle", badge="EXPANSION",
lines=[
(f"para oyunu — {ex}", True),
("substring (i,j) yetmez → sıra KİMDE belli değil", False),
("'kim başlıyor' koordinatı: ben / sen ×2", False),
(f"{distinct_subs} substring × 2 = {coin_entries} giriş", True),
],
foot=f"x sözlüğü = {coin_entries} alt problem (2 × {distinct_subs})")
ax.text(col2_x + col2_w * 0.5, 2.28, "ya / ya", ha="center", va="center",
fontsize=8.0, color=COL_SLATE_500, style="italic", zorder=5)
ax.add_patch(FancyArrowPatch(
(8.00, 2.28), (8.55, 2.28), arrowstyle="-|>", mutation_scale=20,
color=COL_AMBER_700, linewidth=2.6, zorder=4))
# SÜTUN 3
col3_x = 8.70
col3_w = 2.62
ax.text(col3_x + col3_w * 0.5, 4.55, "③ kural", ha="center", va="center",
fontsize=10.2, color=COL_PRIMARY, weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(col3_x, 1.45), col3_w, 2.55, boxstyle="round,pad=0.03,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=3.0, zorder=2))
ax.text(col3_x + col3_w * 0.5, 3.72, "★", ha="center", va="center",
fontsize=17, color=COL_AMBER_600, weight="bold", zorder=4)
ax.text(col3_x + col3_w * 0.5, 3.30, "POLİNOM kaldığı sürece\nÇOĞALT",
ha="center", va="center", fontsize=10.0, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(col3_x + col3_w * 0.5, 2.55,
"daha çok alt problem\n=\ndaha çok kısıt\n=\ndaha kolay recurrence",
ha="center", va="center", fontsize=9.0, color=COL_TEXT, zorder=5)
ax.text(col3_x + col3_w * 0.5, 1.62, "Demaine 57:00 · 58:25", ha="center",
va="center", fontsize=7.2, color=COL_SLATE_500, style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(col3_x, 0.30), col3_w, 0.92, boxstyle="round,pad=0.02,rounding_size=0.05",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=2))
ax.text(col3_x + col3_w * 0.5, 1.02, "bonus köprü", ha="center", va="center",
fontsize=7.6, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(col3_x + col3_w * 0.5, 0.62,
"en uzun yol = ağırlıkları\nNEGATE et + en kısa yol",
ha="center", va="center", fontsize=8.2, color=COL_TEXT, zorder=5)
fig.suptitle(
"Alt problem EXPANSION — dersin birleştirici teması: bariz alt problemler "
"yetmezse uzayı çoğalt",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(-0.05, 11.45)
ax.set_ylim(0.05, 4.85)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d24}
1. **Çoklu girdi**: alt problem uzaylarını çarp (LCS: sonek çifti); 2 dizi polinom, $n$ dizi üstel.
2. **LCS recurrence**: $A[i] \neq B[j] \to \max$(2 seçenek); $A[i] = B[j] \to 1 + $ çapraz; $O(n^2)$.
3. **Ebeveyn işaretçileri**: DP'de çözümü (uzunluk değil, dizinin kendisi) geri kur.
4. **LIS naif çöker**: "artan" kısıtı uygulanamaz → alt problem kısıtı şart.
5. **Alt problem kısıtı**: $L(i) = $ "$A[i]$ ile başlayan LIS"; $O = \max_i L(i)$; $O(n^2)$.
6. **Para oyunu**: substring + 3. koordinat (kim başlıyor); ben max, rakip min; $O(n^2)$.
7. **Subproblem expansion**: kısıt için alt problemi çoğalt (polinom kalsın).
::: {.callout-important title="Tek Bir Cümle"}
DP 2 üç teknik ekler: çoklu girdide alt problem uzaylarını **çarp** (LCS), naif tanım çökerse bir **kısıt** ekleyip alt problemi **genişlet** (LIS), oyunlarda "ben max, rakip min" durumunu koordinata taşı (para oyunu) — hepsi yerel kaba kuvvetle $O(n^2)$, ve ebeveyn işaretçileriyle yalnız değeri değil çözümün kendisini de kurtarırsın.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d24}
::: {.callout-note collapse="true" title="Soru 1: İki dizili (LCS) bir problemde alt problemler nasıl kurulur, ve neden n dizide bu çalışmaz?"}
**Cevap:**
Tek dizide prefix/suffix/substring alt problemdi; iki dizide **alt problem uzaylarını çarparız** — örn. A'nın sonekleri × B'nin sonekleri, yani her alt problem bir **sonek çifti** $L(i, j)$. Alt problem sayısı $(|A|+1) \cdot (|B|+1) = O(n^2)$, polinom. Sabit sayıda dizi (2, 3, …) için çarpım hâlâ polinom; ama **n dizi** olursa alt problem sayısı $n^n$ (üstel) olur — bu yüzden değişken sayıda dizinin LCS'i için polinom algoritma muhtemelen yoktur.
:::
::: {.callout-note collapse="true" title="Soru 2: LCS'te A[i]=B[j] olduğunda neden 'eşleştir' her zaman doğru, hiçbir max gerekmez?"}
**Cevap:**
Değiştirme (exchange) argümanı: bir optimal LCS düşün; çaprazlamayan harf-eşleştirmeleridir. $A[i]$ ve $B[j]$ eşitse, optimal çözümde (a) ikisi de eşleşmemişse, onları eşleyip daha uzun bir çözüm elde ederiz (çelişki); (b) $A[i]$ başka bir şeyle eşleşmişse, onu $B[j]$ ile eşlemeye çevirebiliriz — kayıp olmaz. Yani $A[i]$'yi $B[j]$ ile eşleyen bir optimal çözüm **daima vardır**; o hâlde 1 puan alıp $L(i+1, j+1)$'e inmek güvenlidir, başka seçeneği denemeye (max almaya) gerek yoktur.
:::
::: {.callout-note collapse="true" title="Soru 3: LIS'in naif tanımı L(i) = A[i:]'nin LIS'i neden recurrence vermez? Kısıt nasıl kurtarır?"}
**Cevap:**
Naif tanımda $A[i]$'yi çözüme katmak istediğimizde, kalan $L(i+1)$'in **ilk öğesinin** ne olduğunu bilmeyiz — $A[i] < $ (o öğe) mi? "Artan" koşulunu yerel olarak kontrol edemeyiz, recurrence yazılamaz. Çözüm: alt probleme **kısıt** ekle — $L(i) = $ "**$A[i]$ ile başlayan**" LIS. Artık $A[i]$ kesin dahildir; ikinci öğe $j$'yi kaba kuvvetle ($i < j$ ve $A[i] < A[j]$ olan tüm $j$) deneriz, böylece artan koşulu *yerel* olarak garanti edilir. Orijinal problem artık $L(0)$ değil, **$\max_i L(i)$** (LIS nerede başlar bilinmez).
:::
::: {.callout-note collapse="true" title="Soru 4: Para oyununda x(i,j,sen) neden min? 'Subproblem expansion' burada ne yaptı?"}
**Cevap:**
Oyun sıfır-toplamdır: rakip kendi skorunu maksimize ederken **benim** skorumu minimize eder. $x(i, j, \text{sen}) = $ "sen başlarsan benim alacağım max değer" olduğundan, rakibin hamlesini kontrol edemem; en kötü (benim için en az) durumu varsaymalıyım → **min**. Ben seçtiğimde max, rakip seçtiğinde min — klasik minimax. "Subproblem expansion": alt probleme **üçüncü koordinat** (kim başlıyor: ben/sen) ekleyerek alt problem sayısını 2 katına çıkardık; bu, "hamle sonrası sıra döner" durumunu temsil edip recurrence'ı çok sadeleştirdi (polinom kaldı: $2 \cdot n^2$ alt problem).
:::
## Egzersizler {#sec-egzersizler-d24}
**Egzersiz 1.** LCS'i bir grid (DAG) olarak çiz (örn. "their" vs "habit"); çapraz kenarların eşleşme, diğerlerinin max olduğunu ve ebeveyn izinin LCS'i verdiğini göster.
**Egzersiz 2.** LIS'i Python'da yaz (kısıtlı alt problem); "carbohydrate" gibi bir örnekte $L(i)$ tablosunu doldur.
**Egzersiz 3.** LCS recurrence'ının eşit-harf durumunu ($1 + $ çapraz) değiştirme argümanıyla kanıtla.
**Egzersiz 4.** Para oyununu $[5, 10, 100, 25]$ üzerinde $x(i, j, \text{ben}/\text{sen})$ matrisiyle elle çöz; optimal stratejiyi ebeveyn izinden çıkar.
**Egzersiz 5.** LIS'i DAG en kısa yola indirge: çapraz kenarlara $-1$, diğerlerine $0$ ver; en kısa yolun en uzun artan alt-dizilime karşılık geldiğini göster.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d24}
::: {.callout-warning title="Sonraki: Ders 25 (PS8) — Problem Oturumu 8 (DP uygulamaları)"}
**Ders 25 (PS8): Problem Oturumu 8** (DP uygulamaları). Bir problem oturumuyla DP'yi pekiştiriyoruz: bu derste öğrenilen çoklu girdi, alt problem kısıtı ve genişletme tekniklerini gerçek problemlerde uygulayacağız. SRTBOT disiplini ve "yerel kaba kuvvet" sezgisi merkezde kalır. **Hoca değişimi notu:** problem oturumlarını **Justin Solomon** yürütür (DP ders bloğu Demaine'in; PS8 Solomon'un oturumudur). DP ünitesi Ders 24-27 (L16-L18) boyunca devam eder ve **Ders 30 = PS10/Quiz 3 Gözden Geçirme** ile özetlenir.
**Ders 25 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 2 (LIS) ve 4 (para oyunu) çöz.
- LCS, LIS ve para oyununun SRTBOT'unu ezberden yaz.
- Ana cümleyi tekrar oku: *"Bilmediğin şeyi kaba kuvvetle dene; kısıt için alt problemi genişlet."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d24}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Çoklu girdi** | Alt problem uzaylarını çarp (sonek × sonek) | Böl. 3 |
| **LCS recurrence** | $\neq \to \max$(2); $= \to 1 + $ çapraz; $O(n^2)$ | Böl. 4 |
| **Ebeveyn işaretçileri** | DP çözümünü (dizinin kendisi) geri kur | Böl. 5 |
| **Alt problem kısıtı** | $L(i) = A[i]$ ile başlayan LIS; $O = \max_i L(i)$ | Böl. 7 |
| **LIS recurrence** | $1 + \max\{L(j) : i < j,\, A[i] < A[j]\}$; $O(n^2)$ | Böl. 7 |
| **Para oyunu** | $x(i, j, p)$; ben max, rakip min; substring | Böl. 9 |
| **Minimax** | Ben seçince max, rakip seçince min | Böl. 9 |
| **Subproblem expansion** | Kısıt için alt problemi çoğalt (polinom) | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d24}
::: {.callout-tip title="6 köprü"}
Bu dersin üç tekniği — çoklu girdi çarpımı, alt problem kısıtı, subproblem expansion — ML ve sistem mühendisliğindeki çok sayıda araca doğrudan bağlanır; köprülerin özeti:
1. **LCS** → `diff`/git üç-yol birleştirme, DNA/protein hizalama, plagiarism tespiti, edit-distance.
2. **LIS** → patience sorting (LIS'i $O(n \log n)$'e indiren kart-yığma algoritması), zamanlama, en uzun uyumlu kayıt dizisi.
3. **Minimax (para oyunu)** → oyun yapay zekâsı (satranç, go); **alpha-beta budama** minimax ağacını gereksiz dalları keserek hızlandırır — para oyununun max/min recurrence'ının doğrudan genişlemesi.
4. **Ebeveyn işaretçileri** → çözüm rekonstrüksiyonu: hizalama, rota, düzenleme betiği (edit script); değil değer, çözümün kendisi.
5. **Subproblem expansion** → durum-augmentasyonu; **OMSCS CS 6515'te DP tasarımının kalbi** — her DP probleminde "bariz alt problem yetmiyorsa hangi koordinatı eklerim?" refleksi.
6. **Çoklu girdi çarpımı** → çok boyutlu DP tabloları; sabit-boyut çarpım polinom, $n$-boyut üstel.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
DP 2, tek diziden ötesine geçer. İki dizi varsa alt problem uzaylarını **çarp** (LCS). Naif tanım recurrence vermiyorsa bir **kısıt** ekleyip alt problemi **genişlet** (LIS: "A[i] ile başla"). Oyunlarda durumu (kim başlıyor) koordinata taşı; ben **max**, rakip **min** (minimax). Bilmediğin her şeyi yerel kaba kuvvetle dener, alt problemleri yeniden kullanırsın — hepsi polinom ($O(n^2)$). Ve ebeveyn işaretçileriyle yalnız değeri değil, çözümün kendisini de kurtarırsın.
:::
