7 Problem Oturumu 2

Ders 4-5’in uygulaması: master theorem + özyineleme ağacı, sonsuz dizide üstel sıçrama, augmentation ile veri yapısı tasarımı ve two-finger ile O(n)

Oturum bilgisi

Solomon’un videosu: YouTube — Problem Session 2 (≈60 dk)
OCW sayfası: MIT 6.006 Problem Session 2
Seri: MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 6 (Problem Oturumu 2)
Hoca: Justin Solomon
Okuma süresi: ≈26 dk

7.1 Bu Problem Oturumu Ne Hakkında?

İkinci problem oturumu, son haftanın konularını uygular: yineleme çözme (master theorem + özyineleme ağacı), arama ve veri yapısı tasarımı. Justin Solomon dört problemi birer “İfade → Yaklaşım → Çözüm → Karmaşıklık” akışıyla işler. Her problemin kazandırdığı taşınabilir araç Şekil 7.1 içinde özetlenir.

Bir genel beceri tüm oturuma damga vurur: problemler çoğu zaman “saçma” bir hikâyeyle (sonsuz taşlar, tuğla üfleyen kurt) sarmalanır; işin ilk adımı işe yarayan iki cümleyi çıkarmaktır. Solomon bunun bir danışmanlık becerisi olduğunu söyler.

“extracting the two words that matter.” — Justin, 1:09:29

İkinci bir uyarı asimptotik gösterim üzerinedir: O, Θ, Ω harflerini özensiz kullanmak en sık yapılan hatadır.

“every single time you write one of those letters down, you should step back 50 feet and look at it and think… did I do that right?” — Justin, 11:54

flowchart TD
    R["Problem Oturumu 2<br/>(Ders 4-5 uygulaması)"] --> P1["Problem 1<br/>Yineleme Çözme"]
    R --> P2["Problem 2<br/>Sonsuz Diziyi Arama"]
    R --> P3["Problem 3<br/>Katmanlı Görüntü Editörü"]
    R --> P4["Problem 4<br/>Tuğla Üfleme"]
    P1 --> T1["Master theorem + ağaç<br/>n^(log_b a) anahtar · 3 durum"]
    P2 --> T2["Üstel sıçrama (galloping)<br/>sınır bul → O(log k)"]
    P3 --> T3["Augmentation<br/>set + sequence birleştir"]
    P4 --> T4["Two-finger<br/>n² → n monoton parmak"]

    classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
    classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
    classDef tool fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
    class R root
    class P1,P2,P3,P4 prob
    class T1,T2,T3,T4 tool

Şekil 7.1: Problem Oturumu 2’nin kavram haritası: dört problem (üst sıra) ve her birinin öğrettiği taşınabilir araç (alt sıra). Problem 1 master theorem + özyineleme ağacı (n^(log_b a) anahtar nicelik), Problem 2 üstel sıçrama (galloping) ile O(log k) arama, Problem 3 augmentation (set + sequence birleştirme), Problem 4 two-finger ile n² → n indirgemesi kazandırır. Hepsi Ders 4-5 temeline dayanır.

7.2 Problem 1: Yineleme Çözme — Master Theorem ve Özyineleme Ağacı

İfade. $T(n) = a \cdot T(n/b) + f(n)$ biçimindeki yinelemeleri çöz. Her birini iki yolla yap: (1) master theorem (kural seti), (2) özyineleme ağacı çizip seviye seviye işi toplayarak.

Yaklaşım — Anahtar Niceliği Hesapla, f ile Kıyasla

Master theorem üç duruma ayrılır; anahtar nicelik $n^{\log_b a}$’dır ($a$ = dallanma sayısı, $b$ = problemin küçülme oranı, $f$ = düğüm başına iş). Bu niceliğin üssünü ($\log_b a$) hesapla, $f$’in üssüyle kıyasla, duruma karar ver. Özyineleme ağacı aynı sonucu daha yavaş ama aydınlatıcı biçimde verir; master theorem ise hızlıdır ama “neden”i göstermez.

“the a is kind of like a branching factor… b is the amount that your problem size reduces… f is the amount of work that you do at each node.” — Justin, 6:14

Çözüm. Üç durum:

Durum 1: $f(n) = O(n^{\log_b a - \epsilon})$, $\epsilon > 0$ → $T(n) = \Theta(n^{\log_b a})$. ($f$ önemsiz; ağaçta dolaşma baskın.)
Durum 2: $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ → $T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$.
Durum 3: $f(n) = \Omega(n^{\log_b a + \epsilon})$ ve düzenlilik ($a \cdot f(n/b) \le c \cdot f(n)$, $c < 1$) → $T(n) = \Theta(f(n))$. ($f$ baskın.)

Örnek (a): $T(n) = 2T(n/2) + O(\sqrt{n})$. $a = b = 2$, $n^{\log_2 2} = n$. $f = O(\sqrt{n}) = O(n^{1 - 1/2})$, yani $\epsilon = 1/2 > 0$ → Durum 1 → $T(n) = \Theta(n)$.

Örnek (b): $T(n) = 8T(n/4) + O(n^{3/2})$. $\log_4 8 = 3/2$, yani $n^{3/2}$. $f = O(n^{3/2})$, iki taraf eşit → Durum 2, $k = 0$ → $T(n) = O(n^{3/2}\log n)$. ($f$ big-O olduğundan sonuç da big-O, big-$\Theta$ değil.)

Özyineleme ağacı (ikinci yöntem): Ağaçta $l$. seviyede $2^l$ (veya $8^l$) düğüm var, her biri $f(n/2^l)$ iş yapar; seviye sayısı $\log_b n$. Tüm seviyeleri topla — ortaya bir geometrik seri çıkar; sadeleştirince master theorem’le aynı sonuç gelir. Bu iki okumanın görsel karşılaştırması Şekil 7.2’de gösterilir: sol panel ağaç + seviye toplamları, sağ panel 3-durum kararı.

“master theorem… the giant sledgehammer for solving recurrences without understanding why you got the answer.” — Justin, 4:09

Karmaşıklık. Sonuçlar: (a) $\Theta(n)$, (b) $O(n^{3/2}\log n)$.

Şekil 7.2: Master teoremini **özyineleme ağacıyla** okuma: $T(n)=2T(n/2)+O(\sqrt{n})$ ($n=64$). **Sol panel:** kök ($l=0$) tek alt-problem $\sqrt{n}$; her seviyede düğüm sayısı ikiye katlanır ($2^l$) ve her düğümün işi $\sqrt{n/2^l}$’e iner. **Seviye toplamı** $2^l\cdot\sqrt{n/2^l}$ aşağı indikçe $\sqrt{2}$ çarpanıyla *büyür* — $8 \to 11{,}3 \to 16 \to 22{,}6 \to 32 \to 45{,}3 \to 64$ — yani artan bir **geometrik seri**dir ve **yapraklar** ($l=6$, **amber/BASKIN**) baskın terimi verir: $64$ düğüm $\times \sqrt{1}=64=\Theta(n)$. Tüm seviyelerin toplamı $\approx 199{,}2$, ama asimptotik olarak yaprak terimi belirleyicidir → $\Theta(n)$. **Sağ panel:** 3-durum karar kuralı — $f(n)$’in üssü $d=\exp(f)=\tfrac12$ ile kritik üs $c^{*}=\log_b a=\log_2 2=1$ karşılaştırılır. $d<c^{*}$ olduğundan **Durum 1** seçilir (yapraklar baskın, $\Theta(n^{c^{*}})$); Durum 2 ($d=c^{*}$, dengeli) ve Durum 3 ($d>c^{*}$, kök baskın) burada uygulanmaz. Sonuç: $\Theta(n)$.

7.3 Problem 2: Sonsuz Diziyi Arama

İfade. Sonsuz bir gezegen dizisinde, indeksi $k$ olan gezegeni bul. Bir gezegende durup oracle’a sorabilirsin: “aradığım indeks benden büyük mü küçük mü?” Hedef: $O(\log k)$ zaman (dikkat: $k$, verinin boyutu değil, aranan indeks).

Yaklaşım — Önce Sağ Sınırı Bul, Sonra İkili Ara

İçgüdü ikili arama; ama ikili arama bir sağ sınır ister ve sonsuz dizide sağ sınır yok. Önce bir sağ sınır bulmalıyız — sonsuz bir kümenin “ortası” yoktur, bu yüzden indeksi her adımda ikiye katlayarak (üstel sıçrama) hedefi aşan ilk gücü buluruz.

“what is the middle of an infinite set of planets? Infinite, exactly. It’s a problem.” — Justin, 49:26

Çözüm. İki aşama:

