---
title: "Dinamik Programlama 4: Pseudopolinom, Subset Sum"
subtitle: "DP finali — tamsayı alt problemler, rod cutting, OR-recurrence ile subset sum, pseudopolinom hiyerarşisi ve dört dersin toparlanması"
---
::: {.callout-note title="Oturum bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 18: Dynamic Programming, Part 4](https://www.youtube.com/watch?v=i9OAOk0CUQE) (≈64 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 18: Dynamic Programming, Part 4](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec18/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 27 (L18)
- **Hoca:** Erik Demaine (dinamik programlama; **DP serisinin FİNALİ 4/4**)
- **Okuma süresi:** ≈27 dk
> Bu, DP ünitesinin **dördüncü ve son dersidir**. Ders 26 (L17) subproblem expansion'ı (Floyd-Warshall, parantezleme, parmaklama) derinleştirdi; bu ders **tamsayı (integer) alt problemleri** ele alır: Fibonacci'deki gibi bir tamsayı girdinin daha küçük sürümlerine bakmak. İki örnek — **rod cutting** ($O(L^2)$, gerçek polinom) ve **subset sum** ($O(n \cdot T)$, pseudopolinom) — ile yeni bir kavrama varırız: **pseudopolinom zaman**. Subset sum ayrıca bir **karar problemi**dir: recurrence'da min/max yerine **OR** kullanılır, "evet" certificate ile kolay kanıtlanır, "hayır" zordur — sonraki dersin (P/NP) habercisi. Ders dört DP dersinin **diagonal** (teknik-bazlı) toparlanmasıyla kapanır.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d27}
DP serisinin **finali** (4/4, Erik Demaine). Odak: **tamsayı (integer) alt problemler** — Fibonacci'deki gibi, bir tamsayı girdinin daha küçük sürümlerine bakmak. Bu, yeni bir kavrama götürür: **pseudopolinom zaman**.
> *"pseudopolynomial is a pretty good running time."* — Demaine, 0:40
İki örnek (rod cutting, subset sum) + tüm DP'lerin **diagonal** (teknik-bazlı) toparlanması. Üç ana fikir:
1. **Tamsayı alt problem** — integer girdiyi $0 \ldots n$ arası daha küçük tamsayılara böl (rod cutting, subset sum).
2. **Karar problemi** — "evet/hayır" çıktısı; recurrence'da min/max yerine **OR**.
3. **Pseudopolinom** — $n \cdot T$ gibi süre: girdi *boyutuna* değil girdi *sayılarına* polinom; "polinom değil ama yeterince iyi".
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 27'nin (L18) kavram haritası: kök = Dinamik Programlama 4 (Demaine) — DP serisinin FİNALİ 4/4; tek tema TAMSAYI ALT PROBLEM, yani integer girdiyi 0 ile n arası daha küçük tamsayılara bölmek (Fibonacci'nin genellemesi). Dört dal — (1) Rod cutting tamsayı alt problem: L uzunluk çubuğu tamsayı parçalara böl, ilk parçanın boyu p tahmin et, x(ell) eşittir max p için v(p) artı x(ell eksi p), L alt problem çarpı O(L) seçim eşittir O(L kare); örnek L eşittir 7 değerler bir on onuc onsekiz yirmi otuzbir otuziki optimal uc arti iki arti iki eşittir onuc arti on arti on eşittir otuzuc. (2) Rod cutting polinom mu evet GERÇEK polinom: polinom zaman demek sürenin girdi BOYUTUNA polinom olması, girdi boyutu kelime cinsinden, rod girdisi L arti bir kelime, O(L kare) L arti bire polinom yani polinom zaman. (3) Subset sum KARAR problemi: n tamsayılık coklu küme A arti hedef T, herhangi alt küme T'ye toplanır mı, cıktı tek bit evet hayır, recurrence x(i,t) eşittir x(i arti bir, t) OR x(i arti bir, t eksi a-i) yani min max DEĞİL OR cünkü herhangi bir secenek evet verirse evet, n çarpı T alt problem çarpı O(bir) eşittir O(n çarpı T); evet'i kanıtlamak KOLAY certificate göster, hayır'ı kanıtlamak ZOR kısa yol yok NP habercisi. (4) Pseudopolinom poli DEĞİL: O(n çarpı T) girdi boyutu n arti bir kelime ama süre hem n hem T'ye bağlı, T bir kelimeye sığar w bit yani T küçük eşit iki üzeri w, w'nin üst sınırı YOK yani T eşittir iki üzeri n olabilir yani n çarpı T eşittir n çarpı iki üzeri n ÜSTEL; hiyerarşi strongly polinom sayıdan bağımsız büyük weakly polinom sayının LOG'una radix sort büyük pseudo polinom sayının KENDİSİNE subset sum; özel durum T küçük eşit poly(n) ise pseudo gerçek polinoma iner bu radix sort doğrusal koşulu. Birleştirici tema: dört DP dersi teknikleri kademeli tanıttı basit alt problem sonra coklu girdi ve kısıt sonra subproblem expansion sonra tamsayı alt problem ve pseudopolinom, DP ne bilsem işim biterdi sorusunu yerel kaba kuvvetle çözen güçlü bir tasarım çatısıdır."
flowchart TD
A["Ders 27 (L18): Dinamik Programlama 4 — Pseudopolinom, Subset Sum"] --> RC["Rod cutting — tamsayı alt problem"]
RC --> RCa["x(ℓ) = max{ v(p) + x(ℓ−p) }<br/>L alt problem × O(L) → O(L²); örnek 3+2+2 = 33"]
A --> RP["Rod cutting polinom mu? — EVET (gerçek)"]
RP --> RPa["polinom = girdi BOYUTUNA polinom<br/>girdi L+1 kelime; O(L²) → polinom zaman"]
A --> SS["Subset sum — KARAR problemi"]
SS --> SSa["x(i,t) = x(i+1,t) OR x(i+1,t−aᵢ)<br/>min/max DEĞİL OR; n·T × O(1) → O(n·T); evet kolay hayır zor"]
A --> PS["Pseudopolinom — poli DEĞİL"]
PS --> PSa["T ≤ 2ʷ, w üst sınırı YOK → T = 2ⁿ → n·2ⁿ üstel<br/>strongly > weakly (log) > pseudo (sayı); T ≤ poly(n) → poli (radix)"]
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 RC,RP,SS,PS branch
class RCa,RPa,SSa,PSa leaf
```
::: {.callout-tip title="Builder Notu — subset sum = knapsack / bütçe-dağıtımının temeli"}
Subset sum, **sırt çantası (knapsack)**, bütçe-dağıtım ve kaynak-tahsis problemlerinin çekirdeğidir: "verilen bir kapasite/hedefe hangi öğe alt kümesi sığar?" sorusu her yerde karşına çıkar. Aynı $O(n \cdot T)$ DP tablosu, hedef yerine kapasite koyduğunda 0/1 knapsack'e dönüşür. Ama dikkat: bu süre **pseudopolinom**dur — $T$ (veya kapasite) büyükse patlar.
- **İleriye → knapsack/bütçe:** subset sum, knapsack ve bütçe-dağıtımının temelidir; çok boyutlu DP tablolarında kapasite/bütçe bir koordinattır.
- **İleriye → NP-tamlık:** subset sum bir karar problemidir; "evet"i kanıtlamak kolay (certificate), "hayır"ı zor — sonraki dersin (P/NP) habercisi.
- **Geriye → radix sort (Ders 7, L5):** pseudopolinom'un "poli olma" koşulu ($T \le \text{poly}(n)$), radix sort'un doğrusal çalışma koşuluyla **aynıdır** (sayılar poli-sınırlı) — aynı kavram iki yerde.
- **İleriye → OMSCS CS 6515:** "sayılar küçükse hızlı" bilinci; pseudopolinom algoritmaların hangi durumda pratik olduğunu (T küçük) ayırt etmek graduate algoritmalarının temel refleksidir.
Tek cümle: *Tamsayı girdiyi küçük sürümlerine bölerek DP yaparız; rod cutting $O(L^2)$ gerçek polinom, ama subset sum $O(n \cdot T)$ yalnız "pseudopolinom"dur ($T = 2^n$ olabilir) — yine de sayılar küçükse mükemmel.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 27 (L18) DP 4: Pseudopolinom / Subset Sum motoru
# (_engine.py D27 bölümü + bağımlılıkları INLINE GÖMÜLÜ — import YOK,
# brief: setup hücresine göm). Fonksiyonlar:
# rod_cutting / rod_plan / brute_rod / build_rod_example
# → tamsayı alt problem DP (x(ℓ)=max{v(p)+x(ℓ−p)}) + üstel tanık.
# subset_sum / subset_sum_certificate / brute_subset_sum
# + build_subset_example / build_subset_small_example → OR-recurrence DP
# (karar problemi) + 2ⁿ bitmask tanığı + ebeveyn-izi certificate.
# verify_subset_certificate → NP Tanım-2 doğrulayıcısı (D28/L19 köprüsü).
# bowling_bottom_up / build_bowling_example → OR-vs-minmax figürü için
# OPTİMİZASYON (max-birleştirici) karşı-örneği.
# Slate+Amber viz sabitleri (_viz.py COL_*) + apply_style. Bu hücre gizli
# (#| echo: false).
#
# Aşağıdaki TÜM figür hücreleri burada tanımlanan fonksiyonları IMPORT ETMEDEN
# kullanır (dosyadan import YOK). Notion'daki öğretim içeriği (görünür pseudocode)
# bu motorun tarif seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir).
# ============================================================================
import math
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# "HAYIR" / yanlış-cert için kırmızımsı ton (Slate paletiyle uyumlu uyarı rengi)
COL_RED = "#b91c1c" # red-700 — yanlış-cert çarpısı / "kanıt yok"
COL_RED_BG = "#fee2e2" # red-100 — açık kırmızı dolgu
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py — bowling_bottom_up (L15 §10) — OR-vs-minmax figürü karşı-örneği
# ---------------------------------------------------------------------------
def bowling_bottom_up(v):
"""Bowling bottom-up DP (L15 §10): B[n]=0 taban; i azalan; B[i] = max(
atla B[i+1], tek B[i+1]+vᵢ, çift B[i+2]+vᵢ·vᵢ₊₁ — yalnız ≥2 pin varsa).
O(n). OPTİMİZASYON DP'si (max-birleştirici) → OR karşıtı. Döndürür: B."""
n = len(v)
B = [0] * (n + 1)
for i in range(n - 1, -1, -1):
B[i] = max(B[i + 1], B[i + 1] + v[i])
if i + 1 < n:
B[i] = max(B[i], B[i + 2] + v[i] * v[i + 1])
return B
def build_bowling_example():
"""L15 dizisi: v = [1, 9, 9, 2, −5, −5]. Optimal 109."""
return [1, 9, 9, 2, -5, -5]
# ---------------------------------------------------------------------------
# _engine.py D27 (L18) §2-3 — Rod cutting: tamsayı alt problem DP
# ---------------------------------------------------------------------------
def rod_cutting(L, v):
"""Rod cutting bottom-up DP (L18 §2): x(ℓ) = ℓ uzunluk çubuğun max-değer
bölünmesi; R: ilk parça p kaba kuvvet — x(ℓ) = max{v[p] + x(ℓ−p) :
p = 1..ℓ}; T: ℓ artan; B: x(0)=0; O: x(L). L × O(L) = O(L²) GERÇEK
polinom (girdi L+1 kelime). v[p] = p uzunluk parça değeri (v[0] yok).
Döndürür: (x tablosu, first parça-seçim tablosu)."""
x = [0] * (L + 1)
first = [0] * (L + 1)
for length in range(1, L + 1):
best, bp = None, None
for p in range(1, length + 1):
cand = v[p] + x[length - p]
if best is None or cand > best:
best, bp = cand, p
x[length] = best
first[length] = bp
return x, first
def rod_plan(L, v):
"""Ebeveyn izi: optimal bölünmenin parça listesi (azalan sıralı)."""
x, first = rod_cutting(L, v)
parts, length = [], L
while length > 0:
parts.append(first[length])
length -= first[length]
return sorted(parts, reverse=True), x[L]
def brute_rod(L, v):
"""Bağımsız tanık (üstel, DP'siz): tüm bölünme kompozisyonlarını DFS ile
gez, max toplam değer. Yalnız küçük L testi."""
if L == 0:
return 0
return max(v[p] + brute_rod(L - p, v) for p in range(1, L + 1))
def build_rod_example():
"""L18 §2 örneği: L = 7, v = [_, 1, 10, 13, 18, 20, 31, 32] (1-indeksli;
v[0] doldurma). Optimal 3+2+2 → 13+10+10 = 33."""
return 7, [0, 1, 10, 13, 18, 20, 31, 32]
# ---------------------------------------------------------------------------
# _engine.py D27 (L18) §4-5 — Subset sum: OR-recurrence DP (karar problemi)
# ---------------------------------------------------------------------------
def subset_sum(A, T):
"""Subset sum memoized DP (L18 §5): x(i, t) = A[i:] sonekinin bir alt
kümesi t'ye toplanır mı? R: aᵢ'yi koyMA → x(i+1, t) VEYA koy (aᵢ ≤ t
ise) → x(i+1, t−aᵢ) — karar problemi → min/max değil OR. T: i azalan.
B: x(n, 0)=True; x(n, t≠0)=False. O: x(0, T). n·T alt problem × O(1)
= O(n·T) PSEUDOpolinom. Döndürür: (cevap, memo) — figür tablosu için."""
n = len(A)
memo = {}
def x(i, t):
if (i, t) in memo:
return memo[(i, t)]
if i == n:
r = (t == 0)
else:
r = x(i + 1, t) # aᵢ dışarıda
if not r and A[i] <= t:
r = x(i + 1, t - A[i]) # aᵢ içeride
memo[(i, t)] = r
return r
return x(0, T), memo
def subset_sum_certificate(A, T):
"""'Evet' certificate'i (L18 §5 + §4 asimetri): ebeveyn iziyle T'ye
toplanan alt kümeyi geri kur; cevap 'hayır' ise None (kısa kanıt YOK —
NP habercisi). Döndürür: alt küme listesi veya None."""
ok, _ = subset_sum(A, T)
if not ok:
return None
subset, t = [], T
n = len(A)
for i in range(n):
if subset_sum(A[i + 1:], t)[0]: # aᵢ'siz devam mümkünse atla
continue
subset.append(A[i]) # değilse aᵢ kesin içeride
t -= A[i]
return subset
def brute_subset_sum(A, T):
"""Bağımsız tanık (2ⁿ bitmask, DP'siz): herhangi alt küme T'ye
toplanır mı?"""
n = len(A)
for mask in range(1 << n):
if sum(A[k] for k in range(n) if mask >> k & 1) == T:
return True
return False
def build_subset_example():
"""L18 §4 örneği: A = {2, 5, 7, 8, 9}; T = 21 → EVET (5+7+9);
T = 25 → HAYIR (kısa kanıt yok)."""
return [2, 5, 7, 8, 9], 21, 25
def build_subset_small_example():
"""L18 Egzersiz 2 örneği: A = {3, 4, 3, 1}, T = 6 → EVET (3+3) —
figür tablo örneği."""
return [3, 4, 3, 1], 6
def verify_subset_certificate(A, T, cert):
"""NP Tanım-2 doğrulayıcısı (L19 §6 köprüsü): girdi (A, T) + certificate
(alt küme) al, POLİNOM zamanda kontrol et — (1) toplam T mi, (2) cert
A'nın çoklu-küme alt kümesi mi. O(|cert| + |A|). Döndürür: bool."""
if sum(cert) != T:
return False
pool = list(A)
for e in cert:
if e in pool:
pool.remove(e)
else:
return False
return True
```
## 1. DP 4/4: Tamsayı Alt Problemler {#sec-1-dp-4-4-tamsayi-alt-problemler}
İlk üç DP dersi sequence (prefix/suffix/substring), çoklu girdi (çarpım) ve subproblem expansion'ı kurdu. Bu ders, **tamsayı girdi** alt problemini derinleştirir: Fibonacci'de $n$ verildi, $0 \ldots n$ için çözdük. Aynı teknik rod cutting ve subset sum'da. SRTBOT aynı kalır; yeni soru: "bu süre **polinom** mu?"
## 2. Rod Cutting: Tamsayı Alt Problem {#sec-2-rod-cutting-tamsayi-alt-problem}
**Problem.** $L$ uzunluğunda çubuk; $v(\ell) = \ell$ uzunluğunda parçanın satış değeri. Çubuğu tamsayı parçalara bölüp **toplam değeri maksimize** et. Örnek: $L = 7$, değerler $[1, 10, 13, 18, 20, 31, 32] \to$ optimal $3 + 2 + 2 = 13 + 10 + 10 = 33$.
**Çalışılan Örnek.** **S:** $x(\ell) = \ell$ uzunluk çubuğunun maksimum-değer bölünmesi, $\ell = 0 \ldots L$. **R:** ilk kesilecek parçanın boyu $p$'yi tahmin et:
$$x(\ell) = \max\{\, v(p) + x(\ell - p) : p = 1 \ldots \ell \,\}$$
**T:** $\ell$ artan. **B:** $x(0) = 0$. **O:** $x(L)$. **Süre:** $L$ alt problem $\times\, O(L)$ ($p$ seçimi) $= O(L^2)$. (DAG-en-uzun-yol olarak da görülebilir: değerleri negatifleyip en kısa yol.)
@fig-rod-cutting bu örneği motor üzerinde somutlaştırır: optimal bölünme $3 + 2 + 2$ (parça değerleri $v(3) = 13$, iki kez $v(2) = 10$), toplam $33$ — `rod_plan` ve üstel `brute_rod` birebir aynı sonucu verir. Alt tablo $x(\ell)$'ı $\ell = 0 \ldots 7$ için ve her hücrenin kazanan ilk parçasını ($\text{first}(\ell)$) gösterir; $L$ alt problem $\times\, O(L)$ rozeti $O(L^2)$'nin **gerçek polinom** olduğunu (girdi $L + 1$ kelime) vurgular.
```{python}
#| label: fig-rod-cutting
#| fig-cap: "Rod cutting: tamsayı alt problem DP (Demaine L18 §2-3 İMZA, 19:22). ÜST panel: 7-birim çubuk + optimal 3+2+2 kesim (amber ayraçlar), her parça v(p) değeriyle etiketli (v(3)=13, v(2)=10, v(2)=10), sağ kutuda toplam = 13+10+10 = 33; altta uzunluk-değer çizelgesi v(1..7) (kullanılan p=2,3 amber vurgulu). ALT panel: x(ℓ) DP tablosu ℓ=0..7 + kazanan ilk parça first(ℓ) satırı; taban x(0)=0 soluk, hedef x(7)=33 amber; recurrence kutusu x(ℓ) = max{ v(p) + x(ℓ−p) : p=1..ℓ }; O(L²) rozeti 'L alt problem × O(L) = O(L²), GERÇEK polinom (girdi L+1 kelime · Demaine 19:22)'. Veri MOTORDAN (assert): build_rod_example == (7, [0,1,10,13,18,20,31,32]); rod_plan == ([3,2,2], 33); brute_rod == 33; x == [0,1,10,13,20,23,31,33]; first == [0,1,2,3,2,2,6,2]; parça değerleri [13,10,10] toplam 33."
#| fig-width: 11.5
#| fig-height: 6.5
# fig-rod-cutting (L18 §2-3 İMZA): tamsayı alt problem rod cutting. Veri MOTORDAN.
L, v = build_rod_example()
assert L == 7, L
assert v == [0, 1, 10, 13, 18, 20, 31, 32], v
x, first = rod_cutting(L, v)
assert x == [0, 1, 10, 13, 20, 23, 31, 33], x
assert first == [0, 1, 2, 3, 2, 2, 6, 2], first
parts, val = rod_plan(L, v)
assert parts == [3, 2, 2] and val == 33, (parts, val)
assert brute_rod(L, v) == 33
assert sum(parts) == L
seg_lengths = parts # [3, 2, 2] (sol→sağ görsel düzen)
seg_values = [v[p] for p in seg_lengths] # [13, 10, 10]
assert seg_values == [13, 10, 10], seg_values
assert sum(seg_values) == val == 33
v_ruler = [v[p] for p in range(1, L + 1)]
assert v_ruler == [1, 10, 13, 18, 20, 31, 32], v_ruler
n_subproblems = L
fig, (ax_top, ax_bot) = plt.subplots(
2, 1, figsize=(11.5, 6.5), gridspec_kw={"height_ratios": [1.0, 1.15]})
# ===== ÜST PANEL — 7-birim çubuk + optimal 3+2+2 kesim + değer cetveli =====
ax_top.set_title(
"Rod cutting — optimal bölünme (3+2+2) · motor: rod_plan = "
f"{parts}, değer = {val}",
color=COL_TEXT, fontsize=12.5, weight="bold", pad=12)
unit_w = 1.0
bar_y, bar_h = 1.7, 0.78
seg_fills = [COL_AMBER_300, COL_AMBER_100, COL_AMBER_100]
seg_edges = [COL_AMBER_700, COL_ACCENT, COL_ACCENT]
for k in range(L):
ax_top.add_patch(FancyBboxPatch(
(k * unit_w, bar_y), unit_w, bar_h, boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=0.8, zorder=1))
ax_top.text(k * unit_w + unit_w * 0.5, bar_y - 0.22, str(k + 1),
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
zorder=4)
cut_x = 0.0
for s_idx, (slen, sval) in enumerate(zip(seg_lengths, seg_values)):
bx = cut_x * unit_w
bw = slen * unit_w
ax_top.add_patch(FancyBboxPatch(
(bx, bar_y), bw, bar_h, boxstyle="square,pad=0.0",
fc=seg_fills[s_idx], ec=seg_edges[s_idx], linewidth=2.6, zorder=2))
ax_top.text(bx + bw * 0.5, bar_y + bar_h * 0.5, f"p={slen}",
ha="center", va="center", fontsize=11, color=COL_TEXT,
weight="bold", zorder=4)
ax_top.text(bx + bw * 0.5, bar_y + bar_h + 0.30, f"v({slen}) = {sval}",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=5)
cut_x += slen
cut_pos = 0
boundaries = []
for slen in seg_lengths[:-1]:
cut_pos += slen
boundaries.append(cut_pos)
for b in boundaries:
ax_top.plot([b * unit_w, b * unit_w],
[bar_y - 0.10, bar_y + bar_h + 0.10],
color=COL_ACCENT, linewidth=3.0, zorder=6)
ax_top.add_patch(FancyArrowPatch(
(b * unit_w, bar_y + bar_h + 0.18), (b * unit_w, bar_y + bar_h + 0.02),
arrowstyle="-|>", mutation_scale=12, color=COL_ACCENT,
linewidth=2.0, zorder=6))
total_x = L * unit_w + 0.55
ax_top.add_patch(FancyBboxPatch(
(total_x, bar_y), 1.9, bar_h,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=3))
ax_top.text(total_x + 0.95, bar_y + bar_h * 0.62,
f"toplam = {seg_values[0]}+{seg_values[1]}+{seg_values[2]}",
ha="center", va="center", fontsize=9.5, color=COL_TEXT, zorder=4)
ax_top.text(total_x + 0.95, bar_y + bar_h * 0.26, f"= {val}",
ha="center", va="center", fontsize=13, color=COL_AMBER_700,
weight="bold", zorder=4)
ruler_y, ruler_h, ruler_w = 0.30, 0.55, 0.92
ax_top.text(-0.30, ruler_y + ruler_h * 0.5, "v(p):", ha="right", va="center",
fontsize=9.5, color=COL_PRIMARY, weight="bold")
for p in range(1, L + 1):
rx = (p - 1) * ruler_w
used = p in seg_lengths
ax_top.add_patch(FancyBboxPatch(
(rx, ruler_y), ruler_w * 0.94, ruler_h, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if used else COL_BG,
ec=COL_ACCENT if used else COL_PRIMARY,
linewidth=2.0 if used else 1.2, zorder=2))
ax_top.text(rx + ruler_w * 0.47, ruler_y + ruler_h * 0.62, str(v_ruler[p - 1]),
ha="center", va="center", fontsize=10, color=COL_TEXT,
weight="bold", zorder=4)
ax_top.text(rx + ruler_w * 0.47, ruler_y + ruler_h * 0.18, f"p={p}",
ha="center", va="center", fontsize=7.5, color=COL_SLATE_500,
zorder=4)
ax_top.text(L * ruler_w + 0.30, ruler_y + ruler_h * 0.5,
"uzunluk-değer çizelgesi", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic")
ax_top.set_xlim(-1.4, L * unit_w + 2.8)
ax_top.set_ylim(-0.05, bar_y + bar_h + 0.75)
ax_top.set_aspect("equal")
ax_top.axis("off")
# ===== ALT PANEL — x(ℓ) DP tablosu + first(ℓ) + recurrence + O(L²) rozeti =====
cell_w, cell_h = 1.05, 0.95
tbl_x0, tbl_y = 0.0, 2.05
ax_bot.text(tbl_x0 - 0.28, tbl_y + cell_h + cell_h * 0.5, "ℓ", ha="right",
va="center", fontsize=11, color=COL_PRIMARY, weight="bold")
ax_bot.text(tbl_x0 - 0.28, tbl_y + cell_h * 0.5, "x(ℓ)", ha="right",
va="center", fontsize=11, color=COL_PRIMARY, weight="bold")
ax_bot.text(tbl_x0 - 0.28, tbl_y - cell_h * 0.5 + 0.02, "ilk parça", ha="right",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold")
for ell in range(L + 1):
cx = tbl_x0 + ell * cell_w
ax_bot.add_patch(FancyBboxPatch(
(cx, tbl_y + cell_h), cell_w * 0.94, cell_h, boxstyle="square,pad=0.0",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.4, zorder=2))
ax_bot.text(cx + cell_w * 0.47, tbl_y + cell_h + cell_h * 0.5, str(ell),
ha="center", va="center", fontsize=11, color=COL_TEXT,
weight="bold", zorder=4)
is_base = (ell == 0)
is_goal = (ell == L)
ax_bot.add_patch(FancyBboxPatch(
(cx, tbl_y), cell_w * 0.94, cell_h, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if is_goal else (COL_WHITE if is_base else COL_BG),
ec=COL_ACCENT if is_goal else (COL_SLATE_400 if is_base else COL_PRIMARY),
linewidth=2.6 if is_goal else (1.2 if is_base else 1.5), zorder=2))
ax_bot.text(cx + cell_w * 0.47, tbl_y + cell_h * 0.5, str(x[ell]),
ha="center", va="center", fontsize=12,
color=COL_AMBER_700 if is_goal else COL_TEXT,
weight="bold", zorder=4)
ax_bot.add_patch(FancyBboxPatch(
(cx, tbl_y - cell_h), cell_w * 0.94, cell_h * 0.85,
boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.0, zorder=2))
fp_txt = "—" if ell == 0 else f"p={first[ell]}"
ax_bot.text(cx + cell_w * 0.47, tbl_y - cell_h * 0.5 + 0.02, fp_txt,
ha="center", va="center", fontsize=9.5,
color=COL_SLATE_500 if ell == 0 else COL_AMBER_700,
weight="bold", zorder=4)
ax_bot.text(tbl_x0 + 0 * cell_w + cell_w * 0.47, tbl_y - cell_h - 0.32,
"taban x(0)=0", ha="center", va="center", fontsize=8.5,
color=COL_SLATE_500, style="italic")
ax_bot.text(tbl_x0 + L * cell_w + cell_w * 0.47, tbl_y - cell_h - 0.32,
f"hedef x(L)={x[L]}", ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold")
rec_y = tbl_y - cell_h - 1.55
ax_bot.add_patch(FancyBboxPatch(
(tbl_x0 + 0.1, rec_y), 5.75, 0.92,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=2))
ax_bot.text(tbl_x0 + 0.35, rec_y + 0.60,
"Yineleme (recurrence):", ha="left", va="center",
fontsize=10, color=COL_TEXT, weight="bold")
ax_bot.text(tbl_x0 + 0.35, rec_y + 0.26,
"x(ℓ) = max{ v(p) + x(ℓ−p) : p = 1..ℓ }", ha="left", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold")
badge_x = tbl_x0 + 6.55
ax_bot.add_patch(FancyBboxPatch(
(badge_x, rec_y - 0.08), 5.05, 1.08,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax_bot.text(badge_x + 2.52, rec_y + 0.72,
f"{n_subproblems} alt problem × O(L) = O(L²)",
ha="center", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=4)
ax_bot.text(badge_x + 2.52, rec_y + 0.36,
"GERÇEK polinom", ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=4)
ax_bot.text(badge_x + 2.52, rec_y + 0.06,
"(girdi = L+1 kelime · Demaine 19:22)", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=4)
ax_bot.set_xlim(-1.5, tbl_x0 + (L + 1) * cell_w + 4.6)
ax_bot.set_ylim(rec_y - 0.55, tbl_y + 2 * cell_h + 0.35)
ax_bot.set_aspect("equal")
ax_bot.axis("off")
fig.tight_layout()
plt.show()
```
## 3. Rod Cutting Polinom mu? {#sec-3-rod-cutting-polinom-mu}
Evet — **gerçek polinom** (strongly polynomial). "Polinom zaman" = sürenin **girdi boyutuna** polinom olması. Girdi boyutu **kelime (word)** cinsinden ölçülür.
> *"polynomial time means that the running time is polynomial in the size of the input."* — Demaine, 19:22
Rod cutting girdisi: bir sayı $L$ + $L$ sayılık değer dizisi $= L + 1$ kelime. $O(L^2)$, $L + 1$'e polinomdur $\to$ polinom zaman. ✓ ( @fig-rod-cutting'in $O(L^2)$ rozeti bu sonucu birebir taşır: $L$ alt problem $\times\, O(L)$ seçim.)
## 4. Subset Sum: Karar Problemi {#sec-4-subset-sum-karar-problemi}
**Problem.** $n$ tamsayılık çoklu-küme (multiset) $A$ + hedef $T$. **Herhangi bir alt küme $T$'ye toplanır mı?** Bu bir **karar problemi** — çıktı tek bit: evet/hayır. Örnek: $A = \{2, 5, 7, 8, 9\}$, $T = 21 \to$ evet ($5 + 7 + 9$); $T = 25 \to$ hayır.
> *"this is what we call a decision problem... we're just interested in a yes or no answer."* — Demaine, 27:10
İlginç: "evet"i kanıtlamak kolay — alt kümeyi göster; "hayır"ı kanıtlamak için bilinen kısa bir yol yok. Sonraki dersin habercisi.
> *"there's no succinct way as far as we know to prove to someone that the answer is no."* — Demaine, 26:49
@fig-certificate bu asimetriyi motor üzerinde gösterir: $T = 21$ için `subset_sum_certificate` certificate $\{5, 7, 9\}$ döndürür ($5 + 7 + 9 = 21$); bir doğrulayıcı bunu **polinom zamanda** kontrol eder (`verify_subset_certificate` $\to$ True). Yanlış bir certificate $\{5, 7, 8\}$ ($= 20 \neq 21$) de hızla reddedilir. Ama $T = 25$ için certificate `None`'dır — hiçbir alt küme $25$ vermez ve bunu kısa yoldan kanıtlamanın bilinen yolu yok, tek kesinlik $2^5 = 32$ alt kümenin **hepsini** taramak. Bu asimetri, Ders 28'in (L19) **NP** sınıfının habercisidir.
```{python}
#| label: fig-certificate
#| fig-cap: "Karar problemi asimetrisi: «EVET»i doğrulamak kolay, «HAYIR»ı zor (Demaine L18 §4, 27:10 + 26:49; NP habercisi → Ders 28/L19). SOL panel 'EVET kanıtı KOLAY': A = {2,5,7,8,9} 5 madalyon, certificate {5,7,9} amber seçili; doğrulayıcı kutusu '5+7+9 = 21 ✓ → polinom zamanda KONTROL (Demaine 27:10)'; yanlış-cert {5,7,8} → 20 ≠ 21 kırmızı REDDET (doğrulayıcı yine hızlı yakalar). SAĞ panel 'HAYIR kanıtı YOK': T=25 büyük kırmızı soru kutusu 'hiçbir alt küme 25 vermez, kısa ispat yok, certificate = None (Demaine 26:49)'; 2⁵ = 32 alt kümenin mini-ızgarası (hepsi ✗); alt rozet → Ders 28 (L19): NP — EVET doğrulanabilir, HAYIR değil. Veri MOTORDAN (assert): build_subset_example == ([2,5,7,8,9], 21, 25); subset_sum(A,21)[0] is True, certificate == [5,7,9] (toplam 21); subset_sum(A,25)[0] is False, certificate is None; verify_subset_certificate(A,21,[5,7,9]) is True; verify_subset_certificate(A,21,[5,7,8]) is False (5+7+8=20); 2⁵ = 32."
#| fig-width: 12.0
#| fig-height: 5.5
# fig-certificate (L18 §4): karar problemi asimetrisi. Veri MOTORDAN.
A, T_yes, T_no = build_subset_example()
assert A == [2, 5, 7, 8, 9], A
assert (T_yes, T_no) == (21, 25), (T_yes, T_no)
yes_ok, _ = subset_sum(A, T_yes)
no_ok, _ = subset_sum(A, T_no)
assert yes_ok is True and no_ok is False
cert_yes = subset_sum_certificate(A, T_yes)
cert_no = subset_sum_certificate(A, T_no)
assert cert_yes == [5, 7, 9] and sum(cert_yes) == T_yes, cert_yes
assert cert_no is None, cert_no
bad_cert = [5, 7, 8]
assert verify_subset_certificate(A, T_yes, cert_yes) is True
assert verify_subset_certificate(A, T_yes, bad_cert) is False
assert sum(bad_cert) == 20
cert_sum = sum(cert_yes)
bad_sum = sum(bad_cert)
n_subsets = 2 ** len(A)
assert n_subsets == 32
fig, (ax_l, ax_r) = plt.subplots(1, 2, figsize=(12.0, 5.5))
fig.patch.set_facecolor(COL_WHITE)
# ---- SOL: EVET kanıtı KOLAY ----
ax_l.set_title("EVET kanıtı KOLAY — doğrulayıcı polinom zamanda kontrol eder",
color=COL_TEXT, fontsize=12, weight="bold", pad=14)
ax_l.text(0.5, 8.95, "girdi: A = { 2, 5, 7, 8, 9 }, T = 21",
ha="left", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
r = 0.52
cx0, cy = 1.15, 7.85
gap = 1.55
cert_set = set(cert_yes)
for k, a in enumerate(A):
cx = cx0 + k * gap
hot = a in cert_set
ax_l.add_patch(Circle((cx, cy), r,
facecolor=COL_AMBER_100 if hot else COL_BG,
edgecolor=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.8 if hot else 1.8, zorder=3))
ax_l.text(cx, cy, str(a), ha="center", va="center",
fontsize=14, color=COL_TEXT, weight="bold", zorder=4)
if hot:
ax_l.text(cx, cy + r + 0.30, "✓", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax_l.text(cx0 - r - 0.18, cy + r + 0.55, "certificate seçilen öğeler",
ha="left", va="center", fontsize=8.5, color=COL_AMBER_700,
style="italic", zorder=5)
box_x, box_y, box_w, box_h = 0.55, 4.65, 8.9, 1.85
ax_l.add_patch(FancyBboxPatch(
(box_x, box_y), box_w, box_h,
boxstyle="round,pad=0.05,rounding_size=0.14",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=2))
sum_str = " + ".join(str(c) for c in cert_yes)
ax_l.text(box_x + 0.35, box_y + box_h - 0.50,
"doğrulayıcı: certificate {5, 7, 9} verildi",
ha="left", va="center", fontsize=10.5, color=COL_TEXT,
weight="bold", zorder=4)
ax_l.text(box_x + 0.35, box_y + 0.62,
f"topla: {sum_str} = {cert_sum} ✓ → polinom zamanda KONTROL",
ha="left", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax_l.text(box_x + box_w - 0.30, box_y + 0.18, "Demaine 27:10",
ha="right", va="bottom", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=4)
ax_l.add_patch(FancyArrowPatch(
(cx0 + 2 * gap, cy - r - 0.10), (cx0 + 2 * gap, box_y + box_h + 0.12),
arrowstyle="-|>", mutation_scale=16, color=COL_AMBER_600,
linewidth=2.0, zorder=3))
bad_str = " + ".join(str(b) for b in bad_cert)
bbox_x, bbox_y, bbox_w, bbox_h = 0.55, 2.25, 8.9, 1.55
ax_l.add_patch(FancyBboxPatch(
(bbox_x, bbox_y), bbox_w, bbox_h,
boxstyle="round,pad=0.05,rounding_size=0.14",
fc=COL_RED_BG, ec=COL_RED, linewidth=1.8, zorder=2))
ax_l.text(bbox_x + 0.35, bbox_y + bbox_h - 0.42,
"yanlış certificate {5, 7, 8}: doğrulayıcı yine HIZLI yakalar",
ha="left", va="center", fontsize=10, color=COL_TEXT,
weight="bold", zorder=4)
ax_l.text(bbox_x + 0.35, bbox_y + 0.50,
f"topla: {bad_str} = {bad_sum} ✗ {bad_sum} ≠ {T_yes} → REDDET",
ha="left", va="center", fontsize=11, color=COL_RED,
weight="bold", zorder=4)
ax_l.text(bbox_x + bbox_w - 0.40, bbox_y + bbox_h - 0.42, "✗",
ha="right", va="center", fontsize=20, color=COL_RED,
weight="bold", zorder=5)
ax_l.text(box_x + box_w * 0.5, 1.30,
"geçerli bir certificate VAR → O(|cert| + |A|) doğrulama",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=4)
ax_l.set_xlim(0, 10)
ax_l.set_ylim(0.7, 9.5)
ax_l.axis("off")
# ---- SAĞ: HAYIR kanıtı YOK ----
ax_r.set_title("HAYIR kanıtı YOK — kısa ispatın bilinen yolu yok",
color=COL_TEXT, fontsize=12, weight="bold", pad=14)
ax_r.text(0.5, 8.95, "girdi: A = { 2, 5, 7, 8, 9 }, T = 25",
ha="left", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
qx, qy, qw, qh = 0.55, 6.30, 8.9, 2.15
ax_r.add_patch(FancyBboxPatch(
(qx, qy), qw, qh, boxstyle="round,pad=0.05,rounding_size=0.16",
fc=COL_RED_BG, ec=COL_RED, linewidth=2.0, zorder=2))
ax_r.text(qx + 0.55, qy + qh - 0.45, "?", ha="center", va="center",
fontsize=26, color=COL_RED, weight="bold", zorder=4)
ax_r.text(qx + 1.25, qy + qh - 0.50, "hiçbir alt küme 25 vermez",
ha="left", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=4)
ax_r.text(qx + 0.40, qy + 0.78, "ama bunu KISA yoldan ispatlamanın",
ha="left", va="center", fontsize=10.5, color=COL_RED,
weight="bold", zorder=4)
ax_r.text(qx + 0.40, qy + 0.38, "bilinen yolu yok — certificate = None",
ha="left", va="center", fontsize=10.5, color=COL_RED,
weight="bold", zorder=4)
ax_r.text(qx + qw - 0.30, qy + 0.16, "Demaine 26:49",
ha="right", va="bottom", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=4)
ax_r.text(0.55, 5.55,
f"tek bilinen kesinlik: 2⁵ = {n_subsets} alt kümenin HEPSİNİ tara",
ha="left", va="center", fontsize=10, color=COL_TEXT, weight="bold")
g_cols, g_rows = 8, 4
assert g_cols * g_rows == n_subsets
gx0, gy0 = 1.05, 4.55
dx, dy = 1.02, 0.92
rr = 0.30
for idx in range(n_subsets):
col = idx % g_cols
row = idx // g_cols
cx = gx0 + col * dx
cyy = gy0 - row * dy
ax_r.add_patch(Circle((cx, cyy), rr, facecolor=COL_WHITE,
edgecolor=COL_SLATE_400, linewidth=1.2, zorder=3))
ax_r.text(cx, cyy, "✗", ha="center", va="center", fontsize=10,
color=COL_RED, weight="bold", zorder=4)
ax_r.text(gx0 + (g_cols - 1) * dx + rr + 0.25, gy0 - (g_rows - 1) * dy * 0.5,
f"{n_subsets}\nalt küme\nhepsi ✗", ha="left", va="center",
fontsize=8.5, color=COL_RED, weight="bold", zorder=4)
ax_r.text(0.55 + qw * 0.5, 0.92,
"doğrulama için kısa certificate YOK → kaba kuvvet 2ⁿ",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=4)
bx, by, bw, bh = 0.55, 0.05, 8.9, 0.66
ax_r.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_PRIMARY, ec=COL_PRIMARY, linewidth=1.4, zorder=2))
ax_r.text(bx + bw * 0.5, by + bh * 0.5,
"sonraki ders (Ders 28, L19): NP — EVET doğrulanabilir, HAYIR değil",
ha="center", va="center", fontsize=9.8, color=COL_WHITE,
weight="bold", zorder=4)
ax_r.set_xlim(0, 10)
ax_r.set_ylim(-0.2, 9.5)
ax_r.axis("off")
fig.suptitle(
"Karar problemi asimetrisi: «EVET»i doğrulamak kolay, «HAYIR»ı zor (NP habercisi)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.99)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## 5. Subset Sum Recurrence: OR {#sec-5-subset-sum-recurrence-or}
**Çalışılan Örnek.** **S:** $x(i, t) = A[i:]$ sonekinin herhangi bir alt kümesi $t$'ye toplanır mı? ($0 \le i \le n$, $0 \le t \le T$). $a_i$'yi kümeye **koy** ya da **koyma** — iki seçenek:
$$x(i, t) = x(i+1, t) \;\textbf{ OR }\; \bigl( x(i+1, t - a_i) \;:\; a_i \le t \bigr)$$
*(İkinci terim yalnız $a_i \le t$ ise geçerlidir.)*
İlk: $a_i$ dışarıda. İkinci: $a_i$ içeride $\to$ kalan $t - a_i$'ye toplanmalı; $a_i \le t$ koşulu negatif $t$'yi önler. Optimizasyon değil $\to$ min/max değil, **OR**. **T:** $i$ azalan. **B:** $x(n, 0) = $ evet; $x(n, t \neq 0) = $ hayır. **O:** $x(0, T)$. $2^n$ alt kümeyi, yerel ikili seçimlerle ve memoization ile tararız (alt problemler "toplamı $t$ olan" tüm alt kümeleri tek değere çöker).
**Süre:** $n \cdot T$ alt problem $\times\, O(1) = O(n \cdot T)$. ("Evet" durumunda ebeveyn işaretçileriyle alt küme de bulunur.)
@fig-or-vs-minmax bu recurrence'ın özünü, bir optimizasyon DP'siyle (bowling) yan yana koyar: yapı **aynı** (yerel ikili seçim + memoize), değişen yalnız **birleştirici**dir — bowling `max` ile sayı (motor: $B(0) = 109$), subset sum `OR` ile tek bit ($x(0, 6) = x(1, 6)$ False $\text{OR}\ x(1, 3)$ True $=$ True) üretir.
```{python}
#| label: fig-or-vs-minmax
#| fig-cap: "Karar vs optimizasyon recurrence: subset sum OR-birleştirici tek bit, bowling max-birleştirici sayı (Demaine L18 §5). SOL sütun 'OPTİMİZASYON (çoğu DP)': bowling B(i) = max(atla, tek, çift); çıktı SAYI 109; min/max SAYILARI birleştirir. SAĞ sütun 'KARAR (subset sum)': gerçek hücre x(0,6) = x(1,6)=HAYIR OR x(1,3)=EVET; çıktı TEK BİT EVET; OR BOOLEANLARI birleştirir (Python any). ORTA köprü rozeti 'yapı AYNI: yerel ikili seçim + memoize; değişen yalnız BİRLEŞTİRİCİ'. Alt not: EVET'te ebeveyn iziyle alt küme de çıkar → certificate [3,3] (toplam 6 = T). Veri MOTORDAN (assert): build_subset_small_example == ([3,4,3,1], 6); subset_sum(A,6)[0] is True; x(0,6) = x(1,6)=False OR x(1,3)=True = True; a₀=3, t−a₀=3; certificate == [3,3] toplam 6; build_bowling_example == [1,9,9,2,−5,−5]; bowling_bottom_up B[0] == 109."
#| fig-width: 11.0
#| fig-height: 5.2
# fig-or-vs-minmax (L18 §5): KARAR (OR) vs OPTİMİZASYON (max). Veri MOTORDAN.
A, T = build_subset_small_example()
assert A == [3, 4, 3, 1] and T == 6, (A, T)
ans, memo = subset_sum(A, T)
assert ans is True
i0, t0 = 0, 6
a_i = A[i0]
cell_val = memo[(i0, t0)]
skip_val = memo[(i0 + 1, t0)]
inc_val = memo[(i0 + 1, t0 - a_i)]
assert cell_val is True and skip_val is False and inc_val is True
assert (skip_val or inc_val) is cell_val
assert a_i == 3 and (t0 - a_i) == 3
cert = subset_sum_certificate(A, T)
assert cert == [3, 3] and sum(cert) == T
vb = build_bowling_example()
assert vb == [1, 9, 9, 2, -5, -5], vb
B = bowling_bottom_up(vb)
bowling_opt = B[0]
assert bowling_opt == 109, bowling_opt
def _yes_no(b):
return "EVET" if b else "HAYIR"
fig, ax = plt.subplots(figsize=(11, 5.2))
LX = 2.35
RX = 8.65
BOX_W = 4.05
Y_TITLE = 9.45
Y_BOX_TOP = 8.45
BOX_H = 2.65
Y_OUT = 3.05
Y_COMB = 1.58
Y_MID = 4.78
ax.text(LX, Y_TITLE, "OPTİMİZASYON", ha="center", va="center",
fontsize=14, color=COL_PRIMARY, weight="bold")
ax.text(LX, Y_TITLE - 0.52, "(çoğu DP)", ha="center", va="center",
fontsize=10.5, color=COL_SLATE_500, style="italic")
ax.text(RX, Y_TITLE, "KARAR", ha="center", va="center",
fontsize=14, color=COL_AMBER_700, weight="bold")
ax.text(RX, Y_TITLE - 0.52, "(subset sum)", ha="center", va="center",
fontsize=10.5, color=COL_SLATE_500, style="italic")
ax.add_patch(FancyBboxPatch(
(LX - BOX_W / 2, Y_BOX_TOP - BOX_H), BOX_W, BOX_H,
boxstyle="round,pad=0.02,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.2, zorder=2))
ax.text(LX, Y_BOX_TOP - 0.42, "bowling örneği", ha="center", va="center",
fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=4)
ax.text(LX, Y_BOX_TOP - 1.20, "B(i) = max(\natla, tek, çift\n)",
ha="center", va="center", fontsize=12.5, color=COL_TEXT,
weight="bold", zorder=4, linespacing=1.5)
ax.text(LX, Y_BOX_TOP - 2.38, "birleştirici = max",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.add_patch(FancyBboxPatch(
(LX - 1.45, Y_OUT - 0.55), 2.9, 1.10,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=2.2, zorder=3))
ax.text(LX, Y_OUT + 0.16, "çıktı: SAYI", ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(LX, Y_OUT - 0.22, str(bowling_opt), ha="center", va="center",
fontsize=20, color=COL_TEXT, weight="bold", zorder=5)
ax.add_patch(FancyArrowPatch(
(LX, Y_BOX_TOP - BOX_H - 0.05), (LX, Y_OUT + 0.58),
arrowstyle="-|>", mutation_scale=16, color=COL_PRIMARY,
linewidth=2.0, zorder=2))
ax.text(LX, Y_COMB, "min/max SAYILARI birleştirir",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold", zorder=4)
ax.add_patch(FancyBboxPatch(
(RX - BOX_W / 2, Y_BOX_TOP - BOX_H), BOX_W, BOX_H,
boxstyle="round,pad=0.02,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=2.4, zorder=2))
ax.text(RX, Y_BOX_TOP - 0.42, "gerçek hücre: x(%d, %d)" % (i0, t0),
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
style="italic", zorder=4)
ax.text(RX, Y_BOX_TOP - 1.02, "x(%d,%d) =" % (i0, t0), ha="center",
va="center", fontsize=13, color=COL_TEXT, weight="bold", zorder=4)
sub_y = Y_BOX_TOP - 1.72
ax.text(RX - 1.18, sub_y, "x(%d,%d)" % (i0 + 1, t0), ha="center",
va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=4)
ax.text(RX - 1.18, sub_y - 0.42, _yes_no(skip_val), ha="center",
va="center", fontsize=9.5, color=COL_SLATE_500, weight="bold", zorder=4)
ax.text(RX, sub_y - 0.10, "OR", ha="center", va="center",
fontsize=12.5, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(RX + 1.18, sub_y, "x(%d,%d)" % (i0 + 1, t0 - a_i), ha="center",
va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=4)
ax.text(RX + 1.18, sub_y - 0.42, _yes_no(inc_val), ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(RX, Y_BOX_TOP - BOX_H + 0.22, "birleştirici = OR (any)",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.add_patch(FancyBboxPatch(
(RX - 1.45, Y_OUT - 0.55), 2.9, 1.10,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=2.2, zorder=3))
ax.text(RX, Y_OUT + 0.16, "çıktı: TEK BİT", ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(RX, Y_OUT - 0.24, _yes_no(cell_val), ha="center", va="center",
fontsize=18, color=COL_TEXT, weight="bold", zorder=5)
ax.add_patch(FancyArrowPatch(
(RX, Y_BOX_TOP - BOX_H - 0.05), (RX, Y_OUT + 0.58),
arrowstyle="-|>", mutation_scale=16, color=COL_AMBER_600,
linewidth=2.0, zorder=2))
ax.text(RX, Y_COMB, "OR BOOLEANLARI birleştirir (Python any)",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=4)
MID_X = (LX + RX) / 2.0
BR_W, BR_H = 3.30, 1.72
ax.add_patch(FancyBboxPatch(
(MID_X - BR_W / 2, Y_MID - BR_H / 2), BR_W, BR_H,
boxstyle="round,pad=0.02,rounding_size=0.14",
fc=COL_WHITE, ec=COL_AMBER_700, linewidth=2.6, zorder=6))
ax.text(MID_X, Y_MID + 0.58, "yapı AYNI", ha="center", va="center",
fontsize=13, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(MID_X, Y_MID + 0.06, "yerel ikili seçim + memoize", ha="center",
va="center", fontsize=9, color=COL_TEXT, zorder=7)
ax.text(MID_X, Y_MID - 0.48, "değişen: yalnız BİRLEŞTİRİCİ", ha="center",
va="center", fontsize=9, color=COL_PRIMARY, weight="bold", zorder=7)
for cx, col in ((LX, COL_PRIMARY), (RX, COL_AMBER_600)):
side = -1 if cx < MID_X else 1
ax.plot([MID_X + side * BR_W / 2, cx],
[Y_MID + 0.55, Y_BOX_TOP - BOX_H + 0.10],
color=col, linewidth=1.3, linestyle=":", alpha=0.75, zorder=1)
note = ("EVET'te ebeveyn iziyle alt küme de çıkar → certificate: "
"%s (toplam %d = T)" % ("+".join(map(str, cert)), sum(cert)))
ax.add_patch(FancyBboxPatch(
(MID_X - 4.85, 0.30), 9.7, 0.78,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.5, zorder=2))
ax.text(MID_X, 0.69, note, ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=4)
ax.set_xlim(0, 11)
ax.set_ylim(0, 10)
ax.axis("off")
fig.tight_layout()
plt.show()
```
@fig-subset-table aynı DP'yi `build_subset_small_example` ($A = \{3, 4, 3, 1\}$, $T = 6$) üzerinde tam tabloyla gösterir: satırlar $i = 0 \ldots 4$, sütunlar $t = 0 \ldots 6$. Kritik detay — **yalnız memoization'ın gerçekten sorduğu hücreler doludur** (motor `memo`'sundan): $16$ hücre, $n \cdot T = 4 \cdot 6 = 24$ olası alt problemin ve $6 \times 22$ üst-sınırın çok altında — memoization yalnız gerekeni çözer (pseudopolinom tanığı). Certificate yolu $[3, 3]$ kalın amber "koy" / soluk "koyma" oklarıyla izlenir.
```{python}
#| label: fig-subset-table
#| fig-cap: "Subset Sum: x(i,t) OR-recurrence memoization tablosu (Demaine L18 §5 İMZA). A = {3,4,3,1}, T = 6. Satırlar i=0..4 (taban i=4 EN ALTTA, satır etiketi A[i:] soneki), sütunlar t=0..6. SADECE memoization'ın gerçekten sorduğu hücreler dolu (motor memo'sundan, 16 hücre); kalanlar soluk kesik 'hiç sorulmadı' — memoization yalnız gerekeni çözer (pseudopolinom tanığı). True = amber ✓, False = slate ✗. Cevap x(0,6) büyük amber çerçeve = EVET. Certificate yolu [3,3]: koy adımları kalın amber ok (koy a₀=3 t:6→3, koy a₂=3 t:3→0), koyma adımları soluk slate ok (koyma a₁=4, koyma a₃=1). Recurrence kutusu: x(i,t) = x(i+1,t) OR x(i+1,t−aᵢ) [aᵢ≤t] — karar problemi → min/max DEĞİL OR. Alt rozet: n·T = 4·6 = 24 alt problem × O(1) = O(n·T) pseudopolinom. Veri MOTORDAN (assert): build_subset_small_example == ([3,4,3,1], 6); subset_sum True, memo[(0,6)] True, memo[(4,0)] True; certificate == [3,3] toplam 6; yol [(0,6)PUT3,(1,3)skip4,(2,3)PUT3,(3,0)skip1]; memo hücre sayısı 16."
#| fig-width: 11.5
#| fig-height: 6.5
# fig-subset-table (L18 §5 İMZA): OR-recurrence memo tablosu. Veri MOTORDAN.
A, T = build_subset_small_example()
assert A == [3, 4, 3, 1] and T == 6, (A, T)
ok, memo = subset_sum(A, T)
assert ok is True
assert brute_subset_sum(A, T) is True # bağımsız 2ⁿ tanık
cert = subset_sum_certificate(A, T)
assert cert == [3, 3] and sum(cert) == T, cert
n = len(A)
assert memo[(0, T)] is True and memo[(n, 0)] is True
assert len(memo) == 16, len(memo) # pseudopolinom tanığı: ≤ 6×22
# Certificate yolunu motor mantığıyla yeniden üret (PUT/skip kararları)
path = []
t_cur = T
for i in range(n):
if subset_sum(A[i + 1:], t_cur)[0]:
path.append((i, t_cur, "skip", A[i]))
else:
path.append((i, t_cur, "PUT", A[i]))
t_cur -= A[i]
assert t_cur == 0
assert path == [(0, 6, "PUT", 3), (1, 3, "skip", 4),
(2, 3, "PUT", 3), (3, 0, "skip", 1)], path
path_cells = [(0, 6), (1, 3), (2, 3), (3, 0), (4, 0)]
for c in path_cells:
assert c in memo and memo[c] is True
T_MAX = T
n_cols = T_MAX + 1
n_rows = n + 1
cw, ch = 1.0, 1.0
x_lab = 1.7
y_top = 0.0
def cell_xy(i, t):
return x_lab + t * cw, y_top - i * ch
def cell_center(i, t):
xx, yy = cell_xy(i, t)
return xx + cw * 0.5, yy + ch * 0.5
suffix_label = {}
for i in range(n + 1):
suf = A[i:]
if suf:
suffix_label[i] = "A[%d:] = {%s}" % (i, ", ".join(str(a) for a in suf))
else:
suffix_label[i] = "A[%d:] = {} (boş)" % i
fig, ax = plt.subplots(figsize=(11.5, 6.5))
path_set = set(path_cells)
for t in range(n_cols):
cx, _ = cell_center(0, t)
ax.text(cx, y_top + ch * 0.72, "t=%d" % t, ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold")
ax.text(x_lab + n_cols * cw * 0.5, y_top + ch * 1.35,
"hedef toplam t →", ha="center", va="center",
fontsize=10.5, color=COL_SLATE_500, style="italic")
for i in range(n_rows):
_, ylab = cell_center(i, 0)
is_base = (i == n)
ax.text(x_lab - 0.18, ylab, suffix_label[i], ha="right", va="center",
fontsize=8.6, color=(COL_AMBER_700 if is_base else COL_SLATE_500),
weight=("bold" if is_base else "normal"))
ax.text(x_lab - 0.18, ylab - 0.30, "i=%d%s" % (i, " (taban)" if is_base else ""),
ha="right", va="center", fontsize=7.8,
color=(COL_AMBER_700 if is_base else COL_SLATE_400),
weight=("bold" if is_base else "normal"))
for t in range(n_cols):
xx, yy = cell_xy(i, t)
asked = (i, t) in memo
on_path = (i, t) in path_set
if not asked:
ax.add_patch(FancyBboxPatch(
(xx, yy), cw * 0.92, ch * 0.92, boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=0.9,
linestyle=(0, (2, 2)), zorder=2, alpha=0.55))
continue
val = memo[(i, t)]
if val:
fc, ec = COL_AMBER_100, COL_ACCENT
lw = 2.6 if on_path else 2.0
else:
fc, ec = COL_BG, COL_SLATE_400
lw = 1.5
ax.add_patch(FancyBboxPatch(
(xx, yy), cw * 0.92, ch * 0.92, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cx, cy = cell_center(i, t)
mark = "✓" if val else "✗"
ax.text(cx, cy + ch * 0.04, mark, ha="center", va="center",
fontsize=15, weight="bold", zorder=5,
color=(COL_AMBER_700 if val else COL_SLATE_500))
ax.text(x_lab + n_cols * cw * 0.5, cell_xy(n, 0)[1] - 0.40,
"Taban (i=n=4): x(4, 0)=True (boş alt küme → 0) · x(4, t≠0)=False",
ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold")
ax0, ay0 = cell_xy(0, T)
ax.add_patch(FancyBboxPatch(
(ax0 - 0.07, ay0 - 0.07), cw * 0.92 + 0.14, ch * 0.92 + 0.14,
boxstyle="square,pad=0.0", fc="none", ec=COL_AMBER_600,
linewidth=3.4, zorder=6))
acx, acy = cell_center(0, T)
ax.text(acx, acy + ch * 0.66, "CEVAP", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(acx, acy - ch * 0.66, "x(0, 6)", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=7)
for idx in range(len(path)):
i, t, dec, ai = path[idx]
c_from = path_cells[idx]
c_to = path_cells[idx + 1]
x0c, y0c = cell_center(*c_from)
x1c, y1c = cell_center(*c_to)
put = (dec == "PUT")
col = COL_AMBER_600 if put else COL_SLATE_500
lw = 3.0 if put else 1.6
rad = -0.32 if put else 0.32
ax.add_patch(FancyArrowPatch(
(x0c, y0c - ch * 0.42), (x1c, y1c + ch * 0.42),
arrowstyle="-|>", mutation_scale=16, color=col, linewidth=lw,
zorder=8, shrinkA=2, shrinkB=2,
connectionstyle="arc3,rad=%s" % rad))
mx, my = (x0c + x1c) * 0.5, (y0c + y1c) * 0.5
if put:
txt = "koy a%d=%d\n(t: %d→%d)" % (i, ai, t, t - ai)
else:
txt = "koyma a%d=%d" % (i, ai)
off = -0.95 if put else 0.95
ax.text(mx + off, my, txt, ha=("right" if put else "left"), va="center",
fontsize=7.6, color=col, weight=("bold" if put else "normal"),
zorder=9)
rec_x = x_lab + n_cols * cw + 0.55
rec_y = y_top - 1.2
ax.add_patch(FancyBboxPatch(
(rec_x, rec_y - 1.35), 4.7, 2.35,
boxstyle="round,pad=0.10,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=4))
ax.text(rec_x + 2.35, rec_y + 0.72, "Yineleme (OR)", ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=5)
ax.text(rec_x + 2.35, rec_y + 0.14, "x(i, t) = x(i+1, t)", ha="center",
va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(rec_x + 2.35, rec_y - 0.30, "OR x(i+1, t − aᵢ) [aᵢ ≤ t]",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(rec_x + 2.35, rec_y - 0.95, "karar problemi → min/max DEĞİL, OR",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=5)
leg_y = rec_y - 2.05
ax.add_patch(FancyArrowPatch((rec_x + 0.15, leg_y), (rec_x + 0.95, leg_y),
arrowstyle="-|>", mutation_scale=14, color=COL_AMBER_600,
linewidth=3.0, zorder=5))
ax.text(rec_x + 1.05, leg_y, "koy (aᵢ alt kümede)", ha="left", va="center",
fontsize=8.4, color=COL_AMBER_700, zorder=5)
ax.add_patch(FancyArrowPatch((rec_x + 0.15, leg_y - 0.48),
(rec_x + 0.95, leg_y - 0.48),
arrowstyle="-|>", mutation_scale=14, color=COL_SLATE_500,
linewidth=1.6, zorder=5))
ax.text(rec_x + 1.05, leg_y - 0.48, "koyma (aᵢ atlanır)", ha="left", va="center",
fontsize=8.4, color=COL_SLATE_500, zorder=5)
ax.add_patch(FancyBboxPatch((rec_x + 0.30, leg_y - 1.15), 0.5, 0.5,
boxstyle="square,pad=0.0", fc=COL_WHITE, ec=COL_SLATE_400,
linewidth=0.9, linestyle=(0, (2, 2)), alpha=0.55, zorder=5))
ax.text(rec_x + 1.05, leg_y - 0.90, "soluk hücre = hiç sorulmadı",
ha="left", va="center", fontsize=8.4, color=COL_SLATE_500, zorder=5)
ax.text(rec_x + 1.05, leg_y - 1.22, "(memoization yalnız gerekeni çözer)",
ha="left", va="center", fontsize=7.6, color=COL_SLATE_400,
style="italic", zorder=5)
badge_y = y_top - n_rows * ch - 0.55
ax.add_patch(FancyBboxPatch(
(x_lab, badge_y - 0.34), n_cols * cw, 0.62,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(x_lab + n_cols * cw * 0.5, badge_y - 0.03,
"n·T = %d·%d = %d alt problem × O(1) = O(n·T) pseudopolinom"
% (n, T, n * T),
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(x_lab + n_cols * cw * 0.5, y_top + ch * 1.95,
"Subset Sum — x(i, t) memoization tablosu (A = {3, 4, 3, 1}, T = 6)",
ha="center", va="center", fontsize=13, color=COL_TEXT, weight="bold")
ax.set_xlim(-0.2, rec_x + 4.9)
ax.set_ylim(badge_y - 0.9, y_top + ch * 2.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 6. Subset Sum Polinom Değil: Pseudopolinom {#sec-6-subset-sum-polinom-degil}
$O(n \cdot T)$ **polinom değildir**. Girdi boyutu $= n + 1$ kelime, ama süre hem $n$'e hem $T$'ye bağlı. $T$ bir kelimeye sığar ($w$ bit) $\to T \le 2^w$. Word-RAM'de $w \ge \log n$ garantilidir ama **$w$'nin üst sınırı yoktur** — $w = n$ bile makul ($n$ sayı, her biri $n$-bit). O zaman $T = 2^n \to n \cdot T = n \cdot 2^n$ **üstel**.
Yine de "yeterince iyi": **pseudopolinom**.
## 7. Pseudopolinom Tanımı ve Hiyerarşi {#sec-7-pseudopolinom-tanimi-hiyerarsi}
**Pseudopolinom zaman:** girdi *boyutuna* **ve** girdi *sayılarına* polinom (sabit dereceli). $O(n \cdot T)$ böyledir: $n \cdot T = $ boyut $\times T$, sabit derece. Pseudopoli ama poli değil.
Önemli özel durum: girdi sayıları boyutun **polinomu** ise (örn. $T \le \text{poly}(n)$) $\to$ pseudopoli **polinoma** iner. Bu, **radix sort'un doğrusal çalışma koşuluyla aynıdır**.
> *"this is the condition when radix sort runs in linear time."* — Demaine, 50:50
Hiyerarşi (iyiden kötüye): **strongly polynomial** (girdi sayılarından bağımsız) $\to$ **weakly polynomial** (sayıların **log**'una polinom — radix sort) $\to$ **pseudopolynomial** (sayıların **kendisine** polinom — subset sum). "log of an exponential is polynomial" olduğundan weakly poli neredeyse poli kadar iyidir.
> *"log of an exponential is polynomial."* — Demaine, 53:41
@fig-pseudo-hierarchy bu üç kademeyi hem merdiven şemasıyla hem de büyüme grafiğiyle gösterir: $n = 20$, $T = 2^{20}$ için strongly ($n^2 = 400$), weakly ($n \cdot \log_2 T = 400$) ve pseudo ($n \cdot T \approx 2{,}1 \times 10^7$) — pseudo, weakly/strongly'den $\sim 52$ bin kat büyük. Sağ panel $w$ (bit) arttıkça pseudo'nun $n \cdot 2^w$ üstel patlamasını ($T \le 2^w$, $w$'nin üst sınırı yok $\to T = 2^n$), strongly'nin sabit ve weakly'nin doğrusal kaldığını çizer; radix koşulu ($T \le \text{poly}(n)$) rozetiyle.
```{python}
#| label: fig-pseudo-hierarchy
#| fig-cap: "Polinom hiyerarşisi: sayılar nasıl ölçülür? — strongly · weakly · pseudo (Demaine L18 §7 İMZA, 53:41 + 50:50). SOL panel üç-kademe merdiven (sayılara bağımlılık artar ↑): (1) STRONGLY polynomial — sayıların DEĞERİNDEN bağımsız, yalnız girdi kelime sayısının polinomu; merge sort · BFS · rod cutting O(L²); n² = 400. (2) WEAKLY polynomial — sayıların LOG'una (bit uzunluğu w) doğrusal; radix sort · ağırlıklı Dijkstra; n·log₂T = 20·20 = 400; yan not 'log of an exponential is polynomial, log(2ⁿ)=n' (Demaine 53:41). (3) PSEUDOpolynomial — sayıların KENDİSİNE doğrusal → bit uzunluğuna ÜSTEL; subset sum O(n·T) · knapsack; n·T = 20·1.048.576 = 20.971.520. SAĞ panel T büyüdükçe süre (log-y), x = w (bit) 8..24: strongly n² sabit, weakly n·w doğrusal, pseudo n·2ʷ ÜSTEL patlama (amber); 'T ≤ 2ʷ, w üst sınırı YOK → T = 2ⁿ → n·2ⁿ üstel' kutusu + alt rozet 'T ≤ poly(n) ise pseudo → gerçek polinom (radix koşulu, Demaine 50:50)'. Veri FORMÜLDEN (assert): n=20, T=2²⁰=1.048.576; strongly=400, weakly=400, pseudo=20.971.520; pseudo/weakly=52428.8; her w için pseudo=n·2ʷ üstel."
#| fig-width: 12.0
#| fig-height: 5.8
# fig-pseudo-hierarchy (L18 §7 İMZA): polinom hiyerarşisi. Veri FORMÜLDEN.
n_h = 20
w_ref = 20
T_h = 2 ** w_ref
log2T = int(math.log2(T_h))
strongly = n_h ** 2
weakly = n_h * log2T
pseudo = n_h * T_h
ratio = pseudo / weakly
assert T_h == 1048576 and log2T == 20
assert strongly == 400 and weakly == 400 and pseudo == 20971520
assert abs(ratio - 52428.8) < 1e-6
ws = list(range(8, 25, 2))
strong_curve = [n_h ** 2 for _ in ws]
weak_curve = [n_h * w for w in ws]
pseudo_curve = [n_h * (2 ** w) for w in ws]
for w, sc, wc, pc in zip(ws, strong_curve, weak_curve, pseudo_curve):
assert sc == 400 and wc == n_h * w and pc == n_h * (2 ** w)
assert pseudo_curve == sorted(pseudo_curve)
def _fmt_int(x):
return f"{x:,}".replace(",", ".")
fig, (axL, axR) = plt.subplots(1, 2, figsize=(12.0, 5.8))
fig.patch.set_facecolor(COL_WHITE)
# ---- SOL: üç-kademe merdiven ----
steps = [
("STRONGLY polynomial",
"sayıların DEĞERİNDEN bağımsız\n(yalnız girdi kelime sayısının polinomu)",
"merge sort · BFS · rod cutting O(L²)",
f"n² = {strongly}", COL_BG, COL_PRIMARY, False),
("WEAKLY polynomial",
"sayıların LOG'una (bit uzunluğu w)\ndoğrusal → bit cinsinden polinom",
"radix sort · ağırlıklı Dijkstra",
f"n·log₂T = {n_h}·{log2T} = {weakly}", COL_AMBER_100, COL_AMBER_600, False),
("PSEUDOpolynomial",
"sayıların KENDİSİNE (değerine) doğrusal\n→ bit uzunluğuna ÜSTEL",
"subset sum O(n·T) · knapsack",
f"n·T = {n_h}·{_fmt_int(T_h)} = {_fmt_int(pseudo)}",
COL_AMBER_300, COL_AMBER_700, True),
]
step_w, step_h = 6.6, 1.62
x_shift = 0.55
y_gap = 1.92
for k, (title, measure, algo, value, fc, ec, hot) in enumerate(steps):
x0 = k * x_shift
y0 = k * y_gap
lw = 2.6 if hot else 1.8
axL.add_patch(FancyBboxPatch(
(x0, y0), step_w, step_h,
boxstyle="round,pad=0.04,rounding_size=0.14",
fc=fc, ec=ec, linewidth=lw, zorder=3))
axL.text(x0 + 0.30, y0 + step_h - 0.34, title, ha="left", va="center",
fontsize=12, color=COL_TEXT, weight="bold", zorder=5)
axL.text(x0 + 0.30, y0 + step_h - 0.92, measure, ha="left", va="center",
fontsize=8.3, color=COL_SLATE_500, zorder=5)
axL.text(x0 + 0.30, y0 + 0.30, value, ha="left", va="center",
fontsize=9.5, color=(COL_AMBER_700 if hot else COL_TEXT),
weight="bold", zorder=5)
axL.text(x0 + step_w - 0.22, y0 + step_h - 0.34, algo,
ha="right", va="center", fontsize=8.0,
color=(COL_AMBER_700 if hot else COL_PRIMARY),
style="italic", weight="bold", zorder=5,
bbox=dict(boxstyle="round,pad=0.22", fc=COL_WHITE,
ec=(COL_ACCENT if hot else COL_SLATE_400), linewidth=1.2))
if k < len(steps) - 1:
axL.add_patch(FancyArrowPatch(
(x0 + 0.55, y0 + step_h + 0.02),
(x0 + x_shift + 0.55, y0 + y_gap - 0.02),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.0, zorder=4, connectionstyle="arc3,rad=0.0"))
note_x = x_shift + step_w + 0.25
note_y = y_gap + step_h * 0.5
axL.text(note_x, note_y, "log of an exponential\nis polynomial\nlog(2ⁿ) = n",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
weight="bold", zorder=6,
bbox=dict(boxstyle="round,pad=0.32", fc=COL_AMBER_100,
ec=COL_AMBER_600, linewidth=1.4))
axL.text(note_x + 0.06, note_y - 0.95, "Demaine 53:41", ha="left",
va="center", fontsize=7.2, color=COL_SLATE_500, style="italic", zorder=6)
axL.annotate("", xy=(-0.55, 2 * y_gap + step_h - 0.2), xytext=(-0.55, 0.2),
arrowprops=dict(arrowstyle="-|>", color=COL_SLATE_500, linewidth=1.6))
axL.text(-0.78, y_gap + step_h * 0.5, "sayılara bağımlılık artar",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
rotation=90, style="italic")
axL.set_xlim(-1.25, x_shift + step_w + 3.05)
axL.set_ylim(-0.5, 2 * y_gap + step_h + 0.65)
axL.set_title("Üç kademe — bir algoritma 'polinom' ne demek?",
color=COL_TEXT, fontsize=12.5, weight="bold", pad=12)
axL.axis("off")
# ---- SAĞ: T büyüdükçe süre (log-y) ----
apply_style(axR)
axR.semilogy(ws, strong_curve, color=COL_PRIMARY, linewidth=2.2,
marker="o", markersize=4, zorder=4,
label="strongly n² (sabit, sayıdan bağımsız)")
axR.semilogy(ws, weak_curve, color=COL_AMBER_600, linewidth=2.2,
marker="s", markersize=4, zorder=4,
label="weakly n·w (doğrusal, log T)")
axR.semilogy(ws, pseudo_curve, color=COL_ACCENT, linewidth=2.8,
marker="^", markersize=5, zorder=5,
label="pseudo n·2ʷ (ÜSTEL patlama)")
axR.axvline(w_ref, color=COL_SLATE_400, linewidth=1.2, linestyle="--", zorder=2)
axR.text(w_ref, pseudo_curve[-1] * 0.4, f" w={w_ref}\n T=2²⁰", ha="left",
va="top", fontsize=8, color=COL_SLATE_500, zorder=6)
axR.annotate("n·2ʷ → 2ⁿ üstel",
xy=(ws[-1], pseudo_curve[-1]),
xytext=(ws[-1] - 6.5, pseudo_curve[-1] * 2.2),
fontsize=9, color=COL_AMBER_700, weight="bold",
arrowprops=dict(arrowstyle="-|>", color=COL_AMBER_700, linewidth=1.6),
zorder=7)
axR.set_xlabel("w = kelime biti (sayının bit uzunluğu) · T ≤ 2ʷ")
axR.set_ylabel("işlem sayısı (log ölçek)")
axR.set_title("T büyüdükçe: pseudo patlar, weakly/strongly sakin",
color=COL_TEXT, fontsize=12.5, weight="bold", pad=12)
axR.set_xticks(ws)
axR.legend(loc="upper left", fontsize=8.5, framealpha=0.92)
axR.text(0.975, 0.20,
"T ≤ 2ʷ · w'nin üst sınırı YOK\n→ T = 2ⁿ olabilir\n→ n·T = n·2ⁿ üstel",
transform=axR.transAxes, ha="right", va="bottom",
fontsize=8.7, color=COL_AMBER_700, weight="bold", zorder=8,
bbox=dict(boxstyle="round,pad=0.34", fc=COL_AMBER_100,
ec=COL_AMBER_600, linewidth=1.4))
axR.text(0.5, -0.205,
"T ≤ poly(n) ise pseudo → gerçek polinom (radix koşulu, Demaine 50:50)",
transform=axR.transAxes, ha="center", va="top",
fontsize=8.6, color=COL_PRIMARY, weight="bold", zorder=8,
bbox=dict(boxstyle="round,pad=0.3", fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.3))
fig.suptitle(
"Polinom hiyerarşisi: sayılar nasıl ölçülür? — strongly · weakly · pseudo",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.995)
plt.tight_layout(rect=(0, 0, 1, 0.96))
plt.show()
```
## 8. DP Karakterizasyonu: Alt Problem Tipleri {#sec-8-dp-karakterizasyonu-alt-problem-tipleri}
Dört dersteki tüm DP'ler, **alt problem tipine** göre:
- **Prefix/Suffix:** bowling, LCS (iki sonek), LIS.
- **Substring:** değişen para oyunu (iki uçtan), parantezleme (ortadan).
- **Tamsayı:** Fibonacci, rod cutting, subset sum (+ Floyd-Warshall, vertex-prefix olarak).
- **Vertex:** DAG SP, Bellman-Ford, Floyd-Warshall (en kısa yol DP'leri).
Pseudopoli olanlar: **rod cutting** (aslında poli), **subset sum** (pseudopoli) — tamsayı alt problemli olanlar.
## 9. DP Karakterizasyonu: Constraint / Branching / Combination {#sec-9-dp-karakterizasyonu-constraint-branching-combination}
- **Constraint/expansion:** non-expansive (LIS: kısıt ekledi ama alt problem sayısı sabit); expansive (para oyunu $\times 2$, parmaklama $\times F$, Bellman-Ford $\times V$).
- **Branching (özyineleme-dışı iş):** sabit (Fibonacci, bowling, LCS, para oyunu, Floyd-Warshall, subset sum); derece-bazlı (DAG SP, Bellman-Ford $\to E$ terimi); doğrusal (LIS, parantezleme, rod cutting).
- **Combination:** tek-en-iyi (çoğu $\to$ DAG en kısa yol); çoklu-birleştirme (Fibonacci toplar, Floyd-Warshall yol birleştirir, parantezleme iki parçayı çarpar/toplar).
- **Original problem:** tek alt problem (çoğu) vs çoklu (DAG SP, LIS, Bellman-Ford, Floyd-Warshall'da hepsinin min/max'ı).
@fig-dp-taxonomy bu iki bölümün ($\S 8$ alt problem + $\S 9$ constraint/branching/combination) **diagonal** toparlanmasını tek tabloda dizer: $11$ DP örneği satır, dört sınıflama ekseni sütun. Pseudopoli satırlar (rod cutting, subset sum) amber vurgulu; alt şerit dört dersin kademeli tanıtımını (DP1 = Ders 23 $\to$ DP4 = Ders 27) gösterir.
```{python}
#| label: fig-dp-taxonomy
#| fig-cap: "DP taksonomisi: dört dersin diagonal toparlanması — her örnek alt problem × constraint × branching × combination ekseninde (Demaine L18 §8-9 İMZA, 1:03:02). 11 DP örneği satır; 4 sınıflama sütunu. Alt problem tipi renk kodlu (prefix/suffix · substring · tamsayı amber · vertex yeşil); constraint (non-exp vs expansive ×k amber); branching (sabit · derece · doğrusal); combination (tek-en-iyi · çoklu amber). Pseudopoli satırlar AMBER vurgu: rod cutting (GERÇEK poli O(L²), girdi L+1 kelime) ve subset sum (PSEUDO poli O(n·T), T=2ⁿ olabilir) — ikisi de tamsayı. Ders rozetleri DP1=Ders 23, DP2=Ders 24, DP3=Ders 26, DP4=Ders 27 (araya Ders 25 = PS8). Alt şerit: dört ders KADEMELİ tanıttı — DP1 temel → DP2 çoklu+kısıt → DP3 expansion → DP4 tamsayı+pseudo (Demaine 1:03:02). Veri L18 §8-9 BİREBİR (assert): 11 örnek; pseudopoli = {rod cutting, subset sum}; expansive = {para oyunu, parantezleme, Floyd-Warshall, Bellman-Ford}; çoklu-birleştirme = {Fibonacci, Floyd-Warshall, parantezleme}; derece = {DAG SP, Bellman-Ford}."
#| fig-width: 12.5
#| fig-height: 6.5
# fig-dp-taxonomy (L18 §8-9 İMZA): dört dersin diagonal toparlanması.
# Veri L18 §8-9 BİREBİR (kavramsal — kendi-doğrulamalı assert).
EXAMPLES = [
# name, subprob, cons, branch, combo, pseudo, lesson
("Fibonacci", "tamsayı", "non-exp", "sabit", "çoklu", False, "DP1"),
("bowling", "prefix/suffix", "non-exp", "sabit", "tek-en-iyi", False, "DP1"),
("LCS", "prefix/suffix", "non-exp", "sabit", "tek-en-iyi", False, "DP2"),
("LIS", "prefix/suffix", "non-exp", "doğrusal", "tek-en-iyi", False, "DP2"),
("para oyunu", "substring", "×2", "sabit", "tek-en-iyi", False, "DP2"),
("parantezleme", "substring", "×F", "doğrusal", "çoklu", False, "DP3"),
("Floyd-Warshall", "vertex", "×V", "sabit", "çoklu", False, "DP3"),
("DAG SP", "vertex", "non-exp", "derece (E)", "tek-en-iyi", False, "DP3"),
("Bellman-Ford", "vertex", "×V", "derece (E)", "tek-en-iyi", False, "DP3"),
("rod cutting", "tamsayı", "non-exp", "doğrusal", "tek-en-iyi", True, "DP4"),
("subset sum", "tamsayı", "non-exp", "sabit", "tek-en-iyi", True, "DP4"),
]
COLS = [
("alt problem tipi", "prefix/suffix · substring · tamsayı · vertex"),
("constraint", "non-exp · expansive ×k"),
("branching", "sabit · derece · doğrusal"),
("combination", "tek-en-iyi · çoklu"),
]
_SUBPROB_STYLE = {
"prefix/suffix": (COL_BG, COL_PRIMARY, COL_TEXT),
"substring": ("#e6edf5", COL_SLATE_500, COL_TEXT),
"tamsayı": (COL_AMBER_100, COL_AMBER_600, COL_AMBER_700),
"vertex": ("#dfe7e3", "#3f7d5e", "#2f5d46"),
}
_LESSON_STYLE = {
"DP1": (COL_BG, COL_SLATE_500),
"DP2": (COL_AMBER_100, COL_AMBER_600),
"DP3": (COL_AMBER_300, COL_AMBER_700),
"DP4": (COL_ACCENT, COL_AMBER_700),
}
# iç tutarlılık ASSERT (L18 §8-9 birebir, kendi-doğrulamalı)
_pseudo_set = {nm for (nm, *r) in EXAMPLES if r[4]}
assert _pseudo_set == {"rod cutting", "subset sum"}, _pseudo_set
_exp_set = {nm for (nm, sp, cons, *r) in EXAMPLES if cons != "non-exp"}
assert _exp_set == {"para oyunu", "parantezleme", "Floyd-Warshall", "Bellman-Ford"}, _exp_set
_multi = {nm for (nm, sp, c, b, cb, *r) in EXAMPLES if cb == "çoklu"}
assert _multi == {"Fibonacci", "Floyd-Warshall", "parantezleme"}, _multi
_deg = {nm for (nm, sp, c, b, *r) in EXAMPLES if b == "derece (E)"}
assert _deg == {"DAG SP", "Bellman-Ford"}, _deg
assert len(EXAMPLES) == 11
def _cell_pill(ax, cx, cy, w, h, text, fc, ec, tc, lw=1.4, fs=8.6, bold=True):
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, cy - h * 0.5), w, h,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=fc, ec=ec, linewidth=lw, zorder=4))
ax.text(cx, cy, text, ha="center", va="center", fontsize=fs,
color=tc, weight="bold" if bold else "normal", zorder=5)
fig, ax = plt.subplots(figsize=(12.5, 6.5))
fig.patch.set_facecolor(COL_WHITE)
n_rows_t = len(EXAMPLES)
label_x = 0.30
badge_x = 3.05
col_x = [4.60, 6.95, 9.10, 11.30]
col_w = [2.05, 1.95, 1.95, 1.95]
top_y = 0.0
row_h = 0.74
row_gap = 0.80
row_y = [top_y - (r + 1) * row_gap for r in range(n_rows_t)]
pill_h = 0.50
ax.text(label_x, top_y, "DP örneği", ha="left", va="center",
fontsize=10, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(badge_x, top_y, "ders", ha="center", va="center",
fontsize=10, color=COL_SLATE_500, weight="bold", zorder=6)
for c, (title, sub) in enumerate(COLS):
ax.text(col_x[c], top_y + 0.14, title, ha="center", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(col_x[c], top_y - 0.20, sub, ha="center", va="center",
fontsize=6.6, color=COL_SLATE_500, style="italic", zorder=6)
ax.plot([label_x - 0.10, col_x[-1] + col_w[-1] * 0.5 + 0.05],
[top_y - 0.42, top_y - 0.42], color=COL_SLATE_400, linewidth=1.2, zorder=3)
pano_l = label_x - 0.12
pano_r = col_x[-1] + col_w[-1] * 0.5 + 0.10
for r, (name, sp, cons, br, cb, ps, ls) in enumerate(EXAMPLES):
y = row_y[r]
if ps:
bfc, bec, blw = COL_AMBER_100, COL_ACCENT, 2.2
else:
bfc, bec, blw = (COL_WHITE if r % 2 == 0 else "#f7f8fa"), COL_SLATE_400, 0.8
ax.add_patch(FancyBboxPatch(
(pano_l, y - row_h * 0.5), pano_r - pano_l, row_h,
boxstyle="round,pad=0.0,rounding_size=0.04",
fc=bfc, ec=bec, linewidth=blw, zorder=2, alpha=0.95))
name_col = COL_AMBER_700 if ps else COL_TEXT
ax.text(label_x, y, name, ha="left", va="center", fontsize=10.2,
color=name_col, weight="bold", zorder=5)
if ps:
tag = "GERÇEK poli O(L²)" if name == "rod cutting" else "PSEUDO poli O(n·T)"
ax.text(label_x, y - row_h * 0.42, tag, ha="left", va="center",
fontsize=6.4, color=COL_AMBER_600, style="italic", zorder=5)
lfc, lec = _LESSON_STYLE[ls]
ltc = COL_WHITE if ls == "DP4" else lec
_cell_pill(ax, badge_x, y, 0.92, pill_h, ls, lfc, lec, ltc, lw=1.6, fs=8.8)
sfc, sec, stc = _SUBPROB_STYLE[sp]
_cell_pill(ax, col_x[0], y, col_w[0], pill_h, sp, sfc, sec, stc, lw=1.5)
if cons == "non-exp":
cfc, cec, ctc = COL_WHITE, COL_SLATE_400, COL_SLATE_500
ctxt = "non-exp"
else:
cfc, cec, ctc = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700
ctxt = f"expansive {cons}"
_cell_pill(ax, col_x[1], y, col_w[1], pill_h, ctxt, cfc, cec, ctc, lw=1.4)
if br == "sabit":
bfc2, bec2, btc2 = COL_WHITE, COL_SLATE_400, COL_SLATE_500
elif br == "doğrusal":
bfc2, bec2, btc2 = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700
else:
bfc2, bec2, btc2 = "#dfe7e3", "#3f7d5e", "#2f5d46"
_cell_pill(ax, col_x[2], y, col_w[2], pill_h, br, bfc2, bec2, btc2, lw=1.4)
if cb == "çoklu":
cbfc, cbec, cbtc = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700
cbtxt = "çoklu-birleştirme"
else:
cbfc, cbec, cbtc = COL_WHITE, COL_SLATE_400, COL_SLATE_500
cbtxt = "tek-en-iyi"
_cell_pill(ax, col_x[3], y, col_w[3], pill_h, cbtxt, cbfc, cbec, cbtc, lw=1.4)
strip_y = row_y[-1] - row_gap - 0.10
seg = [
("DP1", "Ders 23", "temel alt problem\n(Fibonacci, bowling)"),
("DP2", "Ders 24", "çoklu girdi + kısıt\n(LCS, LIS, para oyunu)"),
("DP3", "Ders 26", "subproblem expansion\n(parantezleme, Floyd-W.)"),
("DP4", "Ders 27", "tamsayı + pseudopolinom\n(rod cutting, subset sum)"),
]
seg_left = pano_l + 0.05
seg_right = pano_r - 0.05
seg_w = (seg_right - seg_left) / len(seg)
box_w = seg_w - 0.42
for i, (lab, ders, desc) in enumerate(seg):
cx = seg_left + seg_w * (i + 0.5)
lfc, lec = _LESSON_STYLE[lab]
ltc = COL_WHITE if lab == "DP4" else lec
ax.add_patch(FancyBboxPatch(
(cx - box_w * 0.5, strip_y - 0.40), box_w, 0.80,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=lfc, ec=lec, linewidth=1.8, zorder=3, alpha=0.92))
ax.text(cx, strip_y + 0.22, f"{lab} · {ders}", ha="center", va="center",
fontsize=9.2, color=ltc, weight="bold", zorder=5)
ax.text(cx, strip_y - 0.12, desc, ha="center", va="center",
fontsize=7.0, color=COL_TEXT if lab != "DP4" else COL_WHITE, zorder=5)
if i < len(seg) - 1:
ax.add_patch(FancyArrowPatch(
(cx + box_w * 0.5 + 0.02, strip_y),
(cx + seg_w - box_w * 0.5 - 0.02, strip_y),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700,
linewidth=2.0, zorder=4))
ax.text((seg_left + seg_right) * 0.5, strip_y - 0.62,
"dört DP dersi teknikleri KADEMELİ tanıttı — her ders bir öncekine "
"yeni bir araç ekledi (Demaine 1:03:02)",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=5)
fig.suptitle(
"DP taksonomisi: dört dersin diagonal toparlanması — her örnek alt problem × "
"constraint × branching × combination ekseninde",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.set_xlim(pano_l - 0.20, pano_r + 0.20)
ax.set_ylim(strip_y - 0.95, top_y + 0.45)
ax.axis("off")
plt.tight_layout(rect=(0, 0, 1, 0.965))
plt.show()
```
## 10. Dört Dersin Özeti {#sec-10-dort-dersin-ozeti}
Dört DP dersi, teknikleri **kademeli** tanıttı: basit alt problemler (DP1) $\to$ çoklu girdi + kısıt (DP2) $\to$ subproblem expansion (DP3) $\to$ tamsayı alt problem + pseudopolinom (DP4). Her ders bir önceki üzerine yeni bir araç ekledi — basit branching'ten karmaşık birleştirmeye.
> *"these four dp lectures were all about showing you these main techniques of dynamic programming."* — Demaine, 1:03:02
Özü: alt problemleri (sequence/integer/vertex) tanımla, kısıt/expansion ile state hatırla, "ne bilsem işim biterdi?" sorusunu yerel kaba kuvvetle dene, memoize et — DP çok güçlü bir tasarım çatısıdır. ( @fig-dp-taxonomy bu kademeli yolculuğu DP1 $\to$ DP4 alt şeridinde özetler.)
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d27}
1. **Tamsayı alt problem**: integer girdiyi $0 \ldots n$'ye böl (Fibonacci, rod cutting, subset sum).
2. **Rod cutting**: $x(\ell) = \max\{v(p) + x(\ell - p)\}$; $O(L^2)$, gerçek polinom (girdi $L + 1$ kelime).
3. **Subset sum**: karar problemi; $x(i, t) = \text{OR}(\text{koyma}, \text{koy})$; $O(n \cdot T)$.
4. **Karar problemi**: min/max yerine OR; "evet" kolay kanıt, "hayır" zor.
5. **Pseudopolinom**: girdi boyutu $\times$ sayılara polinom; $T = 2^n$ olabilir $\to$ poli değil.
6. **Hiyerarşi**: strongly $>$ weakly (log sayı, radix sort) $>$ pseudopoly (sayı, subset sum).
7. **DP karakterizasyonu**: alt problem (prefix/substring/integer/vertex) $\times$ constraint $\times$ branching $\times$ combination.
::: {.callout-important title="Tek Bir Cümle"}
DP'nin son aracı tamsayı alt problemdir: integer girdiyi küçük sürümlerine böleriz; rod cutting $O(L^2)$ gerçek polinom ama subset sum $O(n \cdot T)$ yalnız pseudopolinomdur ($T = 2^n$ olabilir) — yine de sayılar küçükse mükemmel, tıpkı radix sort gibi.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d27}
::: {.callout-note collapse="true" title="Soru 1: Subset sum bir «karar problemi» olduğu için recurrence'ı diğer DP'lerden nasıl farklı? Neden OR?"}
**Cevap:**
Çoğu DP **optimizasyon** problemidir (min/max) — recurrence'ın dışına min veya max koyarız. Subset sum ise **karar problemi**: çıktı tek bit (evet/hayır), bir değer değil. $a_i$'yi koyma ($x(i+1, t)$) ya da koy ($x(i+1, t - a_i)$) seçeneklerinden **herhangi biri** "evet" verirse cevap "evet"tir $\to$ birleştirici **OR** (Python'da `any`). Min/max sayıları, OR ise booleanları birleştirir. (Yine de yapı aynı: alt problemleri tanımla, yerel ikili seçimi kaba kuvvetle dene, memoize et.)
:::
::: {.callout-note collapse="true" title="Soru 2: O(L²) rod cutting «polinom» ama O(n·T) subset sum «polinom değil» — fark nedir?"}
**Cevap:**
Polinom zaman $=$ sürenin **girdi boyutuna** (kelime sayısı) polinom olması. Rod cutting girdisi $L + 1$ kelime; $O(L^2)$, $L$'ye polinom $\to$ **polinom**. Subset sum girdisi $n + 1$ kelime; süre $O(n \cdot T)$ hem $n$'e hem **$T$**'ye bağlı. $T$ bir kelimeye sığar ($w$ bit) $\to T \le 2^w$; $w$'nin üst sınırı yoktur ($w = n$ bile olabilir) $\to T = 2^n \to n \cdot T = n \cdot 2^n$ **üstel**. Yani $T$ girdi boyutuyla sınırlı değil; süre girdi boyutuna polinom **değil**. (Fark: $L$ hem girdi boyutu hem süre parametresi; $T$ yalnız bir girdi *sayısı*, boyut değil.)
:::
::: {.callout-note collapse="true" title="Soru 3: «Pseudopolinom» ne demek, ve ne zaman gerçek polinoma dönüşür?"}
**Cevap:**
Pseudopolinom $=$ sürenin girdi boyutuna **ve girdideki sayıların kendisine** polinom olması (sabit derece). $O(n \cdot T)$ böyledir: $n$ (boyut) $\times T$ (sayı). Gerçek polinom değildir çünkü $T$ üstel büyüyebilir. **Özel durum:** girdi sayıları boyutun polinomuysa ($T \le \text{poly}(n)$), pseudopolinom **polinoma** iner. Bu, radix sort'un doğrusal çalıştığı koşulla **aynıdır** (sayılar poli-sınırlı). Hiyerarşi: strongly poly (sayıdan bağımsız) $>$ weakly poly (sayının log'u, radix sort) $>$ pseudopoly (sayının kendisi, subset sum). "Sayılar küçükse hızlı" — pratikte çoğu zaman yeterince iyi.
:::
::: {.callout-note collapse="true" title="Soru 4: Dört DP dersi hangi teknikleri kademeli olarak tanıttı?"}
**Cevap:**
**DP1** (SRTBOT + memoization): temel çerçeve, basit alt problemler (Fibonacci, bowling), prefix/suffix/substring. **DP2:** çoklu girdi (alt problem çarpımı, LCS), alt problem kısıtı (LIS), oyunlarda min/max (para oyunu). **DP3:** subproblem expansion (Floyd-Warshall vertex-prefix, parantezleme min+max, parmaklama state). **DP4:** tamsayı alt problem + pseudopolinom (rod cutting, subset sum). Her ders bir öncekine yeni bir araç ekledi: basit branching'ten derece/doğrusal branching'e, tek-en-iyi birleştirmeden çoklu birleştirmeye. Sıra, DP'nin tüm ana tekniklerini metodik biçimde göstermek için seçildi.
:::
## Egzersizler {#sec-egzersizler-d27}
**Egzersiz 1.** Rod cutting'i $L = 7$, $[1, 10, 13, 18, 20, 31, 32]$ üzerinde $x(\ell)$ tablosuyla elle çöz; optimal bölünmeyi ($33$) bul.
**Egzersiz 2.** Subset sum'ı Python'da yaz ($x(i, t)$, OR recurrence); $A = \{3, 4, 3, 1\}$, $T = 6$ için tabloyu doldur ve ebeveyn izinden alt kümeyi çıkar.
**Egzersiz 3.** Subset sum'ın neden $O(n \cdot T)$ olduğunu ve $T = 2^n$ durumunda neden üstel olduğunu input-size argümanıyla açıkla.
**Egzersiz 4.** Counting sort ve direct-access-array'in de neden pseudopolinom olduğunu ($u$'ya bağımlılık) yaz; radix sort'un neden weakly polynomial olduğunu açıkla.
**Egzersiz 5.** Gördüğün her DP dersi örneğini (Fibonacci, bowling, LCS, LIS, para oyunu, parantezleme, Floyd-Warshall, rod cutting, subset sum) alt problem tipine (prefix/suffix/substring/integer/vertex) göre sınıfla.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d27}
::: {.callout-warning title="Sonraki: Ders 28 (L19) — Hesaplama Karmaşıklığı (P, NP, indirgemeler)"}
**Ders 28 (L19): Hesaplama Karmaşıklığı** (P, NP, indirgemeler). Erik Demaine ile, "hangi problemler verimli çözülebilir?" sorusuna geçiyoruz: **P** (polinom-zaman çözülebilir), **NP** (çözümü polinom-zamanda doğrulanabilir), **NP-tamlık** ve **indirgeme**. Subset sum'ın "evet kolay, hayır zor" gözlemi tam buraya bağlanır. (L19, Ders 30 = Quiz 3 Gözden Geçirme kapsamında değil; tanımlarını final sınavında kullanırsın.)
**Ders 28 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 2 (subset sum) ve 5 (DP sınıflama) çöz.
- Pseudopolinom hiyerarşisini (strongly/weakly/pseudo) ezberden anlat.
- Ana cümleyi tekrar oku: *"Sayılar küçükse pseudopolinom mükemmeldir; $T = 2^n$ olabileceğinden poli değildir."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d27}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Tamsayı alt problem** | Integer girdiyi $0 \ldots n$'ye böl (Fibonacci, rod, subset) | Böl. 1 |
| **Rod cutting** | $x(\ell) = \max\{v(p) + x(\ell - p)\}$; $O(L^2)$ | Böl. 2 |
| **Polinom zaman** | Süre girdi boyutuna (kelime) polinom | Böl. 3 |
| **Karar problemi** | Evet/hayır çıktı; recurrence'da OR | Böl. 4-5 |
| **Subset sum** | $x(i, t) = \text{OR}(\text{koyma}, \text{koy})$; $O(n \cdot T)$ | Böl. 5 |
| **Pseudopolinom** | Boyut $\times$ sayılara polinom; $T = 2^n$ olabilir | Böl. 6-7 |
| **Hiyerarşi** | strongly $>$ weakly (log) $>$ pseudo (sayı) | Böl. 7 |
| **DP karakterizasyonu** | alt problem $\times$ constraint $\times$ branching $\times$ combination | Böl. 8-9 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d27}
::: {.callout-tip title="6 köprü"}
Bu dersin iki örneği — tamsayı alt problemli rod cutting ve subset sum — ve pseudopolinom kavramı, sistem mühendisliği, kriptografi ve graduate algoritmalarındaki çok sayıda araca bağlanır; köprülerin özeti:
1. **Subset sum** $\to$ **knapsack**, bütçe-dağıtım, kaynak tahsisi; NP-tamlık (kriptografi — subset-sum tabanlı şifreleme tarihçesi).
2. **Karar problemi + sertifika** $\to$ **NP** tanımı; "evet kolay, hayır zor" $\to$ sonraki ders (P/NP). Certificate verifier (`verify_subset_certificate`) NP Tanım-2'nin ta kendisidir.
3. **Pseudopolinom** $\to$ "sayılar küçükse hızlı"; gerçek sistemde $T$ sınırlıysa pratik — kapasite/bütçe küçük tutulduğunda DP tablosu patlamaz.
4. **Pseudopoli $=$ radix sort koşulu** $\to$ sayı-sınırı bilinci; pseudopolinom'un poli-olma koşulu ($T \le \text{poly}(n)$), radix sort'un doğrusal koşuluyla **aynı** kavramdır — iki yerde **çift-kayıt** aynı fikrin.
5. **DP diagonal review** $\to$ tasarım deseni kütüphanesi; **OMSCS CS 6515**'in DP omurgası — alt problem $\times$ constraint $\times$ branching $\times$ combination ekseni graduate algoritmalarında tekrar tekrar karşına çıkar.
6. **Tamsayı alt problem** $\to$ çok boyutlu DP tabloları; bütçe/kapasite parametreleri bir koordinat olarak eklenir (state $=$ kapasite). **OMSCS pseudo-bilinç:** bir DP'nin pseudopolinom mu gerçek polinom mu olduğunu ayırt etmek — graduate seviyede "bu algoritma büyük girdide patlar mı?" refleksinin temelidir.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
DP'nin son aracı **tamsayı alt problemdir** — integer girdiyi küçük sürümlerine böl. Ama dikkat: rod cutting $O(L^2)$ gerçek polinomken, subset sum $O(n \cdot T)$ yalnız **pseudopolinom**dur, çünkü $T$ bir kelimeye sığsa da $2^n$ kadar büyük olabilir. Pseudopolinom "polinom değil ama yeterince iyi": sayılar küçükse (radix sort koşulu) gerçek polinoma iner. Karar problemlerinde min/max yerine **OR** kullanırsın. Dört DP dersi, basit alt problemlerden pseudopolinoma uzanan tüm tasarım tekniklerini kademeli öğretti — DP, "ne bilsem işim biterdi?" sorusunu yerel kaba kuvvetle çözen güçlü bir çatıdır.
:::
