---
title: "Toparlanma ve Sonraki Dersler"
subtitle: "Dönem retrospektifi — dört hedef, üç ünitenin tek omurgası ve 6.046 köprüsü"
---
::: {.callout-note title="Oturum bilgisi"}
- **Ku'nun videosu:** [YouTube — Lecture 20: Course Review](https://www.youtube.com/watch?v=2NMtS1ecb3o) (≈38 dk — normal dersten kısa)
- **OCW sayfası:** [MIT 6.006 Lecture 20](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec20/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 31 (L20)
- **Hoca:** Jason Ku (dönem retrospektifi; sondan bir önceki ders)
- **Okuma süresi:** ≈24 dk
> **SONDAN BİR ÖNCEKİ ders** — test edilebilir materyal bitti; bu ders **yüksek-seviye sentez**. Önceki ders (Ders 30 / Quiz 3 Review, Ku) DP'yi gözden geçirdi; bu retrospektif tüm dönemi tek bir omurgada toplar ve 6.046'ya köprü kurar. Son ders (Ders 32 / L21) dönemi kapatır.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d31}
Sondan bir önceki ders (**Jason Ku**): **dönem retrospektifi** + "buradan nereye?". Test edilebilir tüm materyal bitti; bu ders öğrendiklerimizi bağlama oturtur ve sonraki teori derslerini tanıtır — **yüksek-seviye sentez**.
> *"Welcome, everybody, to the second-to-last lecture of 6.006."* — Ku, 0:18
Üç ana parça: (1) **6.006'nın 4 hedefi** (neden bu dersi alıyoruz), (2) **3 ünitenin tek bir hikâye olarak** özeti (veri yapıları → çizge → DP), (3) **6.046 ve ötesi** (karmaşıklığı/modeli gevşeten teori dalları).
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 31'in (L20) kavram haritası: kök = Toparlanma ve Sonraki Dersler (Ku) — dönem retrospektifi, yüksek-seviye sentez, test edilebilir materyal bitti. Dört dal — (1) Dört hedef: zor problemi çöz algoritma üret, doğruluğu kanıtla özyineleme artı tümevarım uygulamalı 6.042, verimliliği kanıtla word-RAM artı asimptotik artı ölçeklenebilirlik, insanlara ilet EN ÖNEMLİSİ doğru ama anlaşılmayan kod tam puan almaz. (2) Üç ünite tek omurga: Quiz 1 veri yapıları bir şey bul dizi vs küme artı sıralama heap counting radix; Quiz 2 çizgeler düğüm durum kenar geçiş SSSP genellik-runtime takası DAG BFS Dijkstra Bellman-Ford; Quiz 3 DP eşittir çizge inşası SRTBOT alt problem düğüm bağıntı kenar topolojik sıra DAG, çizgeyi SEN kurarsın yaratıcı kısım. (3) Final için L19 tanımlar: P alt küme NP alt küme EXP iç içe, reduction yönü bilinen-zoru hedefe indirge, hard vs complete. (4) 6.046 OMSCS CS 6515: doğal uzantı union-find MST max-flow gerçek reduction artı analiz çok daha zor; tanım gevşetme randomized Las Vegas Monte Carlo, numerical kesinliği zamanla öde, approximation sabit-çarpan yakın, model değişimi cache quantum parallel. Birleştirici tema: 6.006'nın amacı sadece algoritma yazmak değil doğruluğu ve verimliliği insanlara iletmek; üç ünite tek özyinelemeli hikâyedir bul ilişkilendir inşa et; 6.046 bu hikâyeyi derinleştirir ve doğru verimli tanımını gevşetir."
flowchart TD
A["Ders 31 (L20): Toparlanma ve Sonraki Dersler — dönem retrospektifi (Ku)"] --> G["Dört hedef — neden bu dersi alıyoruz"]
G --> Ga["çöz · doğruluğu kanıtla (uyg. 6.042) · verimliliği kanıtla<br/>İNSANLARA İLET = EN ÖNEMLİSİ (anlaşılmayan kod tam puan almaz)"]
A --> U["Üç ünite — tek omurga"]
U --> Ua["Quiz 1 veri yapıları (bul) · Quiz 2 çizgeler (ilişki)<br/>Quiz 3 DP = çizge İNŞASI (SRTBOT) — çizgeyi SEN kurarsın"]
A --> F["Final için — L19 tanımları"]
F --> Fa["P ⊆ NP ⊆ EXP iç içe · reduction yönü<br/>hard vs complete (genelde doğru/yanlış sorusu)"]
A --> S["6.046 ve ötesi — OMSCS CS 6515"]
S --> Sa["doğal uzantı: union-find · MST · max-flow · reduction<br/>tanım gevşetme: randomized · numerical · approximation · model"]
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 G,U,F,S branch
class Ga,Ua,Fa,Sa leaf
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 31 (L20) Toparlanma ve Sonraki Dersler motoru
# (_engine.py D31 bölümü + bağımlılıkları + _viz.py yardımcıları INLINE
# GÖMÜLÜ — import YOK). Fonksiyonlar / sınıflar:
# MonteCarloHashSet / monte_carlo_demo → L20 §7 Monte Carlo (hep hızlı,
# bazen yanlış-negatif); "ilk iki çarpışanı sakla" (Kontrol-3/Egz-5).
# HashTableChaining → L20 §7 Las Vegas chaining (hep doğru).
# bfs / dijkstra (+ ChangeablePQ) / bellman_ford_classic (+ relax_edge /
# _reachable_from) / sssp_backbone_check
# → L20 §4 üç-ünite omurga tanığı
# (BFS == Dijkstra(w=1) == Bellman-Ford aynı δ).
# _viz draw_lasvegas_montecarlo / _node_box + Slate+Amber sabitleri.
# Bu hücre gizli (#| echo: false). Aşağıdaki TÜM figür hücreleri burada
# tanımlananları IMPORT ETMEDEN kullanır (dosyadan import YOK).
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir).
# ============================================================================
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
COL_DROP = "#dc2626" # red-600 — düşürülen/yanlış-negatif öğe çarpısı
INF = float("inf")
def _node_box(ax, x, y, w, h, label, ec=COL_PRIMARY, fc=COL_BG, fontsize=10):
"""Ortalanmış yuvarlatılmış bir kutu + etiket (çizge düğümü)."""
box = FancyBboxPatch(
(x - w / 2, y - h / 2), w, h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.0, zorder=2)
ax.add_patch(box)
ax.text(x, y, label, ha="center", va="center",
fontsize=fontsize, color=COL_TEXT, weight="bold", zorder=4)
return box
# ---------------------------------------------------------------------------
# _engine.py L9 §8 — BFS (ağırlıksız SP); omurga tanığı (Quiz 2)
# ---------------------------------------------------------------------------
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür.
'Henüz görülmemiş' kontrolü ilk (= en kısa) uzaklığı sabitler. O(V+E)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henüz görülmemiş
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
# ---------------------------------------------------------------------------
# _engine.py L11 §8 + L12 — kenar gevşetme + Bellman-Ford (genel SP)
# ---------------------------------------------------------------------------
def relax_edge(d, weight, u, v):
"""Kenar gevşetme: üçgen eşitsizliği ihlali varsa tahmini düşür."""
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
return True
return False
def _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (tanık → −∞ yayma)."""
seen = set(start)
stack = list(start)
while stack:
u = stack.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
return seen
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford: V−1 tur kenar gevşetme; V. turda hâlâ gevşeyen
düğümler TANIK → erişilenlere −∞ yay. O(V·E)."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1): # V−1 tur (δ_{V−1})
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
relax_edge(d, weight, u, v)
witnesses = set()
for u in adj: # V. tur: tanık tespiti
if d[u] == INF:
continue
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
witnesses.add(v)
for v in _reachable_from(adj, witnesses):
d[v] = -INF
return d
# ---------------------------------------------------------------------------
# _engine.py L13 §5-6 — ChangeablePQ + Dijkstra (ağırlıklı SP, w ≥ 0)
# ---------------------------------------------------------------------------
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü (cross-link). build O(n), delete_min/decrease_key O(log n)."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (cross-link ile O(1) bul). O(log n)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6): en yakını çıkar, kenarlarını gevşet, decrease_key
ile güncelle. Ağırlıklar ≥ 0 ŞART."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
# ---------------------------------------------------------------------------
# _engine.py L4 §6-9 — HashTableChaining (Las Vegas: hep doğru)
# ---------------------------------------------------------------------------
class HashTableChaining:
"""Zincirlemeli hash tablosu (L4 §6-9): m kova + her kovada zincir.
Çakışan anahtarlar aynı kovanın ZİNCİRİNE eklenir; aramada zincir lineer
taranır. Las Vegas: contains HEP doğru, zincir uzunsa bazen yavaş."""
def __init__(self, m):
self.m = m
self.buckets = [[] for _ in range(m)] # her kova bir zincir (list of (k,v))
self.n = 0
def _hash(self, key):
return key % self.m # division method
def insert(self, key, value=True):
idx = self._hash(key)
chain = self.buckets[idx]
for pos, (k, _v) in enumerate(chain):
if k == key:
chain[pos] = (key, value)
return
chain.append((key, value))
self.n += 1
def contains(self, key):
idx = self._hash(key)
return any(k == key for (k, _v) in self.buckets[idx])
def chain_lengths(self):
return [len(chain) for chain in self.buckets]
# ---------------------------------------------------------------------------
# _engine.py D31 (L20) §7 — Monte Carlo küme (hep hızlı, bazen yanlış)
# ---------------------------------------------------------------------------
class MonteCarloHashSet:
"""Monte Carlo küme (L20 §7, Ku): her kovada EN FAZLA 2 öğe sakla →
insert/contains HEP O(1) (hep verimli) ama taşan öğe kaybolur →
contains bazen YANLIŞ-NEGATİF (muhtemelen doğru). Las Vegas chaining
tam tersi: hep doğru, muhtemelen verimli."""
def __init__(self, m):
self.m = m
self.buckets = [[] for _ in range(m)]
self.dropped = 0 # taşan (kaybolan) öğe sayısı
def insert(self, key):
b = self.buckets[hash(key) % self.m]
if key in b:
return
if len(b) < 2: # yalnız ilk iki çarpışan
b.append(key)
else:
self.dropped += 1 # sessizce düşür → hata kaynağı
def contains(self, key):
return key in self.buckets[hash(key) % self.m] # ≤ 2 bakış: O(1)
def monte_carlo_demo(keys, m):
"""Tanık: aynı anahtarlar Monte Carlo kümeye eklenir; yanlış-negatif
sayısı == dropped (kaybolan tam olarak yanlış cevap verir); yanlış-
POZİTİF asla olmaz. Döndürür: (yanlış_negatif, dropped, yanlış_pozitif_var_mı)."""
s = MonteCarloHashSet(m)
for kx in keys:
s.insert(kx)
fneg = sum(1 for kx in set(keys) if not s.contains(kx))
fpos = any(s.contains(("yok", kx)) for kx in range(50))
return fneg, s.dropped, fpos
def sssp_backbone_check(adj):
"""Üç-ünite omurga tanığı (L20 §4): ağırlıksız çizgede üç algoritma
aynı δ — BFS (Quiz 2), Dijkstra(w=1) (genellik-runtime takası),
Bellman-Ford (en genel). Döndürür: üçü birebir mi (bool)."""
s = next(iter(adj))
w1 = {(u, v): 1 for u in adj for v in adj[u]}
delta, _ = bfs(adj, s)
dj = dijkstra(adj, w1, s)
bf = bellman_ford_classic(adj, w1, s)
return all(dj[v] == bf[v] == delta.get(v, INF) for v in adj)
# ---------------------------------------------------------------------------
# _viz.py — draw_lasvegas_montecarlo (L20 §7 İMZA figür yerleştirici)
# ---------------------------------------------------------------------------
def draw_lasvegas_montecarlo(ax, lv_buckets, lv_longest, lv_found, lv_total,
mc_buckets, mc_dropped, mc_dropped_keys,
mc_fneg, mc_fpos, m):
"""Las Vegas vs Monte Carlo iki-tur randomizasyon (L20 §7). Çizilen TÜM
sayılar çağıran hücreden (motordan canlı) gelir; bu fonksiyon yerleştirir."""
bucket_h = 0.9
row_gap = 1.05
cell_w = 0.62
cell_h = 0.6
L_x = 0.0
L_chain_x0 = 1.2
R_x = 13.0
R_chain_x0 = 14.2
top_y = 0.0
def _bucket_y(i):
return top_y - i * row_gap
title_y = top_y + bucket_h * 1.25
ax.text(L_chain_x0 + 2.3, title_y + 0.95, "LAS VEGAS",
ha="center", va="center", fontsize=15, color=COL_PRIMARY, weight="bold")
ax.text(L_chain_x0 + 2.3, title_y + 0.45, "hep DOĞRU, muhtemelen verimli",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", style="italic")
ax.text(R_chain_x0 + 1.6, title_y + 0.95, "MONTE CARLO",
ha="center", va="center", fontsize=15, color=COL_PRIMARY, weight="bold")
ax.text(R_chain_x0 + 1.6, title_y + 0.45, "hep VERİMLİ, muhtemelen doğru",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", style="italic")
# SOL — Las Vegas chaining (tam zincirler)
longest_idx = max(range(len(lv_buckets)), key=lambda i: len(lv_buckets[i]))
for i, chain in enumerate(lv_buckets):
y = _bucket_y(i)
is_longest = (i == longest_idx)
ax.add_patch(FancyBboxPatch(
(L_x, y), 0.95, cell_h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100 if is_longest else COL_BG,
ec=COL_ACCENT if is_longest else COL_PRIMARY,
linewidth=2.4 if is_longest else 1.6, zorder=3))
ax.text(L_x + 0.47, y + cell_h * 0.5, f"h={i}", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
prev_cx = L_x + 0.95
prev_cy = y + cell_h * 0.5
for c, key in enumerate(chain):
x = L_chain_x0 + c * cell_w
ax.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.9, cell_h, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if is_longest else COL_BG,
ec=COL_ACCENT if is_longest else COL_PRIMARY,
linewidth=2.2 if is_longest else 1.3, zorder=3))
ax.text(x + cell_w * 0.45, y + cell_h * 0.5, str(key),
ha="center", va="center", fontsize=8, color=COL_TEXT, zorder=4)
ax.add_patch(FancyArrowPatch(
(prev_cx, prev_cy), (x, prev_cy), arrowstyle="-|>",
mutation_scale=8, color=COL_ACCENT if is_longest else COL_SLATE_400,
linewidth=1.6 if is_longest else 1.0, zorder=2))
prev_cx = x + cell_w * 0.9
if is_longest:
ax.text(L_chain_x0 + len(chain) * cell_w + 0.15, y + cell_h * 0.5,
f"en uzun = {lv_longest}", ha="left", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=4)
badge_y_L = _bucket_y(m - 1) - 1.05
ax.add_patch(FancyBboxPatch(
(L_x, badge_y_L - 0.05), 5.7, 0.62,
boxstyle="round,pad=0.04,rounding_size=0.08",
fc="#cfe8da", ec="#3f7d5e", linewidth=2.0, zorder=3))
ax.text(L_x + 2.85, badge_y_L + 0.26, f"{lv_found}/{lv_total} bulundu ✓",
ha="center", va="center", fontsize=12, color="#1f5137",
weight="bold", zorder=4)
ax.text(L_x + 2.85, badge_y_L - 0.55, "hashing böyledir — bazen zincir uzun",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=4)
# SAĞ — Monte Carlo (≤2 öğe; taşanlar kırmızı çarpı)
for i in range(m):
y = _bucket_y(i)
kept = mc_buckets[i]
dropped = mc_dropped_keys[i]
ax.add_patch(FancyBboxPatch(
(R_x, y), 0.95, cell_h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(R_x + 0.47, y + cell_h * 0.5, f"h={i}", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
prev_cx = R_x + 0.95
prev_cy = y + cell_h * 0.5
for c, key in enumerate(kept):
x = R_chain_x0 + c * cell_w
ax.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.9, cell_h, boxstyle="square,pad=0.0",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.3, zorder=3))
ax.text(x + cell_w * 0.45, y + cell_h * 0.5, str(key),
ha="center", va="center", fontsize=8, color=COL_TEXT, zorder=4)
ax.add_patch(FancyArrowPatch(
(prev_cx, prev_cy), (x, prev_cy), arrowstyle="-|>",
mutation_scale=8, color=COL_SLATE_400, linewidth=1.0, zorder=2))
prev_cx = x + cell_w * 0.9
for c, key in enumerate(dropped):
x = R_chain_x0 + (len(kept) + c) * cell_w
ax.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.9, cell_h, boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_DROP, linewidth=1.3, zorder=3))
ax.text(x + cell_w * 0.45, y + cell_h * 0.5, str(key),
ha="center", va="center", fontsize=7.5, color=COL_DROP,
zorder=4, alpha=0.85)
ax.plot([x + 0.04, x + cell_w * 0.9 - 0.04], [y + 0.04, y + cell_h - 0.04],
color=COL_DROP, linewidth=1.6, zorder=5)
ax.plot([x + 0.04, x + cell_w * 0.9 - 0.04], [y + cell_h - 0.04, y + 0.04],
color=COL_DROP, linewidth=1.6, zorder=5)
drop_col_cx = R_chain_x0 + 3.5 * cell_w
drop_label_y = _bucket_y(0) + cell_h + 0.55
ax.text(drop_col_cx, drop_label_y, f"DÜŞÜRÜLDÜ {mc_dropped}",
ha="center", va="center", fontsize=10.5, color=COL_DROP,
weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(drop_col_cx, drop_label_y - 0.22), (drop_col_cx, _bucket_y(0) + cell_h + 0.02),
arrowstyle="-|>", mutation_scale=11, color=COL_DROP, linewidth=1.6, zorder=6))
badge_y_R = _bucket_y(m - 1) - 1.05
ax.add_patch(FancyBboxPatch(
(R_x, badge_y_R - 0.05), 7.0, 0.62,
boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(R_x + 3.5, badge_y_R + 0.26,
f"contains hep O(1) AMA {mc_fneg}/{lv_total} yanlış-negatif",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=4)
fpos_txt = "yanlış-POZİTİF asla (asimetri)" if not mc_fpos \
else "yanlış-pozitif GÖRÜLDÜ (!)"
ax.text(R_x + 3.5, badge_y_R - 0.55, fpos_txt, ha="center", va="center",
fontsize=9.5, color=COL_DROP, style="italic", weight="bold", zorder=4)
# ORTA köprü — takas + Ku alıntısı
mid_x = (L_chain_x0 + 4.0 + R_x) / 2.0 - 0.3
mid_y_center = _bucket_y((m - 1) / 2.0) + cell_h * 0.5
box_w, box_h = 4.2, 3.0
ax.add_patch(FancyBboxPatch(
(mid_x - box_w / 2, mid_y_center - box_h / 2), box_w, box_h,
boxstyle="round,pad=0.06,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.2, zorder=6))
ax.text(mid_x, mid_y_center + box_h / 2 - 0.45, "TAKAS",
ha="center", va="center", fontsize=12.5, color=COL_PRIMARY,
weight="bold", zorder=7)
ax.text(mid_x, mid_y_center + 0.55, "doğruluk ⟷ süre\ngarantisi",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=7)
ax.text(mid_x, mid_y_center - 0.45, "birini sabitle,\ndiğerini olasılaştır",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=7)
ax.text(mid_x, mid_y_center - box_h / 2 + 0.42, "Ku: “I pay for precision with time”",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=7)
ax.add_patch(FancyArrowPatch(
(mid_x - box_w / 2 - 0.05, mid_y_center), (L_chain_x0 + 4.05, mid_y_center),
arrowstyle="<|-", mutation_scale=13, color=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.add_patch(FancyArrowPatch(
(mid_x + box_w / 2 + 0.05, mid_y_center), (R_x - 0.05, mid_y_center),
arrowstyle="-|>", mutation_scale=13, color=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.set_xlim(L_x - 0.5, R_chain_x0 + 6.4 * cell_w + 2.2)
ax.set_ylim(_bucket_y(m - 1) - 1.9, title_y + 1.4)
ax.set_aspect("equal")
ax.axis("off")
return ax
```
## 1. 6.006'nın 4 Hedefi {#sec-1-6006nin-4-hedefi}
Ders dört (aslında 3+1) hedef üzerine kuruluydu:
1. **Zor hesaplama problemlerini çöz** — algoritma üret (6.0001/6.009'daki gibi "bilgisayara çözdüğünü göster").
2. **Doğruluğu kanıtla** — her geçerli girdi için doğru çıktı; sonsuz girdi uzayı → özyineleme + tümevarım. "Bu ders aslında **uygulamalı 6.042**'dir."
3. **Verimliliği kanıtla** — "iyi" ne demek? **Hesaplama modeli** (word-RAM) + asimptotik + **ölçeklenebilirlik** (performans, girdi büyüme oranına göre).
4. **İnsanlara iletişim** — en önemlisi. Kod doğru olsa bile ne yaptığı anlaşılmazsa tam puan yok.
> *"your algorithm might be correct or efficient, but you need to be able to communicate that to humans."* — Ku
Bilgisayar bilimi büyük ölçüde **başkalarıyla** çalışmaktır; ne yaptığını ve neden doğru/verimli olduğunu iletemezsen sınırlısın. @fig-four-goals dört hedefi soldan sağa kademeli bir disiplin olarak dizer ve dördüncü kademeyi (iletişim) amber/büyük olarak öne çıkarır.
```{python}
#| label: fig-four-goals
#| fig-cap: "6.006'nın dört hedefi (Ku L20 §1): bir algoritmayı yalnız çözmek değil, doğruluğunu ve verimliliğini KANITLAYIP İNSANLARA İLETMEK. Soldan sağa DÖRT kademe (akış oklarıyla bağlı): (1) ZOR PROBLEMİ ÇÖZ — algoritma tasarla; (2) DOĞRULUĞU KANITLA — özyineleme + tümevarım 'uygulamalı 6.042'; (3) VERİMLİLİĞİ KANITLA — word-RAM + asimptotik + ölçeklenebilirlik; (4) İNSANLARA İLET — EN ÖNEMLİSİ (amber, büyük), Ku alıntısı 'your algorithm might be correct or efficient, but you need to be able to communicate that to humans'. Alt şerit: doğru ama anlaşılmayan kod TAM PUAN ALMAZ — bilgisayar bilimi büyük ölçüde BAŞKALARIYLA çalışmaktır. KAVRAMSAL figür (sayı yok)."
#| fig-width: 11.5
#| fig-height: 5.5
# fig-four-goals (L20 §1): dört hedef. KAVRAMSAL — sayı yok (asimptotik/sınıf).
_GOALS = [
{"no": "1", "name": "ZOR PROBLEMİ\nÇÖZ",
"desc": "Hesaplama problemini\nbir algoritmayla çöz.", "accent": False},
{"no": "2", "name": "DOĞRULUĞU\nKANITLA",
"desc": "Özyineleme + tümevarım\n— \"uygulamalı 6.042\".", "accent": False},
{"no": "3", "name": "VERİMLİLİĞİ\nKANITLA",
"desc": "word-RAM + asimptotik\n+ ölçeklenebilirlik.", "accent": False},
{"no": "4", "name": "İNSANLARA\nİLET",
"desc": "Algoritmanı başkalarına\nANLATABİLMELİSİN.", "accent": True},
]
_KU_QUOTE = ('"your algorithm might be correct or efficient, but you need\n'
'to be able to communicate that to humans"')
assert len(_GOALS) == 4 and _GOALS[3]["accent"] is True
assert all(not g["accent"] for g in _GOALS[:3])
fig, ax = plt.subplots(figsize=(11.5, 5.5))
fig.patch.set_facecolor(COL_WHITE)
base_w, base_h = 2.35, 2.30
big_w, big_h = 3.05, 2.95
gap = 0.62
y_mid = 2.95
xs = []
cursor = 0.55
for g in _GOALS:
w = big_w if g["accent"] else base_w
xs.append(cursor + w * 0.5)
cursor += w + gap
box_geom = []
for k, g in enumerate(_GOALS):
cx = xs[k]
accent = g["accent"]
w = big_w if accent else base_w
h = big_h if accent else base_h
bot = y_mid - h * 0.5
top = y_mid + h * 0.5
box_geom.append((cx, w, h, top, bot))
if accent:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 3.2
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 2.0
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, bot), w, h, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=3))
rno = 0.27 if accent else 0.23
rx, ry = cx - w * 0.5 + rno + 0.06, top - rno - 0.06
ax.add_patch(Circle((rx, ry), rno,
facecolor=COL_ACCENT if accent else COL_PRIMARY,
edgecolor=COL_WHITE, linewidth=1.8, zorder=6))
ax.text(rx, ry, g["no"], ha="center", va="center",
fontsize=12 if accent else 11, color=COL_WHITE, weight="bold", zorder=7)
name_y = y_mid + (0.62 if accent else 0.38)
ax.text(cx, name_y, g["name"], ha="center", va="center",
fontsize=15 if accent else 13,
color=COL_AMBER_700 if accent else COL_TEXT,
weight="bold", zorder=7, linespacing=1.05)
desc_y = y_mid - (0.32 if accent else 0.42)
ax.text(cx, desc_y, g["desc"], ha="center", va="center",
fontsize=9.0 if accent else 8.8,
color=COL_TEXT if accent else COL_SLATE_500, zorder=7,
linespacing=1.15, style="normal" if accent else "italic")
if accent:
ax.add_patch(FancyBboxPatch(
(cx - 1.02, top + 0.10), 2.04, 0.46,
boxstyle="round,pad=0.02,rounding_size=0.12",
fc=COL_ACCENT, ec=COL_AMBER_700, linewidth=1.8, zorder=8))
ax.text(cx, top + 0.33, "EN ÖNEMLİSİ", ha="center", va="center",
fontsize=11, color=COL_WHITE, weight="bold", zorder=9)
ax.text(cx, bot + 0.46, _KU_QUOTE, ha="center", va="center",
fontsize=7.4, color=COL_AMBER_700, style="italic",
zorder=7, linespacing=1.2)
ax.text(cx, bot + 0.05, "— Jason Ku, L20", ha="center", va="top",
fontsize=6.8, color=COL_SLATE_500, zorder=7)
for k in range(len(box_geom) - 1):
cx0, w0, _h0, _t0, _b0 = box_geom[k]
cx1, w1, _h1, _t1, _b1 = box_geom[k + 1]
x_start = cx0 + w0 * 0.5 + 0.06
x_end = cx1 - w1 * 0.5 - 0.06
last = (k == len(box_geom) - 2)
ax.add_patch(FancyArrowPatch(
(x_start, y_mid), (x_end, y_mid), arrowstyle="-|>",
mutation_scale=20 if last else 16,
color=COL_AMBER_600 if last else COL_SLATE_400,
linewidth=3.0 if last else 2.2, zorder=2))
fig.suptitle(
"6.006'nın dört hedefi — bir algoritmayı yalnız çözmek değil, "
"doğruluğunu ve verimliliğini KANITLAYIP İNSANLARA İLETMEK",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.965)
strip_left = 0.30
strip_right = cursor - gap
strip_top = y_mid - max(big_h, base_h) * 0.5 - 0.30
strip_h = 0.78
ax.add_patch(FancyBboxPatch(
(strip_left, strip_top - strip_h), strip_right - strip_left, strip_h,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_AMBER_300, linewidth=1.6, zorder=2))
ax.text((strip_left + strip_right) * 0.5, strip_top - strip_h * 0.5,
"doğru ama anlaşılmayan kod TAM PUAN ALMAZ — "
"bilgisayar bilimi büyük ölçüde BAŞKALARIYLA çalışmaktır",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.set_xlim(0.0, cursor - gap + 0.55)
ax.set_ylim(strip_top - strip_h - 0.30, y_mid + big_h * 0.5 + 0.85)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 2. Karmaşıklık — Final İçin (L19 Özeti) {#sec-2-karmasiklik-final-icin}
L19 (Ders 28) hiçbir ödevde işlenmedi; final'de **tanımlar** test edilir. Mesaj: çoğu problem "iyi" (polinom) çözülemez — **ama** önemsediğimiz problemler **rastgele değildir**: ya **certificate ile polinom-zamanda doğrulanır** (NP) ya da **üstel kaba kuvvetle** çözülür.
> *"the problems we think about are not random."* — Ku
Final'de beklenenler: P/NP/EXP **iç içe geçişi** ($EXP \supseteq NP \supseteq P$), **reduction yönü** (A'yı zor-bilinen B'ye indirgersen A da zordur), **hard vs complete** ayrımı. Genelde doğru/yanlış sorusu. @fig-final-defs bu üç tanımı yan yana üç mini-kartla toplar.
```{python}
#| label: fig-final-defs
#| fig-cap: "Final hazırlığı — L19 tanımları (L20 §2): sınıflar · reduction yönü · hard vs complete. KART 1 'iç içe kümeler': EXP ⊇ NP ⊇ P iç içe bant (önemsediğimiz problemler rastgele değil — ya NP'de polinom-DOĞRULANABİLİR ya da üstel kaba kuvvetle ÇÖZÜLEBİLİR). KART 2 'reduction yönü': DOĞRU yön amber ok — bilinen-ZOR A ≤ hedef B ⟹ B ZOR; TERS yön kırmızı çarpı (A'yı zor YAPMAZ). KART 3 'hard vs complete': NP-hard = alt sınır (NP DIŞINA taşabilir); NP-complete = NP ∩ NP-hard. Alt şerit: tanımları EZBER değil KAVRA + Ku tanığı 'the problems we think about are not random'. KAVRAMSAL figür (sayı yok)."
#| fig-width: 11.5
#| fig-height: 5.2
# fig-final-defs (L20 §2): L19 tanımları. KAVRAMSAL — sayı yok.
COL_WRONG = "#b91c1c" # red-700 — ters reduction yönü (yanlış) işareti
fig, ax = plt.subplots(figsize=(11.5, 5.2))
fig.patch.set_facecolor(COL_WHITE)
ax.set_facecolor(COL_WHITE)
card_y0, card_y1 = 1.05, 7.55
card_w = 3.55
gap = 0.55
x0 = 0.30
card_x = [x0 + i * (card_w + gap) for i in range(3)]
def _card_frame(cx, title):
ax.add_patch(FancyBboxPatch(
(cx, card_y0), card_w, card_y1 - card_y0,
boxstyle="round,pad=0.04,rounding_size=0.14",
fc=COL_WHITE, ec=COL_PRIMARY, linewidth=1.7, zorder=2))
ax.add_patch(FancyBboxPatch(
(cx + 0.10, card_y1 - 0.78), card_w - 0.20, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.2, zorder=3))
ax.text(cx + card_w / 2, card_y1 - 0.47, title, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4)
return cx + card_w / 2
# KART 1 — iç içe kümeler: EXP ⊇ NP ⊇ P
c1 = _card_frame(card_x[0], "1 · iç içe kümeler")
ax.add_patch(FancyBboxPatch(
(c1 - 1.45, 2.05), 2.90, 3.85, boxstyle="round,pad=0.02,rounding_size=0.18",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=1.8, zorder=3))
ax.text(c1, 5.62, "EXP", ha="center", va="center", fontsize=10.5,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(c1 + 1.40, 5.62, "üstel kaba\nkuvvetle çözülür", ha="right", va="center",
fontsize=6.6, color=COL_AMBER_700, style="italic", zorder=6)
ax.add_patch(FancyBboxPatch(
(c1 - 1.10, 2.40), 2.20, 2.70, boxstyle="round,pad=0.02,rounding_size=0.16",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.8, zorder=4))
ax.text(c1, 4.78, "NP", ha="center", va="center", fontsize=10.5,
color=COL_TEXT, weight="bold", zorder=6)
ax.text(c1, 4.45, "polinomda\nDOĞRULANABİLİR", ha="center", va="center",
fontsize=6.4, color=COL_PRIMARY, zorder=6)
ax.add_patch(FancyBboxPatch(
(c1 - 0.72, 2.70), 1.44, 1.30, boxstyle="round,pad=0.02,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=5))
ax.text(c1, 3.55, "P", ha="center", va="center", fontsize=10.5,
color=COL_TEXT, weight="bold", zorder=6)
ax.text(c1, 3.18, "polinomda\nÇÖZÜLÜR", ha="center", va="center",
fontsize=6.4, color=COL_PRIMARY, zorder=6)
ax.text(c1, 1.62, "P ⊆ NP ⊆ EXP", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
# KART 2 — reduction yönü
c2 = _card_frame(card_x[1], "2 · reduction yönü")
ax_lx = card_x[1] + 0.55
ax_rx = card_x[1] + card_w - 0.55
yA = 5.55
ax.add_patch(FancyBboxPatch(
(ax_lx - 0.62, yA - 0.34), 1.24, 0.66, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(ax_lx, yA + 0.06, "A", ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(ax_lx, yA - 0.20, "bilinen-ZOR", ha="center", va="center",
fontsize=6.2, color=COL_AMBER_700, zorder=5)
ax.add_patch(FancyBboxPatch(
(ax_rx - 0.62, yA - 0.34), 1.24, 0.66, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=4))
ax.text(ax_rx, yA + 0.06, "B", ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=5)
ax.text(ax_rx, yA - 0.20, "hedef", ha="center", va="center",
fontsize=6.2, color=COL_PRIMARY, zorder=5)
ax.add_patch(FancyArrowPatch(
(ax_lx + 0.66, yA), (ax_rx - 0.66, yA), arrowstyle="-|>",
mutation_scale=16, color=COL_ACCENT, linewidth=2.6, zorder=5, shrinkA=2, shrinkB=2))
ax.text((ax_lx + ax_rx) / 2, yA + 0.30, "A ≤ B", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text((ax_lx + ax_rx) / 2, yA - 0.62, "⟹ B de ZOR", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text((card_x[1] + card_w / 2), yA + 0.66, "DOĞRU", ha="center", va="center",
fontsize=8.0, color=COL_ACCENT, weight="bold", zorder=5)
yW = 3.85
ax.add_patch(FancyBboxPatch(
(ax_lx - 0.62, yW - 0.34), 1.24, 0.66, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=4))
ax.text(ax_lx, yW + 0.02, "B", ha="center", va="center", fontsize=10,
color=COL_SLATE_500, weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(ax_rx - 0.62, yW - 0.34), 1.24, 0.66, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=4))
ax.text(ax_rx, yW + 0.02, "A", ha="center", va="center", fontsize=10,
color=COL_SLATE_500, weight="bold", zorder=5)
ax.add_patch(FancyArrowPatch(
(ax_lx + 0.66, yW), (ax_rx - 0.66, yW), arrowstyle="-|>",
mutation_scale=13, color=COL_SLATE_400, linewidth=1.6, zorder=4, shrinkA=2, shrinkB=2))
xc, yc = (ax_lx + ax_rx) / 2, yW
ax.plot([xc - 0.22, xc + 0.22], [yc - 0.22, yc + 0.22],
color=COL_WRONG, linewidth=3.0, zorder=7, solid_capstyle="round")
ax.plot([xc - 0.22, xc + 0.22], [yc + 0.22, yc - 0.22],
color=COL_WRONG, linewidth=3.0, zorder=7, solid_capstyle="round")
ax.text((card_x[1] + card_w / 2), yW - 0.62, "ters yön A'yı zor YAPMAZ",
ha="center", va="center", fontsize=7.8, color=COL_WRONG, weight="bold", zorder=5)
ax.text((card_x[1] + card_w / 2), yW + 0.62, "YANLIŞ", ha="center", va="center",
fontsize=8.0, color=COL_WRONG, weight="bold", zorder=5)
ax.text(card_x[1] + card_w / 2, 2.32,
"Kural: bilinen-zor A'yı hedef B'ye\nindirge → B zor.",
ha="center", va="center", fontsize=7.0, color=COL_PRIMARY, zorder=5)
ax.text(card_x[1] + card_w / 2, 1.55,
"L20 özeti aynı şey: \"A'yı zor-bilinen\nyöne indirgeme\" = bu yön.",
ha="center", va="center", fontsize=6.6, color=COL_SLATE_500,
style="italic", zorder=5)
# KART 3 — hard vs complete
c3 = _card_frame(card_x[2], "3 · hard vs complete")
npx0 = c3 - 1.35
ax.add_patch(FancyBboxPatch(
(npx0, 3.55), 1.95, 2.35, boxstyle="round,pad=0.02,rounding_size=0.16",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=3))
ax.text(npx0 + 0.48, 5.65, "NP", ha="center", va="center", fontsize=10,
color=COL_TEXT, weight="bold", zorder=6)
nhx0 = c3 - 0.30
ax.add_patch(FancyBboxPatch(
(nhx0, 3.20), 2.05, 2.95, boxstyle="round,pad=0.02,rounding_size=0.16",
fc="none", ec=COL_AMBER_600, linewidth=2.2, zorder=4))
ax.text(nhx0 + 1.55, 5.92, "NP-hard", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(nhx0 + 1.62, 3.42, "NP dışına\nTAŞABİLİR", ha="center", va="center",
fontsize=6.2, color=COL_AMBER_700, style="italic", zorder=6)
ax.add_patch(FancyBboxPatch(
(nhx0 - 0.02, 3.92), 0.92, 1.55, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=5))
ax.text(nhx0 + 0.44, 4.92, "NP-\ncomp.", ha="center", va="center",
fontsize=7.0, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(c3, 2.62, "NP-hard: alt sınır (≥ tüm NP)", ha="center", va="center",
fontsize=7.4, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(c3, 2.18, "NP-complete = NP ∩ NP-hard", ha="center", va="center",
fontsize=7.4, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(c3, 1.60, "(hem NP'de hem NP-hard)", ha="center", va="center",
fontsize=6.6, color=COL_SLATE_500, style="italic", zorder=5)
# ALT ŞERİT
strip_y0, strip_h = -0.55, 1.35
ax.add_patch(FancyBboxPatch(
(0.10, strip_y0), card_x[2] + card_w - 0.40, strip_h,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_600, linewidth=1.6, zorder=2))
ax.text((card_x[2] + card_w) / 2 + 0.05, strip_y0 + strip_h - 0.42,
"Final genelde DOĞRU/YANLIŞ sorusu — tanımları EZBER değil KAVRA",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4)
ax.text((card_x[2] + card_w) / 2 + 0.05, strip_y0 + 0.34,
"Ku: önemsediğimiz problemler RASTGELE DEĞİL — "
"\"the problems we think about are not random\"",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700,
style="italic", zorder=4)
fig.suptitle(
"Final hazırlığı — L19 tanımları: sınıflar · reduction yönü · hard vs complete",
color=COL_TEXT, fontsize=13, weight="bold", y=0.985)
ax.set_xlim(-0.1, card_x[2] + card_w + 0.35)
ax.set_ylim(-0.75, 8.05)
ax.axis("off")
plt.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()
```
## 3. Üç Ünite — Quiz 1: Veri Yapıları (Kara Kutular) {#sec-3-quiz-1-veri-yapilari}
Sabit-olmayan boyutta girdide **bir şey bulmak**. İki sorgu tipi: **dizi (extrinsic sıra)** vs **küme (intrinsic anahtar)**.
- **Dizi:** dinamik dizi (Python list — en yaygın; sona ekle/çıkar süper) ve sıra AVL (ortaya ekleme için).
- **Küme:** hash table (sözlük işlemleri $O(1)$ beklenen), küme AVL (dinamik **sıralı** işlemler: önceki/sonraki), sıralı dizi (statikse yeterli).
Sonra bu veri yapılarını **sıralama** için kullandık: öncelik kuyruğu sıralaması (dizi/sıralı dizi → $n^2$), **heap sort** ($n \log n$), AVL sort, ve **counting/radix** (direct access array → lineer, polinom-sınırlı sayılar).
Bu ünite, sonraki ikisiyle birlikte **tek bir omurganın** ilk parçasıdır. @fig-three-units bu üç üniteyi tek özyinelemeli hikâye olarak (bul → ilişkilendir → inşa et) yan yana dizer; bu **İMZA figür** §3, §4 ve §5'i birden kapsar.
```{python}
#| label: fig-three-units
#| fig-cap: "Üç ünite, tek omurga (Ku L20 §3-5 İMZA): Quiz 1 (veri yapıları + sıralama) → Quiz 2 (çizgeler) → Quiz 3 (DP = çizge inşası). PANO 1 'Quiz 1 — bir şey BUL': iki kara kutu DİZİ (sıra: dinamik dizi / sıra-AVL) vs KÜME (anahtar: hash / küme-AVL / sıralı dizi); sıralama şeridi n² → n log n → lineer (kümeyi/sırayı HIZLANDIRIR). PANO 2 'Quiz 2 — İLİŞKİLER': düğüm=durum kenar=geçiş mini-çizge; SSSP merdiveni BFS → DAG ilişki → Dijkstra(w≥0) → Bellman-Ford (kısıt gevşedikçe süre doğrusaldan uzaklaşır). PANO 3 'Quiz 3 — çizgeyi SEN KUR': SRTBOT → alt-problem DAG'ı (alt problem=düğüm, bağımlılık=kenar, T=DAG); Ku alıntıları 'quiz 3 material as really an application of the graph material' + 'creative process in trying to construct that graph'. Üç pano amber oklarla bağlı; alt rozet 'tek özyinelemeli hikâye: BUL → İLİŞKİLENDİR → İNŞA ET'. KAVRAMSAL sentez (asimptotik etiketler sınıf adıdır, ölçülmüş rakam değil)."
#| fig-width: 12.5
#| fig-height: 6.0
# fig-three-units (L20 §3-5 İMZA): üç ünite tek omurga. KAVRAMSAL sentez.
def _panel(ax, bx, by, bw, bh, accent=False, lw_acc=2.8, lw=1.9):
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.05,rounding_size=0.16",
fc=COL_WHITE, ec=COL_ACCENT if accent else COL_PRIMARY,
linewidth=lw_acc if accent else lw, zorder=2))
def _chip(ax, cx, cy, w, h, label, accent=False, fontsize=8.0, sub=None):
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, cy - h * 0.5), w, h, boxstyle="round,pad=0.015,rounding_size=0.05",
fc=COL_AMBER_100 if accent else COL_BG, ec=COL_ACCENT if accent else COL_PRIMARY,
linewidth=1.9 if accent else 1.4, zorder=4))
ax.text(cx, cy + (0.055 if sub else 0.0), label, ha="center", va="center",
fontsize=fontsize, color=COL_AMBER_700 if accent else COL_TEXT,
weight="bold", zorder=5)
if sub:
ax.text(cx, cy - h * 0.30, sub, ha="center", va="center",
fontsize=fontsize - 2.0, color=COL_SLATE_500, zorder=5)
def _draw_mini_relation_graph(ax, ox, oy, scale):
pos = {"u": (0.0, 1.0), "v": (1.0, 1.4), "w": (1.0, 0.5),
"x": (2.0, 1.0), "y": (2.0, 0.0)}
edges = [("u", "v", False), ("u", "w", False), ("v", "x", True),
("w", "x", False), ("w", "y", False)]
r = 0.16
def P(node):
gx, gy = pos[node]
return ox + gx * scale, oy + gy * scale
for a, b, hot in edges:
ax_, ay_ = P(a)
bx_, by_ = P(b)
ax.add_patch(FancyArrowPatch(
(ax_, ay_), (bx_, by_), arrowstyle="-|>", mutation_scale=11,
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.4 if hot else 1.4,
shrinkA=r * scale * 1.05, shrinkB=r * scale * 1.05, zorder=2))
for node in pos:
x, y = P(node)
ax.add_patch(Circle((x, y), r * scale, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.5, zorder=5))
ux, uy = P("u")
ax.text(ux - r * scale - 0.04, uy, "düğüm =\ndurum", ha="right", va="center",
fontsize=6.6, color=COL_SLATE_500, style="italic", linespacing=1.0, zorder=6)
vx, vy = P("v")
xx, xy = P("x")
ax.text((vx + xx) * 0.5, (vy + xy) * 0.5 + 0.16, "kenar =\ngeçiş",
ha="center", va="bottom", fontsize=6.6, color=COL_AMBER_700,
style="italic", linespacing=1.0, zorder=6)
def _draw_mini_dag(ax, ox, oy, scale):
pos = {"s0": (0.0, 0.5), "s1": (1.0, 1.0), "s2": (1.0, 0.0), "s3": (2.0, 0.5)}
edges = [("s0", "s1"), ("s0", "s2"), ("s1", "s3"), ("s2", "s3")]
r = 0.15
def P(node):
gx, gy = pos[node]
return ox + gx * scale, oy + gy * scale
for a, b in edges:
ax_, ay_ = P(a)
bx_, by_ = P(b)
ax.add_patch(FancyArrowPatch(
(ax_, ay_), (bx_, by_), arrowstyle="-|>", mutation_scale=11,
color=COL_AMBER_600, linewidth=1.9,
shrinkA=r * scale * 1.05, shrinkB=r * scale * 1.05, zorder=2))
for node in pos:
x, y = P(node)
ax.add_patch(Circle((x, y), r * scale, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=1.8, zorder=5))
ax.text(x, y, "alt-\nprob", ha="center", va="center", fontsize=5.4,
color=COL_AMBER_700, weight="bold", linespacing=0.9, zorder=6)
def _fill_panel1(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
ax.text(cx, by + bh - 0.40, "Quiz 1 — bir şey BUL", ha="center", va="center",
fontsize=11.5, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(cx, by + bh - 0.82, "iki kara kutu: SIRA tut · ANAHTARLA bul",
ha="center", va="center", fontsize=7.8, color=COL_SLATE_500,
style="italic", zorder=6)
col_w = bw * 0.42
lx = bx + bw * 0.27
rx = bx + bw * 0.73
head_y = by + bh - 1.45
_chip(ax, lx, head_y, col_w, 0.42, "DİZİ (sıra)", accent=False, fontsize=8.8)
_chip(ax, rx, head_y, col_w, 0.42, "KÜME (anahtar)", accent=True, fontsize=8.8)
for s, iy0 in [(["dinamik dizi", "sıra-AVL"], lx), (["hash", "küme-AVL", "sıralı dizi"], rx)]:
iy = head_y - 0.55
for label in s:
ax.text(iy0, iy, "· " + label, ha="center", va="center", fontsize=7.6,
color=COL_TEXT if iy0 == lx else COL_AMBER_700, zorder=6)
iy -= 0.34
strip_y = by + 0.92
ax.text(cx, strip_y + 0.55, "sıralama — kümeyi/sırayı HIZLANDIRIR",
ha="center", va="center", fontsize=8.0, color=COL_PRIMARY,
weight="bold", zorder=6)
stages = [("PQ-sort", "n²", COL_AMBER_300, COL_AMBER_700),
("heap-sort", "n log n", COL_AMBER_100, COL_AMBER_600),
("counting/radix", "lineer", "#cfe8da", "#3f7d5e")]
seg_w = (bw - 0.7) / 3.0
sx = bx + 0.35
for i, (name, cost, fc, ec) in enumerate(stages):
x0 = sx + i * seg_w
ax.add_patch(FancyBboxPatch(
(x0, strip_y - 0.20), seg_w * 0.92, 0.40,
boxstyle="round,pad=0.01,rounding_size=0.05", fc=fc, ec=ec,
linewidth=1.6, zorder=4))
ax.text(x0 + seg_w * 0.46, strip_y + 0.04, name, ha="center", va="center",
fontsize=6.8, color=COL_TEXT, weight="bold", zorder=5)
ax.text(x0 + seg_w * 0.46, strip_y - 0.13, cost, ha="center", va="center",
fontsize=7.4, color=ec, weight="bold", family="monospace", zorder=5)
if i < 2:
ax.add_patch(FancyArrowPatch(
(x0 + seg_w * 0.92, strip_y), (x0 + seg_w, strip_y),
arrowstyle="-|>", mutation_scale=9, color=COL_AMBER_700,
linewidth=1.4, zorder=5))
ax.text(cx, strip_y - 0.50, "yavaştan hıza: n² → n log n → lineer",
ha="center", va="center", fontsize=6.8, color=COL_SLATE_500,
style="italic", zorder=6)
def _fill_panel2(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
ax.text(cx, by + bh - 0.40, "Quiz 2 — İLİŞKİLER", ha="center", va="center",
fontsize=11.5, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(cx, by + bh - 0.82, "düğüm = durum · kenar = geçiş", ha="center",
va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=6)
gscale = 0.62
gox = bx + (bw - 2.0 * gscale) * 0.5
goy = by + bh - 2.55
_draw_mini_relation_graph(ax, gox, goy, gscale)
ax.text(cx, by + 1.95, "SSSP merdiveni — kısıt vs süre", ha="center",
va="center", fontsize=8.0, color=COL_PRIMARY, weight="bold", zorder=6)
ladder = [("BFS", "ağırlıksız"), ("DAG ilişki", "topolojik sıra"),
("Dijkstra", "w ≥ 0"), ("Bellman-Ford", "genel · neg. çevrim tespiti")]
ry = by + 1.55
for name, cons in ladder:
_chip(ax, bx + bw * 0.30, ry, bw * 0.40, 0.30, name, accent=False, fontsize=7.2)
ax.text(bx + bw * 0.56, ry, cons, ha="left", va="center",
fontsize=6.6, color=COL_AMBER_700, style="italic", zorder=6)
ry -= 0.40
ax.text(cx, ry - 0.02, "kısıt gevşedikçe süre doğrusaldan uzaklaşır",
ha="center", va="center", fontsize=6.8, color=COL_SLATE_500,
style="italic", zorder=6)
def _fill_panel3(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
ax.text(cx, by + bh - 0.40, "Quiz 3 — çizgeyi SEN KUR", ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(cx, by + bh - 0.82, "çizge VERİLMEZ — SEN kurarsın", ha="center",
va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=6)
srt_y = by + bh - 1.55
ax.add_patch(FancyBboxPatch(
(bx + bw * 0.12, srt_y - 0.26), bw * 0.76, 0.52,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(cx, srt_y, "SRTBOT", ha="center", va="center", fontsize=10.5,
color=COL_AMBER_700, weight="bold", family="monospace", zorder=5)
ax.text(cx, srt_y - 0.46, "Subproblem · Relate · Topo · Base · Original · Time",
ha="center", va="center", fontsize=5.6, color=COL_SLATE_500,
style="italic", zorder=5)
ax.add_patch(FancyArrowPatch(
(cx, srt_y - 0.60), (cx, srt_y - 0.95), arrowstyle="-|>",
mutation_scale=14, color=COL_AMBER_700, linewidth=2.0, zorder=5))
dscale = 0.62
dox = bx + (bw - 2.0 * dscale) * 0.5
doy = by + 1.55
_draw_mini_dag(ax, dox, doy, dscale)
ax.text(cx, by + 1.15, "alt problem = düğüm · bağımlılık = kenar · T = DAG",
ha="center", va="center", fontsize=7.2, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(cx, by + 0.66,
"“quiz 3 material as really an application\nof the graph material”",
ha="center", va="center", fontsize=6.6, color=COL_TEXT,
style="italic", linespacing=1.05, zorder=6)
ax.text(cx, by + 0.18,
"“creative process in trying to\nconstruct that graph”",
ha="center", va="center", fontsize=6.6, color=COL_SLATE_500,
style="italic", linespacing=1.05, zorder=6)
fig, ax = plt.subplots(figsize=(12.5, 6.0))
fig.patch.set_facecolor(COL_WHITE)
bw, bh = 3.55, 4.55
gap = 1.45
by = 0.0
box_x = [0.0, bw + gap, 2 * (bw + gap)]
accents = [False, False, True]
fillers = [_fill_panel1, _fill_panel2, _fill_panel3]
for k in range(3):
_panel(ax, box_x[k], by, bw, bh, accent=accents[k])
fillers[k](ax, box_x[k], by, bw, bh)
arrow_y = by + bh * 0.5
flow_labels = ["bul →\nilişkilendir", "ilişkilendir →\ninşa et"]
for k in (0, 1):
x_from = box_x[k] + bw + 0.05
x_to = box_x[k + 1] - 0.05
xm = (x_from + x_to) * 0.5
ax.add_patch(FancyArrowPatch(
(x_from, arrow_y), (x_to, arrow_y), arrowstyle="-|>",
mutation_scale=20, color=COL_ACCENT, linewidth=3.0, zorder=6))
ax.text(xm, arrow_y + 0.46, flow_labels[k], ha="center", va="center",
fontsize=6.6, color=COL_AMBER_700, weight="bold",
style="italic", linespacing=1.0, zorder=7)
badge_y = by - 0.62
bx0 = box_x[0] + bw * 0.10
bx1 = box_x[2] + bw - bw * 0.10
ax.add_patch(FancyBboxPatch(
(bx0, badge_y - 0.28), bx1 - bx0, 0.56, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text((bx0 + bx1) * 0.5, badge_y,
"tek özyinelemeli hikâye: BUL → İLİŞKİLENDİR → İNŞA ET",
ha="center", va="center", fontsize=11.0, color=COL_AMBER_700,
weight="bold", zorder=5)
fig.suptitle(
"Üç ünite, tek omurga: Quiz 1 (veri yapıları + sıralama) → Quiz 2 "
"(çizgeler) → Quiz 3 (DP = çizge inşası)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(box_x[0] - 0.5, box_x[2] + bw + 0.5)
ax.set_ylim(badge_y - 0.55, by + bh + 0.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 4. Üç Ünite — Quiz 2: Çizgeler {#sec-4-quiz-2-cizgeler}
Çizge = elemanlar **arası ilişki**: düğüm = sistemin **durumu**, kenar = **geçiş**. Ayrık sistemleri (yol ağı, sıra-tabanlı oyun) modellemenin güçlü çerçevesi.
Odak: **tek-kaynak en kısa yollar** — genellik/runtime takasıyla birden çok algoritma:
- **DAG** (çevrim yok) → lineer (DAG relaxation).
- **BFS** → ağırlıksız.
- **Dijkstra** → negatif olmayan ağırlık.
- **Bellman-Ford** → genel (negatif çevrim tespiti).
Bu merdivenin önemli bir özelliği: **uygulanabildiği yerde hepsi aynı cevabı verir**. @fig-backbone-witness ağırlıksız ($w = 1$) küçük bir çizgede üç algoritmanın birebir aynı $\delta$ ürettiğini motor tanığıyla gösterir — `bfs == dijkstra(w=1) == bellman_ford_classic` her düğümde aynı; `_verify` D31 koşusunda `random.seed(31)` ile 60 rastgele çizgede `sssp_backbone_check` 60/60 True. Kural: **kısıtın en dar uygulanabilir basamağını seç** (en hızlısı odur).
```{python}
#| label: fig-backbone-witness
#| fig-cap: "SSSP omurga tanığı (Ku L20 §4, motor-tanıklı): ağırlıksız (w=1) çizgede BFS = Dijkstra(w=1) = Bellman-Ford aynı δ — genellik ARTAR, cevap DEĞİŞMEZ. SOL küçük çizge (4 düğüm, kaynak s=0 amber, her kenar w=1); SAĞ tablo (satır=düğüm, sütun=BFS / Dijkstra(w=1) / Bellman-Ford) üç sütun BİREBİR aynı → tek δ (amber eşitlik kuşağı). Beklenen δ (kaynak 0): δ(0)=0, δ(1)=1, δ(2)=1, δ(3)=2 — _engine'den CANLI alınır + assert; sssp_backbone_check True. Alt rozet: SSSP merdiveni BFS O(V+E) → Dijkstra(w=1) O(V log V + E) → Bellman-Ford O(V·E) (genellik artar) · 60 random çizgede birebir (_verify D31) · kuralı kısıtın EN DAR uygulanabilir basamağını seç (Quiz 2)."
#| fig-width: 11.5
#| fig-height: 5.8
# fig-backbone-witness (L20 §4): SSSP omurga tanığı. Motor-tanıklı + assert.
adj_bb = {0: [1, 2], 1: [3], 2: [3], 3: [0]}
src_bb = next(iter(adj_bb))
w1_bb = {(u, v): 1 for u in adj_bb for v in adj_bb[u]}
delta_bfs, _ = bfs(adj_bb, src_bb)
d_dij = dijkstra(adj_bb, w1_bb, src_bb)
d_bf = bellman_ford_classic(adj_bb, w1_bb, src_bb)
nodes_bb = sorted(adj_bb.keys())
rows_bb = [(v, delta_bfs.get(v, INF), d_dij[v], d_bf[v]) for v in nodes_bb]
for v, b, dj, bf in rows_bb:
assert b == dj == bf, (v, b, dj, bf)
assert sssp_backbone_check(adj_bb) is True
assert [r[1] for r in rows_bb] == [0, 1, 1, 2], [r[1] for r in rows_bb]
def _fmt_bb(val):
if val == INF:
return "∞"
if val == -INF:
return "−∞"
return str(int(val))
fig = plt.figure(figsize=(11.5, 5.8))
fig.patch.set_facecolor(COL_WHITE)
gs = fig.add_gridspec(
2, 2, width_ratios=[1.0, 2.5], height_ratios=[3.0, 0.8],
left=0.02, right=0.985, top=0.80, bottom=0.045, wspace=0.10, hspace=0.32)
ax_graph = fig.add_subplot(gs[0, 0])
ax_table = fig.add_subplot(gs[0, 1])
ax_badge = fig.add_subplot(gs[1, :])
fig.text(0.5, 0.95, "Aynı çizge, üç algoritma: genellik ARTAR, cevap DEĞİŞMEZ",
ha="center", va="center", fontsize=15, color=COL_TEXT, weight="bold")
fig.text(0.5, 0.885,
"SSSP omurgası — ağırlıksız (w=1) çizgede BFS = Dijkstra(w=1) = "
"Bellman-Ford aynı δ (uygulanabilir oldukça)",
ha="center", va="center", fontsize=10.5, color=COL_SLATE_500, style="italic")
# SOL çizge
ax_graph.axis("off")
ax_graph.set_aspect("equal")
pos_bb = {0: (0.0, 1.0), 1: (1.6, 1.0), 2: (0.0, -0.6), 3: (1.6, -0.6)}
for u in adj_bb:
for v in adj_bb[u]:
x0, y0 = pos_bb[u]
x1, y1 = pos_bb[v]
ax_graph.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=15,
color=COL_SLATE_400, linewidth=1.8, shrinkA=20, shrinkB=20, zorder=1))
mx, my = (x0 + x1) / 2.0, (y0 + y1) / 2.0
ax_graph.text(mx, my, "w=1", ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=4,
bbox=dict(boxstyle="round,pad=0.12", fc=COL_WHITE,
ec=COL_AMBER_300, linewidth=0.8))
for v in nodes_bb:
x, y = pos_bb[v]
is_src = (v == src_bb)
_node_box(ax_graph, x, y, 0.62, 0.5, str(v),
ec=COL_ACCENT if is_src else COL_PRIMARY,
fc=COL_AMBER_100 if is_src else COL_BG, fontsize=12)
sx, sy = pos_bb[src_bb]
ax_graph.text(sx, sy + 0.55, f"kaynak s={src_bb}", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold")
ax_graph.text(0.8, -1.45, "ağırlıksız çizge — her kenar w=1", ha="center",
va="center", fontsize=9.5, color=COL_SLATE_500, style="italic")
ax_graph.set_xlim(-0.85, 2.45)
ax_graph.set_ylim(-1.75, 1.75)
# SAĞ tablo
ax_table.axis("off")
col_labels = ["düğüm", "BFS", "Dijkstra(w=1)", "Bellman-Ford"]
col_w = [1.35, 1.55, 2.05, 2.05]
col_x = [0.0]
for cw in col_w:
col_x.append(col_x[-1] + cw)
header_y = 0.0
row_h = 0.62
n_rows = len(rows_bb)
eq_x0, eq_x1 = col_x[1], col_x[4]
band_top = header_y + row_h * 0.55
band_bot = header_y - row_h * (n_rows + 0.55)
ax_table.add_patch(FancyBboxPatch(
(eq_x0, band_bot), eq_x1 - eq_x0, band_top - band_bot,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=0.5, alpha=0.55))
for c, lab in enumerate(col_labels):
cx = (col_x[c] + col_x[c + 1]) / 2.0
ax_table.text(cx, header_y, lab, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4)
ax_table.plot([col_x[0], col_x[-1]], [header_y - row_h * 0.5] * 2,
color=COL_PRIMARY, linewidth=1.6, zorder=3)
for r, (v, b, dj, bf) in enumerate(rows_bb):
ry = header_y - row_h * (r + 1)
cx0 = (col_x[0] + col_x[1]) / 2.0
is_src = (v == src_bb)
ax_table.text(cx0, ry, str(v), ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if is_src else COL_TEXT, weight="bold", zorder=4)
for j, val in enumerate((b, dj, bf)):
cx = (col_x[j + 1] + col_x[j + 2]) / 2.0
ax_table.text(cx, ry, _fmt_bb(val), ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=4)
if r < n_rows - 1:
ax_table.plot([col_x[0], col_x[-1]], [ry - row_h * 0.5] * 2,
color=COL_SLATE_400, linewidth=0.6, alpha=0.5, zorder=2)
tbl_bot = header_y - row_h * (n_rows + 0.5)
ax_table.add_patch(FancyBboxPatch(
(col_x[0], tbl_bot), col_x[-1] - col_x[0], (header_y + row_h * 0.5) - tbl_bot,
boxstyle="square,pad=0.0", fc="none", ec=COL_PRIMARY, linewidth=1.6, zorder=2.5))
eq_cx = (eq_x0 + eq_x1) / 2.0
ax_table.text(eq_cx, tbl_bot - 0.36, "üç sütun BİREBİR aynı → tek δ",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax_table.set_xlim(-0.2, col_x[-1] + 0.2)
ax_table.set_ylim(tbl_bot - 0.7, header_y + row_h * 0.5 + 0.25)
# ALT rozet
ax_badge.axis("off")
x0b, x1b = 0.0, 10.0
ax_badge.add_patch(FancyBboxPatch(
(x0b, 0.0), x1b - x0b, 1.0, boxstyle="round,pad=0.02,rounding_size=0.04",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.4, zorder=1.5))
ladder_bb = [("BFS", "O(V+E)", "yalnız w=1"),
("Dijkstra(w=1)", "O(V log V + E)", "w ≥ 0"),
("Bellman-Ford", "O(V·E)", "her w (negatif dahil)")]
seg_w = (x1b - x0b - 0.6) / 3.0
byb = 0.66
for k, (name, big_o, scope) in enumerate(ladder_bb):
bxb = x0b + 0.3 + seg_w * (k + 0.5)
ax_badge.text(bxb, byb + 0.11, f"{name} · {big_o}", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=3)
ax_badge.text(bxb, byb - 0.14, f"({scope})", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, zorder=3)
if k < 2:
ar_x = x0b + 0.3 + seg_w * (k + 1.0)
ax_badge.add_patch(FancyArrowPatch(
(ar_x - 0.16, byb), (ar_x + 0.16, byb), arrowstyle="-|>",
mutation_scale=12, color=COL_AMBER_700, linewidth=1.6, zorder=4))
ax_badge.text((x0b + x1b) / 2.0, 0.22,
"genellik artar → · 60 random çizgede birebir (motor tanığı, "
"_verify D31) · kuralı: kısıtın EN DAR uygulanabilir basamağını "
"seç (Quiz 2)",
ha="center", va="center", fontsize=8.6, color=COL_AMBER_700,
weight="bold", zorder=3)
ax_badge.set_xlim(x0b - 0.15, x1b + 0.15)
ax_badge.set_ylim(-0.05, 1.05)
plt.show()
```
## 5. Üç Ünite — Quiz 3: DP = Uygulamalı Çizge {#sec-5-quiz-3-dp-uygulamali-cizge}
DP, **özyinelemeli çerçevenin** çizgeye uygulanışıdır. SRTBOT aslında bir **çizge inşa eder**: alt problemler = düğümler, bağıntı = kenarlar, topolojik sıra + taban durumlar.
> *"You can actually think of the quiz 3 material as really an application of the graph material."* — Ku
**Kilit fark:** Quiz 2'de çizge sana **verilir**; Quiz 3'te çizgeyi **sen kurarsın** — bu yüzden DP yaratıcıdır ve daha zordur.
> *"There's a creative process in trying to construct that graph."* — Ku
Bu nokta @fig-three-units'in üçüncü panosunda görünür: SRTBOT, alt-problemleri düğüm, bağıntıyı kenar yapan bir DAG kurar; yaratıcı kısım o çizgeyi var etmektir. Üç ünite böylece tek omurgada kapanır — **bul → ilişkilendir → inşa et**.
## 6. 6.046 — Doğal Uzantı {#sec-6-6046-dogal-uzanti}
6.046 (Design and Analysis of Algorithms) — lisans devam dersi (OMSCS karşılığı **CS 6515 Graduate Algorithms**). İki bakış. **Birincisi: 006'nın uzantısı** — algoritmayı *söylemek* kolay, ama **doğruluk + verimlilik analizi** çok daha zor. İçerik:
- **union-find** + **amortization via potential analysis** (dinamik dizideki "pahalı işi seyrek yap" sezgisinin formel hâli; dinamik bağlı bileşenler, near-constant sorgu).
- **Minimum Spanning Tree** (greedy) — ağırlıklı çizgede tüm düğümleri bağlayan min-ağırlık ağaç.
- **Network flow / max-flow & cuts** — kapasiteli çizgede source→sink max "su"; Dijkstra/Bellman-Ford gibi **artımlı** polinom algoritmalar.
- **Tasarım paradigmaları** (divide-and-conquer, DP, **greedy**) derinlemesine; **reductions** ile gerçekten NP-hard kanıtı.
Greedy zordur: tüm seçimleri taramaz, **lokal en iyiyi** seçip ilerler ve umut eder — DP'nin "hepsini dene"sinden farklı, daha çetin paradigma. @fig-6046-bridge bu uzantıyı (sol sütun) ve bir sonraki bölümdeki tanım gevşetmeyi (sağ sütun) tek bir köprü şemasında toplar; her kart 6.006 köküne (← "...") bağlıdır.
```{python}
#| label: fig-6046-bridge
#| fig-cap: "6.006 → 6.046 köprüsü (Ku L20 §6-7) — iki bakış: doğal uzantı (006 köklerinden büyür) vs 'doğru/verimli' tanımını gevşetme. ÜST köprü bandı '6.006 → 6.046 (OMSCS · CS 6515)' amber ok. SOL sütun (A) DOĞAL UZANTI 5 kart: union-find + amortization (← dinamik dizi amortizasyonu L2); MST greedy (← ağırlıklı çizge / SSSP Quiz 2); max-flow & cuts (← Dijkstra/Bellman-Ford artımlı Quiz 2); tasarım paradigmaları d&c·DP·greedy (← SRTBOT/DP Quiz 3); gerçek reduction'larla NP-hardness (← NP-hard pratiği Ders 28·L19). SAĞ sütun (B) TANIM GEVŞETME 4 kart: randomized LV/MC (← hashing beklenen O(1) L5); numerical 'kesinliği zamanla öde' (← word-RAM tamsayı modeli L1); approximation sabit-çarpan yakın TSP %10 (← NP-hard pratiği Ders 28); model değişimi cache/quantum/parallel (← tek-işlemci word-RAM L1). Alt not: greedy tüm seçenekleri TARAMAZ — lokal en iyiyi seç + umut et; DP'nin 'hepsini-dene'sinden çetin. KAVRAMSAL figür (sayı yok)."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-6046-bridge (L20 §6-7): köprü. KAVRAMSAL — sayı yok.
_LEFT_CARDS = [
{"topic": "union-find + amortization",
"desc": "Dinamik bağlı bileşenler; potential-analysis\nile near-constant sorgu.",
"root": "dinamik dizi amortizasyonu (L2)"},
{"topic": "Minimum Spanning Tree (greedy)",
"desc": "Ağırlıklı çizgede tüm düğümleri bağlayan\nmin-ağırlık ağaç.",
"root": "ağırlıklı çizge / SSSP (Quiz 2)"},
{"topic": "max-flow & cuts",
"desc": "Kapasiteli çizgede source→sink max akış;\nartımlı polinom algoritmalar.",
"root": "Dijkstra/Bellman-Ford artımlı (Quiz 2)"},
{"topic": "tasarım paradigmaları",
"desc": "divide&conquer · DP · greedy\nderinlemesine.",
"root": "SRTBOT / DP (Quiz 3)"},
{"topic": "gerçek reduction'larla NP-hardness",
"desc": "Bir problemi zor-bilinene indirgeyerek\nNP-hard KANITI.",
"root": "NP-hard pratiği (Ders 28 · L19)"},
]
_RIGHT_CARDS = [
{"topic": "randomized (LV / MC)",
"desc": "Las Vegas = hep doğru · Monte Carlo =\nhep hızlı; daha sıkı sınırlar.",
"root": "hashing beklenen O(1) (L5)"},
{"topic": "numerical",
"desc": "Reel sayı tam saklanamaz → sınırlı kesinlik;\n\"kesinliği zamanla öde\".",
"root": "word-RAM tamsayı modeli (L1)"},
{"topic": "approximation",
"desc": "NP-hard optimumun SABİT-ÇARPAN yakını\n(TSP %10 içinde).",
"root": "NP-hard pratiği (Ders 28)"},
{"topic": "model değişimi",
"desc": "cache (bellek hiyerarşisi) · quantum ·\nparallel/distributed.",
"root": "tek-işlemci word-RAM modeli (L1)"},
]
assert len(_LEFT_CARDS) == 5 and len(_RIGHT_CARDS) == 4
def _draw_card(ax, cx, top, w, h, topic, desc, root, accent):
bot = top - h
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, bot), w, h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_WHITE, ec=COL_ACCENT if accent else COL_PRIMARY, linewidth=1.9, zorder=3))
strip_h = h * 0.34
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, top - strip_h), w, strip_h,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100 if accent else COL_BG,
ec=COL_ACCENT if accent else COL_PRIMARY, linewidth=1.5, zorder=4))
ax.text(cx, top - strip_h * 0.5, topic, ha="center", va="center",
fontsize=9.6, color=COL_AMBER_700 if accent else COL_TEXT,
weight="bold", zorder=6)
ax.text(cx, top - strip_h - (h - strip_h) * 0.34, desc, ha="center",
va="center", fontsize=8.0, color=COL_SLATE_500, zorder=6, linespacing=1.15)
rcap_h = h * 0.255
rcap_w = w * 0.92
ax.add_patch(FancyBboxPatch(
(cx - rcap_w * 0.5, bot + 0.04), rcap_w, rcap_h,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100, ec=COL_AMBER_300, linewidth=1.2, zorder=5))
ax.text(cx, bot + 0.04 + rcap_h * 0.5, f"← {root}", ha="center", va="center",
fontsize=7.2, color=COL_AMBER_700, weight="bold", style="italic", zorder=6)
return bot
fig, ax = plt.subplots(figsize=(12.0, 6.0))
fig.patch.set_facecolor(COL_WHITE)
band_y = 9.55
band_h = 0.92
src_w, dst_w = 2.65, 3.55
cx_mid = 6.0
src_cx = cx_mid - 2.95
dst_cx = cx_mid + 2.95
ax.add_patch(FancyBboxPatch(
(src_cx - src_w * 0.5, band_y - band_h * 0.5), src_w, band_h,
boxstyle="round,pad=0.03,rounding_size=0.12", fc=COL_BG, ec=COL_PRIMARY,
linewidth=2.4, zorder=4))
ax.text(src_cx, band_y, "6.006", ha="center", va="center", fontsize=16,
color=COL_TEXT, weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(src_cx + src_w * 0.5 + 0.10, band_y), (dst_cx - dst_w * 0.5 - 0.10, band_y),
arrowstyle="-|>", mutation_scale=26, color=COL_AMBER_600, linewidth=4.0, zorder=3))
ax.add_patch(FancyBboxPatch(
(dst_cx - dst_w * 0.5, band_y - band_h * 0.5), dst_w, band_h,
boxstyle="round,pad=0.03,rounding_size=0.12", fc=COL_AMBER_100, ec=COL_ACCENT,
linewidth=3.2, zorder=4))
ax.text(dst_cx, band_y + 0.14, "6.046", ha="center", va="center", fontsize=16,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(dst_cx, band_y - 0.26, "OMSCS · CS 6515", ha="center", va="center",
fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=6)
col_head_y = 8.55
left_cx = 3.0
right_cx = 9.0
ax.add_patch(FancyBboxPatch(
(left_cx - 2.65, col_head_y - 0.33), 5.30, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10", fc=COL_BG, ec=COL_PRIMARY,
linewidth=2.0, zorder=4))
ax.text(left_cx, col_head_y, "(A) DOĞAL UZANTI", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold", zorder=6)
ax.add_patch(FancyBboxPatch(
(right_cx - 2.65, col_head_y - 0.33), 5.30, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10", fc=COL_AMBER_100, ec=COL_ACCENT,
linewidth=2.4, zorder=4))
ax.text(right_cx, col_head_y, "(B) TANIM GEVŞETME", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(left_cx, col_head_y - 0.62, "aynı hedefler — analiz çok daha zor",
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500, style="italic", zorder=6)
ax.text(right_cx, col_head_y - 0.62, "\"doğru / verimli\" tanımını esnet",
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500, style="italic", zorder=6)
for tx in (left_cx, right_cx):
ax.add_patch(FancyArrowPatch(
(cx_mid, band_y - band_h * 0.5 - 0.02), (tx, col_head_y + 0.36),
arrowstyle="-|>", mutation_scale=14, color=COL_SLATE_400, linewidth=1.6,
zorder=2, connectionstyle="arc3,rad=0.0"))
card_w = 5.05
left_card_h = 1.34
right_card_h = 1.70
left_gap = 0.18
right_gap = 0.26
cards_top = 7.55
t = cards_top
for c in _LEFT_CARDS:
bot = _draw_card(ax, left_cx, t, card_w, left_card_h,
c["topic"], c["desc"], c["root"], accent=False)
t = bot - left_gap
t = cards_top
for c in _RIGHT_CARDS:
bot = _draw_card(ax, right_cx, t, card_w, right_card_h,
c["topic"], c["desc"], c["root"], accent=True)
t = bot - right_gap
note_y = 0.55
ax.add_patch(FancyBboxPatch(
(0.45, note_y - 0.40), 11.10, 0.80, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_AMBER_300, linewidth=1.6, zorder=2))
ax.text(6.0, note_y,
"greedy: tüm seçenekleri TARAMAZ — lokal en iyiyi seç + umut et "
"· DP'nin \"hepsini-dene\"sinden daha ÇETİN paradigma",
ha="center", va="center", fontsize=9.6, color=COL_AMBER_700, weight="bold", zorder=5)
fig.suptitle(
"6.006 → 6.046 köprüsü — iki bakış: doğal uzantı (006 köklerinden "
"büyür) vs \"doğru/verimli\" tanımını gevşetme",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(0.0, 12.0)
ax.set_ylim(0.0, 10.35)
ax.set_aspect("auto")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. 6.046 — "Doğru/Verimli" Tanımını Gevşetmek {#sec-7-6046-tanimini-gevsetmek}
İkinci bakış: **doğruluk veya hesaplama modelini** gevşet.
> *"6.046 [is about] change my definition of what it means to be correct or efficient."* — Ku
- **Randomized algoritmalar:** **Las Vegas** = *hep doğru, muhtemelen verimli* (hashing böyle — bazen zincir uzun). **Monte Carlo** = *hep verimli, muhtemelen doğru* (sabit zaman ama bazen yanlış). Randomization genelde daha hızlı sınırlar verir.
- **Numerical algoritmalar:** reel sayılar bilgisayarda tam saklanamaz → **sınırlı kesinlikle** hesapla; kesinliği zamanla öde (uzun bölme / karekök analojisi). Sürekli (continuous) optimizasyon.
> *"I pay for precision with time."* — Ku
- **Approximation algoritmalar:** NP-hard optimizasyonda optimumu değil, **sabit çarpan** yakınını polinom-zamanda hedefle (TSP'de %10 içinde).
- **Hesaplama modelini değiştir:** **cache model** (bellek hiyerarşisi: register/L1/.../disk farklı maliyet), **quantum** (entanglement/superposition — şifre kırma), **parallel** (k CPU → k-kat hızlanma; her zaman mümkün değil; multicore paylaşımlı bellek vs distributed).
Randomization'ın somut yüzü iki turdur — aynı 40 anahtarı aynı 7 kovaya iki farklı sözleşmeyle yerleştir. @fig-lasvegas-montecarlo bu **İMZA** tanığı motor-tanıklı gösterir: Las Vegas chaining (`HashTableChaining`) 40/40 doğru (en uzun zincir 6); Monte Carlo (`MonteCarloHashSet`, kova başına ≤2) `contains` hep $O(1)$ ama **26 öğe düşer** → tam 26 yanlış-negatif — ve **yanlış-pozitif asla** (asimetri). `monte_carlo_demo(range(40), 7)` birebir `(26, 26, False)` döndürür: yanlış-negatif = dropped, yanlış-pozitif yok.
```{python}
#| label: fig-lasvegas-montecarlo
#| fig-cap: "Las Vegas vs Monte Carlo (Ku L20 §7 İMZA, motor-tanıklı): aynı 40 anahtar, aynı 7 kova, iki randomizasyon sözleşmesi. SOL LAS VEGAS chaining (HashTableChaining) — hep DOĞRU, muhtemelen verimli; tüm zincirler saklanır (en uzun zincir 6 amber vurgulu); 40/40 bulundu ✓. SAĞ MONTE CARLO (MonteCarloHashSet, kova başına ≤2 öğe) — hep VERİMLİ, muhtemelen doğru; taşan öğeler kırmızı çarpıyla DÜŞÜRÜLDÜ (26 öğe) → contains hep O(1) AMA 26/40 yanlış-negatif; yanlış-POZİTİF asla (asimetri). ORTA TAKAS kutusu: doğruluk ⟷ süre garantisi — birini sabitle, diğerini olasılaştır; Ku 'I pay for precision with time'. Tüm sayılar _engine'den CANLI: monte_carlo_demo(range(40), 7) == (26, 26, False); Las Vegas 40/40 doğru, en uzun zincir = max(chain_lengths) (assert)."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-lasvegas-montecarlo (L20 §7 İMZA): randomized iki tur. Motor-tanıklı + assert.
TOTAL_lv = 40
M_lv = 7
keys_lv = list(range(TOTAL_lv))
fneg_lv, dropped_lv, fpos_lv = monte_carlo_demo(keys_lv, M_lv)
assert (fneg_lv, dropped_lv, fpos_lv) == (26, 26, False), (fneg_lv, dropped_lv, fpos_lv)
mc = MonteCarloHashSet(M_lv)
mc_dropped_keys = [[] for _ in range(M_lv)]
for k in keys_lv:
b = mc.buckets[hash(k) % M_lv]
if k in b:
continue
if len(b) >= 2:
mc_dropped_keys[hash(k) % M_lv].append(k)
mc.insert(k)
mc_buckets = [list(b) for b in mc.buckets]
assert mc.dropped == 26, mc.dropped
assert sum(len(b) for b in mc_dropped_keys) == 26, mc_dropped_keys
ht = HashTableChaining(M_lv)
for k in keys_lv:
ht.insert(k)
lv_buckets = [[k for (k, _v) in chain] for chain in ht.buckets]
lv_lengths = ht.chain_lengths()
lv_longest = max(lv_lengths)
assert lv_lengths == [6, 6, 6, 6, 6, 5, 5], lv_lengths
lv_found = sum(1 for k in keys_lv if ht.contains(k))
assert lv_found == TOTAL_lv, lv_found
fig, ax = plt.subplots(figsize=(12, 6))
fig.patch.set_facecolor(COL_WHITE)
draw_lasvegas_montecarlo(
ax, lv_buckets=lv_buckets, lv_longest=lv_longest,
lv_found=lv_found, lv_total=TOTAL_lv,
mc_buckets=mc_buckets, mc_dropped=mc.dropped, mc_dropped_keys=mc_dropped_keys,
mc_fneg=fneg_lv, mc_fpos=fpos_lv, m=M_lv)
fig.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d31}
1. **4 hedef:** algoritma üret · doğruluğu kanıtla (uygulamalı 6.042) · verimliliği kanıtla (model+asimptotik) · **insanlara ilet** (en önemli).
2. **L19 final'de:** tanımlar — P/NP/EXP iç içe, reduction yönü, hard vs complete.
3. **Quiz 1:** veri yapıları (dizi vs küme) + onları sömüren sıralama (heap/counting/radix).
4. **Quiz 2:** çizgeler — durum/geçiş; SSSP genellik-runtime takası (DAG/BFS/Dijkstra/Bellman-Ford).
5. **Quiz 3:** DP = çizge **inşası** (SRTBOT: düğüm/kenar/topolojik sıra); yaratıcı kısım çizgeyi kurmaktır.
6. **6.046:** ya 006'nın uzantısı (union-find/MST/flow/reductions) ya da tanım gevşetme (randomized/numerical/approximation/model).
::: {.callout-important title="Tek Bir Cümle"}
6.006 sadece algoritma yazmayı değil, doğruluk ve verimliliği **insanlara iletmeyi** öğretir; üç ünite tek bir omurgadır (veri yapısı → çizge → DP=çizge inşası) ve 6.046 bunu derinleştirip "doğru/verimli" tanımını gevşetir (randomized, approximation, farklı hesaplama modelleri).
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d31}
::: {.callout-note collapse="true" title="Soru 1: Dersin 4 hedefinden hangisi «en önemli» sayılır ve neden quiz'de doğru kod tam puan almaz?"}
**Cevap:**
**İletişim (communication)** en önemli hedef. Diğer üçü — algoritma üretmek, doğruluğu kanıtlamak, verimliliği kanıtlamak — teknik olarak yeterli görünse de, 6.006 bunların **insanlara aktarılmasını** ister. Quiz'de doğru ama "ne yaptığı anlaşılmayan" bir Python script'i tam puan almaz; çünkü ders, bir algoritmanın **ne yaptığını ve neden doğru/verimli olduğunu** başkalarına iletme becerisini ölçer. Bilgisayar bilimi büyük ölçüde başkalarıyla çalışmaktır; iletemezsen, ne kadar yetkin olursan ol sınırlı kalırsın.
:::
::: {.callout-note collapse="true" title="Soru 2: «Quiz 3 (DP) aslında çizge materyalinin uygulamasıdır» ifadesini SRTBOT üzerinden açıkla. Quiz 2'den farkı ne?"}
**Cevap:**
SRTBOT bir **çizge inşa eder**: **alt problemler** = düğümler, **bağıntı (R)** = kenarlar (bir alt problemin hangi küçük alt problemlere bağlı olduğu), **topolojik sıra (T)** = çizgenin DAG olması, **taban durumlar (B)** = çıkış-kenarı olmayan düğümler. Yani DP, üzerinde en kısa yol / erişilebilirlik tarzı bir hesaplama yapılan bir DAG'dır. **Quiz 2'den fark:** orada çizge sana **verilir** (düğüm ve kenarlar belli, algoritma uygula). Quiz 3'te çizgeyi **sen kurarsın** — düğümleri (alt problemleri) ve kenarları (bağıntıyı) yaratman gerekir. Bu yaratıcı inşa, DP'yi çizge algoritmalarını uygulamaktan daha zor yapar.
:::
::: {.callout-note collapse="true" title="Soru 3: Las Vegas ve Monte Carlo randomized algoritmaları arasındaki fark nedir? Hashing hangisidir?"}
**Cevap:**
**Las Vegas:** *hep doğru, muhtemelen (beklenen) verimli*. **Monte Carlo:** *hep verimli, muhtemelen doğru*. Hashing bir **Las Vegas** örneğidir: bir öğenin kümede olup olmadığını **her zaman doğru** söyler, ama bazen zincir uzunsa beklenenden yavaştır (verimlilik olasılıksal). Aynı hash table'ı **Monte Carlo** yapabilirsin: her kovada çarpışanların yalnız ilk ikisini sakla → **her zaman sabit zaman** (hep verimli) ama bazen yanlış (saklanmayan öğe "yok" görünür). @fig-lasvegas-montecarlo bunu motor tanığıyla gösterir: aynı 40 anahtarda Monte Carlo 26 yanlış-negatif üretir ($O(1)$ garantisi karşılığında), Las Vegas 40/40 doğrudur. Pratikte bazen "bazen yanlış ama hep hızlı" iyi bir takastır.
:::
::: {.callout-note collapse="true" title="Soru 4: 6.046'nın 006'yı iki farklı şekilde nasıl genişlettiğini özetle."}
**Cevap:**
**(A) Doğal uzantı:** Aynı hedefler, ama **daha zor analiz**. Algoritmayı söylemek kolay; asıl zorluk doğruluk + verimlilik kanıtında. Yeni konular: union-find (potential analysis ile amortization), MST (greedy), network flow / max-flow & cuts (artımlı algoritmalar), tasarım paradigmaları (divide-conquer/DP/greedy derin), gerçek reduction'larla NP-hardness kanıtı.
**(B) Tanım gevşetme:** "Doğru" veya "verimli/model" tanımını esnetir. **Randomized** (Las Vegas/Monte Carlo), **numerical** (reel sayılar sınırlı kesinlikle; kesinliği zamanla öde), **approximation** (NP-hard optimumun sabit-çarpan yakını), **model değişimi** (cache hiyerarşisi, quantum, parallel/distributed). İkisi birlikte 006'nın doğal devamı + yeni teori dallarıdır.
:::
## Egzersizler {#sec-egzersizler-d31}
**Egzersiz 1.** Quiz 1-2-3'ü tek cümlelik bir "omurga" hikâyesi olarak yaz (veri yapısı → çizge → DP=çizge inşası).
**Egzersiz 2.** Bir set veri yapısı seçimi için karar ağacı çiz: dinamik sıralı işlem gerekiyor mu? sözlük yeter mi? statik mi? (hash table / set AVL / sıralı dizi).
**Egzersiz 3.** Verilen bir problemi (örn. TSP) önce tam-optimal (NP-hard) sonra approximation açısından ele al; "%10 içinde yeter" yaklaşımının pratik değerini tartış.
**Egzersiz 4.** word-RAM ile cache modelini karşılaştır: hangi algoritma analizleri ikisinde farklı sonuç verir? (örn. ardışık vs rastgele bellek erişimi).
**Egzersiz 5.** Hashing'i Monte Carlo'ya çeviren "ilk iki çarpışmayı sakla" fikrini kodla ve hata olasılığını tartış.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d31}
::: {.callout-warning title="Sonraki: Ders 32 (L21) — Son Ders: Algoritmalar Her Yerde (Ku + Demaine + Solomon)"}
**Ders 32 (L21): Son Ders** — dönemin kapanışı ve **kursun FİNALİ**. Üç hoca: **Jason Ku** açar, **Erik Demaine** ile **Justin Solomon** devam eder. Bu retrospektifteki "omurga" görüşü (veri yapısı → çizge → DP) ve 6.046 köprüsü, son derste nihai bağlamına oturur — algoritmaların gerçek dünyadaki uygulamaları.
**Ders 32 Öncesi Yapılacak:**
- L19 tanımlarını (P/NP/EXP, reduction yönü, hard/complete) final için gözden geçir.
- Üç ünitenin cheat sheet'lerini (Quiz 1-2-3 review dersleri) birlikte oku.
- 6.046 (CS 6515) konularına göz at: union-find, MST, max-flow, randomized.
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d31}
| Tema | Özet | Sayfada |
|------|------|---------|
| **4 Hedef** | Algoritma · doğruluk · verimlilik · iletişim (en önemli) | Böl. 1 |
| **L19 (final)** | P/NP/EXP iç içe · reduction yönü · hard vs complete | Böl. 2 |
| **Quiz 1** | Veri yapıları (dizi vs küme) + sıralama (heap/counting/radix) | Böl. 3 |
| **Quiz 2** | Çizge (durum/geçiş); SSSP genellik-runtime takası | Böl. 4 |
| **Quiz 3** | DP = SRTBOT ile çizge inşası (yaratıcı) | Böl. 5 |
| **6.046 (A)** | union-find, MST, max-flow, reductions (zor analiz) | Böl. 6 |
| **6.046 (B)** | randomized, numerical, approximation, model değişimi | Böl. 7 |
| **Randomized** | Las Vegas (hep doğru) vs Monte Carlo (hep hızlı) | Böl. 7 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d31}
::: {.callout-tip title="7 köprü"}
Bu retrospektifin omurga görüşü, dört hedefi ve 6.046 köprüsü, graduate algoritmalarına ve gerçek sistem mühendisliğine doğrudan bağlanır; köprülerin özeti:
1. **6.046 = CS 6515** (Graduate Algorithms) — OMSCS çekirdek dersi; bu retrospektif **birebir hazırlık** (omurga görüşü ve 6.046 konu listesi CS 6515 ile örtüşür).
2. **İletişim hedefi** → **kod review, tasarım dokümanı, teknik yazım**: "ne + neden" anlatımı; doğru kod yetmez, anlaşılır olmalı (en önemli builder becerisi).
3. **Max-flow / network flow** → matching, scheduling, segmentation; gerçek **sistem optimizasyonu** (kapasiteli çizgede source→sink akış pek çok kaynak-tahsis problemine oturur).
4. **Randomized (Las Vegas / Monte Carlo)** → hashing, **sketch / probabilistic veri yapıları (Bloom filter)**, ML sampling; "hep hızlı, bazen yanlış" takası `monte_carlo_demo`'nun çalışan örneğidir.
5. **Approximation** → NP-hard pratiği: heuristik + garanti; routing, packing (optimumun sabit-çarpan yakını yeterli olduğunda).
6. **Cache / parallel model** → gerçek performans mühendisliği; multicore, distributed, GPU (word-RAM tek-işlemci modeli yerine bellek hiyerarşisi/paralellik).
7. **Quantum** → post-kuantum kriptografi farkındalığı ($P \neq NP$ güvenliğinin kırılganlığı; quantum entanglement şifre kırmayı değiştirir).
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
6.006'nın gerçek dersi algoritma yazmak değil, **doğruluğu ve verimliliği insanlara iletmektir** — quiz'de anlaşılmayan doğru kod tam puan almaz. Tüm dönem tek bir omurgadır: **veri yapıları** (Quiz 1, bir şey bul) → **çizgeler** (Quiz 2, ilişkiler) → **DP** (Quiz 3, çizgeyi *sen kur* — SRTBOT). Buradan **6.046**'ya (OMSCS CS 6515) gidersin: ya bu hikâyeyi derinleştir (union-find, MST, max-flow, gerçek reduction'lar) ya da "doğru/verimli" tanımını gevşet (randomized = Las Vegas/Monte Carlo, numerical = kesinliği zamanla öde, approximation = optimumun sabit-çarpan yakını, model = cache/quantum/parallel).
:::