Sınır bul (üstel sıçrama): $m = 0, 1, 2, \dots$ için $2^m$ indeksli gezegeni ziyaret et, ta ki $k \le 2^m$ olana dek. Bu, $\log k$ adım sürer ve şu sandviçi verir: $2^{m-1} \le k \le 2^m$.
İkili arama: Artık $[2^{m-1}, 2^m]$ aralığı var (genişliği $\sim k$); bu aralıkta ikili arama, $\log k$ adım.

“I’m going to visit planet 2 to the m for each m starting with m equals 0.” — Justin, 50:25

Şekil 7.3 bu iki aşamayı tek bir sayı-doğrusunda izler: önce galloping yaylarıyla sınır, sonra numaralı mid sorgularıyla ikili arama.

Karmaşıklık. $\log k$ (sınır bulma) + $\log k$ (ikili arama) = $O(\log k)$.

Şekil 7.3: Sonsuz diziyi arama — iki aşamalı O(log k) strateji (hedef indeks $k=50$). **AŞAMA 1 (üstel sıçrama / galloping):** sağ sınır bilinmediği için indeksi her adımda **ikiye katlayarak** $2^0,2^1,\dots,2^m$ sorgulanır (amber yaylar: $1,2,4,8,16,32,64$). İlk $2^6=64 \ge k$ bulununca durulur — toplam **7 sorgu** — ve bu, $2^5=32 \le k \le 2^6=64$ **sandviçini** verir (üstteki köşeli parantez). Hedef $k=50$ amber kesik dikey çizgiyle işaretlidir. **AŞAMA 2 (ikili arama):** artık sonlu $[32,64]$ aralığında klasik ikili arama yapılır; numaralı mid sorguları sırasıyla $48 \to 56 \to 52 \to 50$ (4 sorgu, ✓ = bulundu). Her iki aşama da $O(\log k)$ olduğundan toplam **11 sorgu** $= O(\log k)$ (rozet sağ altta) — $\log_2 50 \approx 5{,}64$. Anahtar sezgi: sınır galloping ile $O(\log k)$’da bulunur, sonra ikili arama yine $O(\log k)$’da bitirir.

7.4 Problem 3: Katmanlı Görüntü Editörü

İfade. Bir görüntü editörü veri yapısı tasarla: katmanları üst-alt sırada tutar. İşlemler: make_doc $O(1)$, import(x) (üste ekle) $O(n)$, display() (sırayla tüm ID’ler) $O(n)$, ve move_below(x, y) ($x$ katmanını $y$’nin altına taşı) $O(\log n)$.

Yaklaşım — İki Yönü Ayır, Sonra Augmentation ile Bağla

Problemde iki yön var: dizi (sequence) yönü (display sırası) ve küme (set) yönü (bir katmanı hızlı bulmak). İkisini ayrı veri yapısıyla çöz, sonra bir augmentation ile bağla — sıralı dizideki her anahtara, bağlı listedeki düğümün işaretçisini iliştir. Böylece “bul” $O(\log n)$, “yeniden bağla” $O(1)$ olur.

Çözüm. İki yapı birlikte çalışır:

Çift bağlı liste (doubly linked list): katmanların ekran sırasını tutar (display için $O(n)$).
Sıralı dizi (set): ID’leri sıralı tutar; ikili aramayla bir ID’yi $O(\log n)$’de bulur.
Augmentation: sıralı dizideki her anahtara, o öğenin bağlı listedeki düğümüne bir işaretçi ekle. (Bir düğümü silmek diğer işaretçileri bozmaz — işaretçiler geçerli kalır.)

“we can attach data to our keys… I am going to attach a pointer into my linked list.” — Justin, 1:02:21

move_below(x, y) üç adım: (1) $x$ ve $y$’yi sıralı dizide ikili aramayla bul, bağlı liste işaretçilerini al — $O(\log n)$; (2) $x$’i bağlı listeden çıkar ve $y$’nin altına ekle — işaretçiler elimizde olduğundan $O(1)$; (3) küme değişmez (sadece sıra değişti). Önemli sağlama: move_below kümeyi değiştirmez, çünkü hangi öğelerin olduğu değil, yalnızca sıraları değişir.

Karmaşıklık. make_doc $O(1)$, import $O(n)$ (sıralı diziye ekleme), display $O(n)$, move_below $O(\log n)$ (bulma) + $O(1)$ (yeniden bağlama).

7.5 Problem 4: Tuğla Üfleme

İfade. Bir sıra evin tuğla sayıları verilir. Kurt bir eve üfleyince o ev ve sağındaki kendisinden az tuğlalı tüm evler yıkılır. Her ev için, ona üflendiğinde kaç ev yıkıldığını hesapla. (Hikâyenin özü: “her öğe için, sağında kendisinden küçük olanları say + 1”.)

Yaklaşım — Naif Çift Döngüden Monoton Parmaklara

Naif çözüm çift döngü → $O(n^2)$; yasak. Bir yapısal varsayım kullanılır: bir ev hariç hepsi özel (sağ komşusu kendisinden büyük-eşit), yani dizi artan-sonra-bir-düşüş-sonra-artan iki sıralı parçaya bölünür. Sol yarı (artan) sağa hiçbir şey yıkamaz; her ev yalnızca sağ yarıda kendinden küçükleri yıkar. Sol yarıdaki ev büyüdükçe yıkılan aralık yalnız genişler — geri gitmez — ve bu, two-finger’a kapı açar.

Çözüm. Sol yarıdaki ev tuğla sayısı arttıkça, sağ yarıda yıkılan evlerin aralığı yalnızca büyür (geri gitmez). Bu, iki parmak (two-finger) tekniğine kapı açar: i parmağı sol yarıda ilerlerken, j parmağı sağ yarıda “ilk yıkılmayan” evi işaret eder; i sağa kaydıkça j de sağa kayar, asla sola dönmez.

“It’s called a two-finger algorithm.” — Justin, 1:25:02

j = right_start                              # sağ yarının ilk evi (global indeks)
for i in range(left_end + 1):
    while j < n and heights[j] < heights[i]:
        j += 1                               # j asla geri gitmez (5→6→7→8)
    smaller = j - right_start                # sağda i'den küçük ev sayısı
    damage[i] = 1 + smaller                  # kendisi + sağda küçük ev sayısı

Her iki parmak da diziyi yalnızca bir kez kateder → $O(n)$. (Genel hâl, özel varsayım olmadan, aynı fikir + merge sort ile çözülür.) Şekil 7.4 bu izi $[2,4,6,9]$ sol yarısı ile $[1,3,5,7]$ sağ yarısı üzerinde adım adım gösterir; j parmağının $5 \to 6 \to 7 \to 8$ ile yalnız sağa kaydığına dikkat.

Karmaşıklık. Two-finger ile $O(n)$ ($n^2$ naif veya $n\log n$ ikili-arama yerine).

Şekil 7.4: İki parmak (two-finger) tuğla üfleme izi — Problem 4 İMZA figürü. Dizi tek düşüşten (9→1) ikiye ayrılır: **sol yarı** [2,4,6,9] artan, **sağ yarı** [1,3,5,7] artan. Sol parmak `i` sol yarıyı soldan sağa sweep eder (amber, eşik = `heights[i]`); sağ parmak `j` sağ yarıda eşikten küçük olmayan **ilk** evi işaretler. `i` sağa kaydıkça eşik büyür, bu yüzden `j` yalnız **sağa** kayar — asla geri gitmez (5→6→7→8). **Adım 1** (eşik 2): sağda yalnız 1 küçük → hasar 2. **Adım 2** (eşik 4): 1,3 küçük → hasar 3. **Adım 3** (eşik 6): 1,3,5 → hasar 4. **Adım 4** (eşik 9): 1,3,5,7 → hasar 5. Yıkılan sağ-yarı evleri her satırda koyu amber. İki parmak diziyi birer kez katettiği için toplam **O(n)** — naif “her ev için sağı tara” O(n²) yerine. Sağ yarının kendi içi de artan olduğundan oradaki her ev yalnız kendini yıkar (hasar 1); nihai `hasar[]` = [2,3,4,5,1,1,1,1].

7.6 Ne Öğrendik?

Altı Taşınabilir Araç

Bu oturum, Ders 4-5’in teorisini dört somut problemde uyguladı ve altı taşınabilir araç kazandırdı:

Master theorem + özyineleme ağacı: Yinelemeyi iki yolla çöz; $n^{\log_b a}$ anahtar niceliktir, ağaç “neden”i gösterir.
Asimptotik titizlik: $O$ / $\Theta$ / $\Omega$’yu özensiz yazma; $f$ big-O ise sonuç da big-O’dur.
Üstel sıçrama (galloping): Sağ sınırı olmayan aramada, $2^m$ ile sınır bul, sonra ikili ara — $O(\log k)$.
Augmentation ile iki yapı birleştirme: set (ID bul) + sequence (sıra tut); anahtara liste işaretçisi ekle.
Two-finger ile $n^2 \to n$: Monoton ilerleyen iki parmak, çift döngüyü lineere indirir.
Problem okuma: Süslü hikâyeden “işe yarayan iki cümleyi” çıkarmak — algoritmik özü görmek.

