---
title: "Son Ders: Algoritmalar Her Yerde"
subtitle: "Üç geometrici hocanın araştırma vitrini — origami, self-assembly, mesh geodeziği, ray casting ve redistricting; kursun kapanışı"
---
::: {.callout-note title="Oturum bilgisi"}
- **Hocaların videosu:** [YouTube — Lecture 21: Algorithms—Next Steps (final)](https://www.youtube.com/watch?v=4nXw-f6NJ9s) (≈50 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 21: Algorithms—Next Steps](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-21-algorithms2014next-steps/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 32 (L21) — **SON DERS**
- **Hoca:** ÜÇ HOCA — **Jason Ku** açar, **Erik Demaine** + **Justin Solomon** devam eder
- **Okuma süresi:** ≈28 dk
> **Kursun FİNALİ** — tema: *algorithms are everywhere* (Demaine) + *6.006 is unavoidable* (Solomon). Üç hoca da geometrici; kendi araştırmalarında 6.006 araçlarının (NP-hardness, DP, çizge, veri yapısı, approximation, hesaplama modeli) nasıl döndüğünü gösterirler.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d32}
6.006'nın **son dersi** (Jason Ku açar, Erik Demaine + Justin Solomon devam eder). Üç hoca da **geometrici** — kendi araştırmalarında 6.006 materyalini nasıl kullandıklarını gösterirler. Tema tek cümle:
> *"algorithms are everywhere."* — Demaine
Ve Solomon'ın ısrarı:
> *"6.006 is unavoidable."* — Solomon
Uzmanlaşma dersleri (daha çok çizge, hesaplama modelleri, randomness, complexity) + uygulamalar (biyoloji, kriptografi, **grafik/geometri**) gezilir; sonra Demaine (computational origami, self-assembly, ileri veri yapıları, planar çizge, recreational) ve Solomon (mesh geometrisi, computer graphics, politik redistricting) somut örnekler verir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 32'nin (L21) kavram haritası: kök = Son Ders Algoritmalar Her Yerde (Ku açar, Demaine ve Solomon devam) — kursun FİNALİ, üç geometrici hocanın araştırma vitrini. Beş dal — (1) Demaine origami 6.849: tasarım design hedef şekil to kıvrım deseni ÇÖZÜLEBİLİR vs katlanabilirlik foldability desen katlanır mı NP-hard; her şeyi katla 90 lar şerit yöntemi korkunç verimsiz; Origamizer Tachi 3B model to kare yüzde 22 alan çelik tavşan; fold-and-cut tek düz kesik herhangi şekil; maze folding köşe tipi gadget sabit ölçek faktörü. (2) Demaine self-assembly: DNA tile dört kenar tutkal tamamlayıcı yapışır sıcaklıkla ayarlanır; hesaplama modeli GEOMETRİK word-RAM tek komuttan farklı; keyfi şekil log n paralel adım sabit tutkal; replikator bilinmeyen şekli kalıplar 3B fotokopi. (3) Demaine ileri veri yapısı 6.851 planar recreational 6.892: van Emde Boas log w fusion tree log n bölü log w min karekök log n bölü log log n AVL log n den iyi; planar SSSP lineer Baker yaklaşımı BFS katmanları sil bir artı bir bölü k PTAS; oyun NP-hard Tetris Mario Portal Witness Recurse undecidable resim asma. (4) Solomon mesh 6.838: simplicial complex düğüm kenar ÜÇGEN; kenar Dijkstra YANLIŞ çizgeler üçgenlerle konuşamaz; doğru MMP geodezik n log n Dijkstra seviye kümeleri artı pencereleme; pratik fast marching yaklaşık hızlı. (5) Solomon ray casting 6.837 artı redistricting: ray casting O p çarpı n Stanford Bunny 69 bin üçgen 2 milyon piksel; sınırlayıcı kutu KD tree uzay bölme ağacı O p log n sezgisel; scene graph DAG 100 sandalye; GPU SIMD 30 fps; redistricting bağlı partisyon en iyi plan NP-hard tek düze örnekleme Hamiltonian indirgeme Yüksek Mahkeme. Birleştirici tema: 6.006 nın altı aracı sınıfta kalmıyor origami katlamadan DNA self-assembly ye mesh geodeziğinden ray casting ve politik gerrymandering e kadar her gerçek araştırma probleminde karşına çıkar algoritmalar her yerde 6.006 kaçınılmaz buradan 6.046 CS 6515 ve uzmanlık derslerine."
flowchart TD
A["Ders 32 (L21): Son Ders — Algoritmalar Her Yerde (Ku · Demaine · Solomon)"] --> O["Demaine — origami (6.849)"]
O --> Oa["tasarım ÇÖZÜLEBİLİR vs foldability NP-hard<br/>Origamizer %22 · fold-and-cut · maze (sabit ölçek)"]
A --> S["Demaine — self-assembly"]
S --> Sa["DNA tile + tutkal; model GEOMETRİK<br/>keyfi şekil log n paralel · replikator (3B fotokopi)"]
A --> D["Demaine — 6.851 / planar / 6.892"]
D --> Da["van Emde Boas log w · fusion log n/log w < AVL log n<br/>planar SSSP lineer · Baker PTAS · oyun NP-hard"]
A --> M["Solomon — mesh (6.838)"]
M --> Ma["kenar-Dijkstra YANLIŞ (çizge ≠ üçgen)<br/>MMP geodezik n log n · fast marching"]
A --> R["Solomon — graphics + redistricting"]
R --> Ra["ray casting O(p·n) → KD tree O(p log n) · DAG · SIMD<br/>redistricting: en iyi plan + örnekleme NP-hard"]
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 O,S,D,M,R branch
class Oa,Sa,Da,Ma,Ra leaf
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 32 (L21) Son Ders motoru
# (_engine.py D32 bölümü + bağımlılıkları + _viz.py yardımcıları INLINE
# GÖMÜLÜ — import YOK). Fonksiyonlar / sınıflar:
# mesh_edge_vs_geodesic → L21 §5 Solomon tanığı (birim kare mesh:
# kenar-Dijkstra 2.0 vs geodezik √2 ≈ 1.414; oran √2 ≈ %41 uzun).
# ray_cast_naive / ray_cast_indexed → L21 §6 Solomon tanığı (her ışın ×
# her nesne O(p·n) vs sırala + ikili arama; hit'ler BİREBİR aynı,
# karşılaştırma sayacı motordan).
# dijkstra (+ ChangeablePQ) + INF → mesh tanığının altyapısı (D19/L13).
# 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 bisect import bisect_right
import matplotlib.pyplot as plt
from matplotlib.patches import (
FancyBboxPatch, FancyArrowPatch, Circle, Polygon, 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"
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py L13 §5-6 — ChangeablePQ + Dijkstra (mesh tanığının altyapısı)
# ---------------------------------------------------------------------------
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 D32 (L21) §5 — mesh kenar-Dijkstra vs geodezik (Solomon tanığı)
# ---------------------------------------------------------------------------
def mesh_edge_vs_geodesic():
"""Solomon tanığı (L21 §5): birim kare mesh (4 köşe, 2 üçgen, köşegen
kenar YOK); karşı köşeye kenar-Dijkstra = 2.0 (iki kenar), gerçek
geodezik (üçgen yüzeyinden çapraz) = √2 ≈ 1.414 — kenar-Dijkstra
%41 UZUN (yanlış). Döndürür: (kenar_yolu, geodezik, oran)."""
corners = {(0, 0), (1, 0), (0, 1), (1, 1)}
adj = {c: [] for c in corners}
w = {}
for (x1, y1) in corners: # yalnız eksen-paralel kenarlar
for (x2, y2) in corners:
if abs(x1 - x2) + abs(y1 - y2) == 1:
adj[(x1, y1)].append((x2, y2))
w[((x1, y1), (x2, y2))] = 1.0
edge_path = dijkstra(adj, w, (0, 0))[(1, 1)]
geodesic = 2 ** 0.5
return edge_path, geodesic, edge_path / geodesic
# ---------------------------------------------------------------------------
# _engine.py D32 (L21) §6 — ray casting naif vs indexed (Solomon tanığı)
# ---------------------------------------------------------------------------
def ray_cast_naive(rays, intervals):
"""Naif ray casting 1B modeli (L21 §6): her ışın (nokta) × her nesne
(aralık) tara → ilk (en soldaki başlayan) çarpılan nesne. O(p·n).
Döndürür: (hit listesi, karşılaştırma sayacı)."""
hits, comps = [], 0
for r in rays:
best = None
for idx, (a, b) in enumerate(intervals):
comps += 1
if a <= r <= b and (best is None or a < intervals[best][0]):
best = idx
hits.append(best)
return hits, comps
def ray_cast_indexed(rays, intervals):
"""Hızlandırılmış model (L21 §6 uzay-bölme fikrinin 1B analoğu):
aralıkları başlangıca göre SIRALA (ön-işleme) + her ışında ikili
arama ile adaydan geriye tara; ilk kapsayan en-soldaki aday.
Karşılaştırma sayısı naiften KAT KAT az (log-davranış; sezgisel —
Solomon: 'ideal log, veriye bağlı'). Döndürür: (hits, comps)."""
order = sorted(range(len(intervals)), key=lambda i: intervals[i][0])
starts = [intervals[order[q]][0] for q in range(len(order))]
hits, comps = [], 0
for r in rays:
hi = bisect_right(starts, r) # başlangıcı ≤ r adaylar
comps += max(1, (len(starts)).bit_length()) # ikili arama bedeli
best = None
for q in range(hi): # en soldan: ilk kapsayan
comps += 1
idx = order[q]
if intervals[idx][1] >= r:
best = idx
break
hits.append(best)
return hits, comps
```
## 1. Üç Geometrici + Jason'ın Origami Yolculuğu {#sec-1-uc-geometrici-origami}
Bu dönemin üç hocası da geometriyle ilgilenir. **Jason Ku** makine mühendisi olarak başladı; tutkusu **origami**ydi. Origami modelleri tasarlarken kullandığı yöntemlerin aslında **algoritma** olduğunu sonradan fark etti. Demaine ile origami + **katlanabilir yapılar** (uzay uçuşu, açılır köprü/barınak, yeniden yapılandırılabilir madde) üzerine çalışmaya başladı — "telefonun maddesini yeniden programla" hayali (yazılım gibi maddeyi katla).
Bu ders, 6.006'nın **tüm araçlarının** gerçek araştırmada nasıl döndüğünü gösteren bir vitrindir: NP-hardness (Ders 28), DP (Quiz 3), çizge (Quiz 2), veri yapısı (Quiz 1), approximation, hesaplama modeli. Üç hoca sırayla origami, self-assembly, ileri veri yapıları, mesh geodeziği, ray casting ve redistricting örneklerini açar.
## 2. Demaine — Computational Origami (6.849) {#sec-2-demaine-origami}
İki problem tipi:
- **Tasarım (design):** hedef şekil → kıvrım deseni (crease pattern). Genelde **çözülebilir**.
- **Katlanabilirlik (foldability):** verilen kıvrım deseni katlanır mı? Genelde **NP-hard** (Demaine + Ku, genel foldability'nin NP-hard olduğunu kanıtladı).
> *"most of those problems are NP-hard."* — Demaine (foldability)
**"Her şeyi katlayabilirsin":** yeterince büyük bir kareden herhangi bir poligon/3B yüzey katlanabilir (90'lar; ince şeride katla + zigzag — ama malzemenin tamamına yakınını çöpe atar, korkunç verimsiz). Modern hedef: **ölçek faktörünü** küçült. **Origamizer** (Tomohiro Tachi; Demaine+Ku analiz etti): 3B model → kareden kat, **%22 alan** (çelik tavşan). **Maze folding** (ilk Demaine+Ku makalesi): dikdörtgenden labirent; her köşe tipi (derece 4/3/2) için küçük gadget kıvrımları tasarla, sınırları uyumluysa yapıştır → keyfi n×n labirent **sabit ölçek faktörüyle**.
**Fold-and-cut:** kâğıdı düz katla + **tek düz kesik** → herhangi bir şekil (kuğu, melekbalığı, MIT logosu). Demaine'in ilk computational origami problemi; algoritma, çizdiğin herhangi bir çizgenin tüm kenarlarını hizalayan kıvrım desenini hesaplar. @fig-origami bu üç fikri (tasarla vs katla, Origamizer, fold-and-cut + maze) tek panoda toplar — sayılar yalnız kaynak-alıntılıdır (%22 alan; sabit ölçek), motor rakamı değil.
::: {.callout-tip title="Builder Notu — NP-hardness pratiği refleksi"}
Foldability'nin NP-hard olması, bir builder için "bu problemi her zaman verimli çözen genel algoritma arama, yön değiştir" refleksidir. **Tasarım yönü** (şekil → desen) çözülebilirken **karar yönü** (desen → katlanır mı?) NP-hard — aynı domain'in iki yönü farklı zorlukta. Bu, Ders 28'deki reduction pratiğinin gerçek araştırmadaki karşılığı: yönü değiştirip kolay tarafa odaklan. OMSCS CS 6515'te bu, "verilen problemin hangi yönünün polinom, hangisinin NP-hard olduğunu tanıma" becerisidir.
:::
```{python}
#| label: fig-origami
#| fig-cap: "Computational origami (Demaine, L21 §1-2 VİTRİN): tasarla vs katla · Origamizer · fold-and-cut + maze. KART 1 'design vs foldability' (iki yön, iki zorluk): şekil → katlama deseni ÇÖZÜLEBİLİR (yeşilimsi — verilen 3B hedefe ulaşan kıvrım desenini ÜRETMEK için algoritma var) vs desen → katlanır mı? NP-hard (kırmızı — bir desenin düz katlanabilirliğine KARAR vermek NP-zor; Demaine + Bern–Hayes, Ku kanıta katkı). KART 2 'Origamizer' (amber vurgu): 3B model (çelik tavşan) → TEK kare kâğıt kıvrım deseni (Tachi); rozet '%22 alan (çelik tavşan)' kaynak-alıntılı verim; 90'ların 'şerit yöntemi' üstü çizik 'korkunç verimsiz'. KART 3 'fold-and-cut + maze': düz katla + TEK düz kesik → herhangi düz-kenarlı şekil (kuğu silueti); maze folding köşe-tipi gadget'ları (derece 4/3/2) + sabit ölçek. Alt şerit: origami yolculuğu — yöntemlerin aslında ALGORİTMA olduğunu sonradan fark etti. KAVRAMSAL VİTRİN (sayı yalnız kaynak-alıntılı: %22 alan, sabit ölçek — motor rakamı değil)."
#| fig-width: 12.0
#| fig-height: 5.5
# fig-origami (L21 §1-2 VİTRİN): KAVRAMSAL — sayı yalnız kaynak-alıntılı (%22, sabit ölçek).
COL_GOOD = "#cfe8da" # açık yeşilimsi — "çözülebilir / algoritma var"
COL_GOOD_EC = "#3f7d5e" # yeşil çerçeve
COL_HARD = "#f3c9c2" # açık kırmızımsı — "NP-hard"
COL_HARD_EC = "#b23a2e" # kırmızı çerçeve
def _og_card(ax, bx, by, bw, bh, title, subtitle, accent=False):
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=2.8 if accent else 1.9, zorder=2))
cx = bx + bw * 0.5
ax.text(cx, by + bh - 0.40, title, ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700 if accent else COL_PRIMARY,
weight="bold", zorder=6)
ax.text(cx, by + bh - 0.80, subtitle, ha="center", va="center",
fontsize=7.6, color=COL_SLATE_500, style="italic", zorder=6)
def _og_dir_box(ax, cx, cy, w, h, label, verdict, kind):
if kind == "good":
fc, ec, tc = COL_GOOD, COL_GOOD_EC, COL_GOOD_EC
else:
fc, ec, tc = COL_HARD, COL_HARD_EC, COL_HARD_EC
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, cy - h * 0.5), w, h,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=2.0, zorder=4))
ax.text(cx, cy + h * 0.16, label, ha="center", va="center",
fontsize=8.0, color=COL_TEXT, weight="bold", zorder=5)
ax.text(cx, cy - h * 0.24, verdict, ha="center", va="center",
fontsize=8.6, color=tc, weight="bold", zorder=5)
def _og_fill_card1(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
dw, dh = bw * 0.80, 0.74
y_good = by + bh - 1.72
y_hard = by + bh - 2.70
_og_dir_box(ax, cx, y_good, dw, dh,
"şekil → katlama deseni", "ÇÖZÜLEBİLİR", kind="good")
_og_dir_box(ax, cx, y_hard, dw, dh,
"desen → katlanır mı?", "NP-hard", kind="hard")
ax.add_patch(FancyArrowPatch(
(cx, y_good - dh * 0.5 - 0.02), (cx, y_hard + dh * 0.5 + 0.02),
arrowstyle="<|-|>", mutation_scale=11, color=COL_SLATE_500,
linewidth=1.5, zorder=5))
ax.text(cx + dw * 0.5 + 0.14, (y_good + y_hard) * 0.5, "yön\nönemli",
ha="left", va="center", fontsize=6.4, color=COL_SLATE_500,
style="italic", linespacing=1.0, zorder=6)
ax.text(cx, by + 0.88,
"kurmak ≠ çözmek: bir deseni ÜRETMEK\n"
"için algoritma var; bir desenin düz\n"
"katlanabilirliğine KARAR NP-zor",
ha="center", va="center", fontsize=6.5, color=COL_TEXT,
linespacing=1.16, zorder=6)
ax.text(cx, by + 0.30, "(Demaine + Bern–Hayes; Ku kanıta katkı)",
ha="center", va="center", fontsize=6.2, color=COL_SLATE_500,
style="italic", zorder=6)
def _og_draw_bunny(ax, cx, cy, s):
body = [(-0.55, -0.30), (-0.30, 0.20), (0.20, 0.35), (0.55, 0.10),
(0.55, -0.30), (-0.55, -0.30)]
ax.add_patch(Polygon([(cx + px * s, cy + py * s) for px, py in body],
closed=True, fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.6, zorder=4))
for off in (-0.18, 0.10):
ear = [(off, 0.30), (off - 0.06, 0.80), (off + 0.08, 0.34)]
ax.add_patch(Polygon([(cx + px * s, cy + py * s) for px, py in ear],
closed=True, fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.4, zorder=4))
ax.text(cx, cy - 0.52 * s, "3B model", ha="center", va="center",
fontsize=6.6, color=COL_SLATE_500, style="italic", zorder=5)
def _og_draw_crease_square(ax, cx, cy, s):
half = 0.65 * s
ax.add_patch(FancyBboxPatch(
(cx - half, cy - half), 2 * half, 2 * half,
boxstyle="square,pad=0.0", fc=COL_AMBER_100, ec=COL_ACCENT,
linewidth=2.0, zorder=3))
for (x0, y0, x1, y1) in [(-1, -1, 1, 1), (-1, 1, 1, -1),
(-1, 0, 1, 0), (0, -1, 0, 1),
(-1, -0.5, 0.5, 1), (-0.5, -1, 1, 0.5)]:
ax.plot([cx + x0 * half, cx + x1 * half],
[cy + y0 * half, cy + y1 * half],
color=COL_AMBER_700, linewidth=0.8, alpha=0.7, zorder=4)
ax.text(cx, cy - half - 0.18, "kare kâğıt deseni", ha="center", va="center",
fontsize=6.6, color=COL_SLATE_500, style="italic", zorder=5)
def _og_fill_card2(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
bunny_x = bx + bw * 0.30
sq_x = bx + bw * 0.72
mid_y = by + bh - 2.05
_og_draw_bunny(ax, bunny_x, mid_y, 0.62)
_og_draw_crease_square(ax, sq_x, mid_y, 0.62)
ax.add_patch(FancyArrowPatch(
(bunny_x + 0.42, mid_y), (sq_x - 0.50, mid_y), arrowstyle="-|>",
mutation_scale=14, color=COL_ACCENT, linewidth=2.4, zorder=5))
ax.text((bunny_x + sq_x) * 0.5, mid_y + 0.30, "Origamizer\n(Tachi)",
ha="center", va="center", fontsize=6.8, color=COL_AMBER_700,
weight="bold", linespacing=1.0, zorder=6)
badge_y = by + bh - 2.92
ax.add_patch(FancyBboxPatch(
(cx - bw * 0.34, badge_y - 0.22), bw * 0.68, 0.44,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_GOOD, ec=COL_GOOD_EC, linewidth=2.0, zorder=4))
ax.text(cx, badge_y, "%22 alan (çelik tavşan)", ha="center", va="center",
fontsize=8.6, color=COL_GOOD_EC, weight="bold", zorder=5)
strip_y = by + 0.78
ax.text(cx, strip_y, "90'lar şerit yöntemi", ha="center", va="center",
fontsize=7.6, color=COL_SLATE_500, zorder=6)
ax.plot([cx - 1.02, cx + 1.02], [strip_y, strip_y],
color=COL_HARD_EC, linewidth=1.8, zorder=7)
ax.text(cx, strip_y - 0.36, "“korkunç verimsiz”", ha="center", va="center",
fontsize=7.2, color=COL_HARD_EC, weight="bold", style="italic",
zorder=6)
def _og_draw_swan(ax, cx, cy, s):
pts = [
(-0.55, -0.20), (-0.30, 0.05), (0.00, 0.10), (0.25, 0.05),
(0.45, -0.10), (0.40, 0.25), (0.28, 0.55), (0.42, 0.70),
(0.32, 0.78), (0.18, 0.62), (0.12, 0.30), (-0.05, 0.00),
(-0.40, -0.05), (-0.60, -0.05), (-0.55, -0.20),
]
ax.add_patch(Polygon([(cx + px * s, cy + py * s) for px, py in pts],
closed=True, fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.7, zorder=4))
def _og_fill_card3(ax, bx, by, bw, bh):
cx = bx + bw * 0.5
fold_y = by + bh - 1.95
ax.add_patch(FancyBboxPatch(
(bx + bw * 0.14, fold_y - 0.32), bw * 0.30, 0.64,
boxstyle="round,pad=0.01,rounding_size=0.04",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=4))
ax.text(bx + bw * 0.29, fold_y, "düz katla", ha="center", va="center",
fontsize=7.0, color=COL_AMBER_700, weight="bold", zorder=5)
ax.plot([bx + bw * 0.46, bx + bw * 0.56], [fold_y, fold_y],
color=COL_HARD_EC, linewidth=2.0, linestyle=(0, (3, 2)), zorder=5)
ax.text(bx + bw * 0.51, fold_y + 0.26, "TEK\nkesik", ha="center",
va="center", fontsize=6.2, color=COL_HARD_EC, weight="bold",
linespacing=0.95, zorder=6)
ax.add_patch(FancyArrowPatch(
(bx + bw * 0.58, fold_y), (bx + bw * 0.70, fold_y), arrowstyle="-|>",
mutation_scale=12, color=COL_ACCENT, linewidth=2.0, zorder=5))
_og_draw_swan(ax, bx + bw * 0.84, fold_y, 0.60)
ax.text(cx, fold_y - 0.62, "fold-and-cut teoremi: tek kesikle herhangi şekil",
ha="center", va="center", fontsize=6.8, color=COL_PRIMARY,
weight="bold", zorder=6)
maze_y = by + bh - 3.55
ax.add_patch(FancyBboxPatch(
(bx + bw * 0.10, maze_y - 0.50), bw * 0.80, 1.00,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(cx, maze_y + 0.30, "maze folding", ha="center", va="center",
fontsize=8.4, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(cx, maze_y - 0.06, "köşe-tipi gadget'ları (derece 4 / 3 / 2)",
ha="center", va="center", fontsize=6.8, color=COL_TEXT, zorder=5)
ax.text(cx, maze_y - 0.34, "+ sabit ölçek", ha="center", va="center",
fontsize=7.2, color=COL_AMBER_700, weight="bold", style="italic",
zorder=5)
fig, ax = plt.subplots(figsize=(12.0, 5.5))
fig.patch.set_facecolor(COL_WHITE)
bw, bh = 3.45, 4.20
gap = 0.95
by = 0.0
box_x = [0.0, bw + gap, 2 * (bw + gap)]
_og_cards = [
(box_x[0], "design vs foldability", "iki yön — iki zorluk", False, _og_fill_card1),
(box_x[1], "Origamizer", "3B model → kare kâğıt deseni", True, _og_fill_card2),
(box_x[2], "fold-and-cut + maze", "tek kesik · labirent katlama", False, _og_fill_card3),
]
for x0, title, sub, accent, filler in _og_cards:
_og_card(ax, x0, by, bw, bh, title, sub, accent=accent)
filler(ax, x0, by, bw, bh)
badge_y = by - 0.58
bx0 = box_x[0] + bw * 0.06
bx1 = box_x[2] + bw - bw * 0.06
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,
"origami yolculuğu: yöntemlerin aslında ALGORİTMA olduğunu sonradan fark etti",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=5)
fig.suptitle(
"Computational origami (Demaine, L21): tasarla vs katla · Origamizer · "
"fold-and-cut + maze",
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()
```
## 3. Demaine — Self-Assembly (Geometrik Hesaplama Modeli) {#sec-3-demaine-self-assembly}
DNA şeritleriyle **kendiliğinden birleşen** kareler (tile): her karenin 4 kenarında "tutkal" (glue) deseni; yalnız tamamlayıcı desenler yapışır; sıcaklıkla ayarlanır (yüksek sıcaklık → yapışmaz, düşük → yanlış da yapışır). İyi ayarlanırsa **ikili sayaç** kuran bir sistem tasarlanır.
> *"the model of computation is geometric."* — Demaine
Bu, 6.006'nın "tek tek çalışan komut" modelinden **çok farklı**: program, o anda yüzen karelerin birleşimi. Bu modelde keyfi bir şekli **log n paralel adımda** (sabit sayıda tutkalla) inşa etmek kanıtlanabilir; hatta bir **replikatör** (bilinmeyen şekli kalıplayıp 3B fotokopi) kurulabilir. @fig-self-assembly DNA tile şemasını (tamamlayıcı kenarlar yapışır, sıcaklık ayarı) word-RAM vs geometrik model karşılaştırmasıyla yan yana koyar.
::: {.callout-tip title="Builder Notu — hesaplama modeli sınıfta kalmaz"}
Self-assembly'nin "geometrik hesaplama modeli", word-RAM'in tek-işlemci komut sırası varsayımının **bir alternatifidir** — Ders 31'deki 6.046 köprüsünün "model değişimi" maddesi burada fiziksel forma kavuşur. Klasik analiz "adım sayısı"nı sayar; geometrik modelde program yüzen karelerin eş-zamanlı birleşimidir, paralellik fiziksel. Bir builder için ders: bir problemin karmaşıklığı **hangi makine modelinde** analiz ettiğine bağlıdır; quantum, GPU/SIMD ve DNA computing aynı "modeli değiştir, yeni alt sınırlar al" felsefesini paylaşır.
:::
```{python}
#| label: fig-self-assembly
#| fig-cap: "Demaine vitrini: DNA öz-montaj (self-assembly) + GEOMETRİK hesaplama modeli (L21 §3 VİTRİN). SOL panel DNA karoları (tile): 4 kenarı tutkal (glue) desenli kareler; tamamlayıcı kenarlar (girinti ↔ çıkıntı) kendiliğinden yapışır — T1.sağ (tutkal A) ↔ T2.sol (tutkal A) amber okla YAPIŞIR; farklı tutkal (A ↔ B) yapışmaz (× işareti). Alt şerit sıcaklık ayarı: YÜKSEK → hiç yapışmaz, DÜŞÜK → yanlış kenarlar da yapışır. SAĞ panel 'hesaplama modeli GEOMETRİK (Demaine)': word-RAM vs geometrik mini-tablo (yürütme komut-sırası vs yüzen karelerin eş-zamanlı birleşimi; paralellik ardışık vs fiziksel paralel; durum bellek-hücreleri vs kenar-tutkalları + sıcaklık) + iki rozet (keyfi şekil SABİT tutkal kümesiyle log n PARALEL adımda kurulur; replikator bilinmeyen şekli kalıplar → 3B fotokopisini çıkarır). KAVRAMSAL VİTRİN (sayı yok; log n / ikili sayaç iddiaları Demaine L21 kaynak-alıntılı, motor rakamı değil)."
#| fig-width: 11.5
#| fig-height: 5.5
# fig-self-assembly (L21 §3 VİTRİN): KAVRAMSAL — sayı yok (log n iddiası kaynak-alıntılı).
GLUE_A = COL_AMBER_600
GLUE_B = COL_PRIMARY
GLUE_C = COL_AMBER_700
def _sa_draw_glue(ax, cx, cy, side, kind, color, size=0.13):
nx = {"top": (0, 1), "bottom": (0, -1), "left": (-1, 0), "right": (1, 0)}[side]
sign = 1 if kind == "tab" else -1
ox = nx[0] * size * sign
oy = nx[1] * size * sign
ax.add_patch(Circle((cx + ox, cy + oy), size,
facecolor=color if kind == "tab" else COL_WHITE,
edgecolor=color, linewidth=1.8, zorder=6))
def _sa_draw_tile(ax, x, y, w, h, label, glues, fill=COL_BG, edge=COL_PRIMARY, lw=1.8):
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.01,rounding_size=0.05",
fc=fill, ec=edge, linewidth=lw, zorder=4))
cx, cy = x + w / 2, y + h / 2
ax.text(cx, cy, label, ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=7)
mids = {
"top": (cx, y + h), "bottom": (cx, y),
"left": (x, cy), "right": (x + w, cy),
}
for side, g in glues.items():
if g is None:
continue
kind, color = g
mx, my = mids[side]
_sa_draw_glue(ax, mx, my, side, kind, color)
return cx, cy
def _sa_draw_left_panel(ax):
ax.set_xlim(0, 5.9)
ax.set_ylim(0, 5.6)
ax.set_aspect("equal")
ax.axis("off")
ax.text(2.95, 5.35, "DNA karoları (tile) — tutkal desenli kenarlar",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
ax.text(2.95, 5.02, "tamamlayıcı kenarlar (girinti ↔ çıkıntı) kendiliğinden yapışır",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic")
tw = 1.25
x1, y1 = 0.55, 2.95
_sa_draw_tile(ax, x1, y1, tw, tw, "T1",
{"right": ("tab", GLUE_A), "top": ("tab", GLUE_B),
"left": None, "bottom": None})
x2, y2 = x1 + tw + 0.55, y1
_sa_draw_tile(ax, x2, y2, tw, tw, "T2",
{"left": ("slot", GLUE_A), "top": ("tab", GLUE_B),
"right": ("tab", GLUE_C), "bottom": None})
gap_cx = (x1 + tw + x2) / 2
midy = y1 + tw / 2
ax.add_patch(FancyArrowPatch(
(x2 + tw + 0.78, midy), (gap_cx + 0.14, midy),
arrowstyle="-|>", mutation_scale=13, color=COL_ACCENT,
linewidth=2.0, zorder=8))
ax.text(x2 + tw + 0.85, midy + 0.05, "tutkal A ↔ A\nYAPIŞIR",
ha="left", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=8)
x3, y3 = 0.55, 1.00
_sa_draw_tile(ax, x3, y3, tw, tw, "T3",
{"right": ("tab", GLUE_A), "top": None,
"left": None, "bottom": None})
x4, y4 = x3 + tw + 1.05, y3
_sa_draw_tile(ax, x4, y4, tw, tw, "T4",
{"left": ("slot", GLUE_B), "top": None,
"right": None, "bottom": None})
gapx = (x3 + tw + x4) / 2
gapy = y3 + tw / 2
ax.add_patch(FancyArrowPatch(
(x3 + tw + 0.10, gapy), (gapx - 0.12, gapy),
arrowstyle="-|>", mutation_scale=11, color=COL_SLATE_400,
linewidth=1.5, linestyle="--", zorder=5))
ax.text(gapx, gapy + 0.42, "A ↔ B\nyapışmaz",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text(gapx, gapy - 0.02, "×", ha="center", va="center",
fontsize=16, color=COL_SLATE_500, weight="bold", zorder=7)
ax.add_patch(FancyBboxPatch(
(0.25, 0.10), 5.40, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=3))
ax.text(2.95, 0.41,
"sıcaklık ayarı: YÜKSEK → hiç yapışmaz · DÜŞÜK → yanlış kenarlar da yapışır",
ha="center", va="center", fontsize=8.0, color=COL_AMBER_700,
weight="bold", zorder=5)
_SA_MODEL_ROWS = [
("yürütme", "komut sırası\n(fetch-execute)", "yüzen karelerin\neş-zamanlı birleşimi"),
("paralellik", "ardışık — adım adım", "fiziksel paralel\n(öz-montaj)"),
("durum", "bellek hücreleri\n+ adresler", "kenar tutkalları\n+ sıcaklık"),
]
def _sa_draw_right_panel(ax):
ax.set_xlim(0, 6.4)
ax.set_ylim(0, 5.6)
ax.set_aspect("auto")
ax.axis("off")
ax.add_patch(FancyBboxPatch(
(0.15, 4.78), 6.10, 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(3.20, 5.11, "hesaplama modeli: GEOMETRİK (Demaine)",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=5)
col_x = [0.15, 1.70, 3.95]
col_w = [1.50, 2.20, 2.30]
head_y = 4.30
heads = ["", "word-RAM (klasik)", "geometrik (öz-montaj)"]
head_cols = [COL_TEXT, COL_PRIMARY, COL_AMBER_700]
for ci, (cx0, cw, ht, hc) in enumerate(zip(col_x, col_w, heads, head_cols)):
if ht:
ax.add_patch(FancyBboxPatch(
(cx0, head_y), cw, 0.48, boxstyle="square,pad=0.0",
fc=COL_BG if ci == 1 else COL_AMBER_100,
ec=COL_PRIMARY if ci == 1 else COL_ACCENT,
linewidth=1.6, zorder=3))
ax.text(cx0 + cw / 2, head_y + 0.24, ht, ha="center", va="center",
fontsize=8.6, color=hc, weight="bold", zorder=5)
row_h = 0.74
for r, (aspect, wram, geo) in enumerate(_SA_MODEL_ROWS):
y = head_y - (r + 1) * row_h
ax.text(col_x[0] + col_w[0] - 0.10, y + row_h / 2, aspect,
ha="right", va="center", fontsize=8.4, color=COL_TEXT,
weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(col_x[1], y + 0.05), col_w[1], row_h - 0.10, boxstyle="square,pad=0.0",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.3, zorder=2))
ax.text(col_x[1] + col_w[1] / 2, y + row_h / 2, wram,
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
zorder=4, linespacing=1.15)
ax.add_patch(FancyBboxPatch(
(col_x[2], y + 0.05), col_w[2], row_h - 0.10, boxstyle="square,pad=0.0",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.6, zorder=2))
ax.text(col_x[2] + col_w[2] / 2, y + row_h / 2, geo,
ha="center", va="center", fontsize=7.6, color=COL_AMBER_700,
weight="bold", zorder=4, linespacing=1.15)
badge_y = 0.95
badge_w = 2.95
badge_h = 0.92
ax.add_patch(FancyBboxPatch(
(0.15, badge_y), badge_w, badge_h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(0.15 + badge_w / 2, badge_y + badge_h - 0.24, "keyfi şekil",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(0.15 + badge_w / 2, badge_y + 0.33,
"SABİT tutkal kümesiyle\nlog n PARALEL adımda kurulur",
ha="center", va="center", fontsize=8.0, color=COL_TEXT, zorder=5)
bx2 = 0.15 + badge_w + 0.30
ax.add_patch(FancyBboxPatch(
(bx2, badge_y), badge_w, badge_h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(bx2 + badge_w / 2, badge_y + badge_h - 0.24, "replikator",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(bx2 + badge_w / 2, badge_y + 0.33,
"bilinmeyen şekli kalıplar →\n3B \"fotokopisini\" çıkarır",
ha="center", va="center", fontsize=8.0, color=COL_TEXT, zorder=5)
ax.text(3.20, 0.40,
"ikili sayaç, keyfi şekil, replikator: tutkal desenli karolarla fiziksel hesaplama (Demaine L21)",
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=5)
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 5.5),
gridspec_kw={"width_ratios": [1.0, 1.12]})
fig.patch.set_facecolor(COL_WHITE)
_sa_draw_left_panel(axL)
_sa_draw_right_panel(axR)
fig.suptitle(
"Demaine vitrini: DNA öz-montaj (self-assembly) + GEOMETRİK hesaplama modeli (L21 §3)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## 4. Demaine — İleri Veri Yapıları, Planar Çizgeler, Recreational {#sec-4-demaine-ileri-veri-yapilari}
**İleri Veri Yapıları (6.851):** dinamik **sıralı** küme (insert/delete + find-next/prev). 6.006'da gördüğümüz **set AVL** (Ders 10) = $O(\log n)$. Daha iyisi word-RAM'de: **van Emde Boas** = $O(\log w)$ (w = kelime boyutu), **fusion trees** = $O(\log n / \log w)$. İkisinin min'i ≈ $O(\sqrt{\log n / \log\log n})$ — AVL'nin $\log n$'inden hayli iyi (sıralı küme için sabit-zaman **imkânsız**, kanıtlanır). Bunlar **kaynak-formül**dür (Demaine L21), motor değil.
**Planar Çizgeler:** yolu düzlemde çizişimsiz (veya az çizişimli) çizge. Planar'da SSSP **lineer** (Dijkstra'nın $v \log v$'si yerine — Ders 19); planar Bellman-Ford ≈ **lineer** ($v \log^2 v / \log\log v$, $v^2$ yerine). **Baker yaklaşımı (1994):** BFS katmanlarına ayır (Ders 13'teki BFS katmanları), her k'ıncı katmanı sil (~$1/k$ kayıp) → $1 + 1/k$ yaklaşım; kalan sabit-katmanlı yapı "birkaç döngü" → fancy DP polinom-zamanda çözer → **PTAS** (her ε için $1+\varepsilon$, ama büyük ε daha yavaş).
**Recreational (6.892):** oyun/bulmaca zorluk kanıtları. Tetris, Super Mario, Portal, The Witness **NP-hard**; "Recurse" **undecidable** (mükemmel oynayan algoritma yok). Ayrıca balon büküm, **resim-asma problemi** (iki çividen herhangi biri çıkınca resim düşsün; monoton Boole fonksiyonları; Rivest ile sonuç).
## 5. Solomon — Mesh Üzerinde En Kısa Yol (Dijkstra Neden Yanlış) {#sec-5-solomon-mesh}
Solomon uygulamalı geometri/graphics çalışır (6.837 Computer Graphics, 6.838 geometri işleme). Ana nesne: **simplicial complex** — düğüm + kenar + **üçgen** kümesi. 6.006'da çizge sadece düğüm+kenardır; graphics'te bu bir **yüzey**dir.
**Tuzak:** üçgen mesh'te iki köşe arası en kısa yol için kenarlarda Dijkstra (Ders 19) koşturmak **yanlış** (sık yapılan hata). Çapraz geçen gerçek geodezik daha kısadır:
> *"graphs don't know how to talk to triangles."* — Solomon
@fig-mesh-dijkstra bunu motor tanığıyla gösterir: birim kare mesh'te (4 köşe, 2 üçgen, köşegen **kenar yok**) karşı köşeye kenar-Dijkstra iki eksen-paralel kenar boyunca $2.0$ verir; gerçek geodezik üçgen yüzeyini çaprazlar ve $\sqrt{2} \approx 1.4142$ olur. Oran $\sqrt{2}$ — kenar-Dijkstra **%41 daha uzun**. Tüm bu sayılar `mesh_edge_vs_geodesic()`'ten **canlı** gelir (kenar yolu $= 2.0$, geodezik $= \sqrt{2}$, oran $= \sqrt{2}$; assert ile); `_verify` D32 koşusunda PASS.
Doğru algoritma **MMP** (üçgen alan üzerinde geodezik, $O(n \log n)$) — Dijkstra'nın mesafe-fonksiyonu **seviye kümeleri** fikrini genişletir (ama pencereleme ile). Pratikte **fast marching** (geodeziğin yaklaşığı; daha hızlı, kolay, neredeyse ayırt edilemez) tercih edilir.
```{python}
#| label: fig-mesh-dijkstra
#| fig-cap: "Çizgeler üçgenlerle konuşamaz: kenar-Dijkstra (2.0) vs gerçek geodezik (√2) — Solomon L21 §5 İMZA, motor-tanıklı. SOL birim kare mesh: 4 köşe (0,0)(1,0)(1,1)(0,1), iki üçgen yüzey, köşegen KENAR yok; eksen-paralel kenarlar w=1 ince slate; kenar-Dijkstra yolu (0,0)→(1,0)→(1,1) kalın slate KIRIK yol 'uzunluk 2.0'; gerçek geodezik (0,0)→(1,1) düz amber çapraz '√2 ≈ 1.414'; '%41 daha uzun!' rozeti. Tüm sayılar mesh_edge_vs_geodesic()'ten CANLI: kenar yolu 2.0, geodezik √2, oran √2, yüzde (√2−1)·100 ≈ 41 (assert). SAĞ kural kutuları: Sorun çizge (düğüm+kenar) üçgenlerin İÇİNDEN geçen yolları BİLMEZ; Solomon alıntısı 'graphs don't know how to talk to triangles'; Doğru çözüm MMP kesin geodezik O(n log n) — Dijkstra'nın seviye-kümeleri + pencereleme (Mitchell–Mount–Papadimitriou); Pratik fast marching eikonal denklem ızgarada yaklaşık hızlı. Alt not: graphics'te simplicial complex = düğüm + kenar + ÜÇGEN; 6.006 çizgesi yetmez."
#| fig-width: 11.5
#| fig-height: 5.8
# fig-mesh-dijkstra (L21 §5 İMZA): veri MOTORDAN + ASSERT (elle kopya yok).
_md_R = 0.055
def _md_corner(ax, x, y, label, *, dx=0.0, dy=0.0):
ax.add_patch(Circle((x, y), _md_R, facecolor=COL_PRIMARY, edgecolor=COL_PRIMARY,
linewidth=1.2, zorder=6))
ax.text(x + dx, y + dy, label, ha="center", va="center", fontsize=9,
color=COL_SLATE_500, weight="bold", zorder=6)
def _md_draw_mesh(ax, edge_path, geodesic, ratio):
pct = (ratio - 1.0) * 100.0 # motordan: (√2 − 1)·100 ≈ %41
ax.text(0.5, 1.42, "Birim kare mesh — çizge yolu ÜÇGENİ göremez",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=7)
ax.text(0.5, 1.30, "4 köşe · 2 üçgen · köşegen KENAR yok",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=7)
ax.add_patch(Polygon([(0, 0), (1, 0), (1, 1)], closed=True,
facecolor=COL_BG, edgecolor="none", zorder=1))
ax.add_patch(Polygon([(0, 0), (1, 1), (0, 1)], closed=True,
facecolor=COL_WHITE, edgecolor="none", zorder=1))
square = [((0, 0), (1, 0)), ((1, 0), (1, 1)),
((1, 1), (0, 1)), ((0, 1), (0, 0))]
for (p0, p1) in square:
ax.plot([p0[0], p1[0]], [p0[1], p1[1]], color=COL_SLATE_400,
linewidth=1.4, zorder=2)
for (p0, p1) in square:
mx, my = (p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5
ax.text(mx, my, "1", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, zorder=3,
bbox=dict(boxstyle="round,pad=0.10", fc=COL_WHITE,
ec=COL_SLATE_400, lw=0.8))
ax.plot([0, 1], [0, 1], color=COL_SLATE_400, linewidth=1.0,
linestyle=(0, (4, 3)), zorder=2)
ax.add_patch(FancyArrowPatch(
(0, 0), (1, 0), arrowstyle="-|>", mutation_scale=15,
color=COL_PRIMARY, linewidth=3.4, shrinkA=8, shrinkB=2, zorder=4))
ax.add_patch(FancyArrowPatch(
(1, 0), (1, 1), arrowstyle="-|>", mutation_scale=15,
color=COL_PRIMARY, linewidth=3.4, shrinkA=2, shrinkB=8, zorder=4))
edge_str = f"{edge_path:.1f}" # motordan 2.0
ax.text(1.085, 0.5, f"kenar-Dijkstra\nuzunluk {edge_str}",
ha="left", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.add_patch(FancyArrowPatch(
(0, 0), (1, 1), arrowstyle="-|>", mutation_scale=15,
color=COL_ACCENT, linewidth=3.0, shrinkA=8, shrinkB=8, zorder=5))
geo_str = f"{geodesic:.3f}" # motordan 1.414
ax.text(0.30, 0.66, f"geodezik √2 ≈ {geo_str}",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", rotation=45, zorder=6)
_md_corner(ax, 0, 0, "(0,0)", dx=-0.085, dy=-0.075)
_md_corner(ax, 1, 0, "(1,0)", dx=0.085, dy=-0.075)
_md_corner(ax, 1, 1, "(1,1)", dx=0.085, dy=0.075)
_md_corner(ax, 0, 1, "(0,1)", dx=-0.085, dy=0.075)
ax.add_patch(FancyBboxPatch(
(0.30, -0.40), 0.85, 0.24,
boxstyle="round,pad=0.02,rounding_size=0.05",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=6))
ax.text(0.725, -0.28, f"%{pct:.0f} daha uzun!",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=7)
ax.set_xlim(-0.35, 1.75)
ax.set_ylim(-0.55, 1.55)
ax.set_aspect("equal")
ax.axis("off")
def _md_rule_box(ax, x, y, w, h, title, body, *, accent=False):
if accent:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tcol = COL_BG, COL_PRIMARY, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.03,rounding_size=0.06",
fc=fc, ec=ec, linewidth=2.0, zorder=3))
ax.text(x + 0.12, y + h - 0.16, title, ha="left", va="top",
fontsize=10.5, color=tcol, weight="bold", zorder=4)
ax.text(x + 0.12, y + h - 0.42, body, ha="left", va="top",
fontsize=9, color=COL_TEXT, zorder=4)
def _md_draw_rules(ax):
ax.text(2.55, 5.62, "Çizge neden yetmez — ve doğru araç",
ha="center", va="center", fontsize=12, color=COL_TEXT,
weight="bold", zorder=6)
_md_rule_box(
ax, 0.10, 4.05, 4.90, 1.15,
"Sorun: çizge (düğüm + kenar) üçgenlerin İÇİNDEN geçen yolları BİLMEZ",
"En kısa yol köşeden köşeye kenarlarla zıplar; oysa gerçek geodezik\n"
"üçgen yüzeyini düz keser. Kenar grafiği yüzeyi temsil edemez.")
ax.add_patch(FancyBboxPatch(
(0.10, 3.05), 4.90, 0.82,
boxstyle="round,pad=0.03,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(0.30, 3.66, "“graphs don't know how to talk to triangles”",
ha="left", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", style="italic", zorder=4)
ax.text(0.30, 3.30, "— Justin Solomon, 6.006 L21 §5",
ha="left", va="center", fontsize=8.5, color=COL_SLATE_500,
zorder=4)
_md_rule_box(
ax, 0.10, 1.80, 4.90, 1.08,
"Doğru çözüm: MMP — kesin geodezik O(n log n)",
"Dijkstra'nın seviye-kümeleri (level sets) fikri + pencereleme\n"
"(windowing): mesafe dalgası yüzey boyunca yayılır, köşelerle sınırlı\n"
"değil. Mitchell–Mount–Papadimitriou algoritması.")
_md_rule_box(
ax, 0.10, 0.95, 4.90, 0.68,
"Pratik: fast marching — yaklaşık, hızlı",
"Eikonal denklemini ızgarada çözer; kesin değil ama büyük mesh'lerde\n"
"ucuz. Üretimde sık tercih edilir.")
ax.add_patch(FancyBboxPatch(
(0.10, 0.10), 4.90, 0.66,
boxstyle="round,pad=0.02,rounding_size=0.05",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=3))
ax.text(2.55, 0.43,
"Graphics'te simplicial complex = düğüm + kenar + ÜÇGEN; "
"6.006 çizgesi (düğüm + kenar) yetmez.",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=4)
ax.set_xlim(0.0, 5.10)
ax.set_ylim(0.0, 5.90)
ax.set_aspect("auto")
ax.axis("off")
# --- motor verisi + iç tutarlılık (figür yalnız bunu çizer) ---
_md_edge, _md_geo, _md_ratio = mesh_edge_vs_geodesic()
assert _md_edge == 2.0, _md_edge
assert abs(_md_geo - 2 ** 0.5) < 1e-12, _md_geo
assert abs(_md_ratio - 2 ** 0.5) < 1e-12, _md_ratio
assert abs((_md_ratio - 1.0) - (2 ** 0.5 - 1.0)) < 1e-12
fig, (ax_l, ax_r) = plt.subplots(
1, 2, figsize=(11.5, 5.8),
gridspec_kw={"width_ratios": [5.0, 5.1]})
fig.patch.set_facecolor(COL_WHITE)
_md_draw_mesh(ax_l, _md_edge, _md_geo, _md_ratio)
_md_draw_rules(ax_r)
fig.suptitle(
"Çizgeler üçgenlerle konuşamaz: kenar-Dijkstra (2.0) vs gerçek geodezik (√2)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
fig.subplots_adjust(left=0.02, right=0.98, top=0.90, bottom=0.04, wspace=0.06)
plt.show()
```
## 6. Solomon — Ray Casting & Stanford Bunny {#sec-6-solomon-ray-casting}
**Ray casting (6.837):** her ekran pikseli için, gözden bir ışın gönder, çarptığı **ilk** nesneyi bul → renk. Maliyet: piksel sayısı × nesne sayısı = $O(p \cdot n)$. **Stanford Bunny** (69.000 üçgen) × 1080p (~2 milyon piksel) = iki büyük sayının çarpımı, çok yavaş. Bu rakamlar (69.000 üçgen, ~2 milyon piksel, ~30 fps bütçesi) **kaynak verisidir** (L21 birebir), motor değil. Her graphics özelliği (saydamlık, yansıma, parçalanma) maliyeti artırır.
**Çıkış: veri yapıları + algoritmalar.** Tavşanı bir kutuya koy; ışın kutuya değmiyorsa tavşana değmez ($O(1)$ hızlanma). Kutuyu özyinelemeli ikiye böl → **uzay-bölme ağacı** (KD tree). İdealde $O(p \log n)$ (ağaçta gez) — ama bu bir **sezgisel**; veriye bağlı, ortalama $\log n$. **Scene graph:** sahnedeki 100 özdeş sandalye için 100 model saklama; bir sandalye + her kopya için bir dönüşüm → **DAG** (yönlü çevrimsiz çizge). GPU = **SIMD** paralellik; numerical + approximation; algı koruma (~30 fps bütçesi).
@fig-raycast bu hızlandırmayı Solomon örneğinin 1B analoğuyla motor-tanıklı gösterir: aynı sahnede (seed-32 ile 30 nesne × 25 ışın) naif `ray_cast_naive` **750 karşılaştırma**, indexed `ray_cast_indexed` (sırala + ikili arama) **409 karşılaştırma** yapar — ve **hit'ler birebir aynı** (doğruluk korunur, yalnız iş azalır). Bu sayaçlar motordan canlı gelir (assert ile); `_verify` D32 koşusunda daha geniş 40-rastgele sahnede de naif toplamı indexed toplamından daima büyüktür (motor tanığı; örn. 5526 > 4494 türünden — naif > indexed daima).
::: {.callout-tip title="Builder Notu — KD tree / collision gerçek-sistem"}
Ray casting'in $O(p \cdot n) \to O(p \log n)$ kazancı, bir builder için **uzay-bölme veri yapısı** (KD tree, BVH, octree) refleksidir: "her nesneyi her sorgu için tarama, sahneyi hiyerarşik kutula". Aynı yapı **çarpışma tespiti** (collision detection), 3B tarama, oyun navigasyonu ve nearest-neighbor aramada döner. Dikkat çekici nokta Solomon'ın "**sezgisel** — $\log n$ veri dağılımına bağlı" uyarısıdır: gerçek sistemde garanti değil, ortalama-durum performans mühendisliğidir. Scene graph'ın **DAG**'ı (Ders 19'daki DAG soyutlaması) ise tekrar eden geometriyi bir kez saklayıp dönüşümle paylaştırır — bellek mühendisliğinin temel deseni.
:::
```{python}
#| label: fig-raycast
#| fig-cap: "Ray casting hızlandırma: naif O(p·n) → sıralı + ikili arama (uzay-bölme ağacı) — Solomon L21 §6 İMZA, motor-tanıklı. ÜST 1B model şeması (deterministik seed-32 sahne: 30 nesne × 25 ışın): sayı doğrusu üzerinde aralıklar (nesneler) + ışın noktaları (amber); NAİF her ışın × her nesne çizgi-demeti (yoğun slate, O(p·n)); INDEXED sırala + ikili arama (seyrek amber, ~O(p log n)). Sayaç rozetleri MOTORDAN: naif karşılaştırma 750 vs indexed 409 (kazanç 750→409); 'hit'ler BİREBİR aynı' doğruluk tanığı (yeşil). Tüm sayaçlar ray_cast_naive / ray_cast_indexed'ten CANLI (assert: c1==750, c2==409, hit'ler eşit). ALT Stanford Bunny anlatım kutusu (kaynak L21 §6): Naif O(p·n) = 69.000 üçgen × ~2 milyon piksel (1080p) iki dev sayının çarpımı → sınırlayıcı kutu O(1) eleme → uzay-bölme ağacı (KD) → ideal O(p log n) SEZGİSEL veriye bağlı (Solomon). Scene graph: 100 özdeş sandalye = 1 model + 100 dönüşüm = DAG. Donanım: GPU SIMD paralellik + numerical/approximation + ~30 fps render bütçesi. Bunny rakamları kaynak L21 (motor değil); sayaçlar motordan."
#| fig-width: 12.0
#| fig-height: 6.3
# fig-raycast (L21 §6 İMZA): sayaçlar MOTORDAN (deterministik seed-32) + ASSERT.
import random as _rc_random
def _rc_scene():
"""seed 32 ile 30 aralık (nesne) + 25 ışın; (intervals, rays, naif, indexed)."""
_rc_random.seed(32)
intervals = sorted(
(a, a + _rc_random.randint(1, 20))
for a in (_rc_random.randint(0, 80) for _ in range(30)))
rays = [_rc_random.randint(0, 100) for _ in range(25)]
h1, c1 = ray_cast_naive(rays, intervals)
h2, c2 = ray_cast_indexed(rays, intervals)
return intervals, rays, (h1, c1), (h2, c2)
def _rc_draw_scene(ax, intervals, rays, naive, indexed):
h1, c1 = naive
h2, c2 = indexed
n_obj = len(intervals)
n_ray = len(rays)
show_obj = intervals[:7]
show_ray = sorted(set(rays))[:7]
xmax_data = 100.0
def X(v):
return v / xmax_data * 10.0
y_axis = 0.0
y_obj0 = 1.05
obj_gap = 0.42
ax.plot([X(0), X(100)], [y_axis, y_axis], color=COL_SLATE_400,
linewidth=1.6, zorder=2)
for t in (0, 25, 50, 75, 100):
ax.plot([X(t), X(t)], [y_axis - 0.06, y_axis + 0.06],
color=COL_SLATE_400, linewidth=1.2, zorder=2)
ax.text(X(t), y_axis - 0.22, str(t), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=2)
ax.text(X(100) + 0.25, y_axis, "konum", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=2)
obj_centers = []
for k, (a, b) in enumerate(show_obj):
y = y_obj0 + k * obj_gap
ax.add_patch(FancyBboxPatch(
(X(a), y - 0.11), X(b) - X(a), 0.22,
boxstyle="round,pad=0.01,rounding_size=0.03",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(X(a) - 0.10, y, f"n{k}", ha="right", va="center",
fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=3)
obj_centers.append(((X(a) + X(b)) * 0.5, y))
y_obj_top = y_obj0 + (len(show_obj) - 1) * obj_gap
ray_pts = []
for r in show_ray:
ax.add_patch(Circle((X(r), y_axis), 0.07, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=1.0, zorder=5))
ray_pts.append((X(r), y_axis))
ax.text(X(show_ray[-1]) + 0.05, y_axis + 0.28, "ışınlar",
ha="left", va="bottom", fontsize=8, color=COL_AMBER_700,
weight="bold", zorder=5)
for (rx, ry) in ray_pts[:3]:
for (ox, oy) in obj_centers:
ax.plot([rx, ox], [ry, oy], color=COL_SLATE_400,
linewidth=0.5, alpha=0.55, zorder=1)
ax.text(X(8), y_obj_top + 0.58, "NAİF: her ışın × her nesne", ha="left",
va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(X(8), y_obj_top + 0.34, "tüm çiftleri dene → O(p·n)", ha="left",
va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6)
for j, (rx, ry) in enumerate(ray_pts[:3]):
ox, oy = min(obj_centers, key=lambda c: abs(c[0] - rx))
ax.add_patch(FancyArrowPatch(
(rx, ry + 0.10), (ox, oy - 0.12), arrowstyle="-|>",
mutation_scale=11, color=COL_ACCENT, linewidth=1.8,
zorder=4, connectionstyle="arc3,rad=0.12"))
ax.text(X(58), y_obj_top + 0.58, "INDEXED: sırala + ikili arama", ha="left",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(X(58), y_obj_top + 0.34, "ön-işleme → adaya atla → ~O(p log n)",
ha="left", va="center", fontsize=8.5, color=COL_AMBER_600,
style="italic", zorder=6)
by = y_obj_top + 1.30
ax.add_patch(FancyBboxPatch(
(X(2), by), 3.0, 0.52, boxstyle="round,pad=0.03,rounding_size=0.06",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=7))
ax.text(X(2) + 0.15, by + 0.26, f"naif karşılaştırma: {c1}", ha="left",
va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=8)
ax.add_patch(FancyBboxPatch(
(X(40), by), 3.0, 0.52, boxstyle="round,pad=0.03,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=7))
ax.text(X(40) + 0.15, by + 0.26, f"indexed karşılaştırma: {c2}", ha="left",
va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=8)
ax.add_patch(FancyArrowPatch(
(X(40) - 0.15, by + 0.26), (X(40) - 0.85, by + 0.26),
arrowstyle="-|>", mutation_scale=14, color=COL_AMBER_700,
linewidth=2.0, zorder=8))
ax.text(X(40) - 0.50, by - 0.13, f"{c1}→{c2}", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=8)
COL_GOOD = "#cfe8da"
COL_GOOD_EC = "#3f7d5e"
ax.add_patch(FancyBboxPatch(
(X(74), by), 2.55, 0.52, boxstyle="round,pad=0.03,rounding_size=0.06",
fc=COL_GOOD, ec=COL_GOOD_EC, linewidth=2.0, zorder=7))
ax.text(X(74) + 1.27, by + 0.26, "hit'ler BİREBİR aynı", ha="center",
va="center", fontsize=10, color="#2f5e47", weight="bold", zorder=8)
ax.text(X(50), y_axis - 0.40,
f"{n_ray} ışın × {n_obj} nesne sahnesi (seed 32) — doğruluk korunur, "
"iş azalır",
ha="center", va="top", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=7)
ax.set_xlim(X(-2), X(108))
ax.set_ylim(y_axis - 0.75, by + 0.78)
ax.set_aspect("auto")
ax.axis("off")
def _rc_flow_box(ax, x, y, w, h, title, body, *, accent=False, good=False):
if good:
fc, ec, tcol = "#cfe8da", "#3f7d5e", "#2f5e47"
elif accent:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tcol = COL_BG, COL_PRIMARY, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.03,rounding_size=0.05",
fc=fc, ec=ec, linewidth=2.0, zorder=3))
ax.text(x + w * 0.5, y + h - 0.14, title, ha="center", va="top",
fontsize=9.5, color=tcol, weight="bold", zorder=4)
ax.text(x + w * 0.5, y + h - 0.40, body, ha="center", va="top",
fontsize=8, color=COL_TEXT, zorder=4)
def _rc_flow_arrow(ax, x0, x1, y):
ax.add_patch(FancyArrowPatch(
(x0, y), (x1, y), arrowstyle="-|>", mutation_scale=15,
color=COL_AMBER_700, linewidth=2.2, zorder=5))
def _rc_draw_bunny(ax):
ax.text(5.0, 3.78, "Stanford Bunny — O(p·n)'den uzay-bölme ağacına (kaynak: L21 §6)",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=6)
fy, fh = 2.05, 1.30
_rc_flow_box(
ax, 0.10, fy, 2.30, fh, "Naif: O(p·n)",
"69.000 üçgen ×\n~2 milyon piksel (1080p)\n= iki dev sayının çarpımı\n→ çok yavaş",
accent=False)
ax.text(1.25, fy - 0.18, "kaynak: L21 §6", ha="center", va="center",
fontsize=7, color=COL_SLATE_500, style="italic", zorder=6)
_rc_flow_arrow(ax, 2.45, 2.78, fy + fh * 0.5)
_rc_flow_box(
ax, 2.82, fy, 2.20, fh, "Sınırlayıcı kutu",
"tavşanı bir kutuya koy;\nışın kutuya değmezse\nhiçbir üçgeni kontrol etme\n→ O(1) eleme",
accent=False)
_rc_flow_arrow(ax, 5.07, 5.40, fy + fh * 0.5)
_rc_flow_box(
ax, 5.44, fy, 2.20, fh, "Uzay-bölme ağacı (KD)",
"kutuyu özyinelemeli\nİKİYE böl → ağaçta gez,\nçoğu üçgeni atla",
accent=True)
_rc_flow_arrow(ax, 7.69, 8.02, fy + fh * 0.5)
_rc_flow_box(
ax, 8.06, fy, 1.84, fh, "ideal O(p log n)",
"ağaçta log n gezinme\nSEZGİSEL — veriye\nbağlı (Solomon)",
good=True)
sy, sh = 0.18, 1.40
ax.add_patch(FancyBboxPatch(
(0.10, sy), 4.80, sh, boxstyle="round,pad=0.03,rounding_size=0.05",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=3))
ax.text(0.30, sy + sh - 0.16, "Scene graph — tekrarı paylaş",
ha="left", va="top", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
ax.text(0.30, sy + sh - 0.42, "100 özdeş sandalye = 1 model + 100 dönüşüm",
ha="left", va="top", fontsize=8, color=COL_TEXT, zorder=4)
ax.add_patch(Circle((1.05, sy + 0.42), 0.16, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.0, zorder=5))
ax.text(1.05, sy + 0.42, "M", ha="center", va="center", fontsize=9,
color=COL_AMBER_700, weight="bold", zorder=6)
for dx in (2.0, 2.55, 3.10, 3.65):
ax.add_patch(Circle((dx, sy + 0.42), 0.11, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.4, zorder=5))
ax.add_patch(FancyArrowPatch(
(1.22, sy + 0.42), (dx - 0.12, sy + 0.42), arrowstyle="-|>",
mutation_scale=9, color=COL_SLATE_400, linewidth=1.0,
zorder=4, connectionstyle="arc3,rad=-0.12"))
ax.text(4.05, sy + 0.42, "DAG", ha="left", va="center", fontsize=9,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.add_patch(FancyBboxPatch(
(5.10, sy), 4.80, sh, boxstyle="round,pad=0.03,rounding_size=0.05",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.6, zorder=3))
ax.text(5.30, sy + sh - 0.16, "Donanım + bütçe",
ha="left", va="top", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
ax.text(5.30, sy + sh - 0.42,
"GPU = SIMD paralellik (ışınları aynı anda);\n"
"numerical + approximation; algı koruma\n"
"→ ~30 fps render bütçesi",
ha="left", va="top", fontsize=8, color=COL_TEXT, zorder=4)
ax.set_xlim(0.0, 10.0)
ax.set_ylim(0.0, 4.05)
ax.set_aspect("auto")
ax.axis("off")
_rc_intervals, _rc_rays, _rc_naive, _rc_indexed = _rc_scene()
_rc_h1, _rc_c1 = _rc_naive
_rc_h2, _rc_c2 = _rc_indexed
assert _rc_h1 == _rc_h2, "hit'ler aynı değil" # doğruluk korunur
assert _rc_c1 > _rc_c2, (_rc_c1, _rc_c2) # ön-işleme kazancı
assert _rc_c1 == 750, _rc_c1 # seed 32 deterministik
assert _rc_c2 == 409, _rc_c2
assert len(_rc_intervals) == 30 and len(_rc_rays) == 25
fig, (ax_top, ax_bot) = plt.subplots(
2, 1, figsize=(12.0, 6.3),
gridspec_kw={"height_ratios": [1.05, 1.0]})
fig.patch.set_facecolor(COL_WHITE)
_rc_draw_scene(ax_top, _rc_intervals, _rc_rays, _rc_naive, _rc_indexed)
_rc_draw_bunny(ax_bot)
fig.suptitle(
"Ray casting hızlandırma: naif O(p·n) → sıralı + ikili arama (uzay-bölme ağacı)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
fig.subplots_adjust(left=0.02, right=0.98, top=0.91, bottom=0.03, hspace=0.14)
plt.show()
```
## 7. Solomon — Politik Redistricting (Gerrymandering) {#sec-7-solomon-redistricting}
ABD'de Kongre seçim bölgelerini çizmek (gerrymandering: sınırları çizerek sonucu mühendislik). Bölgeler = **bağlantılı çizge partisyonları** (düğümleri bağlı kalacak şekilde kümele). Sorunlar: (1) tek bir "en iyi" plan yok — birden çok kriter (bağlantılılık, nüfus dengesi, kompaktlık) dengelenir; (2) makul bir amaç fonksiyonu için bile **en iyi planı üretmek NP-hard**.
> *"generating the best possible districting plan is NP-hard."* — Solomon
Solomon'ın grubu plan **üretmek** yerine **analiz** eder: "önerilen plan, tüm olası partisyonlar uzayına göre nerede?" Ama **tek-düze örnekleme** (her partisyon eşit olasılık) bile **hesaplama olarak zor** (P ≠ NP varsayımıyla; **Hamiltonian cycle**'a indirgenir — Ders 28'deki reduction aracı). Bu sonuç bir **Yüksek Mahkeme** davasında atıflandı. @fig-redistricting bu iki zorluğu (en iyi plan + örnekleme) iki geçerli bağlı partisyon planının yanında gösterir.
::: {.callout-tip title="Builder Notu — MCMC / hukuk + algoritma kesişimi"}
Redistricting analizi, NP-hardness'ın sosyal-bilim ve **hukuk** kesişimindeki en somut örneğidir: "en iyi planı üretemiyoruz, ama önerilen bir planı tüm partisyon uzayına göre **örnekleyerek** konumlandırabiliriz". Tek-düze örnekleme bile zor olduğundan (Hamiltonian indirgemesi), pratikte **MCMC** (Markov Chain Monte Carlo) ile yaklaşık örnekleme kullanılır — Ders 31'in 6.046 köprüsündeki "randomized + sampling" maddesinin gerçek araştırma karşılığı. Bir builder için ders ikiyönlü: (1) örnekleme araçlarına temkinli yaklaş (yanlılık olabilir), (2) algoritmik analiz mahkeme delili olabilir — hesaplamalı sosyal bilim gerçektir.
:::
```{python}
#| label: fig-redistricting
#| fig-cap: "Politik redistricting (Solomon, L21 §7 VİTRİN): bağlı partisyonlar · en iyi plan + örnekleme NP-hard. SOL panel 5×5 ızgara-çizge, iki BAĞLI partisyon örneği yan yana: Plan A (yatay şeritler) ≠ Plan B (girintili sınırlar) — AYNI çizge, FARKLI bağlı kümeleme (her bölge = kenar-komşu çizgede bağlı düğüm kümesi, 5 bölge × 5 düğüm; bölge-içi kenarlar kalın koyu, kesilen sınırlar ince soluk). Not: tek bir 'en iyi' plan YOK — bağlılık + nüfus dengesi + kompaktlık birlikte dengelenir. SAĞ panel iki hesaplama zorluğu: (1) en iyi planı ÜRETMEK NP-hard (makul amaç fonksiyonu için bile — Solomon, kırmızı); (2) tek-düze ÖRNEKLEME bile zor (her partisyonu eşit olasılıkla çekmek P ≠ NP varsayımıyla zor — Hamiltonian cycle'a indirgenir, kırmızı). Analiz notu: Solomon grubu plan ÜRETMEZ — ANALİZ eder ('önerilen plan tüm olası partisyonlar uzayına göre nerede?'). Rozet (amber): sonuç bir Yüksek Mahkeme davasında atıflandı. Alt not: Ders 28 köprüsü — 'indirgeme' (Hamiltonian → partisyon örnekleme) = NP-hardness aracı. KAVRAMSAL VİTRİN (sayı yok; NP-hard/örnekleme/Yüksek Mahkeme iddiaları kaynak-alıntılı)."
#| fig-width: 11.5
#| fig-height: 5.5
# fig-redistricting (L21 §7 VİTRİN): KAVRAMSAL — sayı yok (NP-hard iddiaları kaynak-alıntılı).
COL_RD_HARD = "#f3c9c2"
COL_RD_HARD_EC = "#b23a2e"
COL_RD_DISTRICTS = ["#dfe4ea", "#fcd9a8", "#cdd9cf", "#e6cfd6", "#cfd8e6"]
COL_RD_DISTRICTS_EC = ["#8a93a3", "#c98a3a", "#6f8f78", "#a87f8d", "#7f8da8"]
def _rd_partition_a():
part = {}
for r in range(5):
for c in range(5):
part[(r, c)] = r
return part
def _rd_partition_b():
regions = {
0: [(0, 0), (0, 1), (0, 2), (1, 0), (2, 0)],
1: [(0, 3), (0, 4), (1, 4), (1, 3), (1, 2)],
2: [(1, 1), (2, 1), (2, 2), (3, 1), (3, 0)],
3: [(2, 3), (2, 4), (3, 4), (3, 3), (3, 2)],
4: [(4, 0), (4, 1), (4, 2), (4, 3), (4, 4)],
}
part = {}
for rid, cells in regions.items():
for cell in cells:
part[cell] = rid
return part
def _rd_grid_connected(part):
by_region = {}
for cell, rid in part.items():
by_region.setdefault(rid, []).append(cell)
for rid, cells in by_region.items():
cellset = set(cells)
start = cells[0]
seen = {start}
stack = [start]
while stack:
(r, c) = stack.pop()
for (dr, dc) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nb = (r + dr, c + dc)
if nb in cellset and nb not in seen:
seen.add(nb)
stack.append(nb)
if len(seen) != len(cellset):
return False
return True
def _rd_draw_grid_partition(ax, part, x0, y0, cell=0.62, title=""):
def px(c):
return x0 + c * cell
def py(r):
return y0 + (4 - r) * cell
for r in range(5):
for c in range(5):
for (dr, dc) in ((0, 1), (1, 0)):
nr, nc = r + dr, c + dc
if nr < 5 and nc < 5:
same = (part[(r, c)] == part[(nr, nc)])
ax.plot([px(c), px(nc)], [py(r), py(nr)],
color=COL_PRIMARY if same else COL_SLATE_400,
linewidth=2.4 if same else 0.8,
alpha=0.95 if same else 0.55,
zorder=2 if same else 1)
for r in range(5):
for c in range(5):
rid = part[(r, c)]
ax.scatter([px(c)], [py(r)], s=58,
facecolor=COL_RD_DISTRICTS[rid % len(COL_RD_DISTRICTS)],
edgecolor=COL_RD_DISTRICTS_EC[rid % len(COL_RD_DISTRICTS_EC)],
linewidths=1.5, zorder=4)
if title:
ax.text(x0 + 2 * cell, y0 + 5 * cell + 0.18, title,
ha="center", va="center", fontsize=8.8,
color=COL_PRIMARY, weight="bold", zorder=5)
def _rd_fill_left_panel(ax):
part_a = _rd_partition_a()
part_b = _rd_partition_b()
_rd_draw_grid_partition(ax, part_a, x0=0.20, y0=1.05,
title="Plan A (yatay şeritler)")
_rd_draw_grid_partition(ax, part_b, x0=3.55, y0=1.05,
title="Plan B (girintili sınırlar)")
ax.text(3.30, 1.05 + 2.5 * 0.62, "≠", ha="center", va="center",
fontsize=22, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(3.20, 5.55, "Bölgeler = BAĞLANTILI çizge partisyonları",
ha="center", va="center", fontsize=10.5, color=COL_TEXT,
weight="bold", zorder=6)
ax.text(3.20, 5.18, "aynı 5×5 çizge — iki geçerli (bağlı) plan",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
ax.add_patch(FancyBboxPatch(
(0.20, 0.10), 5.95, 0.78,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(3.175, 0.62, "tek bir 'en iyi' plan YOK",
ha="center", va="center", fontsize=9.2, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(3.175, 0.30, "bağlılık + nüfus dengesi + kompaktlık birlikte dengelenir",
ha="center", va="center", fontsize=8.0, color=COL_TEXT, zorder=5)
def _rd_hard_box(ax, bx, by, bw, bh, tag, title, body):
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_RD_HARD, ec=COL_RD_HARD_EC, linewidth=2.2, zorder=3))
ax.text(bx + 0.18, by + bh - 0.26, tag, ha="left", va="center",
fontsize=8.0, color=COL_RD_HARD_EC, weight="bold", zorder=5)
ax.text(bx + bw * 0.5, by + bh - 0.28, title, ha="center", va="center",
fontsize=9.6, color=COL_RD_HARD_EC, weight="bold", zorder=5)
ax.text(bx + bw * 0.5, by + bh * 0.40, body, ha="center", va="center",
fontsize=7.8, color=COL_TEXT, linespacing=1.18, zorder=5)
def _rd_fill_right_panel(ax):
bw = 5.95
bx = 0.20
ax.text(bx + bw * 0.5, 5.55, "İki hesaplama zorluğu",
ha="center", va="center", fontsize=10.5, color=COL_TEXT,
weight="bold", zorder=6)
_rd_hard_box(ax, bx, 4.15, bw, 1.10, tag="1",
title="en iyi planı ÜRETMEK NP-hard",
body="makul bir amaç fonksiyonu (bağlılık + nüfus +\n"
"kompaktlık) için bile en iyi partisyon — Solomon")
_rd_hard_box(ax, bx, 2.78, bw, 1.20, tag="2",
title="tek-düze ÖRNEKLEME bile zor",
body="her partisyonu eşit olasılıkla çekmek P ≠ NP\n"
"varsayımıyla zor — Hamiltonian cycle'a indirgenir")
ax.add_patch(FancyBboxPatch(
(bx, 1.52), bw, 1.04, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.7, zorder=3))
ax.text(bx + bw * 0.5, 2.30, "Solomon grubu plan ÜRETMEZ — ANALİZ eder",
ha="center", va="center", fontsize=9.4, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.text(bx + bw * 0.5, 1.84,
"“önerilen plan, tüm olası partisyonlar\nuzayına göre nerede?”",
ha="center", va="center", fontsize=7.8, color=COL_TEXT,
style="italic", linespacing=1.16, zorder=5)
ax.add_patch(FancyBboxPatch(
(bx + bw * 0.06, 0.78), bw * 0.88, 0.54,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=4))
ax.text(bx + bw * 0.5, 1.05, "sonuç bir Yüksek Mahkeme davasında atıflandı",
ha="center", va="center", fontsize=9.4, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(bx + bw * 0.5, 0.30,
"Ders 28 köprüsü: 'indirgeme' (Hamiltonian → partisyon örnekleme) "
"= NP-hardness aracı",
ha="center", va="center", fontsize=7.2, color=COL_SLATE_500,
style="italic", zorder=5)
# Figürde gösterilen İKİ partisyon da gerçekten BAĞLI mı? (Solomon: bağlı partisyon)
assert _rd_grid_connected(_rd_partition_a()), "Plan A bölgeleri bağlı değil"
assert _rd_grid_connected(_rd_partition_b()), "Plan B bölgeleri bağlı değil"
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 5.5))
fig.patch.set_facecolor(COL_WHITE)
_rd_fill_left_panel(axL)
_rd_fill_right_panel(axR)
for ax in (axL, axR):
ax.set_xlim(0.0, 6.35)
ax.set_ylim(0.0, 5.85)
ax.set_aspect("equal")
ax.axis("off")
fig.suptitle(
"Politik redistricting (Solomon, L21): bağlı partisyonlar · en iyi plan + "
"örnekleme NP-hard",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d32}
1. **Üç hoca, tek tema:** 6.006 araçları gerçek araştırmada her yerde.
2. **Demaine — origami:** design (çözülebilir) vs foldability (**NP-hard**); Origamizer; fold-and-cut; maze folding.
3. **Demaine — self-assembly:** DNA tile, **geometrik** hesaplama modeli (log n paralel).
4. **Demaine — 6.851/planar/6.892:** van Emde Boas (log w) < AVL (log n); planar SSSP lineer; Baker PTAS; oyun NP-hardness.
5. **Solomon — mesh:** Dijkstra kenarlarda **yanlış** (çizge üçgenle konuşmaz); MMP geodezik (n log n).
6. **Solomon — graphics:** ray casting $O(p \cdot n)$ → uzay-bölme ağacı ≈ $O(p \log n)$; scene graph **DAG**; SIMD/GPU.
7. **Solomon — redistricting:** gerrymandering; en iyi plan + tek-düze örnekleme **NP-hard** (Hamiltonian indirgemesi).
::: {.callout-important title="Tek Bir Cümle"}
6.006'nın araçları — NP-hardness, DP, çizge, veri yapısı, approximation, hesaplama modeli — origami katlamadan DNA self-assembly'ye, mesh geodeziğinden ray casting ve politik gerrymandering'e kadar her gerçek problemde karşına çıkar: algoritmalar her yerde, 6.006 kaçınılmaz.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d32}
::: {.callout-note collapse="true" title="Soru 1: Origami'de «tasarım» ve «katlanabilirlik» problemleri nasıl farklı, ve hangisi NP-hard?"}
**Cevap:**
**Tasarım (design):** hedef şekilden başlayıp onu üreten kıvrım desenini (crease pattern) bulmak — şekil → desen. Genelde **çözülebilir** (algoritmalar var; örn. Origamizer 3B modeli kareden katlar, %22 alan). **Katlanabilirlik (foldability):** verilen bir kıvrım deseninin düz katlanıp katlanamayacağını belirlemek — desen → "katlanır mı?". Demaine ve Ku bu genel problemin **NP-hard** olduğunu kanıtladı. Bu yüzden araştırma daha çok (daha kolay olan) tasarım tarafına odaklanır. @fig-origami iki yönü ("kurmak ≠ çözmek") yan yana gösterir.
:::
::: {.callout-note collapse="true" title="Soru 2: Üçgen mesh'te iki köşe arası en kısa yol için kenarlarda Dijkstra koşturmak neden yanlıştır?"}
**Cevap:**
Çizge (düğüm+kenar) **üçgenlerin içinden geçen** yolları bilmez — Dijkstra yalnız kenarlar boyunca gidebilir. Sol-üstten sağ-alta giden gerçek geodezik bir üçgenin **yüzeyini çaprazlama** kestiğinde daha kısa olur; oysa kenar-Dijkstra düğümden düğüme zikzak çizmek zorundadır ve daha uzun bir yol bulur. @fig-mesh-dijkstra motor tanığıyla gösterir: birim karede kenar-Dijkstra $2.0$, gerçek geodezik $\sqrt{2} \approx 1.4142$ — %41 fark. Solomon'ın deyişiyle "graphs don't know how to talk to triangles". Doğru çözüm **MMP** algoritmasıdır (geodezik, $O(n \log n)$); Dijkstra'nın mesafe **seviye kümeleri** fikrini üçgen alana (pencereleme ile) genişletir. Pratikte **fast marching** (yaklaşık ama hızlı) sık kullanılır.
:::
::: {.callout-note collapse="true" title="Soru 3: Stanford Bunny'yi render ederken naif ray casting neden yavaş, ve uzay-bölme ağaçları nasıl yardımcı olur?"}
**Cevap:**
Naif ray casting her piksel için **tüm** nesneleri (üçgenleri) tarar → $O(p \cdot n)$. Stanford Bunny 69.000 üçgen × ~2 milyon piksel (1080p) = iki büyük sayının **çarpımı**, çok yavaş; her graphics özelliği (yansıma, saydamlık) bunu artırır. **Çözüm:** tavşanı bir sınırlayıcı kutuya koy — ışın kutuya değmezse hiçbir üçgeni kontrol etme ($O(1)$ eleme). Kutuyu özyinelemeli ikiye böl → **uzay-bölme ağacı** (KD tree); ışın ağaçta gezerek çoğu üçgeni atlar, ideal $O(p \log n)$. @fig-raycast bunu motor-tanıklı 1B sahnede gösterir (naif 750 → indexed 409 karşılaştırma, hit'ler birebir aynı). Dikkat: bu bir **sezgisel** — gerçek $\log n$ garantisi değil, veri dağılımına bağlı ortalama davranış. (Ayrıca özdeş nesneler **scene graph** = DAG ile bir kez saklanır.)
:::
::: {.callout-note collapse="true" title="Soru 4: Politik redistricting'te «en iyi plan» ve «tek-düze örnekleme» neden hesaplama açısından zor?"}
**Cevap:**
İki katman: (1) **En iyi plan NP-hard:** seçim bölgeleri bağlantılı çizge partisyonlarıdır; makul herhangi bir amaç fonksiyonu (bağlantılılık + nüfus dengesi + kompaktlık) için en iyi partisyonu bulmak NP-hard'dır — üstelik kanun zaten "en iyi"yi şart koşmaz. (2) **Tek-düze örnekleme zor:** bir planı, tüm olası partisyonlar uzayından **rastgele eşit-olasılıkla** çekilen bir planla kıyaslamak için, her partisyonu $1/N$ olasılıkla ($N$ = toplam partisyon sayısı) üreten bir araç gerekir; bu **P ≠ NP varsayımıyla zordur** (Hamiltonian cycle'a indirgenir — Ders 28 reduction aracı). Yani gerrymandering analizinde kullanılan örnekleme araçlarına temkinli yaklaşmak gerekir — sonuç bir Yüksek Mahkeme davasında bile atıflandı.
:::
## Egzersizler {#sec-egzersizler-d32}
**Egzersiz 1.** Bu derste geçen her araştırma örneğini bir 6.006 kavramıyla eşle (foldability→NP-hard, mesh path→Dijkstra/geodezik, ray casting→ağaç/log n, scene graph→DAG, redistricting→Hamiltonian reduction).
**Egzersiz 2.** van Emde Boas ($\log w$) ile fusion tree ($\log n / \log w$) sınırlarının min'ini al; $w = \log n$ ve $w = n$ için hangisi kazanır?
**Egzersiz 3.** Baker yaklaşımında her 4. BFS katmanını silmek neden $1 + 1/4$ (yani %25 içinde) bir çözüm verir? $k$ arttıkça runtime'a etkisi?
**Egzersiz 4.** Ray casting'i scene graph (DAG) ile birleştir: 100 özdeş sandalyeli bir sahnede bellek ve render maliyeti nasıl değişir?
**Egzersiz 5.** Self-assembly'nin "geometrik hesaplama modeli"ni word-RAM ile karşılaştır: hangi işlemler paralel, hangi maliyet farklı?
## 6.006 Tamamlandı — Kurs Kapanışı {#sec-6006-tamamlandi-kurs-kapanisi}
Bu, 6.006'nın **son dersiydi**. 32 video boyunca: hesaplama modeli → veri yapıları → sıralama → hashing → ağaçlar/yığınlar → çizgeler/BFS/DFS → en kısa yollar (BFS/DAG/Dijkstra/Bellman-Ford/Johnson) → dinamik programlama (SRTBOT) → hesaplama karmaşıklığı (P/NP) → sentez → araştırma vitrini. @fig-course-map bu 32-ders yolculuğunu tek bir nehir-harita olarak — dört Quiz bloğu, üç hoca, yedi kilometre taşı — gösterir; kitabın kapanış görseli.
> *"I hope you enjoyed this class... algorithms are everywhere."* — Demaine (kapanış)
**Sonraki adım (Builder/OMSCS):** 6.046 (CS 6515 Graduate Algorithms) ve uzmanlık dersleri (6.849 folding, 6.851 ileri veri yapısı, 6.837/6.838 graphics/geometry, 6.892 recreational).
```{python}
#| label: fig-course-map
#| fig-cap: "6.006 — 32 dersin tam haritası (İMZA KURS KAPANIŞI): dört Quiz bloğu, üç hoca, tek nehir. 32 ders-düğümü soldan sağa DÖRT blok-bandında dizilir: Quiz 1 (D1-12 + D14: modeller · veri yapıları · sıralama · hashing · ağaçlar, slate-soluk); Quiz 2 (D13-22: çizgeler BFS/DFS/SSSP/Johnson, slate); Quiz 3 (D23-30: dinamik programlama, amber-soluk); Final (D31-32: sentez + vitrin, amber). ÜÇ HOCA şeritleri (altta): Solomon / Ku / Demaine hangi dersleri taşır; D32 ÜÇÜ BİRDEN (amber yıldız: Ku · Demaine · Solomon). Yedi kilometre taşı rozeti: D1 GİRİŞ · D14 QUIZ 1 · D22 QUIZ 2 · D27 DP FİNALİ · D28 P–NP · D30 QUIZ 3 · D32 FINAL. Üst köprülü oklar (çizge & DP omurga akışı): D16 relax→BF, D18 BF→Dijkstra, D19 Dijkstra→Johnson, D23 SRTBOT→pseudo, D27 pseudo→NP. Kapanış rozeti: 'algorithms are everywhere — 6.006 is unavoidable (Demaine + Solomon, L21)'. KAVRAMSAL KURS-YAPISI figürü (ders numaraları + blok yapısı; sayısal motor iddiası yok)."
#| fig-width: 13.0
#| fig-height: 6.5
# fig-course-map (İMZA KURS KAPANIŞI): KAVRAMSAL — ders no + kurs yapısı (sayısal motor yok).
_CM_BLOCKS = [
{"key": "q1", "label": "Quiz 1 — Modeller · Veri Yapıları · Sıralama · Hashing · Ağaçlar",
"fc": "#e6e9ee", "ec": COL_SLATE_400, "node_fc": "#eef1f5"},
{"key": "q2", "label": "Quiz 2 — Çizgeler: BFS · DFS · SSSP · Johnson",
"fc": "#d6dbe3", "ec": COL_SLATE_500, "node_fc": COL_BG},
{"key": "q3", "label": "Quiz 3 — Dinamik Programlama",
"fc": COL_AMBER_100, "ec": COL_AMBER_300, "node_fc": "#fdf3da"},
{"key": "fin", "label": "Final — Sentez + Vitrin",
"fc": COL_AMBER_300, "ec": COL_AMBER_600, "node_fc": COL_AMBER_100},
]
_CM_LESSON_BLOCK = {}
for _d in range(1, 13):
_CM_LESSON_BLOCK[_d] = "q1"
_CM_LESSON_BLOCK[14] = "q1"
_CM_LESSON_BLOCK[13] = "q2"
for _d in (15, 16, 17, 18, 19, 20, 21, 22):
_CM_LESSON_BLOCK[_d] = "q2"
for _d in range(23, 31):
_CM_LESSON_BLOCK[_d] = "q3"
_CM_LESSON_BLOCK[31] = "fin"
_CM_LESSON_BLOCK[32] = "fin"
_CM_MILESTONES = {
1: "GİRİŞ", 14: "QUIZ 1", 22: "QUIZ 2", 27: "DP FİNALİ",
28: "P–NP", 30: "QUIZ 3", 32: "FINAL",
}
_CM_BRIDGES = [
(16, 18, "relax → BF"),
(18, 19, "BF → Dijkstra"),
(19, 21, "Dijkstra → Johnson"),
(23, 27, "SRTBOT → pseudo"),
(27, 28, "pseudo → NP"),
]
# Hoca şeritleri: her ders sayfasının kaynak-teyitli HOCA satırından
# (Lx/PSx/QRx-notion.md; D32 üç hoca — yıldızla ayrıca işaretli).
_CM_PROF_LANES = [
{"name": "Solomon", "color": COL_SLATE_500,
"ranges": [(4, 4), (6, 6), (13, 13), (15, 15), (17, 17), (20, 20),
(25, 25), (29, 29)], "y": -1.05},
{"name": "Ku", "color": COL_AMBER_700,
"ranges": [(1, 1), (3, 3), (5, 5), (7, 7), (11, 11), (14, 14),
(16, 16), (18, 19), (21, 22), (30, 31)], "y": -1.75},
{"name": "Demaine", "color": COL_PRIMARY,
"ranges": [(2, 2), (8, 10), (12, 12), (23, 24), (26, 28)], "y": -2.45},
]
_CM_N = 32
_CM_X0 = 0.55
_CM_DX = 0.40
_CM_NODE_Y = 0.0
_CM_NODE_R = 0.155
_CM_BADGE_Y = _CM_NODE_Y + 0.92
_CM_BADGE_Y2 = _CM_NODE_Y + 1.42
_CM_BRIDGE_Y = _CM_NODE_Y + 2.30
def _cm_node_x(d):
return _CM_X0 + (d - 1) * _CM_DX
def _cm_block_of(d):
key = _CM_LESSON_BLOCK[d]
for b in _CM_BLOCKS:
if b["key"] == key:
return b
raise KeyError(key)
def _cm_draw_block_bands(ax):
band_y0 = _CM_NODE_Y - 0.42
band_h = 0.84
for b in _CM_BLOCKS:
ds = [d for d in range(1, _CM_N + 1) if _CM_LESSON_BLOCK[d] == b["key"]]
xlo = _cm_node_x(min(ds)) - _CM_DX * 0.55
xhi = _cm_node_x(max(ds)) + _CM_DX * 0.55
ax.add_patch(FancyBboxPatch(
(xlo, band_y0), xhi - xlo, band_h,
boxstyle="round,pad=0.01,rounding_size=0.04",
fc=b["fc"], ec=b["ec"], linewidth=1.6, zorder=1, alpha=0.85))
ly = band_y0 + band_h + 0.16
if b["key"] == "fin":
ax.text(xhi, ly, b["label"], ha="right", va="bottom",
fontsize=6.8, color=COL_AMBER_700, weight="bold", zorder=3)
elif b["key"] == "q3":
ax.text(xlo + 0.10, ly, b["label"], ha="left", va="bottom",
fontsize=6.8, color=COL_TEXT, weight="bold", zorder=3)
else:
ax.text((xlo + xhi) * 0.5, ly, b["label"],
ha="center", va="bottom", fontsize=6.8,
color=COL_TEXT, weight="bold", zorder=3)
def _cm_draw_bridges(ax):
arc_y = _CM_BRIDGE_Y
label_top = arc_y + 0.62
nudge = {0: -0.30, 1: +0.32, 3: -0.34, 4: +0.30}
voff_hi = {1, 4}
for bi, (d0, d1, lab) in enumerate(_CM_BRIDGES):
x0 = _cm_node_x(d0)
x1 = _cm_node_x(d1)
rad = -0.38
ax.add_patch(FancyArrowPatch(
(x0, arc_y), (x1, arc_y),
arrowstyle="-|>", mutation_scale=11,
color=COL_AMBER_600, linewidth=1.7, zorder=4,
connectionstyle=f"arc3,rad={rad}"))
midx = (x0 + x1) * 0.5 + nudge.get(bi, 0.0)
ly = label_top + (0.26 if bi in voff_hi else 0.0)
ax.text(midx, ly, lab, ha="center", va="bottom", fontsize=6.8,
color=COL_AMBER_700, weight="bold", style="italic", zorder=5)
arc_top = arc_y + abs(rad) * (x1 - x0) * 0.5
ax.plot([midx, (x0 + x1) * 0.5], [ly - 0.02, arc_top + 0.02],
color=COL_AMBER_300, linewidth=0.7, zorder=3, alpha=0.7)
def _cm_draw_milestone(ax, d):
x = _cm_node_x(d)
lab = _CM_MILESTONES[d]
is_final = (d == 32)
order = sorted(_CM_MILESTONES)
idx = order.index(d)
badge_y = _CM_BADGE_Y if (idx % 2 == 0) else _CM_BADGE_Y2
if is_final:
badge_y = _CM_BADGE_Y
fc = COL_AMBER_100 if not is_final else COL_AMBER_300
ec = COL_ACCENT if not is_final else COL_AMBER_600
w = 0.62 if len(lab) <= 5 else 0.84
ax.add_patch(FancyBboxPatch(
(x - w * 0.5, badge_y - 0.16), w, 0.32,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=fc, ec=ec, linewidth=2.0 if not is_final else 2.8, zorder=6))
ax.text(x, badge_y, lab, ha="center", va="center",
fontsize=7.4 if not is_final else 8.4,
color=COL_AMBER_700, weight="bold", zorder=7)
ax.add_patch(FancyArrowPatch(
(x, badge_y - 0.16), (x, _CM_NODE_Y + _CM_NODE_R + 0.02),
arrowstyle="-", color=ec, linewidth=1.3, zorder=4,
linestyle="--", alpha=0.8))
def _cm_draw_lesson_nodes(ax):
for d in range(1, _CM_N + 1):
x = _cm_node_x(d)
b = _cm_block_of(d)
milestone = d in _CM_MILESTONES
if milestone:
fc, ec, lw, tc = COL_ACCENT, COL_AMBER_700, 2.4, COL_WHITE
r = _CM_NODE_R * 1.18
else:
fc, ec, lw, tc = b["node_fc"], b["ec"], 1.6, COL_TEXT
r = _CM_NODE_R
ax.add_patch(Circle((x, _CM_NODE_Y), r, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, _CM_NODE_Y, str(d), ha="center", va="center",
fontsize=6.6 if not milestone else 7.2,
color=tc, weight="bold", zorder=6)
def _cm_draw_prof_lanes(ax):
lane_x0 = _cm_node_x(1) - _CM_DX * 0.55
lane_x1 = _cm_node_x(_CM_N) + _CM_DX * 0.55
for lane in _CM_PROF_LANES:
y = lane["y"]
ax.plot([lane_x0, lane_x1], [y, y], color=COL_SLATE_400,
linewidth=0.8, zorder=2, alpha=0.5)
ax.text(lane_x0 - 0.10, y, lane["name"], ha="right", va="center",
fontsize=8.5, color=lane["color"], weight="bold", zorder=4)
for (a, b) in lane["ranges"]:
xa = _cm_node_x(a) - _CM_NODE_R
xb = _cm_node_x(b) + _CM_NODE_R
ax.add_patch(FancyBboxPatch(
(xa, y - 0.12), xb - xa, 0.24,
boxstyle="round,pad=0.005,rounding_size=0.03",
fc=lane["color"], ec=lane["color"], linewidth=1.0,
zorder=3, alpha=0.55))
midd = (a + b) // 2
ax.add_patch(FancyArrowPatch(
(_cm_node_x(midd), _CM_NODE_Y - _CM_NODE_R), (_cm_node_x(midd), y + 0.12),
arrowstyle="-", color=lane["color"], linewidth=0.7,
zorder=2, alpha=0.30, linestyle=":"))
sx = _cm_node_x(32)
star_y = _CM_PROF_LANES[-1]["y"] - 0.55
ax.plot([sx], [star_y], marker="*", markersize=20,
color=COL_ACCENT, markeredgecolor=COL_AMBER_700,
markeredgewidth=1.2, zorder=6)
ax.text(sx, star_y - 0.30, "D32: üçü birden\n(Ku · Demaine · Solomon)",
ha="center", va="top", fontsize=7.2, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(sx, _CM_NODE_Y - _CM_NODE_R), (sx, star_y + 0.16),
arrowstyle="-|>", mutation_scale=10, color=COL_AMBER_600,
linewidth=1.4, zorder=4, alpha=0.7))
# KURS YAPISI assert'leri (kavramsal veri — sayısal motor yok, vitrin kuralı)
assert sorted(_CM_LESSON_BLOCK.keys()) == list(range(1, _CM_N + 1))
assert set(_CM_LESSON_BLOCK.values()) == {"q1", "q2", "q3", "fin"}
assert _CM_LESSON_BLOCK[14] == "q1" and _CM_LESSON_BLOCK[13] == "q2"
assert _CM_LESSON_BLOCK[31] == "fin" and _CM_LESSON_BLOCK[32] == "fin"
assert _CM_MILESTONES[1] == "GİRİŞ" and _CM_MILESTONES[32] == "FINAL"
for _d0, _d1, _l in _CM_BRIDGES:
assert 1 <= _d0 < _d1 <= _CM_N
fig, ax = plt.subplots(figsize=(13.0, 6.5))
fig.patch.set_facecolor(COL_WHITE)
_cm_draw_block_bands(ax)
_cm_draw_prof_lanes(ax)
_cm_draw_lesson_nodes(ax)
for _d in _CM_MILESTONES:
_cm_draw_milestone(ax, _d)
_cm_draw_bridges(ax)
ax.text(_cm_node_x(1) - 0.30, _CM_BRIDGE_Y + 0.30,
"üst oklar: çizge & DP omurga akışı",
ha="left", va="center", fontsize=7.4, color=COL_AMBER_700,
style="italic", zorder=6)
_cm_close_y = _CM_PROF_LANES[-1]["y"] - 1.35
_cm_cx = (_cm_node_x(1) + _cm_node_x(_CM_N)) * 0.5
ax.add_patch(FancyBboxPatch(
(_cm_cx - 5.6, _cm_close_y - 0.30), 11.2, 0.60,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=6))
ax.text(_cm_cx, _cm_close_y,
"algorithms are everywhere — 6.006 is unavoidable (Demaine + Solomon, L21)",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=7)
fig.suptitle(
"6.006 — 32 dersin tam haritası: dört Quiz bloğu, üç hoca, tek nehir",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
ax.set_xlim(_cm_node_x(1) - 1.65, _cm_node_x(_CM_N) + 0.85)
ax.set_ylim(_cm_close_y - 0.55, _CM_BRIDGE_Y + 1.25)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-warning title="Kurs Kapanışı + Buradan Nereye (Ders 32 — SON DERS)"}
**Ders 32 (L21) kursun SON dersiydi** — sonraki ders yok. Üç geometrici hoca (Ku · Demaine · Solomon) 6.006 araçlarının gerçek araştırmadaki vitrinini kapattı. Ders 31'in (L20) omurga görüşü (veri yapısı → çizge → DP) ve 6.046 köprüsü, burada nihai bağlamına oturdu: algoritmalar her yerde.
**Buradan nereye:**
- **6.046** (Design and Analysis of Algorithms) = **OMSCS CS 6515** (Graduate Algorithms) — doğal devam dersi; Ders 31'deki 6.046 köprüsü (union-find, MST, max-flow, randomized, approximation, model değişimi) bunun haritasıdır.
- **Uzmanlık dersleri:** 6.849 (computational origami / folding), 6.851 (ileri veri yapısı: van Emde Boas, fusion tree), 6.837 (computer graphics: ray casting, scene graph), 6.838 (geometri işleme: mesh, geodezik), 6.892 (recreational: oyun NP-hardness).
- **Geriye köprüler:** Dijkstra (Ders 19) mesh geodeziğinde, NP-hard/reduction (Ders 28) foldability ve redistricting'te, AVL (Ders 10) van Emde Boas karşılaştırmasında, BFS katmanları (Ders 13) Baker PTAS'ında karşına çıktı.
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d32}
| Hoca / Alan | Örnek | 6.006 bağlantısı |
|-------------|-------|------------------|
| **Demaine — Origami (6.849)** | design vs foldability; fold-and-cut | NP-hardness, reduction (Ders 28) |
| **Demaine — Self-assembly** | DNA tile, ikili sayaç | Geometrik hesaplama modeli, paralel |
| **Demaine — İleri DS (6.851)** | van Emde Boas log w, fusion tree | AVL (log n) sınırını aşma (Ders 10) |
| **Demaine — Planar / Recreational** | Baker PTAS; oyun NP-hard | BFS (Ders 13), approximation, hardness |
| **Solomon — Mesh (6.838)** | MMP geodezik (Dijkstra yetmez) | Dijkstra seviye kümeleri (Ders 19) |
| **Solomon — Graphics (6.837)** | ray casting; scene graph | $O(p \cdot n) \to$ ağaç $\log n$; DAG |
| **Solomon — Redistricting** | uniform sampling zor | Hamiltonian reduction, P≠NP (Ders 28) |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d32}
::: {.callout-tip title="7 köprü"}
Bu vitrin dersi, 6.006'nın altı aracının gerçek araştırma ve sistem mühendisliğine nasıl bağlandığını gösterir; köprülerin özeti:
1. **NP-hardness pratiği** → foldability, redistricting, oyun zorluğu: "bu problem verimli çözülemez" refleksi (OMSCS CS 6515).
2. **İleri veri yapısı (6.851)** → van Emde Boas/fusion tree; gerçek sistemlerde $\log n$'i kırma.
3. **Planar/approximation (PTAS)** → routing, harita, ağ optimizasyonu: "yapı varsa daha hızlı".
4. **Mesh geodezik (MMP/fast marching)** → robotik yol planlama, 3B tarama, oyun navigasyonu.
5. **Uzay-bölme ağaçları + scene graph (DAG)** → render, çarpışma tespiti, GPU; gerçek performans mühendisliği.
6. **Geometrik/self-assembly model** → DNA computing, moleküler nano-üretim farkındalığı.
7. **Redistricting/sampling** → MCMC, hesaplamalı sosyal bilim, hukuk+algoritma kesişimi.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
6.006'nın altı aracı — **NP-hardness, DP, çizge, veri yapısı, approximation, hesaplama modeli** — sınıfta kalmıyor; origami katlamada (design çözülebilir, foldability NP-hard), DNA self-assembly'de (geometrik hesaplama modeli), mesh üzerinde en kısa yolda (Dijkstra yetmez → MMP geodezik), ray casting'de ($O(p \cdot n) \to$ uzay-bölme ağacı + scene graph DAG) ve politik gerrymandering'de (en iyi plan + örnekleme NP-hard) gerçek araştırma problemlerine dönüşüyor. Üç geometrici hocanın ortak mesajı tek: **algoritmalar her yerde, 6.006 kaçınılmaz.** Buradan 6.046 (CS 6515) ve uzmanlık derslerine.
:::
