---
title: "Quiz 3 Gözden Geçirme"
subtitle: "Dönemin son quiz tekrarı — SRTBOT derin tekrar ve üç gerçek sınav problemi (Lotto, DNA, Tapas)"
---
::: {.callout-note title="Oturum bilgisi"}
- **Ku'nun videosu:** [YouTube — Quiz 3 Review](https://www.youtube.com/watch?v=wEKFGdo4Sck) (≈84 dk)
- **OCW sayfası:** [MIT 6.006 Quiz 3 Review](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/quiz-3-review/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 30 (PS10 / Quiz 3 Review)
- **Hoca:** Jason Ku
- **Okuma süresi:** ≈26 dk
> Bu **normal bir ders değil** — Quiz 3 öncesi **toplu tekrar** oturumudur. Quiz 3 = **DP bloğu**; Quiz 1-2 konuları (veri yapıları, çizge) kümülatif "fair game"dir ama doğrudan test edilmez.
:::
## Bu Quiz Review Ne Hakkında? {#sec-bu-quiz-review-ne-hakkinda-d30}
Bu, Jason Ku ile dönemin **son quiz tekrarıdır**: Quiz 3, tamamen **dinamik programlama (DP)** üzerine. Ku önce **SRTBOT recursive framework**'ünü adım adım tekrar eder, sonra **Spring '18'den üç gerçek sınav/ödev problemini** (Lotto, DNA babalık testi, Tapas) baştan sona çözer. Dördüncü problem (Gokemon Po) zaman yetmediği için bırakıldı.
> *"This is our last quiz review for the term, quiz 3... It's on dynamic programming... problem sets 7 and 8, and lectures 15 through 18."* — Ku, 0:19
::: {.callout-warning title="Kapsam — kitap-numara remap"}
Ku, kapsamı orijinal MIT numaralandırmasıyla anar: "lectures 15 through 18 + problem sets 7 and 8". Bu kitaptaki karşılığı:
- **Ders 23-27 (L15-L18; araya Ders 25 = PS8 girer)** — DP temelleri (SRTBOT, LCS/LIS, Floyd-Warshall, pseudopolinom/subset sum).
- **DP problem oturumları Ders 25 (PS8) ve Ders 29 (PS9)** — Ku'nun andığı "PS 7-8", **orijinal MIT numaralandırmasıdır**.
Alıntılar birebir korunur (Ku "PS7-8" der); kapsam ifadeleri kitap-numaraya remap edilir.
:::
Bu sayfa beş eksende ilerler: (1) **SRTBOT çerçevesinin derin tekrarı**, (2) **üç gerçek problem** tam çözümle (toggle), (3) **quiz hazırlığı egzersizleri**, (4) **sınav stratejisi**, (5) **toplu cheat sheet**.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 30'un (Quiz 3 Review) kavram haritası: kök = Quiz 3 Review. Beş dal — (1) SRTBOT çerçevesi: Subproblem, Relation, Topological order, Base case, Original problem, Time; her özyinelemeli algoritmanın iskeleti, DP alt problemler örtüştüğünde memoize ile DAG'a çöker. (2) durum genişletme (Lotto): suffix DP, geçmişi gelecek kısıtı olarak hatırla, offset state, lineer zaman. (3) çoklu-dizi Boolean DP (DNA): üç dizi, bağımlı indeks elenir, dört seçimli OR, kuartik zaman. (4) pseudopolinom knapsack (Tapas): sıfır-bir knapsack artı tam-s tatlı sayacı, eksi sonsuz taban dengesi, k çıplak sayı olduğu için pseudopolinom. (5) sınav stratejisi: söz artı matematik, çarp toplama, polinom teşhisi, taban dengesi, parent pointer. Sonuç: Quiz 3 = SRTBOT disiplini sınavı."
flowchart TD
A["Ders 30: Quiz 3 Review"] --> B["SRTBOT çerçevesi<br/>S·R·T·B·O·T derin tekrar"]
A --> C["Durum genişletme (Lotto)"]
C --> C1["suffix DP · geçmişi gelecek<br/>kısıtı olarak hatırla · O(n)"]
A --> D["Çoklu-dizi Boolean DP (DNA)"]
D --> D1["üç dizi · bağımlı indeks elenir<br/>∨ 4 seçim · O(n⁴)"]
A --> E["Pseudopolinom knapsack (Tapas)"]
E --> E1["0/1 knapsack + tatlı sayacı<br/>−∞ taban · O(nks)"]
A --> F["Sınav stratejisi"]
F --> F1["söz + matematik · çarp ≠ topla<br/>polinom teşhisi · taban dengesi"]
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 B,C,D,E,F branch
class C1,D1,E1,F1 leaf
```
::: {.callout-tip title="Builder Notu — Bu = DP Midterm"}
Quiz 3, kursun **dinamik programlama sınavıdır**: alt problem tanımı, ilişki (recurrence), topolojik sıra, taban durum, çözüm kurma ve süre analizi. Veri yapıları Quiz 1'de, çizge algoritmaları Quiz 2'de kaldı; burada tek konu DP'dir.
- **Bu = üçüncü ve son sınav.** OMSCS CS 6515 (Graduate Algorithms) ekseninde DP, dersin **en ağır blokudur** — lisansüstü algoritma sınavlarının yarısı DP üzerinedir. Burada kurulan **SRTBOT disiplini** (önce alt problemi sözle tam tanımla, sonra recurrence'ı matematikle yaz) doğrudan oraya taşınır.
- **Durum genişletme refleksi.** Naif suffix DP kısıtı uygulayamadığında reflekste **state ekle** (Lotto: offset; Tapas: tatlı sayacı) — bu, "alt probleme bir soru sor" disiplininin en sık sınav uygulamasıdır.
- **Pseudopolinom teşhisi.** Runtime'da $k$ veya $W$ gibi **çıplak sayı** görünce "polinom mu?" sorusuna **pseudopolinom** demek; çözmeden, yalnız runtime'a bakarak yapılan bir teşhistir (subset sum / knapsack imzası).
Tek cümle: *Quiz 3, "bu problemi DP ile çöz" demez; "alt problemi sözle tam tanımla (tanımsız parametre = puan yok), recurrence'ı matematikle yaz, topolojik sırayı kanıtla, taban durumları (true + false dengesi) kur, runtime'ı girdi boyutuyla sınıflandır" der.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 30 (Quiz 3 Review, Ku) motoru INLINE.
# Kitap taşınabilir olsun diye _engine.py / _engine_QR3.py içinden GEREKEN
# her şey buraya GÖMÜLÜR (dosyadan import YOK). Aşağıdaki figür hücreleri bu
# hücrede tanımlanan globalleri (lotto, dna_match, tapas, build_*_example,
# is_subsequence, INF, ... + COL_*'ı) IMPORT ETMEDEN kullanır.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Quarto render'da jupyter
# inline backend'i ayarlar; yalnız QR3 gerekenler gömülür.
# ============================================================================
import matplotlib.pyplot as plt
from matplotlib.patches import (
Circle, FancyBboxPatch, FancyArrowPatch, Rectangle,
)
# ---------------------------------------------------------------------------
# _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"
# Figür-yerel ek tonlar (palet dışı tek vurgular)
COL_RED = "#b91c1c" # HAYIR / fizik-ihlali kırmızısı
COL_RED_BG = "#fee2e2"
COL_GOOD = "#cfe8da" # EVET / true taban yeşilimsi
COL_GOOD_EC = "#3f7d5e"
# ---------------------------------------------------------------------------
# _engine.py — D24 kara kutusu (LCS altyapısı). P2 tanığı is_subsequence.
# ---------------------------------------------------------------------------
INF = float("inf")
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)
# ---------------------------------------------------------------------------
# _engine_QR3.py — P1-P3 problem fonksiyonları + build_*_example (QR3 motoru).
# ---------------------------------------------------------------------------
# --- P1: Lotto — suffix DP + durum genişletme ---
def lotto(L):
"""QR3 P1 (Ku): ardışık HERHANGİ 7 günde en fazla 2 oyun; kazançlar
pozitif; max toplam. S: x(i, j) = 'gün i'de oynadım; bir önceki oyun
nedeniyle SONRAKİ oyun en erken i+j' (j ∈ 1..6). R: sonraki offset k'yı
kaba kuvvetle dene (k ≥ j; k ≤ 11): x(i, j) = L[i] + max({x(i+k,
max(1, 7−k))} ∪ {0}). T: i artar. B: son oyun → L[i]. O: max over i ∈
ilk 7 gün of x(i, 1). n×6 alt problem × O(11) = O(n) LİNEER.
Döndürür: (max kazanç, memo)."""
n = len(L)
if n == 0:
return 0, {}
memo = {}
def x(i, j):
if (i, j) in memo:
return memo[(i, j)]
best = L[i] # bu, son oyunum
for k in range(j, min(11, n - 1 - i) + 1):
cand = L[i] + x(i + k, max(1, 7 - k))
if cand > best:
best = cand
memo[(i, j)] = best
return best
ans = max(x(i, 1) for i in range(min(7, n)))
return ans, memo
def brute_lotto(L):
"""Bağımsız tanık (2ⁿ bitmask, DP'siz): her 7-günlük pencerede ≤ 2
seçim kısıtıyla max Σ. Üstel; küçük n."""
n = len(L)
best = 0
for mask in range(1 << n):
ok = all(bin(mask >> s & 0b1111111).count("1") <= 2
for s in range(max(1, n - 6)))
if ok:
best = max(best, sum(L[i] for i in range(n) if mask >> i & 1))
return best
def build_lotto_example():
"""QR3 P1 figür örneği: 12 gün, L = [4, 9, 2, 7, 3, 8, 1, 6, 9, 2, 5, 7]."""
return [4, 9, 2, 7, 3, 8, 1, 6, 9, 2, 5, 7]
# --- P2: DNA babalık — 3-string Boolean LCS ---
def dna_match(A, B, C):
"""QR3 P2 (Ku): C, eşit uzunlukta iki ayrık alt-dizilime bölünüp biri
A'nın, diğeri B'nin alt-dizilimi olabilir mi? S: x(i, j, kᵢ, kⱼ) =
A[i:]'den kᵢ + B[j:]'den kⱼ karakterle, C'nin son (kᵢ+kⱼ) karakteri
TAMAMEN eşleşir mi? — C konumu AYRI İNDEKS DEĞİL: |C| − (kᵢ+kⱼ)'den
türer. R (∨, 4 seçim): Aᵢ eşle / Bⱼ eşle / Aᵢ atla / Bⱼ atla.
T: i+j artar. B: x(n,n,0,0)=True; dizi bitti ama kota>0 → False.
O: x(0, 0, n/2, n/2). n⁴ alt problem × O(1) = O(n⁴). Döndürür: bool."""
n = len(C)
if n % 2 == 1:
return False
na, nb = len(A), len(B)
memo = {}
def x(i, j, ki, kj):
if (i, j, ki, kj) in memo:
return memo[(i, j, ki, kj)]
if ki == 0 and kj == 0:
r = True # C bitti — hepsi eşleşti
else:
c = C[n - (ki + kj)] # sıradaki C karakteri
r = False
if ki > 0 and i < na and A[i] == c:
r = x(i + 1, j, ki - 1, kj) # Aᵢ ile eşle
if not r and kj > 0 and j < nb and B[j] == c:
r = x(i, j + 1, ki, kj - 1) # Bⱼ ile eşle
if not r and i < na:
r = x(i + 1, j, ki, kj) # Aᵢ'yi atla
if not r and j < nb:
r = x(i, j + 1, ki, kj) # Bⱼ'yi atla
memo[(i, j, ki, kj)] = r
return r
return x(0, 0, n // 2, n // 2)
def brute_dna(A, B, C):
"""Bağımsız tanık (2ⁿ boyama, DP'siz): C karakterlerini A-grubu /
B-grubu boya (sıra korunur); |A-grubu| = |B-grubu| = n/2 ve iki grup
is_subsequence (D24 kara kutusu) ile A/B içinde mi?"""
n = len(C)
if n % 2 == 1:
return False
for mask in range(1 << n):
if bin(mask).count("1") != n // 2:
continue
ca = "".join(C[q] for q in range(n) if mask >> q & 1)
cb = "".join(C[q] for q in range(n) if not mask >> q & 1)
if is_subsequence(ca, A) and is_subsequence(cb, B):
return True
return False
def build_dna_example():
"""QR3 P2 figür örneği (n=6): A="CGTACG", B="TTAGCA", C="CGTTAG" → EVET;
ikinci (HAYIR) örnek C2="GGGGGG" (A'da 2 G + B'de 1 G < 3+3)."""
return "CGTACG", "TTAGCA", "CGTTAG", "GGGGGG"
# --- P3: Tapas — 0/1 knapsack + tatlı sayacı ---
def tapas(V, C, s_flags, k, s):
"""QR3 P3 (Ku): en fazla k kalori, TAM s tatlı, 0/1; hacmi maksimize
et. S: x(i, j, s′) = tabak i..n−1'den ≤ j kalori ve TAM s′ tatlıyla
max hacim. R (2 seçim): ye → Vᵢ + x(i+1, j−Cᵢ, s′−sᵢ) (Cᵢ ≤ j ∧
sᵢ ≤ s′); yeme → x(i+1, j, s′). T: i artar. B: x(n, j, 0) = 0;
x(n, j, s′≠0) = −∞ (kota tutmadı). O: x(0, k, s).
(n+1)(k+1)(s+1) × O(1) = O(nks). Döndürür: (max hacim | −∞, memo)."""
n = len(V)
memo = {}
def x(i, j, sp):
if (i, j, sp) in memo:
return memo[(i, j, sp)]
if i == n:
r = 0 if sp == 0 else -INF
else:
r = x(i + 1, j, sp) # yeme
if C[i] <= j and s_flags[i] <= sp: # ye
cand = V[i] + x(i + 1, j - C[i], sp - s_flags[i])
if cand > r:
r = cand
memo[(i, j, sp)] = r
return r
return x(0, k, s), memo
def brute_tapas(V, C, s_flags, k, s):
"""Bağımsız tanık (2ⁿ bitmask, DP'siz): ΣC ≤ k VE Σs == s alt
kümelerinde max ΣV; hiçbiri yoksa −∞."""
n = len(V)
best = -INF
for mask in range(1 << n):
idx = [m for m in range(n) if mask >> m & 1]
if sum(C[m] for m in idx) <= k and sum(s_flags[m] for m in idx) == s:
best = max(best, sum(V[m] for m in idx))
return best
def build_tapas_example():
"""QR3 P3 figür örneği: 5 tabak, k = 8, s = 2."""
return [6, 4, 7, 3, 5], [3, 2, 4, 1, 3], [0, 1, 0, 1, 1], 8, 2
```
## SRTBOT Çerçevesi — Derin Tekrar {#sec-srtbot-derin-tekrar}
DP, **özyinelemeli (recursive) çerçevenin** özel hâlidir: alt problemler **birden çok kez** kullanılınca, çakışan alt problemleri **bir kez** hesaplayıp memoize ederiz. Özyineleme ağacı, aynı-değerli düğümler birleşince bir **DAG**'a çöker; DP tam da alt problemlerin örtüştüğü durumdur.
**S — Subproblems (Alt problemler).** $x$ değişkeniyle alt problemleri tanımla: memonun **ne döndürdüğü** ve **ne kadar büyük** olduğu. **Kritik kural:** tanımında görünmeyen parametre kullanırsan yanlış yaparsın.
> *"if you have parameters in your subproblem that don't appear in your subproblem definition, you're doing it wrong."* — Ku (Subproblems)
Sıra (sequence) problemlerinde yaygın seçim: **prefix / suffix** (tek uçtan karar) veya **bitişik alt-dizi** (iki uçtan/ortadan karar). Bu sınıfta **suffix** kullanıyoruz (soldan-sağa okumak kolay); prefix ile birebir aynı — "aynı madalyonun iki yüzü". Çoklu girdide indeksleri **çarpar** (her diziden bir prefix/suffix) ve ek **durum** tutarız (max mı min mi? sıra kimde? çantada ne kadar yer kaldı?).
**R — Relate (Bağıntı).** Alt problemleri **matematiksel ifadeyle** ilişkilendir (kesinlik için söz değil, formül). Genelde $x(\dots) = \max / \min / \sum / \vee / \wedge$ (bir dizi seçim). Strateji: alt problem hakkında bir **soru** sor ("ilk karakterle ne yapayım?"); cevabı bilseydim daha küçük alt probleme inerdim → **polinom sayıda alt problem** olduğu için o sorunun tüm cevaplarını lokal **kaba kuvvetle** dene.
> *"it's really important that you write this in math, because it needs to be precise."* — Ku (Recursion)
**T — Topological order (Topolojik sıra).** "Daha küçük"ün ne demek olduğunu tanımla: bir indeks/parametre hep **artar veya azalır** (bazen indekslerin **toplamı**). Bağıntı acyclic ise alt problem grafı DAG'dır → bottom-up hesaplanır, sonsuz döngü olmaz.
**B — Base cases (Taban durumlar).** Özyinelemenin memo sınırının **dışına** taştığı her yer için sabit-zamanlı cevap. **Taban durum yoksa algoritma sonlu zamanlı bile değildir.**
> *"if you write code without a base case, it's going to be wrong."* — Ku (Base Cases)
**O — Original problem (Özgün problem).** Özgün cevabı alt problem(ler)den üret — çoğu zaman tek bir alt problem, bazen hepsinin max'ı (LIS, max subarray). Tam çözüm dizisini geri getirmek için **parent pointer** sakla (en kısa yoldaki gibi geri yürü).
**T — Time (Süre).** Genelde alt problem başına işin toplamı; iş her alt problemde aynı sınırlıysa **çarp**. Alt problem sayısı = her parametrenin değer sayısının **çarpımı** (toplamı DEĞİL — her biri bağımsız seçilir). İş/alt problem = bağıntıda üzerinde optimize edilen seçim sayısı (branching).
> *"I multiply those numbers together. A lot of people will maybe say, oh, I add them together. No."* — Ku (Running Time)
## Quiz-tarzı Problemler (Spring '18, Tam Çözüm) {#sec-quiz-problemleri-d30}
Aşağıda üç gerçek Spring '18 problemi var; her birinin çözümünü açmadan önce kendin dene. Üçü, SRTBOT'un üç farklı tekniğini sergiler: **durum genişletme** (Lotto), **çoklu-dizi Boolean DP** (DNA), **0/1 knapsack + sayaç** (Tapas). Tüm sayılar QR3 motoruyla doğrulanmıştır.
@fig-lotto-state Problem 1'in imza fikrini gösterir: suffix DP'de naif kısıt uygulanamayınca **durum genişletme** ile "geçmişi gelecek kısıtı olarak hatırla" — sonraki izinli oyun offset'i $j$ state'e eklenir, $k$ döngüsü sabit kalır ve algoritma **lineer** olur.
```{python}
#| label: fig-lotto-state
#| fig-cap: "Lotto — durum genişletme, suffix DP, O(n) lineer (QR3 Problem 1, İMZA figür, Spring-18). 12-gün kazanç şeridi L = [4,9,2,7,3,8,1,6,9,2,5,7]; ardışık HERHANGİ 7 günde en fazla 2 oyun (eşdeğer kısıt: ardışık üç oyun i<j<m için m − i ≥ 7). ÜST panel: optimal oyun günleri amber halka + ✓ (motordan brute-bitmask: günler 1,3,8,11 — kazançlar 9,7,9,7); örnek 7-gün penceresi amber bant, pencerede ≤ 2 oyun. ALT panel: durum x(i, j) = 'i'de oynadım; sonraki ≥ i+j' (j ∈ 1..6); geçiş x(i+k, max(1, 7−k)); k ≤ 11'e bakmak yeter (daha ilerisi asla optimal — arada pozitif gün oynanabilirdi). Motordan: lotto(L) = 32 == bitmask brute; memo 57 ≤ 6·12 = 72 (durum genişletme ×6 tanığı). n×6 alt problem × O(11) = O(n) LİNEER."
#| fig-width: 12.0
#| fig-height: 6.3
# fig-lotto-state (QR3 P1 İMZA): durum genişletme, motordan.
_l_L = build_lotto_example()
_l_n = len(_l_L)
_l_ans, _l_memo = lotto(_l_L)
assert _l_ans == 32, _l_ans
assert brute_lotto(_l_L) == 32
assert len(_l_memo) == 57 <= 6 * _l_n, (len(_l_memo), 6 * _l_n)
# Optimal oyun günlerini brute bitmask ile bul (argmax kümesi — uydurma yok)
_l_best, _l_days = -1, None
for _mask in range(1 << _l_n):
_ok = all(bin(_mask >> _s & 0b1111111).count("1") <= 2
for _s in range(max(1, _l_n - 6)))
if _ok:
_tot = sum(_l_L[i] for i in range(_l_n) if _mask >> i & 1)
if _tot > _l_best:
_l_best, _l_days = _tot, [i for i in range(_l_n) if _mask >> i & 1]
assert _l_best == 32 and _l_days == [1, 3, 8, 11], (_l_best, _l_days)
_days = set(_l_days)
_CW = 0.92
_WIN_START = 1
fig, (ax_top, ax_bot) = plt.subplots(
2, 1, figsize=(12.0, 6.3), gridspec_kw={"height_ratios": [1.0, 1.18]})
fig.patch.set_facecolor(COL_WHITE)
# ===== ÜST PANEL: 12-gün kazanç şeridi + optimal halka + 7-gün penceresi =====
y0 = 0.0
for k, v in enumerate(_l_L):
x = k * _CW
hot = k in _days
ax_top.add_patch(FancyBboxPatch(
(x, y0), _CW * 0.94, _CW * 0.94, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.6 if hot else 1.6, zorder=2))
cx, cy = x + _CW * 0.47, y0 + _CW * 0.47
ax_top.text(cx, cy, str(v), ha="center", va="center",
fontsize=13, color=COL_TEXT, weight="bold", zorder=4)
ax_top.text(cx, y0 - 0.22, str(k), ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, zorder=4)
if hot:
ax_top.add_patch(Circle((cx, cy + _CW * 0.95), _CW * 0.20,
facecolor=COL_ACCENT, edgecolor=COL_AMBER_700,
linewidth=1.8, zorder=5))
ax_top.text(cx, cy + _CW * 0.95, "✓", ha="center", va="center",
fontsize=9.5, color=COL_WHITE, weight="bold", zorder=6)
ax_top.text(-0.55, y0 + _CW * 0.47, "kazanç", ha="right", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=5)
win_lo = _WIN_START * _CW
win_hi = (_WIN_START + 7) * _CW
ax_top.add_patch(Rectangle(
(win_lo - _CW * 0.03, y0 - 0.05), 7 * _CW, _CW * 0.94 + 0.10,
facecolor=COL_AMBER_300, edgecolor=COL_AMBER_600,
linewidth=1.6, alpha=0.28, zorder=1))
_win_in = [k for k in range(_WIN_START, _WIN_START + 7) if k in _days]
ax_top.text((win_lo + win_hi) * 0.5 - _CW * 0.03, y0 + _CW * 1.55,
f"7-gün penceresi ({_WIN_START}…{_WIN_START + 6})\n"
f"pencerede {len(_win_in)} oyun ≤ 2 ✓",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=6,
bbox=dict(boxstyle="round,pad=0.3", fc=COL_WHITE,
ec=COL_AMBER_600, linewidth=1.4))
ax_top.text(_l_n * _CW + 0.30, y0 + _CW * 0.47,
f"optimal\nΣ = {_l_ans}", ha="left", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax_top.text(_l_n * _CW * 0.5, y0 - 0.78,
"ardışık üç oyun i < j < m : m − i ≥ 7 "
"(ardışık HERHANGİ 7 günde ≤ 2 oyun)",
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=5)
ax_top.set_xlim(-1.0, _l_n * _CW + 1.7)
ax_top.set_ylim(y0 - 1.15, y0 + _CW + 2.05)
ax_top.set_aspect("equal")
ax_top.axis("off")
ax_top.set_title("12-gün kazanç şeridi — optimal oyunlar amber halka, "
"örnek 7-gün penceresi amber bant",
color=COL_TEXT, fontsize=11.5, weight="bold", pad=6)
# ===== ALT PANEL: durum-genişletme şeması + geçiş okları =====
bx, by, bw, bh = 0.4, 2.55, 4.5, 1.25
ax_bot.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=2))
ax_bot.text(bx + bw * 0.5, by + bh * 0.70, "durum x(i, j)",
ha="center", va="center", fontsize=12.5, color=COL_TEXT,
weight="bold", zorder=4)
ax_bot.text(bx + bw * 0.5, by + bh * 0.30,
"“i'de oynadım; sonraki ≥ i + j” (j ∈ 1..6)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500, zorder=4)
nx_, ny_, nw, nh = 6.6, 2.55, 5.0, 1.25
ax_bot.add_patch(FancyBboxPatch(
(nx_, ny_), nw, nh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=2))
ax_bot.text(nx_ + nw * 0.5, ny_ + nh * 0.70, "x(i + k, max(1, 7 − k))",
ha="center", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=4)
ax_bot.text(nx_ + nw * 0.5, ny_ + nh * 0.30,
"k gün sonra oyna → yeni_j = max(1, 7 − k)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500, zorder=4)
ax_bot.add_patch(FancyArrowPatch(
(bx + bw + 0.02, by + bh * 0.5), (nx_ - 0.02, ny_ + nh * 0.5),
arrowstyle="-|>", mutation_scale=18, color=COL_ACCENT,
linewidth=2.4, zorder=3))
ax_bot.text((bx + bw + nx_) * 0.5, by + bh + 0.16, "k seç\n(k ≥ j)",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=4)
_ks = [1, 2, 3, 6, 11]
tbl_x, tbl_y, cw = 0.4, 1.05, 1.85
ax_bot.text(tbl_x, tbl_y + 0.55, "örnek geçişler:", ha="left", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", zorder=4)
for c, k in enumerate(_ks):
x = tbl_x + c * cw
new_j = max(1, 7 - k)
ax_bot.add_patch(FancyBboxPatch(
(x, tbl_y - 0.42), cw * 0.92, 0.78,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.3, zorder=2))
ax_bot.text(x + cw * 0.46, tbl_y + 0.14, f"k = {k}", ha="center",
va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
ax_bot.text(x + cw * 0.46, tbl_y - 0.22, f"yeni_j = {new_j}", ha="center",
va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=4)
ax_bot.text(0.4, 0.05,
"k ≤ 11'e bakmak yeter — daha ilerisi asla optimal "
"(arada pozitif gün oynanabilirdi) (Ku)",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5,
bbox=dict(boxstyle="round,pad=0.3", fc=COL_AMBER_100,
ec=COL_AMBER_600, linewidth=1.4))
ax_bot.text(11.55, 1.05, "geçmişi\nGELECEK KISITI\nolarak hatırla\n(Ku)",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5,
bbox=dict(boxstyle="round,pad=0.35", fc=COL_AMBER_100,
ec=COL_ACCENT, linewidth=1.8))
ax_bot.text(6.0, -0.85,
f"n×6 alt problem × O(11) geçiş = O(n) LİNEER · "
f"memo {len(_l_memo)} ≤ 6·{_l_n} = {6 * _l_n} tanığı",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold", zorder=5,
bbox=dict(boxstyle="round,pad=0.35", fc=COL_BG,
ec=COL_PRIMARY, linewidth=1.6))
ax_bot.set_xlim(-0.3, 13.0)
ax_bot.set_ylim(-1.5, 4.2)
ax_bot.set_aspect("equal")
ax_bot.axis("off")
ax_bot.set_title("Durum genişletme — “sonraki oyun en erken i + j” geçişiyle suffix DP",
color=COL_TEXT, fontsize=11.5, weight="bold", pad=4)
fig.suptitle(
"Lotto: durum genişletme — geçmişi gelecek kısıtı olarak hatırla (Ku, Spring-18 P1)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.995)
plt.tight_layout(rect=(0, 0, 1, 0.97))
plt.show()
```
::: {.callout-note collapse="true" title="Problem 1 — Lotto (Tiffany Bannen): suffix DP + durum genişletme, O(n) lineer"}
**İfade.** $n$ gün, gün $i$ kazancı $L(i)$ (pozitif tam sayı). **Ardışık herhangi 7 günde en fazla 2 kez** loto oyna. Toplam kazancı maksimize et. **Lineer zaman** istenir.
**Naif deneme.** $x(i) = i\dots n$ günlerinde max kazanç; R: oyna $L(i) + x(i+1)$ ya da oynama $x(i+1)$. Sorun: kazançlar pozitif → hep oyna; **7-gün kısıtı uygulanmıyor.**
**Düzeltme — durum genişletme.** Gün $i$'de **oynadığımı varsay** (LIS gibi) ve **bir sonraki izinli oyun** offset'i $j$'yi state'e ekle: $x(i, j) =$ "i'de oynadım, sonraki izinli oyun $i+j$" ($j \in 1..6$, çünkü asla $i+6$'dan ileri kısıtlanamam — daha eski oyunlar daha sağa itemez).
> *"I'm remembering what happened in the past by describing it as a restriction of something in the future."* — Ku
**Çözüm.** **S:** yukarıdaki $x(i, j)$. **R:** $x(i) = L(i) + \max_k\, x(i+k, \text{yeni\_j})$, $\text{yeni\_j} = \max(1, 7-k)$; $k =$ bir sonraki oynama günü offset'i. **T:** $i$ kesin artar (suffix). **B:** $x(n) = L(n)$ (son gün $L(n)$ kullanılır); $L(i)$'yi max dışına alıp $\cup\, \{0\}$ yazılırsa bağıntı tabana indirgenir. **O:** $\max_i x(i, 1)$ (ilk ~sabit).
**Karmaşıklık — anahtar.** $k$ döngüsü neden sabit? İki oyun "ortada" sıkışınca: 10 ara eleman → en fazla **11**'e kadar bak. Bundan ileri oynamak asla optimal değil (arada pozitif kazançlı bir gün oynanabilirdi). Yani $n$ alt problem $\times\, O(11) = $ **$O(n)$ lineer**.
**Kategori (Demaine L18):** suffix alt problem + lokal durum genişletme; sabit ama $> 2$ branching; özgün cevapta alt problemleri birleştirme. "Kavramsal olarak en kolay, implement etmesi en zor" tür.
::: {.callout-note title="İndeks köprüsü — Lotto prose vs kod"}
Prosede taban "son gün $L(n)$" diye $1$-tabanlı anlatılır; motorda (`lotto`) diziler $0$-tabanlıdır, dolayısıyla son gün indeksi $n-1$ ve $k$ döngüsü `range(j, min(11, n-1-i)+1)` ile sınırlanır. Aynı matematik (D25/D29 emsali): $1$-tabanlı sınav anlatımı ile $0$-tabanlı kod, $-1$ kaymasıyla birebir örtüşür; motor `lotto(L) = 32` değeri her iki okumayı da doğrular.
:::
:::
@fig-dna-boolean Problem 2'nin imza fikrini gösterir: üç dizi + C'nin tam bölünmesi; C'deki konum **ayrı bir indeks değildir** ($k_i + k_j$'den türer, bağımlı indeks elenir) ve karar dört seçimli bir **OR**'dur.
```{python}
#| label: fig-dna-boolean
#| fig-cap: "DNA babalık testi — 3-string Boolean DP, O(n⁴) kuartik (QR3 Problem 2, Spring-18). Üç n-uzunluklu DNA dizisi; C, eşit uzunlukta iki ayrık alt-dizilime bölünüp biri A'nın diğeri B'nin alt-dizilimi olabilir mi? ÜST panel (somut örnek n=6): C₁=CGTTAG → EVET, 3+3 bölünme (A-grubu CGT amber → A=CGTACG; B-grubu TAG slate → B=TTAGCA); ikinci örnek C₂=GGGGGG → HAYIR (A'da 2 + B'de 1 = 3 G < 6 gerekli). ALT panel (durum/recurrence): x(i, j, kᵢ, kⱼ); C konumu AYRI İNDEKS DEĞİL, |C| − (kᵢ+kⱼ)'den TÜRER → bağımlı indeks elenir; karar ∨ 4 seçim (Aᵢ eşle / Bⱼ eşle / Aᵢ atla / Bⱼ atla); taban dengesi: true taban x(n,n,0,0)=True VARSA false tabanlar da ŞART (dizi bitti ama kota>0 → False). Motordan: dna_match(A,B,C₁)=True == brute (2ⁿ boyama + is_subsequence D24); C₁ boyaması A→[0,1,2], B→[3,4,5]; tek-uzunluk → False. n⁴ alt problem × O(1) = O(n⁴)."
#| fig-width: 11.5
#| fig-height: 6.3
# fig-dna-boolean (QR3 P2): 3-string Boolean DP, motordan.
_A, _B, _C1, _C2 = build_dna_example()
assert (_A, _B, _C1, _C2) == ("CGTACG", "TTAGCA", "CGTTAG", "GGGGGG")
assert dna_match(_A, _B, _C1) is True and brute_dna(_A, _B, _C1) is True
assert dna_match(_A, _B, _C2) is False and brute_dna(_A, _B, _C2) is False
assert dna_match("CGTAC", "TTAGC", "CGTTA") is False # tek uzunluk → False
def _dna_valid_coloring(A, B, C):
"""C'nin geçerli 3+3 boyamasını brute-mantıkla bul (tanık, uydurma yok)."""
n = len(C)
for mask in range(1 << n):
if bin(mask).count("1") != n // 2:
continue
a_pos = [q for q in range(n) if mask >> q & 1]
b_pos = [q for q in range(n) if not mask >> q & 1]
if is_subsequence("".join(C[q] for q in a_pos), A) and \
is_subsequence("".join(C[q] for q in b_pos), B):
return a_pos, b_pos
return None, None
def _dna_earliest(group_chars, strip):
pos, it = [], 0
for ch in group_chars:
while strip[it] != ch:
it += 1
pos.append(it)
it += 1
return pos
_a_pos, _b_pos = _dna_valid_coloring(_A, _B, _C1)
assert _a_pos == [0, 1, 2] and _b_pos == [3, 4, 5], (_a_pos, _b_pos)
_a_chars = [_C1[q] for q in _a_pos]
_b_chars = [_C1[q] for q in _b_pos]
_a_map = _dna_earliest(_a_chars, _A)
_b_map = _dna_earliest(_b_chars, _B)
assert _a_map == [0, 1, 2] and _b_map == [0, 2, 3], (_a_map, _b_map)
_g_total = _A.count("G") + _B.count("G")
assert _g_total == 3 < 6, _g_total
def _dna_box(ax, x, y, w, h, ch, fc, ec, tc, lw=2.2, fs=15):
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=lw, zorder=4))
ax.text(x + w * 0.5, y + h * 0.5, ch, ha="center", va="center",
fontsize=fs, color=tc, weight="bold", zorder=5)
return x + w * 0.5, y + h * 0.5
fig, ax = plt.subplots(figsize=(11.5, 6.3))
fig.patch.set_facecolor(COL_WHITE)
cw, ch = 0.78, 0.74
sw, sh = 0.62, 0.56
# ---- ÜST PANEL: somut örnek C1 boyaması + A/B şeritleri ----
ax.text(0.30, 8.55, "ÜST — Somut örnek (n = 6): C, A ve B'nin alt-dizilimlerine "
"3 + 3 bölünür mü?", ha="left", va="center", fontsize=11.5,
color=COL_PRIMARY, weight="bold", zorder=6)
c_y, c_x0 = 6.55, 1.20
_a_set = set(_a_pos)
c_centers = []
for q, chq in enumerate(_C1):
x = c_x0 + q * (cw + 0.16)
if q in _a_set:
fc, ec, tc = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tc = COL_BG, COL_PRIMARY, COL_TEXT
cx, cy = _dna_box(ax, x, c_y, cw, ch, chq, fc, ec, tc, lw=2.4)
ax.text(cx, c_y - 0.22, str(q), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=5)
c_centers.append((cx, cy))
ax.text(c_x0 - 0.55, c_y + ch * 0.5, "C₁", ha="right", va="center",
fontsize=13, color=COL_TEXT, weight="bold", zorder=6)
a_y, a_x0 = 7.95, 1.55
a_centers = []
for q, chq in enumerate(_A):
x = a_x0 + q * (sw + 0.12)
on = q in set(_a_map)
cx, cy = _dna_box(ax, x, a_y, sw, sh, chq,
COL_AMBER_100 if on else COL_WHITE,
COL_ACCENT if on else COL_SLATE_400,
COL_AMBER_700 if on else COL_SLATE_500,
lw=2.2 if on else 1.3, fs=12)
a_centers.append((cx, cy))
ax.text(a_x0 - 0.50, a_y + sh * 0.5, "A", ha="right", va="center",
fontsize=12.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(a_x0 + 6 * (sw + 0.12) + 0.10, a_y + sh * 0.5, "= CGTACG",
ha="left", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=6)
b_y, b_x0 = 5.05, 1.55
b_centers = []
for q, chq in enumerate(_B):
x = b_x0 + q * (sw + 0.12)
on = q in set(_b_map)
cx, cy = _dna_box(ax, x, b_y, sw, sh, chq,
COL_BG if on else COL_WHITE,
COL_PRIMARY if on else COL_SLATE_400,
COL_TEXT if on else COL_SLATE_500,
lw=2.2 if on else 1.3, fs=12)
b_centers.append((cx, cy))
ax.text(b_x0 - 0.50, b_y + sh * 0.5, "B", ha="right", va="center",
fontsize=12.5, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(b_x0 + 6 * (sw + 0.12) + 0.10, b_y + sh * 0.5, "= TTAGCA",
ha="left", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=6)
for grp_idx, q in enumerate(_a_pos):
cx, cy = c_centers[q]
ax_, ay_ = a_centers[_a_map[grp_idx]]
ax.add_patch(FancyArrowPatch(
(cx, cy + ch * 0.5), (ax_, ay_ - sh * 0.5), arrowstyle="-",
color=COL_ACCENT, linewidth=2.0, zorder=3))
for grp_idx, q in enumerate(_b_pos):
cx, cy = c_centers[q]
bx_, by_ = b_centers[_b_map[grp_idx]]
ax.add_patch(FancyArrowPatch(
(cx, cy - ch * 0.5), (bx_, by_ + sh * 0.5), arrowstyle="-",
color=COL_SLATE_500, linewidth=1.8, zorder=3))
ax.text(c_centers[1][0], c_y - 0.62, "A-grubu CGT (amber → A)",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(c_centers[4][0], c_y - 0.62, "B-grubu TAG (slate → B)",
ha="center", va="center", fontsize=8.5, color=COL_PRIMARY,
weight="bold", zorder=6)
yes_x = c_x0 + 6 * (cw + 0.16) + 0.45
ax.add_patch(FancyBboxPatch(
(yes_x, c_y - 0.02), 2.05, ch + 0.04,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_GOOD, ec=COL_GOOD_EC, linewidth=2.2, zorder=4))
ax.text(yes_x + 1.02, c_y + ch * 0.66, "EVET", ha="center", va="center",
fontsize=12, color=COL_GOOD_EC, weight="bold", zorder=5)
ax.text(yes_x + 1.02, c_y + ch * 0.24, "3 + 3 bölünme var", ha="center",
va="center", fontsize=8, color=COL_GOOD_EC, weight="bold", zorder=5)
c2_x0, c2_y = yes_x + 0.18, b_y + 0.05
ax.text(c2_x0 - 0.05, c2_y + sh + 0.40, "İkinci örnek:", ha="left",
va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6)
mw, mh = 0.40, 0.50
for q, chq in enumerate(_C2):
x = c2_x0 + q * (mw + 0.06)
_dna_box(ax, x, c2_y, mw, mh, chq, COL_WHITE, COL_RED, COL_RED, lw=1.6, fs=10)
ax.text(c2_x0 - 0.50, c2_y + mh * 0.5, "C₂", ha="right", va="center",
fontsize=11, color=COL_RED, weight="bold", zorder=6)
ax.add_patch(FancyBboxPatch(
(c2_x0, c2_y - 0.85), 6 * (mw + 0.06) + 0.30, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_RED_BG, ec=COL_RED, linewidth=2.0, zorder=4))
ax.text(c2_x0 + (6 * (mw + 0.06)) * 0.5 + 0.15, c2_y - 0.54,
"HAYIR (yeterli G yok)", ha="center", va="center",
fontsize=8.5, color=COL_RED, weight="bold", zorder=5)
ax.text(c2_x0 + (6 * (mw + 0.06)) * 0.5 + 0.15, c2_y - 0.78,
f"A'da 2 + B'de 1 = {_g_total} G < 6 gerekli", ha="center",
va="center", fontsize=7, color=COL_RED, style="italic", zorder=5)
ax.plot([0.20, 11.30], [4.35, 4.35], color=COL_SLATE_400,
linewidth=1.0, linestyle=(0, (5, 4)), zorder=1)
# ---- ALT PANEL: durum/recurrence anatomisi ----
ax.text(0.30, 3.95, "ALT — Durum tasarımı ve karar (recurrence)", ha="left",
va="center", fontsize=11.5, color=COL_PRIMARY, weight="bold", zorder=6)
st_x, st_y, st_w, st_h = 0.40, 2.85, 4.55, 0.78
ax.add_patch(FancyBboxPatch(
(st_x, st_y), st_w, st_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.text(st_x + 0.22, st_y + st_h * 0.66, "Durum", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=4)
ax.text(st_x + 0.22, st_y + st_h * 0.30, r"$x(i,\ j,\ k_i,\ k_j)$",
ha="left", va="center", fontsize=14, color=COL_TEXT, weight="bold", zorder=4)
dep_x, dep_y, dep_w, dep_h = 0.40, 1.78, 6.05, 0.92
ax.add_patch(FancyBboxPatch(
(dep_x, dep_y), dep_w, dep_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(dep_x + 0.22, dep_y + dep_h * 0.68, "C konumu AYRI İNDEKS DEĞİL",
ha="left", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(dep_x + 0.22, dep_y + dep_h * 0.34,
r"konum $= |C| - (k_i + k_j)$'den TÜRER → bağımlı indeks ELENİR",
ha="left", va="center", fontsize=9.5, color=COL_TEXT, zorder=4)
or_x, or_y_top = 6.95, 3.55
ax.text(or_x, or_y_top, "Karar (∨ — 4 seçim):", ha="left", va="center",
fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=4)
_choices = [
("Aᵢ eşle", "A[i] = c → x(i+1, j, kᵢ−1, kⱼ)", COL_ACCENT),
("Bⱼ eşle", "B[j] = c → x(i, j+1, kᵢ, kⱼ−1)", COL_PRIMARY),
("Aᵢ atla", "x(i+1, j, kᵢ, kⱼ)", COL_SLATE_500),
("Bⱼ atla", "x(i, j+1, kᵢ, kⱼ)", COL_SLATE_500),
]
for idx, (name, expr, col) in enumerate(_choices):
yy = or_y_top - 0.42 - idx * 0.42
ax.text(or_x + 0.05, yy, "∨" if idx > 0 else "•", ha="center", va="center",
fontsize=11, color=COL_AMBER_600, weight="bold", zorder=4)
ax.text(or_x + 0.30, yy, name, ha="left", va="center", fontsize=9.5,
color=col, weight="bold", zorder=4)
ax.text(or_x + 1.45, yy, expr, ha="left", va="center", fontsize=8.5,
color=COL_TEXT, zorder=4)
bd_x, bd_y, bd_w, bd_h = 0.40, 0.55, 6.05, 0.96
ax.add_patch(FancyBboxPatch(
(bd_x, bd_y), bd_w, bd_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_AMBER_600, linewidth=2.0, zorder=2))
ax.text(bd_x + 0.22, bd_y + bd_h * 0.66, "Taban DENGESİ (Ku):", ha="left",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(bd_x + 0.22, bd_y + bd_h * 0.34,
r"true taban $x(n,n,0,0)=$ True VARSA → false tabanlar da ŞART "
r"(dizi bitti ama kota > 0 → False)",
ha="left", va="center", fontsize=8.7, color=COL_TEXT, zorder=4)
cx_x, cx_y, cx_w, cx_h = 6.95, 0.55, 4.35, 0.96
ax.add_patch(FancyBboxPatch(
(cx_x, cx_y), cx_w, cx_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(cx_x + cx_w * 0.5, cx_y + cx_h * 0.64,
r"$n^4$ alt problem $\times$ $O(1)$ karar", ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(cx_x + cx_w * 0.5, cx_y + cx_h * 0.26, r"$=\ O(n^4)$", ha="center",
va="center", fontsize=13, color=COL_AMBER_700, weight="bold", zorder=4)
fig.suptitle(
"DNA babalık (QR3 P2): 3-string Boolean DP — bağımlı indeks elenir, "
"∨ 4 seçim, O(n⁴)", color=COL_TEXT, fontsize=13, weight="bold", y=0.985)
ax.set_xlim(-0.1, 11.6)
ax.set_ylim(0.30, 9.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-note collapse="true" title="Problem 2 — DNA Babalık Testi (Alice/Bob/Charlie): 3-string Boolean LCS, O(n⁴) kuartik"}
**İfade.** Üç $n$-uzunluklu DNA dizisi $A$, $B$, $C$ (CGTA). Charlie ($C$), **eşit uzunlukta iki (bitişik olmayan) alt-diziye** bölünebiliyorsa eşleşir: biri $A$'nın alt-dizisi, diğeri $B$'nin alt-dizisi. $C$'nin **tüm** karakterleri kullanılmalı ($A$, $B$'ninkiler değil). Charlie sahte mi? **$O(n^4)$** istenir.
**Yaklaşım.** LCS'e benzer ama **üç** dizi + $C$'nin tam bölünmesi. Naif ($i, j, k$ prefix indeksleri) yetmez — $C$'nin kaçını $A$'ya, kaçını $B$'ye verdiğimi bilmem gerek. **Durum:** $k_i = C$'nin $A$'ya eşleşecek kalan karakter sayısı, $k_j = B$'ye eşleşecek kalan. $C$'deki konum **bağımsız değil** — $k_i + k_j$'den hesaplanır ($C$ suffix'inde $k_i + k_j$ karakter kalmalı).
**Çözüm.** **S:** $x(i, j, k_i, k_j) = $ Boolean: $A$ suffix$(i)$'den $k_i$-uzunlukta + $B$ suffix$(j)$'den $k_j$-uzunlukta alt-diziyle, $C$ suffix'inin (uzunluk $k_i + k_j$) **tüm** karakterleri eşleşebilir mi? **R ($\vee$ over 4 seçim):** (1) $A_i = $ ilgili $C$ karakteri ise & $k_i > 0$: $x(i+1, j, k_i-1, k_j)$; (2) $B_j$ eşleşir & $k_j > 0$: $x(i, j+1, k_i, k_j-1)$; (3) $A_i$'yi atla: $x(i+1, j, k_i, k_j)$ ($i < n$); (4) $B_j$'yi atla: $x(i, j+1, k_i, k_j)$ ($j < n$). **T:** $i + j$ kesin artar (en az biri artar). **B:** $x(n, n, 0, 0) = $ **true** (her şey eşleşti); $A$ bitti ama $k_i > 0$ → **false** (ve $B$ için simetrik). **O:** $x(0, 0, n/2, n/2)$; $n$ çift değilse direkt false.
> *"If you give us a true base case, you better be giving us some false base cases."* — Ku (Base Cases)
**Karmaşıklık.** $i, j \in 0..n$; $k_i, k_j \in 0..n/2$ → **$n^4$** alt problem $\times\, O(1)$ (4 seçim) = **$O(n^4)$ kuartik**. (Gerçek babalık değil — kurgu.)
:::
@fig-tapas-knapsack Problem 3'ün imza fikrini gösterir: çekirdek 0/1 knapsack'ine **TAM-s tatlı** sayacı eklenir; bu tam-eşitlik kısıtı tabanı ikiye böler ve "kota tutmadı → $-\infty$" dengesi $-\infty$ tabanlarını zorunlu kılar. $k$ çıplak sayı olduğu için runtime **pseudopolinom**.
```{python}
#| label: fig-tapas-knapsack
#| fig-cap: "Tapas — 0/1 knapsack + tatlı sayısı, O(nks) pseudopolinom (QR3 Problem 3, İMZA figür, Spring-18). n tabak; tabak i: hacim Vᵢ, kalori Cᵢ, tatlılık sᵢ ∈ {0,1}. En fazla k kalori ye; TAM s tatlı tabak ye; 0/1; doyma için hacmi maksimize et. SOL panel: 5 tabak kartı (V hacim üst, C kalori alt, tatlı rozeti); seçilenler (0,1,4) amber ✶; kalori çubuğu 8'e karşı 3+2+3=8 TAM dolu; tatlı sayacı TAM 2/2; max hacim 15. SAĞ panel: x(i, j, s′) iki seçim (ye / yeme); taban dengesi — true taban x(n,j,0)=0 (yeşilimsi) AMA x(n,j,s′≠0)=−∞ (amber uyarı: kota tutmadı → asla seçilme); imkansiz mini-örnek tapas([5],[2],[0],10,3)=−∞ (tek tatsız tabak + s=3); polinom-teşhis (n+1)(k+1)(s+1) × O(1) = O(nks) PSEUDOpolinom (k çıplak sayı — Ku: subset sum gibi). Motordan: tapas(...) = 15 == bitmask brute; optimal {0,1,4} V=[6,4,5]=15, ΣC=8≤8, Σs=2."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-tapas-knapsack (QR3 P3 İMZA): 0/1 knapsack + tatlı sayacı, motordan.
_tV, _tC, _tsf, _tk, _ts = build_tapas_example()
assert (_tV, _tC, _tsf, _tk, _ts) == ([6, 4, 7, 3, 5], [3, 2, 4, 1, 3],
[0, 1, 0, 1, 1], 8, 2)
_t_val, _ = tapas(_tV, _tC, _tsf, _tk, _ts)
assert _t_val == 15 == brute_tapas(_tV, _tC, _tsf, _tk, _ts), _t_val
_imp_val, _ = tapas([5], [2], [0], 10, 3)
assert _imp_val == -INF, _imp_val
# Optimal tabak kümesini brute ile bul (figür amber-seçimi — uydurma yok)
_t_best, _t_set = -INF, None
for _mask in range(1 << len(_tV)):
_idx = [m for m in range(len(_tV)) if _mask >> m & 1]
if sum(_tC[m] for m in _idx) <= _tk and sum(_tsf[m] for m in _idx) == _ts:
_v = sum(_tV[m] for m in _idx)
if _v > _t_best:
_t_best, _t_set = _v, _idx
assert _t_set == [0, 1, 4] and _t_best == 15 == _t_val, (_t_set, _t_best)
assert sum(_tC[i] for i in _t_set) == 8 <= _tk
assert sum(_tsf[i] for i in _t_set) == 2 == _ts
def _tap_plates(ax, V, C, sf, k, s, selected, value):
n = len(V)
sel = set(selected)
ax.text(2.85, 6.62, "Tabaklar — TAM 2 tatlı kotası (0/1 knapsack)",
ha="center", va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold")
card_w, card_h, gap, y0 = 0.94, 1.45, 0.18, 4.45
for i in range(n):
x = 0.10 + i * (card_w + gap)
hot = i in sel
ax.add_patch(FancyBboxPatch(
(x, y0), card_w, card_h, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.6 if hot else 1.7, zorder=3))
cx = x + card_w * 0.5
ax.text(cx, y0 + card_h * 0.62, f"V={V[i]}", ha="center", va="center",
fontsize=13, color=COL_AMBER_700 if hot else COL_TEXT,
weight="bold", zorder=5)
ax.text(cx, y0 + card_h * 0.28, f"C={C[i]} kcal", ha="center",
va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
if sf[i] == 1:
ax.add_patch(FancyBboxPatch(
(cx - 0.34, y0 + card_h * 0.86 - 0.13), 0.68, 0.26,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.2, zorder=5))
ax.text(cx, y0 + card_h * 0.86, "tatlı sᵢ=1", ha="center",
va="center", fontsize=6.6, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(cx, y0 - 0.22, f"tabak {i}", ha="center", va="center",
fontsize=7.6, color=COL_SLATE_400, zorder=5)
if hot:
ax.scatter([cx], [y0 + card_h + 0.18], marker="*", s=140,
color=COL_ACCENT, edgecolor=COL_AMBER_700,
linewidth=0.8, zorder=6)
sel_sorted = sorted(sel)
ax.text(2.85, y0 + card_h + 0.52,
f"seçilen ✶ : {' + '.join(str(V[i]) for i in sel_sorted)} = {value}",
ha="center", va="center", fontsize=9.6, color=COL_AMBER_700, weight="bold")
used_cal = sum(C[i] for i in sel)
by, bh, cal_w, cgap, bx0 = 3.40, 0.46, 0.62, 0.085, 0.40
ax.text(bx0 - 0.05, by + bh + 0.30,
f"kalori bütçesi: {k} kcal → "
f"{' + '.join(str(C[i]) for i in sel_sorted)} = {used_cal} (TAM DOLU)",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold")
for c in range(k):
x = bx0 + c * (cal_w + cgap)
full = c < used_cal
ax.add_patch(FancyBboxPatch(
(x, by), cal_w, bh, boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_300 if full else COL_WHITE,
ec=COL_AMBER_700 if full else COL_SLATE_400,
linewidth=2.0 if full else 1.2, zorder=3))
assert used_cal == k == 8, used_cal
used_s = sum(sf[i] for i in sel)
ax.add_patch(FancyBboxPatch(
(0.40, 2.30), 2.55, 0.66, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3))
ax.text(1.05, 2.63, "tatlı sayacı", ha="center", va="center",
fontsize=8.4, color=COL_SLATE_500, zorder=5)
ax.text(2.30, 2.63, f"TAM {used_s}/{s}", ha="center", va="center",
fontsize=14, color=COL_AMBER_700, weight="bold", zorder=5)
assert used_s == s == 2, used_s
ax.text(0.40, 2.06, "(≤ değil = : tam-eşitlik kısıtı → s′ sayacı)",
ha="left", va="center", fontsize=7.8, color=COL_SLATE_500,
style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(0.40, 0.55), 2.55, 0.78, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=3))
ax.text(1.67, 0.94, f"max hacim = {value}", ha="center", va="center",
fontsize=13, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(3.55, 0.94, "her tabak ≤ 1 kez\n(0/1 — i → i+1)", ha="center",
va="center", fontsize=8.6, color=COL_PRIMARY, weight="bold", zorder=5)
ax.set_xlim(-0.1, 5.65)
ax.set_ylim(-0.1, 7.05)
ax.set_aspect("equal")
ax.axis("off")
def _tap_recurrence(ax, imp_value):
ax.text(3.0, 6.62, "Recurrence + taban dengesi", ha="center", va="center",
fontsize=12.5, color=COL_PRIMARY, weight="bold")
rx, ry, rw, rh = 0.15, 4.45, 5.75, 1.78
ax.add_patch(FancyBboxPatch(
(rx, ry), rw, rh, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.text(rx + rw * 0.5, ry + rh - 0.27,
"x(i, j, s′) = tabak i..n−1'den ≤ j kalori ∧ TAM s′ tatlı → max hacim",
ha="center", va="center", fontsize=9.2, color=COL_PRIMARY,
weight="bold", zorder=4)
ax.text(rx + 0.30, ry + rh - 0.78,
"• YE (Cᵢ ≤ j ∧ sᵢ ≤ s′) → Vᵢ + x(i+1, j−Cᵢ, s′−sᵢ)",
ha="left", va="center", fontsize=9.0, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(rx + 0.30, ry + rh - 1.18, "• YEME → x(i+1, j, s′)",
ha="left", va="center", fontsize=9.0, color=COL_TEXT, zorder=4)
ax.text(rx + rw * 0.5, ry + 0.26,
"iki dalda da i → i+1 : 0/1 knapsack (tabak tüketildi)",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=4)
ty, th = 2.75, 1.30
ax.add_patch(FancyBboxPatch(
(0.15, ty), 2.65, th, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_GOOD, ec=COL_GOOD_EC, linewidth=2.2, zorder=3))
ax.text(1.475, ty + th - 0.30, "TRUE taban", ha="center", va="center",
fontsize=9.0, color=COL_GOOD_EC, weight="bold", zorder=5)
ax.text(1.475, ty + th * 0.42, "x(n, j, 0) = 0", ha="center", va="center",
fontsize=11.5, color=COL_TEXT, weight="bold", zorder=5)
ax.text(1.475, ty + 0.18, "kota tuttu (s′=0) — geçerli", ha="center",
va="center", fontsize=7.6, color=COL_SLATE_500, style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(3.05, ty), 2.85, th, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.8, zorder=3))
ax.text(4.475, ty + th - 0.30, "⚠ FALSE / −∞ taban", ha="center",
va="center", fontsize=9.0, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(4.475, ty + th * 0.42, "x(n, j, s′≠0) = −∞", ha="center",
va="center", fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(4.475, ty + 0.18, "kota tutmadı — asla seçilmesin", ha="center",
va="center", fontsize=7.6, color=COL_AMBER_700, style="italic", zorder=5)
ax.text(3.0, ty - 0.32,
"true taban varsa → FALSE/−∞ tabanlar ŞART (Ku): −∞, max'ta o dalı öldürür",
ha="center", va="center", fontsize=8.4, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(0.15, 0.95), 3.05, 1.05, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_AMBER_600, linewidth=1.8, zorder=3))
ax.text(1.675, 0.95 + 0.80, "imkansız kota örneği (motordan)", ha="center",
va="center", fontsize=8.2, color=COL_AMBER_600, weight="bold", zorder=5)
ax.text(1.675, 0.95 + 0.44, "tapas([5], [2], [0], k=10, s=3)", ha="center",
va="center", fontsize=8.8, color=COL_TEXT, zorder=5)
ax.text(1.675, 0.95 + 0.14,
f"tek tatsız tabak + s=3 talep → "
f"{('−∞' if imp_value == -INF else imp_value)}",
ha="center", va="center", fontsize=9.0, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(3.45, 0.95), 2.45, 1.05, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=3))
ax.text(4.675, 0.95 + 0.80, "(n+1)(k+1)(s+1) × O(1)", ha="center",
va="center", fontsize=8.6, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(4.675, 0.95 + 0.47, "= O(n k s)", ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5)
ax.text(4.675, 0.95 + 0.16, "PSEUDOpolinom — k ÇIPLAK SAYI", ha="center",
va="center", fontsize=7.6, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(3.0, 0.62, "Ku: subset sum gibi — k girdi boyutunda değil, runtime'da",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.1, 6.05)
ax.set_ylim(-0.1, 7.05)
ax.set_aspect("equal")
ax.axis("off")
fig, axes = plt.subplots(1, 2, figsize=(12.0, 6.0),
gridspec_kw={"width_ratios": [1.0, 1.06]})
fig.patch.set_facecolor(COL_WHITE)
_tap_plates(axes[0], _tV, _tC, _tsf, _tk, _ts, _t_set, _t_val)
_tap_recurrence(axes[1], _imp_val)
fig.suptitle(
"Tapas: 0/1 knapsack + TAM-s tatlı sayacı — −∞ taban dengesi "
"(kota tutmadı → asla seçilme) · O(nks) pseudopolinom",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.98)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
::: {.callout-note collapse="true" title="Problem 3 — Tapas (Obert Ratkins): 0/1 knapsack + tatlı sayısı, O(nks) pseudopolinom"}
**İfade.** $n$ tabak; tabak $i$: hacim $V_i$, kalori $C_i$, tatlılık $s_i \in \{0, 1\}$. En fazla **$k$ kalori** ye; **tam $s$ tatlı tabak** ye; aynı tabağı **iki kez alma** (0/1). Doyma için **hacmi maksimize et**. **$O(nks)$** istenir.
**Önce: polinom mu?** Girdi = her tabak için 3 sayı, $n$ tabak → $n$, $s$ polinom; ama **$k$ sadece bir sayı** (bir kelimede, üstel büyüklükte olabilir). Yani **pseudopolinom** (subset sum / knapsack gibi). Sınavda sık sorulur: "runtime polinom mu?" — çözmeden, runtime'a bakıp girdi boyutuyla sınırlanıp sınırlanmadığına bak.
> *"this is a pseudopolynomial running time. Because k is just a number in my problem, similar to subset sum."* — Ku
**Çözüm.** **S:** $x(i, j, s') = P_i \dots P_n$ tabaklarından, en fazla $j$ kalori ve **tam** $s'$ tatlı ile elde edilebilen max hacim. **R (max, 2 seçim):** ye → $V_i + x(i+1, j-C_i, s'-s_i)$ (yalnız $C_i \le j \wedge s_i \le s'$); yeme → $x(i+1, j, s')$ (hep). **T:** $i$ kesin artar. **B:** $x(n+1, j, 0) = 0$ (menü bitti, tam $s$ yendi — iyi); $x(n+1, j, s') = $ **$-\infty$** $s' \ne 0$ ise (tatlı kotası tutmadı — asla seçilmesin). **O:** $x(1, k, s)$.
**Karmaşıklık.** $(n+1)(k+1)(s+1)$ alt problem $\times\, O(1) = $ **$O(nks)$ pseudopolinom**.
::: {.callout-note title="İndeks köprüsü — Tapas prose vs kod"}
Prosede taban "$x(n+1, j, 0)$" ve özgün cevap "$x(1, k, s)$" diye $1$-tabanlı yazılır; motorda (`tapas`) tabaklar $0$-tabanlıdır, dolayısıyla taban `i == n` (tüm tabaklar tüketildi) ve özgün cevap `x(0, k, s)`'dir. Aynı recurrence (D25/D29 emsali): $1$-tabanlı sınav anlatımı, kodda bir indeks kaymasıyla birebir aynı tabloyu üretir; motor `tapas(...) = 15` ve imkansız kotada `−∞` her iki okumayı da doğrular.
:::
:::
::: {.callout-tip title="Atlanan 4. problem — Gokemon Po"}
Canavar yakala; bir konuma git (ride-share ücreti) + bedava yakala, VEYA uygulama-içi satın al (farklı ücret, konum değişmez). Anahtar: **en son nerede olduğumu hatırla** → sonraki konuma mesafe. Pseudopolinom değil; konum durumuyla genişletme. Ku zaman yetmediği için bıraktı (transkript 1:09).
:::
## Quiz Hazırlığı Egzersizleri {#sec-quiz-hazirligi-d30}
**Egzersiz 1.** Lotto'yu **prefix** alt problemiyle yeniden kur (gün $i$'de oynadığımı varsay, önceki izinli oyun). Sonucun suffix versiyonuyla aynı $O(n)$ olduğunu göster.
**Egzersiz 2.** DNA probleminde $C$'deki konumu neden ayrı bir indeks olarak tutmaya gerek olmadığını ($k_i + k_j$'den türediğini) bir örnekle açıkla.
**Egzersiz 3.** Tapas'ta "tam $s$ tatlı" kısıtını "en fazla $s$ tatlı"ya çevirirsen taban durumlar nasıl değişir? Hâlâ $-\infty$ gerekir mi?
**Egzersiz 4.** Verilen bir runtime'ın (örn. $O(nW)$, $O(n^2)$, $O(2^n \cdot n)$) polinom mu pseudopolinom mu üstel mi olduğunu, girdi boyutuna göre sınıflandır.
**Egzersiz 5.** Üç problemin her birinde "alt problem hakkındaki soru"yu ($R$ adımı) tek cümleyle yaz (Lotto: sonraki ne zaman oynayayım? DNA: ilk karakteri kime eşleyeyim? Tapas: bu tabağı yiyeyim mi?).
## Sınav Stratejisi (Kapsam Notları) {#sec-sinav-stratejisi-d30}
- **Söz + matematik:** $S$'yi sözle (memo ne döndürür), $R$'yi matematik formülle yaz — iletişim puanın yarısı.
- **Prefix $\leftrightarrow$ suffix** değiştirilebilir; diziyi ters çevir, aynı DP. Bu sınıf suffix kullanır.
- **Alt problem sayısı = parametrelerin çarpımı** (toplamı değil). İş/alt problem = branching.
- **Polinom teşhisi:** runtime'daki her terimi girdi boyutuyla sınırlayabiliyor musun? $k / W$ gibi "çıplak sayı" varsa **pseudopolinom**.
- **Parent pointer:** sadece optimum değeri değil, **seçimi** (hangi gün/tabak/eşleşme) geri getirmek için max'ta hangi alt probleme gittiğini sakla.
- **Taban durum dengesi:** $\vee$-temelli Boolean DP'de bir **true** taban varsa, mutlaka **false** tabanlar da olmalı (yoksa hep true döner).
::: {.callout-tip title="Builder Notu — Pseudopolinom Teşhisi Gerçek-Dünya Refleksi"}
"Runtime'da çıplak sayı var mı?" sorusu sınıf dışında her yerde işe yarar: bir DP çözümünün $O(nW)$ olması, $W$ büyüdükçe (yüksek bütçe, büyük kapasite) pratikte yavaşlayacağı anlamına gelir — subset sum, knapsack, coin change hepsi bu sınıftandır. Mühendislikte refleks: bir runtime gördüğünde "girdi boyutu kaç bit?" diye sor; $k$ bir kelimede sığan bir sayıysa ama runtime $k$ ile çarpılıyorsa, girdi $\log k$ bit iken çalışma $2^{\log k}$ ile büyür — **pseudopolinom**. Quiz 3'ün Tapas problemi tam olarak bu refleksi test eder.
:::
## Toplu Cheat Sheet — SRTBOT {#sec-toplu-cheat-d30}
| Adım | Ne yapılır | Quiz'de dikkat |
|------|-----------|----------------|
| S — Subproblems | $x(\dots)$ tanımı: memo ne döndürür, ne kadar büyük | Tanımda olmayan parametre = sıfır puan |
| R — Relate | Matematik bağıntı: $\max / \min / \sum / \vee$ over seçimler | Söz değil formül; "soru sor" stratejisi |
| T — Topological | Bir indeks (veya toplam) hep artar/azalır → DAG | Acyclic kanıtı yoksa sonsuz döngü |
| B — Base cases | Memo sınırı dışı için sabit-zaman cevap | Taban yoksa sonlu zaman bile değil |
| O — Original | Özgün cevabı alt problemden üret (+ parent pointer) | Tek alt problem mi, max mı? |
| T — Time | #alt problem (parametre çarpımı) $\times$ iş/alt problem | Çarp, toplama; polinom/pseudopolinom ayrımı |
**DP alt problem kategorileri (Demaine L18):** suffix/prefix (tek-uç karar) · bitişik alt-dizi (iki-uç karar) · çoklu dizi (indeks çarpımı) · durum genişletme (sıra/yön/bütçe/tatlı/konum) · sayıya göre genişletme (pseudopolinom).
## Bu Quiz Review'in Özeti {#sec-ozet-d30}
1. **Quiz 3 = DP bloğu** (Ders 23-27; L15-L18); tek konu dinamik programlama, omurga **SRTBOT**.
2. **SRTBOT çerçevesi**: alt problemi sözle tam tanımla, recurrence'ı matematikle yaz, topolojik sırayı kanıtla, taban durumları (true + false dengesi) kur, özgün cevabı üret, süreyi analiz et.
3. **Lotto (durum genişletme)**: naif suffix kısıt uygulayamayınca offset state ekle; "geçmişi gelecek kısıtı olarak hatırla"; $O(n)$ lineer.
4. **DNA (çoklu-dizi Boolean DP)**: üç dizi; bağımlı indeks ($C$ konumu = $k_i + k_j$) elenir; $\vee$ 4 seçim; true/false taban dengesi; $O(n^4)$.
5. **Tapas (pseudopolinom knapsack)**: 0/1 knapsack + tam-$s$ tatlı sayacı; kota tutmadı → $-\infty$ taban; $k$ çıplak sayı → $O(nks)$ pseudopolinom.
6. **Strateji**: söz + matematik, çarp (toplama değil), polinom teşhisi, parent pointer, taban dengesi.
::: {.callout-important title="Tek Bir Cümle"}
Quiz 3'te kritik olan: alt problemi **sözle** tam tanımla (tanımsız parametre = puan yok), bağıntıyı **matematikle** yaz, topolojik sırayı kanıtla, taban durumları (true + false dengesi) unutma, runtime'ı **girdi boyutuyla** sınıflandır (polinom mu pseudopolinom mu). Üç gerçek problem üç tekniği gösterdi: **durum genişletme** (Lotto — "geçmişi gelecek kısıtı olarak hatırla"), **çoklu-dizi Boolean DP** (DNA — bağımlı indeks elenir), **0/1 knapsack + sayaç** (Tapas — pseudopolinom).
:::
## Builder ve OMSCS Bağlantıları {#sec-builder-omscs-d30}
::: {.callout-tip title="5 köprü"}
Bu son tekrar oturumu, "alt problemi sözle tanımla, recurrence'ı matematikle yaz, runtime'ı girdi boyutuyla sınıflandır" disiplinini kurar — köprülerin özeti:
1. **Quiz 3 = DP midterm** → OMSCS CS 6515: dinamik programlama, graduate algoritma dersinin **en ağır blokudur** (sınavların yarısı DP).
2. **Durum genişletme** → gerçek sistemde "state machine + bütçe" tasarımı: kalan kapasite, kalan adım, son konum — hepsi DP state'i olur.
3. **Çoklu-dizi DP** → biyoinformatik (dizi hizalama), diff/merge araçları, versiyon kontrol — LCS ailesinin pratik karşılıkları.
4. **Pseudopolinom teşhisi** → "runtime'da çıplak sayı var mı?" refleksi: knapsack, subset sum, coin change'in pratik yavaşlık sınırı.
5. **SRTBOT iletişim disiplini** → mühendislikte "önce problemi net tanımla, sonra çöz"; kod yazmadan önce alt problemi sözle ifade etmek, gerçek refleks.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
SRTBOT, **her** özyinelemeli algoritmanın çerçevesidir; DP, alt problemler **örtüştüğünde** (memoize → DAG) devreye girer. Quiz 3'te kritik olan: alt problemi **sözle** tam tanımla (tanımsız parametre = puan yok), bağıntıyı **matematikle** yaz, topolojik sırayı kanıtla, taban durumları (true + false dengesi) unutma, runtime'ı **girdi boyutuyla** sınıflandır (polinom mu pseudopolinom mu). Üç gerçek problem üç tekniği gösterdi: durum genişletme (Lotto), çoklu-dizi Boolean DP (DNA), 0/1 knapsack + sayaç (Tapas).
:::