7.7 Sonraki

Ders 5 (L5) — Doğrusal Zamanlı Sıralama

Sırada Ders 5 (L5): Doğrusal Zamanlı Sıralama var — Jason Ku ile, karşılaştırma modelinin $\Omega(n \log n)$ sınırını aşan sıralamalara (counting sort, radix sort) geçiyoruz. Bu oturumdaki master theorem ve two-finger sezgileri, oradaki doğrusal-zaman analizinde doğrudan işine yarayacak.

--- title: "Problem Oturumu 2" subtitle: "Ders 4-5'in uygulaması: master theorem + özyineleme ağacı, sonsuz dizide üstel sıçrama, augmentation ile veri yapısı tasarımı ve two-finger ile O(n)" --- ::: {.callout-note title="Oturum bilgisi"} - **Solomon'un videosu:** [YouTube — Problem Session 2](https://www.youtube.com/watch?v=KlQiwkhLBg0) (≈60 dk) - **OCW sayfası:** [MIT 6.006 Problem Session 2](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/problem-session-2/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 6 (Problem Oturumu 2) - **Hoca:** Justin Solomon - **Okuma süresi:** ≈26 dk ::: ## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d06} İkinci problem oturumu, son haftanın konularını uygular: **yineleme çözme** (master theorem + özyineleme ağacı), **arama** ve **veri yapısı tasarımı**. Justin Solomon dört problemi birer "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işler. Her problemin kazandırdığı taşınabilir araç @fig-ps2-concept-map içinde özetlenir. Bir genel beceri tüm oturuma damga vurur: problemler çoğu zaman "saçma" bir hikâyeyle (sonsuz taşlar, tuğla üfleyen kurt) sarmalanır; işin ilk adımı **işe yarayan iki cümleyi çıkarmaktır**. Solomon bunun bir danışmanlık becerisi olduğunu söyler. > *"extracting the two words that matter."* — Justin, 1:09:29 İkinci bir uyarı asimptotik gösterim üzerinedir: O, Θ, Ω harflerini özensiz kullanmak en sık yapılan hatadır. > *"every single time you write one of those letters down, you should step back 50 feet and look at it and think... did I do that right?"* — Justin, 11:54 ```{mermaid} %%| label: fig-ps2-concept-map %%| echo: false %%| fig-cap: "Problem Oturumu 2'nin kavram haritası: dört problem (üst sıra) ve her birinin öğrettiği taşınabilir araç (alt sıra). Problem 1 master theorem + özyineleme ağacı (n^(log_b a) anahtar nicelik), Problem 2 üstel sıçrama (galloping) ile O(log k) arama, Problem 3 augmentation (set + sequence birleştirme), Problem 4 two-finger ile n² → n indirgemesi kazandırır. Hepsi Ders 4-5 temeline dayanır." flowchart TD R["Problem Oturumu 2 (Ders 4-5 uygulaması)"] --> P1["Problem 1 Yineleme Çözme"] R --> P2["Problem 2 Sonsuz Diziyi Arama"] R --> P3["Problem 3 Katmanlı Görüntü Editörü"] R --> P4["Problem 4 Tuğla Üfleme"] P1 --> T1["Master theorem + ağaç n^(log_b a) anahtar · 3 durum"] P2 --> T2["Üstel sıçrama (galloping) sınır bul → O(log k)"] P3 --> T3["Augmentation set + sequence birleştir"] P4 --> T4["Two-finger n² → n monoton parmak"] classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937 classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937 classDef tool fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937 class R root class P1,P2,P3,P4 prob class T1,T2,T3,T4 tool ``` ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 6 (PS2) motoru (_engine_PS2.py) + Slate+Amber sabitleri (_viz.py) # Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede # tanımlanan recursion_tree_levels / master_theorem_case / unbounded_search / # two_finger_trace + COL_* globallerini IMPORT ETMEDEN kullanır. Notion'daki öğretim # içeriği (görünür display ```python bloklar) bu motorun tarif seviyesidir; burada # tam, deterministik, test edilmiş sürüm yaşar. # # NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama # backend'ini ezer (plt.show() 0 figür üretir; brief §2/§11). Standalone testte # savefig kullanılır; Quarto render'da jupyter inline backend'i ayarlar. # # Dosyadan import YOK: master theorem + 4 problem fonksiyonu burada self-contained # inline'dır → render dizininden bağımsız. # ============================================================================ import math import bisect from fractions import Fraction import matplotlib.pyplot as plt from matplotlib.patches import FancyBboxPatch, FancyArrowPatch # --------------------------------------------------------------------------- # _viz.py — Slate + Amber stil sabitleri (HEX birebir brief §1/§8) # --------------------------------------------------------------------------- COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve COL_ACCENT = "#f59e0b" # amber-500 — vurgu (baskın seviye / aktif durum / parmak) COL_TEXT = "#1f2937" # slate-800 — metin COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu # Türev amber tonları 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) # Türev slate tonları COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara COL_WHITE = "#ffffff" # --------------------------------------------------------------------------- # _engine_PS2.py — Problem 1: Master Theorem + Özyineleme Ağacı # T(n)=a·T(n/b)+f(n). Anahtar nicelik c_crit = log_b(a). f bir Θ(n^d) (veya # Θ(n^d·log^k n)); d ile c_crit'i kıyasla → Durum 1/2/3. Master theorem rasyonel # aritmetikle (Fraction) → kayan-nokta yuvarlama hatası YOK (tam kıyas). # --------------------------------------------------------------------------- def _log_b_a(a, b): """log_b(a)'yı KESİN bir Fraction olarak döndürür (b^p == a^r ile q=p/r ararız).""" if a < 1 or b < 2: raise ValueError("_log_b_a: a ≥ 1 ve b ≥ 2 olmalı") if a == 1: return Fraction(0) for r in range(1, 65): ar = a ** r p = 0 bp = 1 while bp < ar and p < 256: bp *= b p += 1 if bp == ar: return Fraction(p, r) return Fraction(math.log(a) / math.log(b)).limit_denominator(10 ** 9) def _exp_str(exp): """Bir Fraction üssü insan-okunur metne çevirir (1 → "", 1/2 → "1/2", 2 → "2").""" if exp == 1: return "" if exp.denominator == 1: return str(exp.numerator) return f"{exp.numerator}/{exp.denominator}" def _theta_form(theta_exp, theta_logk, bound): """Sonuç Θ/O formunu okunur metne çevirir (örn. "Θ(n)", "O(n^3/2 log n)").""" sym = "Θ" if bound == "Theta" else "O" es = _exp_str(theta_exp) if theta_exp == 0: base = "" elif es == "": base = "n" else: base = f"n^{es}" if theta_logk == 1: base = (base + " log n").strip() elif theta_logk >= 2: base = (base + f" log^{theta_logk} n").strip() if base == "": base = "1" return f"{sym}({base})" def master_theorem_case(a, b, f): """T(n)=a·T(n/b)+f(n) için master theorem durumunu ve Θ sonucunu döndürür. f = {"exp": Fraction, "logk": int=0, "bound": "O"|"Theta"="Theta"}. d=exp ile c_crit=log_b(a) kıyaslanır: d<c → Durum 1; d=c → Durum 2; d>c → Durum 3. """ exp = Fraction(f["exp"]) if not isinstance(f["exp"], Fraction) else f["exp"] logk = int(f.get("logk", 0)) fbound = f.get("bound", "Theta") c_crit = _log_b_a(a, b) if exp < c_crit: case, theta_exp, theta_logk, out_bound = 1, c_crit, 0, "Theta" elif exp == c_crit: case, theta_exp = 2, c_crit theta_logk = logk + 1 out_bound = "O" if fbound == "O" else "Theta" else: case, theta_exp, theta_logk = 3, exp, logk out_bound = "O" if fbound == "O" else "Theta" return { "case": case, "c_crit": c_crit, "theta_exp": theta_exp, "theta_logk": theta_logk, "bound": out_bound, "form": _theta_form(theta_exp, theta_logk, out_bound), } def recursion_tree_levels(a, b, n): """T(n)=a·T(n/b)+f(n) özyineleme ağacının seviye-seviye yapısını döndürür. Her seviye: node_count=a^level, subproblem_n=n/b^level, level_total=node·sub. Seviye sayısı = log_b(n)+1 (kök = seviye 0; n bir b kuvveti varsayılır). """ if a < 1 or b < 2 or n < 1: raise ValueError("recursion_tree_levels: a≥1, b≥2, n≥1 olmalı") levels = [] level = 0 sub = float(n) while True: node_count = a ** level levels.append({ "level": level, "node_count": node_count, "subproblem_n": sub, "work_per_node": sub, "level_total": node_count * sub, }) if sub <= 1: break sub = sub / b level += 1 if level > 100000: break return levels # --------------------------------------------------------------------------- # _engine_PS2.py — Problem 2: Sonsuz Diziyi Arama (üstel sıçrama + ikili arama) # Sağ sınır yok → önce 2^m galloping ile sınır bul (2^(m-1)≤k≤2^m), sonra ikili ara. # Toplam O(log k). (k = aranan İNDEKS, veri boyutu değil.) # --------------------------------------------------------------------------- def unbounded_search(target_index, oracle=None): """Sonsuz dizide hedefi galloping (üstel sıçrama) + ikili aramayla bulur — O(log k). Aşama 1: m=0,1,2,... için 2^m'i oracle'a sor (probe≥target diyene dek) → sandviç 2^(m-1)<target≤2^m. Aşama 2: [2^(m-1), 2^m] içinde ikili ara. Her oracle çağrısı bir probe; toplam probe O(log k). """ if target_index < 0: raise ValueError("unbounded_search: target_index ≥ 0 olmalı") probes = {"count": 0} if oracle is None: def oracle(probe): if target_index < probe: return -1 if target_index > probe: return +1 return 0 def ask(probe): probes["count"] += 1 return oracle(probe) # Aşama 1: üstel sıçrama (galloping) ile sağ sınır bul m = 0 while True: cmp = ask(2 ** m) if cmp == 0: return {"found": 2 ** m, "probes": probes["count"], "gallop_steps": m} if cmp == -1: break m += 1 lo = 2 ** (m - 1) if m >= 1 else 0 hi = 2 ** m # Aşama 2: [lo, hi] aralığında ikili arama while lo <= hi: mid = (lo + hi) // 2 cmp = ask(mid) if cmp == 0: return {"found": mid, "probes": probes["count"], "gallop_steps": m} elif cmp == +1: lo = mid + 1 else: hi = mid - 1 return {"found": -1, "probes": probes["count"], "gallop_steps": m} # --------------------------------------------------------------------------- # _engine_PS2.py — Problem 4: Tuğla Üfleme (Two-Finger ile O(n)) # heights[i] = i. evin tuğla sayısı. damage[i] = 1 + (sağda strictly küçük ev sayısı). # Özel yapı (artan-düşüş-artan): iki monoton parça; sol yarı eşik artar → sağ yarıda # yıkılan aralık yalnız büyür → j parmağı asla geri gitmez → two-finger O(n). # --------------------------------------------------------------------------- def two_finger_trace(heights): """fig-two-finger için two-finger algoritmasının adım-adım izini üretir. Sol parmak i ve sağ parmak j'nin her i adımındaki konumu + eşik (heights[i]) + damage. j'nin asla geri gitmediğini figür gösterir. """ n = len(heights) drop = None for i in range(n - 1): if heights[i] > heights[i + 1]: drop = i break steps = [] if drop is None: dmg = [1] * n return {"heights": list(heights), "drop": None, "left_end": None, "right_start": None, "steps": steps, "damage": dmg} left_end = drop right_start = drop + 1 j = right_start damage = [1] * n for i in range(left_end + 1): while j < n and heights[j] < heights[i]: j += 1 # j ASLA geri gitmez (monoton) smaller = j - right_start damage[i] = 1 + smaller steps.append({"i": i, "threshold": heights[i], "j": j, "damage": damage[i], "smaller_right": smaller}) return {"heights": list(heights), "drop": drop, "left_end": left_end, "right_start": right_start, "steps": steps, "damage": damage} ``` ## Problem 1: Yineleme Çözme — Master Theorem ve Özyineleme Ağacı {#sec-problem-1-d06} **İfade.** $T(n) = a \cdot T(n/b) + f(n)$ biçimindeki yinelemeleri çöz. Her birini **iki** yolla yap: (1) master theorem (kural seti), (2) özyineleme ağacı çizip seviye seviye işi toplayarak. ::: {.callout-tip title="Yaklaşım — Anahtar Niceliği Hesapla, f ile Kıyasla"} Master theorem üç duruma ayrılır; anahtar nicelik $n^{\log_b a}$'dır ($a$ = dallanma sayısı, $b$ = problemin küçülme oranı, $f$ = düğüm başına iş). Bu niceliğin üssünü ($\log_b a$) hesapla, $f$'in üssüyle kıyasla, duruma karar ver. Özyineleme ağacı aynı sonucu daha yavaş ama **aydınlatıcı** biçimde verir; master theorem ise hızlıdır ama "neden"i göstermez. ::: > *"the a is kind of like a branching factor... b is the amount that your problem size reduces... f is the amount of work that you do at each node."* — Justin, 6:14 **Çözüm.** Üç durum: - **Durum 1:** $f(n) = O(n^{\log_b a - \epsilon})$, $\epsilon > 0$ → $T(n) = \Theta(n^{\log_b a})$. ($f$ önemsiz; ağaçta dolaşma baskın.) - **Durum 2:** $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ → $T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$. - **Durum 3:** $f(n) = \Omega(n^{\log_b a + \epsilon})$ ve düzenlilik ($a \cdot f(n/b) \le c \cdot f(n)$, $c < 1$) → $T(n) = \Theta(f(n))$. ($f$ baskın.) *Örnek (a):* $T(n) = 2T(n/2) + O(\sqrt{n})$. $a = b = 2$, $n^{\log_2 2} = n$. $f = O(\sqrt{n}) = O(n^{1 - 1/2})$, yani $\epsilon = 1/2 > 0$ → **Durum 1** → $T(n) = \Theta(n)$. *Örnek (b):* $T(n) = 8T(n/4) + O(n^{3/2})$. $\log_4 8 = 3/2$, yani $n^{3/2}$. $f = O(n^{3/2})$, iki taraf eşit → **Durum 2**, $k = 0$ → $T(n) = O(n^{3/2}\log n)$. ($f$ big-O olduğundan sonuç da big-O, big-$\Theta$ değil.) **Özyineleme ağacı (ikinci yöntem):** Ağaçta $l$. seviyede $2^l$ (veya $8^l$) düğüm var, her biri $f(n/2^l)$ iş yapar; seviye sayısı $\log_b n$. Tüm seviyeleri topla — ortaya bir **geometrik seri** çıkar; sadeleştirince master theorem'le aynı sonuç gelir. Bu iki okumanın görsel karşılaştırması @fig-recursion-tree'de gösterilir: sol panel ağaç + seviye toplamları, sağ panel 3-durum kararı. > *"master theorem... the giant sledgehammer for solving recurrences without understanding why you got the answer."* — Justin, 4:09 **Karmaşıklık.** Sonuçlar: (a) $\Theta(n)$, (b) $O(n^{3/2}\log n)$. ```{python} #| label: fig-recursion-tree #| fig-cap: "Master teoremini **özyineleme ağacıyla** okuma: $T(n)=2T(n/2)+O(\\sqrt{n})$ ($n=64$). **Sol panel:** kök ($l=0$) tek alt-problem $\\sqrt{n}$; her seviyede düğüm sayısı ikiye katlanır ($2^l$) ve her düğümün işi $\\sqrt{n/2^l}$'e iner. **Seviye toplamı** $2^l\\cdot\\sqrt{n/2^l}$ aşağı indikçe $\\sqrt{2}$ çarpanıyla *büyür* — $8 \\to 11{,}3 \\to 16 \\to 22{,}6 \\to 32 \\to 45{,}3 \\to 64$ — yani artan bir **geometrik seri**dir ve **yapraklar** ($l=6$, **amber/BASKIN**) baskın terimi verir: $64$ düğüm $\\times \\sqrt{1}=64=\\Theta(n)$. Tüm seviyelerin toplamı $\\approx 199{,}2$, ama asimptotik olarak yaprak terimi belirleyicidir → $\\Theta(n)$. **Sağ panel:** 3-durum karar kuralı — $f(n)$'in üssü $d=\\exp(f)=\\tfrac12$ ile kritik üs $c^{*}=\\log_b a=\\log_2 2=1$ karşılaştırılır. $d<c^{*}$ olduğundan **Durum 1** seçilir (yapraklar baskın, $\\Theta(n^{c^{*}})$); Durum 2 ($d=c^{*}$, dengeli) ve Durum 3 ($d>c^{*}$, kök baskın) burada uygulanmaz. Sonuç: $\\Theta(n)$." #| fig-width: 12.4 #| fig-height: 7.2 # fig-recursion-tree — PS2 Problem 1: T(n)=2T(n/2)+O(√n) (Durum 1) özyineleme ağacı. # Seviye l'de 2^l düğüm × √(n/2^l) iş → seviye-toplamları geometrik seri, YAPRAKLAR # baskın (Θ(n)). Sağ panel d=exp(f) vs c*=log_b a 3-durum kararı. amber = baskın seviye # + aktif durum. recursion_tree_levels / master_theorem_case (gizli setup'taki _engine_PS2) # + COL_* / Fraction setup'tan; figüre özgü çizim burada inline. DETERMİNİSTİK (a,b,n sabit). from fractions import Fraction # --- DETERMİNİSTİK girdi: T(n)=2T(n/2)+O(√n), n=64 --- a, b, n = 2, 2, 64 f = {"exp": Fraction(1, 2), "bound": "O"} # O(√n) → exp = 1/2 levels = recursion_tree_levels(a, b, n) # 7 seviye (l=0..6) res = master_theorem_case(a, b, f) # Durum 1 → Θ(n) # Her seviye için ~iş = düğüm sayısı × √(alt-problem boyutu). L = len(levels) # = 7 leaf_level = L - 1 # baskın seviye = yapraklar per_level = [] for lev in levels: l = lev["level"] wpn = math.sqrt(lev["subproblem_n"]) # √(n/2^l) total = lev["node_count"] * wpn # 2^l · √(n/2^l) per_level.append({"l": l, "nodes": lev["node_count"], "sub": lev["subproblem_n"], "wpn": wpn, "total": total}) grand_total = sum(p["total"] for p in per_level) fig, (ax_tree, ax_decide) = plt.subplots( 1, 2, figsize=(12.4, 7.2), gridspec_kw={"width_ratios": [1.92, 1.0]}) fig.patch.set_facecolor(COL_WHITE) # ====================================================================== # SOL PANEL — özyineleme ağacı + seviye-toplamları (geometrik seri) # ====================================================================== draw_levels = [0, 1, 2, 3] y_gap = 1.42 node_h = 0.46 x_span = 12.0 level_y = {} node_xy = {} for row, l in enumerate(draw_levels): y = -row * y_gap level_y[l] = y cnt = 2 ** l if cnt == 1: xs = [0.0] else: xs = [(-x_span / 2) + i * (x_span / (cnt - 1)) for i in range(cnt)] node_xy[l] = xs # kenarlar (ebeveyn → 2 çocuk) for l in draw_levels[:-1]: for i, px in enumerate(node_xy[l]): py = level_y[l] cl = l + 1 for c in (2 * i, 2 * i + 1): cx = node_xy[cl][c] cy = level_y[cl] ax_tree.plot([px, cx], [py - node_h * 0.55, cy + node_h * 0.55], color=COL_SLATE_400, linewidth=1.1, zorder=1) # düğümler for l in draw_levels: y = level_y[l] hot = (l == leaf_level) # yapraklar baskın → amber for px in node_xy[l]: node_w = 0.92 ax_tree.add_patch(FancyBboxPatch( (px - node_w / 2, y - node_h / 2), node_w, node_h, boxstyle="round,pad=0.02,rounding_size=0.05", fc=COL_AMBER_100 if hot else COL_BG, ec=COL_ACCENT if hot else COL_PRIMARY, linewidth=2.0 if hot else 1.4, zorder=3)) ax_tree.text(px, y, "√(n/%d)" % (2 ** l) if l > 0 else "√n", ha="center", va="center", fontsize=7.2, color=COL_TEXT, weight="bold", zorder=4) # son çizilen seviyenin altına "⋮" ve yaprak özeti y_dots = level_y[draw_levels[-1]] - y_gap * 0.78 ax_tree.text(0.0, y_dots, "⋮", ha="center", va="center", fontsize=18, color=COL_SLATE_500, zorder=4) # yaprak seviyesi özet kutusu (amber = baskın) y_leaf = y_dots - y_gap * 0.92 leaf = per_level[leaf_level] lw_box = x_span + 0.9 ax_tree.add_patch(FancyBboxPatch( (-lw_box / 2, y_leaf - node_h * 0.62), lw_box, node_h * 1.24, boxstyle="round,pad=0.02,rounding_size=0.05", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3)) ax_tree.text(0.0, y_leaf, "yaprak seviyesi l=%d: %d düğüm × √1 = %d (BASKIN)" % (leaf["l"], leaf["nodes"], int(round(leaf["total"]))), ha="center", va="center", fontsize=9.2, color=COL_AMBER_700, weight="bold", zorder=4) # --- sağ kenar: seviye-toplamları (geometrik seri) --- x_tot = x_span / 2 + 1.55 ax_tree.text(x_tot, level_y[0] + node_h * 1.35, "seviye toplamı", ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold") for l in draw_levels: p = per_level[l] y = level_y[l] hot = (l == leaf_level) ax_tree.text(x_tot, y, "l=%d: %d × √%g ≈ %.1f" % (l, p["nodes"], p["sub"], p["total"]), ha="left", va="center", fontsize=8.4, color=COL_AMBER_700 if hot else COL_TEXT, weight="bold" if hot else "normal", zorder=4) ax_tree.text(x_tot, y_dots, "⋮ (her seviye ×√2 büyür)", ha="left", va="center", fontsize=8.0, color=COL_SLATE_500, style="italic") ax_tree.text(x_tot, y_leaf, "l=%d: %d × √1 = %d" % (leaf["l"], leaf["nodes"], int(round(leaf["total"]))), ha="left", va="center", fontsize=8.4, color=COL_AMBER_700, weight="bold", zorder=4) # toplam = Θ(n) (yapraklar baskın → geometrik seri tabandan toplar) y_sum = y_leaf - y_gap * 0.95 ax_tree.text(0.0, y_sum, "Σ seviye ≈ %.1f → yaprak terimi baskın (×√2 artan geometrik) → Θ(n) = Θ(%d)" % (grand_total, n), ha="center", va="center", fontsize=9.4, color=COL_AMBER_700, weight="bold", zorder=5, bbox=dict(boxstyle="round,pad=0.4", fc=COL_WHITE, ec=COL_AMBER_600, lw=1.6)) ax_tree.text(0.0, level_y[0] + node_h * 2.1, "T(n) = 2·T(n/2) + O(√n) — ağaç: seviye l'de 2ˡ düğüm × √(n/2ˡ) iş", ha="center", va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold") ax_tree.set_xlim(-x_span / 2 - 1.4, x_tot + 5.6) ax_tree.set_ylim(y_sum - 0.7, level_y[0] + node_h * 3.2) ax_tree.set_aspect("auto") ax_tree.axis("off") # ====================================================================== # SAĞ PANEL — 3-durum karar kuralı (d vs c_crit = log_b a) # ====================================================================== ax_decide.set_xlim(0, 10) ax_decide.set_ylim(-1.1, 10) ax_decide.axis("off") ax_decide.text(5.0, 9.55, "Master Teoremi — 3 Durum", ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold") ax_decide.text(5.0, 8.95, "karşılaştır: d = exp(f) vs c* = log_b a", ha="center", va="center", fontsize=9.2, color=COL_SLATE_500, style="italic") ax_decide.text(5.0, 8.25, "bu örnek: d = 1/2 , c* = log₂2 = 1", ha="center", va="center", fontsize=9.4, color=COL_AMBER_700, weight="bold") cases = [ ("Durum 1", "d < c*", "yapraklar baskın\nΘ(n^c*)", 1), ("Durum 2", "d = c*", "dengeli\nΘ(n^c* · logⁿ⁺¹)", 2), ("Durum 3", "d > c*", "kök baskın\nΘ(f(n))", 3), ] active_case = res["case"] # 1 box_w, box_h = 8.4, 1.78 x0 = 0.8 y_top = 7.0 for k, (title, cond, desc, cnum) in enumerate(cases): y = y_top - k * (box_h + 0.42) hot = (cnum == active_case) ax_decide.add_patch(FancyBboxPatch( (x0, y - box_h), box_w, box_h, boxstyle="round,pad=0.03,rounding_size=0.12", fc=COL_AMBER_100 if hot else COL_BG, ec=COL_ACCENT if hot else COL_SLATE_400, linewidth=2.6 if hot else 1.4, zorder=2)) ax_decide.text(x0 + 0.28, y - 0.42, "%s (%s)" % (title, cond), ha="left", va="center", fontsize=10.2, color=COL_AMBER_700 if hot else COL_TEXT, weight="bold", zorder=4) ax_decide.text(x0 + 0.28, y - box_h + 0.56, desc, ha="left", va="center", fontsize=8.6, color=COL_TEXT if hot else COL_SLATE_500, zorder=4) if hot: ax_decide.text(x0 + box_w - 0.30, y - box_h * 0.5, "◀ BU", ha="right", va="center", fontsize=9.5, color=COL_ACCENT, weight="bold", zorder=5) # sonuç rozet (durum kutularının ALTINDA, çakışma yok) ax_decide.text(5.0, -0.35, "Sonuç: %s = Θ(n)" % res["form"], ha="center", va="center", fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=5, bbox=dict(boxstyle="round,pad=0.45", fc=COL_WHITE, ec=COL_AMBER_600, lw=1.8)) fig.suptitle( "Özyineleme ağacı ile Master Teoremi: T(n)=2T(n/2)+O(√n) → Durum 1 → Θ(n) (yapraklar baskın)", color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985) plt.tight_layout(rect=(0, 0, 1, 0.95)) plt.show() ``` ## Problem 2: Sonsuz Diziyi Arama {#sec-problem-2-d06} **İfade.** Sonsuz bir gezegen dizisinde, indeksi $k$ olan gezegeni bul. Bir gezegende durup oracle'a sorabilirsin: "aradığım indeks benden büyük mü küçük mü?" Hedef: **$O(\log k)$** zaman (dikkat: $k$, verinin boyutu değil, aranan indeks). ::: {.callout-tip title="Yaklaşım — Önce Sağ Sınırı Bul, Sonra İkili Ara"} İçgüdü ikili arama; ama ikili arama bir **sağ sınır** ister ve sonsuz dizide sağ sınır yok. Önce bir sağ sınır *bulmalıyız* — sonsuz bir kümenin "ortası" yoktur, bu yüzden indeksi her adımda ikiye katlayarak (üstel sıçrama) hedefi aşan ilk gücü buluruz. ::: > *"what is the middle of an infinite set of planets? Infinite, exactly. It's a problem."* — Justin, 49:26 **Çözüm.** İki aşama: 1. **Sınır bul (üstel sıçrama):** $m = 0, 1, 2, \dots$ için $2^m$ indeksli gezegeni ziyaret et, ta ki $k \le 2^m$ olana dek. Bu, $\log k$ adım sürer ve şu sandviçi verir: $2^{m-1} \le k \le 2^m$. 2. **İkili arama:** Artık $[2^{m-1}, 2^m]$ aralığı var (genişliği $\sim k$); bu aralıkta ikili arama, $\log k$ adım. > *"I'm going to visit planet 2 to the m for each m starting with m equals 0."* — Justin, 50:25 @fig-unbounded-search bu iki aşamayı tek bir sayı-doğrusunda izler: önce galloping yaylarıyla sınır, sonra numaralı mid sorgularıyla ikili arama. **Karmaşıklık.** $\log k$ (sınır bulma) + $\log k$ (ikili arama) = **$O(\log k)$**. ```{python} #| label: fig-unbounded-search #| fig-cap: "Sonsuz diziyi arama — iki aşamalı O(log k) strateji (hedef indeks $k=50$). **AŞAMA 1 (üstel sıçrama / galloping):** sağ sınır bilinmediği için indeksi her adımda **ikiye katlayarak** $2^0,2^1,\\dots,2^m$ sorgulanır (amber yaylar: $1,2,4,8,16,32,64$). İlk $2^6=64 \\ge k$ bulununca durulur — toplam **7 sorgu** — ve bu, $2^5=32 \\le k \\le 2^6=64$ **sandviçini** verir (üstteki köşeli parantez). Hedef $k=50$ amber kesik dikey çizgiyle işaretlidir. **AŞAMA 2 (ikili arama):** artık sonlu $[32,64]$ aralığında klasik ikili arama yapılır; numaralı mid sorguları sırasıyla $48 \\to 56 \\to 52 \\to 50$ (4 sorgu, ✓ = bulundu). Her iki aşama da $O(\\log k)$ olduğundan toplam **11 sorgu** $= O(\\log k)$ (rozet sağ altta) — $\\log_2 50 \\approx 5{,}64$. Anahtar sezgi: sınır galloping ile $O(\\log k)$'da bulunur, sonra ikili arama yine $O(\\log k)$'da bitirir." #| fig-width: 11 #| fig-height: 5.2 # fig-unbounded-search — PS2 Problem 2: sonsuz dizide arama (üstel sıçrama + ikili # arama) tek bir sayı-doğrusunda. unbounded_search (gizli setup _engine_PS2) ile # probe sırası yakalanır; AŞAMA 1 amber yaylar (galloping), AŞAMA 2 numaralı mid # kareleri (ikili arama). DETERMİNİSTİK (sabit target=50). Setup globalleri: plt, # FancyBboxPatch, FancyArrowPatch, COL_*, unbounded_search. Figüre özgü çizim inline. def draw_unbounded_search(ax, target=50): """Sonsuz dizide arama: üstel sıçrama + ikili arama tek sayı-doğrusunda — O(log k). AŞAMA 1 (galloping): 2^0..2^m ziyaret, ilk 2^m ≥ k durur (sandviç 2^(m-1)≤k≤2^m). AŞAMA 2: [2^(m-1), 2^m] aralığında ikili arama. DETERMİNİSTİK (sabit target). """ # --- algoritmayı izle (probe sırasını yakala) --- def oracle(probe): if target < probe: return -1 if target > probe: return +1 return 0 result = unbounded_search(target, oracle=oracle) # AŞAMA 1: galloping probes 2^0..2^m (ilk 2^m ≥ k) gallop = [] m = 0 while True: gallop.append(2 ** m) if 2 ** m >= target: break m += 1 lo_b, hi_b = 2 ** (m - 1), 2 ** m # sandviç sınırları (32, 64) # AŞAMA 2: ikili arama adımları (lo, hi, mid, karar) bin_steps = [] lo, hi = lo_b, hi_b while lo <= hi: mid = (lo + hi) // 2 if mid == target: bin_steps.append((lo, hi, mid, "found")) break elif target > mid: bin_steps.append((lo, hi, mid, "right")) lo = mid + 1 else: bin_steps.append((lo, hi, mid, "left")) hi = mid - 1 # --- Geometri: tek yatay sayı-doğrusu 0..hi_b --- x_max = hi_b AXIS_Y = 0.0 def X(v): return v / x_max * 10.0 # 0..10 ekran genişliğine ölçekle ax.plot([X(0), X(x_max)], [AXIS_Y, AXIS_Y], color=COL_SLATE_400, linewidth=1.6, zorder=1) ax.annotate("", xy=(X(x_max) + 0.55, AXIS_Y), xytext=(X(x_max), AXIS_Y), arrowprops=dict(arrowstyle="-|>", color=COL_SLATE_400, lw=1.6)) ax.text(X(x_max) + 0.72, AXIS_Y, "∞", ha="left", va="center", fontsize=12, color=COL_SLATE_500) # ----- AŞAMA 1: üstel sıçramalar (amber yaylar) ----- y_gallop = 1.30 crowd_offsets = {0: -0.86, 1: -0.62, 2: -0.38, 3: -0.62} # sıkışık küçük indeks kademele prev = 0 for idx, p in enumerate(gallop): x = X(p) reached = (p >= target) ax.plot([x], [AXIS_Y], marker="o", markersize=7, markerfacecolor=COL_ACCENT if reached else COL_AMBER_100, markeredgecolor=COL_AMBER_700, markeredgewidth=1.6, zorder=5) lab_dy = crowd_offsets.get(idx, -0.34) if idx in crowd_offsets: ax.plot([x, x], [AXIS_Y - 0.10, AXIS_Y + lab_dy + 0.10], color=COL_AMBER_300, linewidth=0.7, zorder=3) ax.text(x, AXIS_Y + lab_dy, f"2^{idx}={p}", ha="center", va="top", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5) if idx > 0: ax.add_patch(FancyArrowPatch( (X(prev), AXIS_Y + 0.06), (x, AXIS_Y + 0.06), arrowstyle="-|>", mutation_scale=12, color=COL_ACCENT, linewidth=2.0, zorder=4, connectionstyle="arc3,rad=-0.40")) prev = p ax.text(X(0), y_gallop + 0.55, "AŞAMA 1 — üstel sıçrama (galloping): 1, 2, 4, 8, 16, 32, 64 …", ha="left", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold") ax.text(X(0), y_gallop + 0.22, f"her adımda indeksi İKİYE KATLA; ilk 2^{m}={hi_b} ≥ k durur → {len(gallop)} sorgu", ha="left", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic") # ----- Sandviç köşeli parantez [2^(m-1), 2^m] ----- y_brk = AXIS_Y + 0.60 xlo, xhi = X(lo_b), X(hi_b) ax.plot([xlo, xlo, xhi, xhi], [y_brk - 0.10, y_brk, y_brk, y_brk - 0.10], color=COL_PRIMARY, linewidth=1.8, zorder=3) ax.text((xlo + xhi) / 2, y_brk + 0.14, f"sandviç: 2^{m-1}={lo_b} ≤ k ≤ 2^{m}={hi_b}", ha="center", va="bottom", fontsize=9, color=COL_PRIMARY, weight="bold") # ----- Hedef k dikey çizgisi ----- xk = X(target) ax.plot([xk, xk], [AXIS_Y - 0.95, y_brk], color=COL_AMBER_600, linewidth=1.4, linestyle="--", zorder=2) ax.text(xk, AXIS_Y - 1.02, f"hedef k = {target}", ha="center", va="top", fontsize=10, color=COL_AMBER_700, weight="bold") # ----- AŞAMA 2: ikili arama (numaralı mid kareleri) ----- y_bin = AXIS_Y - 1.65 ax.add_patch(FancyBboxPatch( (xlo, y_bin - 0.16), xhi - xlo, 0.32, boxstyle="square,pad=0.0", fc=COL_BG, ec=COL_PRIMARY, linewidth=1.4, zorder=2)) for order, (slo, shi, mid, dec) in enumerate(bin_steps, start=1): xm = X(mid) found = (dec == "found") ax.plot([xm], [y_bin], marker="s", markersize=8, markerfacecolor=COL_ACCENT if found else COL_AMBER_100, markeredgecolor=COL_AMBER_700, markeredgewidth=1.6, zorder=5) ax.text(xm, y_bin + 0.26, f"{order}" + (" ✓" if found else ""), ha="center", va="bottom", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=6) ax.text(xm, y_bin - 0.26, str(mid), ha="center", va="top", fontsize=8, color=COL_TEXT, weight="bold", zorder=6) ax.text(X(0), y_bin - 0.60, f"AŞAMA 2 — [{lo_b}, {hi_b}] aralığında ikili arama: " f"{len(bin_steps)} sorgu → k={target} bulundu", ha="left", va="center", fontsize=10, color=COL_AMBER_700, weight="bold") # ----- Toplam maliyet rozeti ----- ax.text(X(x_max) + 0.1, y_bin - 0.05, f"toplam {result['probes']} sorgu\n= O(log k)", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6, bbox=dict(boxstyle="round,pad=0.4", fc=COL_WHITE, ec=COL_AMBER_600, lw=1.4)) ax.set_xlim(X(0) - 0.8, X(x_max) + 2.6) ax.set_ylim(y_bin - 1.0, y_gallop + 0.9) ax.axis("off") return ax fig, ax = plt.subplots(figsize=(11, 5.2)) fig.patch.set_facecolor(COL_WHITE) draw_unbounded_search(ax, target=50) fig.suptitle( "Sonsuz diziyi arama: üstel sıçrama (AŞAMA 1) + ikili arama (AŞAMA 2) — O(log k)", color=COL_TEXT, fontsize=12.5, weight="bold", y=0.99, ) plt.tight_layout() plt.show() ``` ## Problem 3: Katmanlı Görüntü Editörü {#sec-problem-3-d06} **İfade.** Bir görüntü editörü veri yapısı tasarla: katmanları üst-alt sırada tutar. İşlemler: `make_doc` $O(1)$, `import(x)` (üste ekle) $O(n)$, `display()` (sırayla tüm ID'ler) $O(n)$, ve **`move_below(x, y)`** ($x$ katmanını $y$'nin altına taşı) **$O(\log n)$**. ::: {.callout-tip title="Yaklaşım — İki Yönü Ayır, Sonra Augmentation ile Bağla"} Problemde iki yön var: **dizi (sequence)** yönü (display sırası) ve **küme (set)** yönü (bir katmanı hızlı bulmak). İkisini ayrı veri yapısıyla çöz, sonra bir **augmentation** ile bağla — sıralı dizideki her anahtara, bağlı listedeki düğümün işaretçisini iliştir. Böylece "bul" $O(\log n)$, "yeniden bağla" $O(1)$ olur. ::: **Çözüm.** İki yapı birlikte çalışır: - **Çift bağlı liste (doubly linked list):** katmanların ekran sırasını tutar (display için $O(n)$). - **Sıralı dizi (set):** ID'leri sıralı tutar; ikili aramayla bir ID'yi $O(\log n)$'de bulur. - **Augmentation:** sıralı dizideki her anahtara, o öğenin **bağlı listedeki düğümüne bir işaretçi** ekle. (Bir düğümü silmek diğer işaretçileri bozmaz — işaretçiler geçerli kalır.) > *"we can attach data to our keys... I am going to attach a pointer into my linked list."* — Justin, 1:02:21 **`move_below(x, y)`** üç adım: (1) $x$ ve $y$'yi sıralı dizide ikili aramayla bul, bağlı liste işaretçilerini al — $O(\log n)$; (2) $x$'i bağlı listeden çıkar ve $y$'nin altına ekle — işaretçiler elimizde olduğundan $O(1)$; (3) küme değişmez (sadece sıra değişti). Önemli sağlama: `move_below` kümeyi değiştirmez, çünkü hangi öğelerin olduğu değil, yalnızca sıraları değişir. **Karmaşıklık.** `make_doc` $O(1)$, `import` $O(n)$ (sıralı diziye ekleme), `display` $O(n)$, `move_below` **$O(\log n)$** (bulma) + $O(1)$ (yeniden bağlama). ## Problem 4: Tuğla Üfleme {#sec-problem-4-d06} **İfade.** Bir sıra evin tuğla sayıları verilir. Kurt bir eve üfleyince o ev *ve sağındaki* kendisinden az tuğlalı tüm evler yıkılır. Her ev için, ona üflendiğinde kaç ev yıkıldığını hesapla. (Hikâyenin özü: "her öğe için, sağında kendisinden küçük olanları say + 1".) ::: {.callout-tip title="Yaklaşım — Naif Çift Döngüden Monoton Parmaklara"} Naif çözüm çift döngü → $O(n^2)$; yasak. Bir yapısal varsayım kullanılır: bir ev hariç hepsi **özel** (sağ komşusu kendisinden büyük-eşit), yani dizi **artan-sonra-bir-düşüş-sonra-artan** iki sıralı parçaya bölünür. Sol yarı (artan) sağa hiçbir şey yıkamaz; her ev yalnızca sağ yarıda kendinden küçükleri yıkar. Sol yarıdaki ev büyüdükçe yıkılan aralık yalnız *genişler* — geri gitmez — ve bu, two-finger'a kapı açar. ::: **Çözüm.** Sol yarıdaki ev tuğla sayısı arttıkça, sağ yarıda yıkılan evlerin aralığı yalnızca **büyür** (geri gitmez). Bu, **iki parmak (two-finger)** tekniğine kapı açar: `i` parmağı sol yarıda ilerlerken, `j` parmağı sağ yarıda "ilk yıkılmayan" evi işaret eder; `i` sağa kaydıkça `j` de sağa kayar, asla sola dönmez. > *"It's called a two-finger algorithm."* — Justin, 1:25:02 ```python j = right_start # sağ yarının ilk evi (global indeks) for i in range(left_end + 1): while j < n and heights[j] < heights[i]: j += 1 # j asla geri gitmez (5→6→7→8) smaller = j - right_start # sağda i'den küçük ev sayısı damage[i] = 1 + smaller # kendisi + sağda küçük ev sayısı ``` Her iki parmak da diziyi yalnızca bir kez kateder → $O(n)$. (Genel hâl, özel varsayım olmadan, aynı fikir + merge sort ile çözülür.) @fig-two-finger bu izi $[2,4,6,9]$ sol yarısı ile $[1,3,5,7]$ sağ yarısı üzerinde adım adım gösterir; `j` parmağının $5 \to 6 \to 7 \to 8$ ile yalnız sağa kaydığına dikkat. **Karmaşıklık.** Two-finger ile **$O(n)$** ($n^2$ naif veya $n\log n$ ikili-arama yerine). ```{python} #| label: fig-two-finger #| fig-cap: "İki parmak (two-finger) tuğla üfleme izi — Problem 4 İMZA figürü. Dizi tek düşüşten (9→1) ikiye ayrılır: **sol yarı** [2,4,6,9] artan, **sağ yarı** [1,3,5,7] artan. Sol parmak `i` sol yarıyı soldan sağa sweep eder (amber, eşik = `heights[i]`); sağ parmak `j` sağ yarıda eşikten küçük olmayan **ilk** evi işaretler. `i` sağa kaydıkça eşik büyür, bu yüzden `j` yalnız **sağa** kayar — asla geri gitmez (5→6→7→8). **Adım 1** (eşik 2): sağda yalnız 1 küçük → hasar 2. **Adım 2** (eşik 4): 1,3 küçük → hasar 3. **Adım 3** (eşik 6): 1,3,5 → hasar 4. **Adım 4** (eşik 9): 1,3,5,7 → hasar 5. Yıkılan sağ-yarı evleri her satırda koyu amber. İki parmak diziyi birer kez katettiği için toplam **O(n)** — naif \"her ev için sağı tara\" O(n²) yerine. Sağ yarının kendi içi de artan olduğundan oradaki her ev yalnız kendini yıkar (hasar 1); nihai `hasar[]` = [2,3,4,5,1,1,1,1]." #| fig-width: 11.4 #| fig-height: 8.6 # fig-two-finger — PS2 Problem 4 (Tuğla Üfleme) İMZA: two-finger O(n) izi. # two_finger_trace (gizli setup'taki _engine_PS2) + Slate+Amber (COL_*). Girdi # DETERMİNİSTİK: artan sol yarı | artan sağ yarı, tek düşüş 9→1. Figüre özgü # çizim yardımcıları burada inline (setup globalleri: plt, FancyBboxPatch, # FancyArrowPatch, COL_*, two_finger_trace). amber = aktif eşik / yıkılan evler; # i parmağı amber, j parmağı koyu amber (sağa-monoton). _CELL_W, _CELL_H = 0.94, 0.78 _ROW_GAP = 2.0 def _tf_row(ax, y, heights, *, left_end, right_start, i_cur, j_cur, counted, row_label): """Bir two-finger adımı: dizi hücreleri + i/j parmak okları + yıkım sayımı.""" n = len(heights) xs = [k * _CELL_W for k in range(n)] centers = [] for k, h in enumerate(heights): x = xs[k] if k == i_cur: fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6 # aktif sol ev (eşik) elif k in counted: fc, ec, lw = COL_AMBER_300, COL_AMBER_700, 2.0 # yıkılan sağ ev elif k <= left_end: fc, ec, lw = COL_BG, COL_PRIMARY, 1.5 # sol yarı (pasif) else: fc, ec, lw = COL_WHITE, COL_SLATE_400, 1.3 # sağ yarı (ayakta) ax.add_patch(FancyBboxPatch( (x, y), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2)) cx, cy = x + _CELL_W * 0.46, y + _CELL_H * 0.5 centers.append((cx, cy)) ax.text(cx, cy, str(h), ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(cx, y - 0.20, str(k), ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=4) # sol/sağ yarı ayıracı (düşüş çizgisi) sep_x = xs[right_start] - _CELL_W * 0.04 ax.plot([sep_x, sep_x], [y - 0.30, y + _CELL_H + 0.46], color=COL_SLATE_400, linewidth=1.2, linestyle=(0, (3, 3)), zorder=1) # i parmağı (sol, amber) — aktif evin üstünde cxi = centers[i_cur][0] ax.add_patch(FancyArrowPatch( (cxi, y + _CELL_H + 0.40), (cxi, y + _CELL_H + 0.06), arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT, linewidth=2.2, zorder=5)) ax.text(cxi, y + _CELL_H + 0.56, f"i={i_cur}", ha="center", va="bottom", fontsize=9.5, color=COL_ACCENT, weight="bold", zorder=5) # j parmağı (sağ, koyu amber) — yıkılmayan ilk ev (n ise dizinin sağ ucu) cxj = centers[j_cur][0] if j_cur < n else xs[-1] + _CELL_W ax.add_patch(FancyArrowPatch( (cxj, y + _CELL_H + 0.40), (cxj, y + _CELL_H + 0.06), arrowstyle="-|>", mutation_scale=14, color=COL_AMBER_600, linewidth=2.2, zorder=5)) ax.text(cxj, y + _CELL_H + 0.56, f"j={j_cur}", ha="center", va="bottom", fontsize=9.5, color=COL_AMBER_600, weight="bold", zorder=5) # sol satır etiketi + sağ: eşik · yıkım · hasar ax.text(-1.05, y + _CELL_H * 0.5, row_label, ha="right", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) n_counted = len(counted) ax.text(xs[-1] + _CELL_W + 0.55, y + _CELL_H * 0.5, f"eşik={heights[i_cur]} · yıkım={n_counted} · hasar={1 + n_counted}", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5) return centers # --- Deterministik iz: sol artan [2,4,6,9] | sağ artan [1,3,5,7], düşüş 9→1 --- heights = [2, 4, 6, 9, 1, 3, 5, 7] tr = two_finger_trace(heights) n = len(heights) left_end = tr["left_end"] # 3 right_start = tr["right_start"] # 4 steps = tr["steps"] # 4 sol-yarı adımı (i=0..3) fig, ax = plt.subplots(figsize=(11.4, 8.6)) fig.patch.set_facecolor(COL_WHITE) n_rows = len(steps) y_rows = [(-r) * _ROW_GAP for r in range(n_rows)] for r, step in enumerate(steps): j_cur = step["j"] counted = set(range(right_start, j_cur)) # bu adımda yıkılan sağ evler [right_start, j) _tf_row(ax, y_rows[r], heights, left_end=left_end, right_start=right_start, i_cur=step["i"], j_cur=j_cur, counted=counted, row_label=f"Adım {r + 1}") # alt: nihai hasar dizisi (özet) y_dmg = (-n_rows) * _ROW_GAP - 0.15 xs = [k * _CELL_W for k in range(n)] ax.text(-1.05, y_dmg + _CELL_H * 0.5, "hasar[]", ha="right", va="center", fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=5) for k, d in enumerate(tr["damage"]): hot = k <= left_end ax.add_patch(FancyBboxPatch( (xs[k], y_dmg), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=COL_AMBER_100 if hot else COL_BG, ec=COL_ACCENT if hot else COL_SLATE_400, linewidth=2.0 if hot else 1.3, zorder=2)) ax.text(xs[k] + _CELL_W * 0.46, y_dmg + _CELL_H * 0.5, str(d), ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(xs[-1] + _CELL_W + 0.55, y_dmg + _CELL_H * 0.5, "her ev: 1 (kendisi) + sağda küçük ev sayısı", ha="left", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=5) fig.suptitle( "İki parmak (two-finger): i sola sweep ederken j yalnız sağa kayar — O(n)", color=COL_TEXT, fontsize=13, weight="bold", y=0.975) ax.text(xs[-1] * 0.5, y_rows[0] + _CELL_H + 1.05, "sol yarı [2,4,6,9] artan | sağ yarı [1,3,5,7] artan · " "j parmağı 5→6→7→8 (geri gitmez)", ha="center", va="center", fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=5) ax.set_xlim(-3.0, xs[-1] + _CELL_W + 6.4) ax.set_ylim(y_dmg - 0.6, y_rows[0] + _CELL_H + 1.45) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## Ne Öğrendik? {#sec-ne-ogrendik-d06} ::: {.callout-important title="Altı Taşınabilir Araç"} Bu oturum, Ders 4-5'in teorisini dört somut problemde uyguladı ve altı taşınabilir araç kazandırdı: 1. **Master theorem + özyineleme ağacı:** Yinelemeyi iki yolla çöz; $n^{\log_b a}$ anahtar niceliktir, ağaç "neden"i gösterir. 2. **Asimptotik titizlik:** $O$ / $\Theta$ / $\Omega$'yu özensiz yazma; $f$ big-O ise sonuç da big-O'dur. 3. **Üstel sıçrama (galloping):** Sağ sınırı olmayan aramada, $2^m$ ile sınır bul, sonra ikili ara — $O(\log k)$. 4. **Augmentation ile iki yapı birleştirme:** set (ID bul) + sequence (sıra tut); anahtara liste işaretçisi ekle. 5. **Two-finger ile $n^2 \to n$:** Monoton ilerleyen iki parmak, çift döngüyü lineere indirir. 6. **Problem okuma:** Süslü hikâyeden "işe yarayan iki cümleyi" çıkarmak — algoritmik özü görmek. ::: ## Sonraki {#sec-sonraki-d06} ::: {.callout-warning title="Ders 5 (L5) — Doğrusal Zamanlı Sıralama"} Sırada **Ders 5 (L5): Doğrusal Zamanlı Sıralama** var — Jason Ku ile, karşılaştırma modelinin $\Omega(n \log n)$ sınırını aşan sıralamalara (counting sort, radix sort) geçiyoruz. Bu oturumdaki **master theorem** ve **two-finger** sezgileri, oradaki doğrusal-zaman analizinde doğrudan işine yarayacak. :::