9 Problem Oturumu 3

Ders 4-5’in uygulaması: hashing ve doğrusal sıralamanın dört uygulaması — indirgeme, değişmez, radix dönüşümleri, two-finger ve kayan pencere

Oturum bilgisi

Demaine’in videosu: YouTube — Problem Session 3 (≈60 dk)
OCW sayfası: MIT 6.006 Problem Session 3
Seri: MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 8 (Problem Oturumu 3)
Hoca: Erik Demaine
Okuma süresi: ≈26 dk

9.1 Bu Problem Oturumu Ne Hakkında?

Üçüncü problem oturumu (Erik Demaine), son iki haftanın konularını uygular: hashing (Ders 5) ve doğrusal-zamanlı sıralama (counting/radix sort, Ders 4-5). Demaine, her problem için izlediği yöntemi açıkça gösterir: kelime problemini biçimsel bir algoritma hedefine çevir, fikirler üret, sonra detayları kontrol et. Bu üç adımlı disiplin, dört problemin de ortak iskeletidir.

“convert the word problem into a concise formal algorithms thing… come up with ideas… check the details.” — Demaine, 0:46

İki anahtar ipucu tüm oturuma damga vurur (Şekil 33.1): bir problem ifadesinde “expected” (beklenen) görürsen rastgelelik söz konusudur ve elindeki tek rastgelelik aracı hashing’dir; “nice polynomial” (sabit üslü polinom, $u \le n^c$) görürsen radix sort dene. Dört problem birer “İfade → Yaklaşım → Çözüm → Karmaşıklık” akışıyla işlenir.

“‘expected’ is always a good keyword, because it means randomization is involved… the only form of randomization you will use is essentially hashing.” — Demaine, 6:10

flowchart TD
    R["Problem Oturumu 3<br/>(Ders 4-5 uygulaması)"] --> P1["Problem 1<br/>Hash Tablosundan Dizi"]
    R --> P2["Problem 2<br/>Critter Sort (4 anahtar)"]
    R --> P3["Problem 3<br/>Küp Toplamı"]
    R --> P4["Problem 4<br/>Poker (Sliding Window)"]
    H1["ipucu: 'expected'<br/>(beklenen)"] -.-> HASH["→ hashing kullan"]
    H2["ipucu: 'nice polynomial'<br/>(sabit üslü, u ≤ n^c)"] -.-> RADIX["→ radix sort dene"]
    HASH -.-> P1
    HASH -.-> P3
    RADIX -.-> P2
    RADIX -.-> P3
    RADIX -.-> P4

    classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
    classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
    classDef hint fill:#ffffff,stroke:#d97706,stroke-width:1.5px,color:#1f2937
    classDef tool fill:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937
    class R root
    class P1,P2,P3,P4 prob
    class H1,H2 hint
    class HASH,RADIX tool

Şekil 9.1: Problem Oturumu 3’ün kavram haritası: kök (PS3) dört probleme dallanır ve iki anahtar ipucu düğümü tüm araç seçimini yönlendirir. Problem 1 hash tablosundan dizi kurar (indirgeme + değişmez); Problem 2 dört farklı anahtarı doğrusal sıralar (radix dönüşümleri); Problem 3 küp toplamını çözer (hash vs two-finger); Problem 4 poker ellerini sayar (kayan pencere + frekans tablosu). Soldaki iki ipucu — ‘expected’ bekleneni görünce hashing, ‘nice polynomial’ sabit üslü polinom görünce radix sort — Demaine’in problem ifadesinden araca giden tercüme kuralıdır.

9.2 Problem 1: Hash Tablosundan Dizi

İfade. Bir hash tablosu (set: build $O(n)$ beklenen, find $O(1)$ beklenen, insert/delete $O(1)$ beklenen amortize) black box olarak verilir. Bununla bir dizi (sequence) kur: get/set_at $O(1)$ beklenen, insert/delete_at $O(n)$ beklenen, insert/delete first/last $O(1)$ beklenen amortize.

Yaklaşım — İndirgeme (reduction): diziyi set’e çevir

Bu bir indirgemedir (reduction): sequence problemini, çözümünü zaten bildiğimiz set problemine çeviriyoruz. İlk hamle, zorlukları ayırmaktır. insert_at/delete_at için $O(n)$ bütçesi var → her seferinde tüm yapıyı yeniden kurmak serbest. Asıl ustalık gerektiren kısım, uçlardaki ($O(1)$ amortize) işlemlerdir; orada bir indeks hilesi gerekir.

“this is what we call a reduction… we’re reducing the sequence problem to the set problem.” — Demaine, 3:17

Çözüm. Anahtar fikir: her öğeye anahtar = sıradaki indeksi ver, böylece set’te saklanabilir.

get_at(i): find(first + i).value. set_at(i, x): find(first + i) ile nesneyi bul, value’sunu x yap. $O(1)$ beklenen.
insert/delete_at(i): iter ile öğeleri bir diziye çıkar, kaydır, build ile yeniden kur. $O(n)$ — bütçe içinde.
insert/delete_last: anahtar = first + length (veya first + length − 1). $O(1)$.
insert/delete_first: sorun — indeks 0’a eklemek tüm anahtarları kaydırır ($O(n)$). Çözüm: bir first değişkeni tut (en küçük anahtar); başa eklerken first’ü azalt (negatif anahtarlara izin ver). İndeks i artık first + i anahtarına eşlenir.

Aşağıdaki özet, motorun (HashSequence) çekirdek mantığını gösterir: first değişkeni ve insert_first’ün first’ü azaltışı, insert_at’in iter + build ile yeniden kurması.

class HashSequence:                              # diziyi black-box set'e indirger
    def __init__(self, iterable=()):
        self._d = {}                             # set: anahtar -> değer
        self._first = 0                          # en küçük anahtar (negatif olabilir)
        self.build(iterable)

    def get_at(self, i):
        return self._d[self._first + i]          # find(first+i) — O(1) beklenen

    def insert_first(self, x):
        self._first -= 1                         # başa ekle: first AZALIR (negatif anahtar)
        self._d[self._first] = x                 # O(1) — hiçbir şey kaymaz

    def insert_last(self, x):
        self._d[self._first + len(self._d)] = x  # anahtar = first + length — O(1)

    def insert_at(self, i, x):
        items = self.to_list()                   # iter ile çıkar — O(n)
        items.insert(i, x)
        self.build(items)                        # yeniden kur — O(n), bütçe içinde

Bu, bir değişmez (invariant) doğurur: anahtarlar her zaman first ile first + length − 1 arasındadır. Demaine, değişmez yazmanın veri yapısının neden doğru olduğunu gösterdiğini vurgular; doğruluk her işlemin değişmezi koruduğunu göstererek tümevarımla ispatlanır. Şekil 9.2 bu değişmezin build → insert_first → insert_last → delete_first boyunca nasıl korunduğunu adım adım izler.

“This is what we call an invariant. Useful to write these things down so you can understand… why is your data structure correct?” — Demaine, 26:23

Karmaşıklık. get/set_at $O(1)$ beklenen, insert/delete_at $O(n)$ beklenen, uç işlemleri $O(1)$ beklenen amortize. (Negatif anahtarlar, çift-katlama “folding” hilesiyle non-negatife eşlenebilir.)

Şekil 9.2: Hash tablosundan Sequence İNDİRGEMESİ + değişmez (invariant) izi — Problem 1. Anahtar ekseni −2..4 (7 hücre); indeks i → anahtar (first + i) eşlemesi. **Satır 1 build** [x,y,z]: anahtarlar 0..2, first=0. **Satır 2 insert_first(w):** w başa eklenir, first −1’e iner ve −1 anahtarı doğar (amber) — hiçbir şey kaymadan O(1). **Satır 3 insert_last(v):** v sona eklenir, anahtar 3 = first+length doğar (amber). **Satır 4 delete_first:** en küçük anahtar (−1) atılır, first 0’a döner. Her satırın altındaki amber köşeli parantez **değişmezi** gösterir: anahtarlar her işlemden sonra TAM OLARAK first..first+n−1 aralığını doldurur — boşluk yok, taşma yok. Bu, veri yapısının doğruluğunu tümevarımla garanti eder (Demaine 26:23).

9.3 Problem 2: Critter Sort

İfade. n nesneyi dört farklı anahtar türüne göre sırala; her biri için en hızlı doğru algoritmayı bul. (a) tam sayılar $-n..n$; (b) 26-harfli, uzunluğu $\le 10 \cdot \log n$ olan string’ler; (c) tam sayılar $0..n^2$; (d) rasyoneller $w/f$, $0 < w < f < n^2$.

Yaklaşım — Her Anahtarı radix sort’un Kabul Ettiği Tamsayıya Dönüştür

Hepsinde radix sort denenir, ama her biri bir dönüşüm ister: radix sort yalnızca $0..u-1$ aralığında tamsayı anahtar alır ve doğrusal kalması için $u \le n^c$ (sabit üslü) olmalıdır. İş, her anahtar türünü bu kalıba sokan doğru dönüşümü bulmaktır — negatifi kaydır, string’i tek sayıya çevir, rasyoneli çapraz çarp veya ölçekle.

Çözüm. Dört şık:

(a) $-n..n$: Negatifleri “folding” ile araya serpmek sırayı bozar (Demaine’in özellikle uyardığı tuzak). Doğru hamle: her anahtara n ekle → $0..2n$. Radix sort, $u = 2n+1$ → doğrusal.
(b) String’ler: Her harfi bir basamağa eşle, sonra tüm string’i base-n tek sayıya çevir (en önemli harf en yüksek basamak; kısa string’leri sonda doldur). String uzunluğu $10 \cdot \log n$ olsa da, base-n radix sort her counting-sort geçişinde $\log n$ harfi birden işler → yalnızca 10 geçiş ($u = n^{10}$) → doğrusal. (Harf-harf base-26 tuple sort olsaydı $\log n$ geçiş gerekir = $n \log n$, yavaş.)

“Tuple sort is the thing… sort by the last thing, then sort by the previous thing… You can also think of this as radix sorting on a number written in base 26.” — Demaine, 33:53

(c) $0..n^2$: Doğrudan radix sort (iki counting-sort geçişi, $u = n^2$) → doğrusal.
(d) Rasyoneller $w/f$: İki yol. (1) Merge sort + çapraz çarpım: $w_i/f_i$ ile $w_j/f_j$’yi kıyaslamak için bölme yerine $w_i \cdot f_j$ ile $w_j \cdot f_i$’yi karşılaştır (paydalar pozitif olduğundan işaret korunur) → $O(n \log n)$. (2) Doğrusal: İki farklı oran en az $1/n^4$ uzaktadır ($|w_i f_j - w_j f_i| \ge 1$, payda $< n^4$); her oranı $n^4$ ile ölçekleyip tabana yuvarla ($w_i \cdot n^4 \mathbin{//} f_i$) → farklı oranlar farklı tamsayılara gider; $w_i < f_i$ olduğundan anahtarlar $\lfloor w_i \cdot n^4 / f_i \rfloor < n^4$, yani $u \le n^4$ (bölmeden önceki ara çarpım $w_i \cdot n^4$ bile $< n^6$ — her iki sınır da sabit-üslü), radix sort → doğrusal.

“Merge sort is always a good answer. It’s not the best answer.” — Demaine, 40:43

Builder Notu — pad değeri harf kodlarından KÜÇÜK olmalı

Şık (b)’de Notion harfleri $0..25$’e eşlemeyi önerir, ama kısa string’leri sonda pad ile doldururken dikkat gerekir: pad = 0 ve 'a' = 0 olsaydı ab ile aba aynı sayıya giderdi (ab + pad = ab + a), leksikografik sıra bozulurdu. Motor bu yüzden harfleri $1..26$ kodlar ve pad = 0 kullanır (taban 27) — pad tüm harflerden küçük kaldığından ab < aba korunur. İfade düzeyinde bağlayıcı olan, leksikografik doğru sıralamadır; kodlama detayı ona hizmet eder.

Karmaşıklık. (a), (b), (c) doğrusal; (d) merge sort ile $O(n \log n)$ veya ölçekleme + radix sort ile doğrusal.

9.4 Problem 3: Küp Toplamı

İfade. n tam sayı (küp kenar uzunlukları) verilir; toplamı h olan iki sayı bul. (a) tam çözüm, doğrusal beklenen zaman. (b) tam çift yoksa h’ye en yakın küçük(-eşit) çifti, doğrusal en-kötü-durum zamanında bul.

Yaklaşım — ‘expected’ → hash, ‘en-kötü-durum’ → radix + two-finger

İki şık iki ipucuyla ayrışır. (a) “beklenen” geçer → randomizasyon → hashing. (b) “en-kötü-durum” geçer → hash yasak (worst-case garantisi yok); ama $h = 600 \cdot n^6$ sabit bir polinomdur → radix sort ipucu, ardından sıralı dizide two-finger ile çift arama.

Çözüm.

(a) Hash ile: Tüm sayıları bir hash tablosuna koy (build $O(n)$ beklenen). Sonra her $s_i$ için find(h − s_i) çağır — n çağrı, her biri $O(1)$ beklenen.

“Subtract h from si and see whether that exists.” — Demaine, 1:00:38

(b) Two-finger ile: Önce h’den büyük tüm sayıları at (asla çözümde olamazlar, sayılar negatif değil). Kalanlar $\le h$ olduğundan radix sort’la sırala (doğrusal). Sonra iki parmak: i = 0 (en küçük), j = son (en büyük). $s_i + s_j > h$ ise $j{-}{-}$ (toplam çok büyük); $\le h$ ise aday listesine kaydet ve $i{+}{+}$ (daha büyük toplam dene). Her parmak diziyi yalnızca bir kez kateder.

“The two-finger algorithm… This is the big idea. You’re doing it all the time in this class.” — Demaine, 1:10:34

Şekil 9.3 bu izi $[21, 5, 13, 8, 2, 34]$ girdisi ve $h = 30$ üzerinde gösterir: 34 > 30 olduğundan elenir, kalanlar sıralı $[2, 5, 8, 13, 21]$ olur. İki parmak 4 adımda ilerler; en iyi aday $(29, 8, 21)$, yani $8 + 21 = 29 \le 30$ — h’yi geçmeyen en büyük çift. Doğruluk bir değişmezle ispatlanır: her adımda, j’nin sağındaki ve i’nin solundaki tüm çiftler ya çok büyüktür ya da görülen en iyi adaydan küçük-eşittir.

Karmaşıklık. (a) doğrusal beklenen (hash); (b) doğrusal en-kötü-durum (radix sort + two-finger). İkili-arama yaklaşımı $O(n \log n)$ verirdi.

Şekil 9.3: İki parmak (two-finger) küp toplamı izi — Problem 3b İMZA figürü. Ham girdi $[21, 5, 13, 8, 2, 34]$, hedef $h = 30$. **34 > h** olduğundan elenir (üzeri çizili); kalanlar radix sort ile sıralı $[2, 5, 8, 13, 21]$ olur. Sol parmak `i` (amber) en küçükten, sağ parmak `j` (koyu amber) en büyükten başlar. **Adım 1** ($2+21=23 \le 30$): aday, i++. **Adım 2** ($5+21=26 \le 30$): aday, i++. **Adım 3** ($8+21=29 \le 30$): EN İYİ aday, i++. **Adım 4** ($13+21=34 > 30$): toplam fazla, j–. Sonuç **best = (29, 8, 21)** — h’yi geçmeyen en büyük çift. Her parmak diziyi yalnız bir kez katettiği için toplam O(n) (ikili-arama O(n log n) yerine).

9.5 Problem 4: Poker — Kayan Pencere ve Frekans Tablosu

İfade. n kartlık bir deste (her kartta 26 harften biri). Bir “el” = i. konumdan başlayıp döngüsel k kart al, sonra sırala. (a) İki indeks i, j için ellerin eşit olup olmadığını sabit zamanda söyleyen bir yapı kur. (b) En sık görülen eli bul.

Yaklaşım — Sıralı el = frekans tablosu; pencereyi O(1)’de kaydır

El sıralandığından, hangi harfin nerede olduğu değil, her harften kaç tane olduğu önemlidir. 26 harf olduğundan her el bir frekans tablosuyla (26 sayı) temsil edilir. Bu tablo, base-$(n+1)$ yazılmış 26 basamaklı bir sayıdır; $u = (n+1)^{26}$ sabit üslü bir polinomdur → radix sort uygulanabilir. Ardışık eller bir kart farkıyla aktığından, tablo her seferinde sıfırdan değil kayan pencere ile $O(1)$’de güncellenir.

Çözüm.

(a) Kayan pencere (sliding window): İlk k kartın frekans tablosunu hesapla (26 sayım). Pencereyi bir kaydır: çıkan kartın sayacını azalt, giren kartın sayacını artır → $O(1)$’de bir sonraki elin tablosu. Her i için tabloyu kopyala (26 sayı, sabit). İki eli karşılaştırmak = 26 sayıyı karşılaştırmak → $O(1)$.

“It’s called a sliding window technique, where you compute it for the first k guys. And then you remove this item and add this item.” — Demaine, 1:24:21

Aşağıdaki özet, motorun (hand_tables) kayan pencere çekirdeğini gösterir: ilk el $O(k)$, her sonraki el çıkan/giren tek kartla $O(1)$.

def hand_tables(deck, k):                        # her i için döngüsel k-kartlık el
    n = len(deck)
    freq = [0] * 26                              # 26 harf → frekans tablosu
    for t in range(k):
        freq[deck[t]] += 1                       # ilk el — O(k)
    tables = [tuple(freq)]
    for i in range(1, n):
        freq[deck[i - 1]] -= 1                   # çıkan kart: −1  (kayan pencere)
        freq[deck[(i + k - 1) % n]] += 1         # giren kart: +1  (döngüsel)
        tables.append(tuple(freq))               # bir sonraki el — O(1)
    return tables

(b) En sık el: Tüm frekans tablolarını (her biri $(n+1)^{26}$ aralığında bir sayı) radix sort ile sırala (doğrusal, sabit üslü polinom). Tek bir taramayla eşit ardışık grupları say → en sık (ve istenirse leksikografik en iyi) eli bul.

Şekil 9.4 bu izi deste $a\,b\,a\,c\,b\,a$ ($n = 6$, $k = 3$, döngüsel) üzerinde gösterir: el0 → el1 geçişinde çıkan a (−1), giren c (+1). Eller arasında el0, el4 ve el5 aynı tabloya ($a{:}2, b{:}1$) sahiptir; bu üç tekrar onu en sık el (3 kez) yapar.

Karmaşıklık. (a) yapı kurma $O(n)$ (kayan pencere), karşılaştırma $O(1)$; (b) radix sort + tarama → $O(n)$.

Şekil 9.4: Kayan pencere (sliding window) + frekans tablosu izi — Problem 4. Deste $a\,b\,a\,c\,b\,a$ ($n=6$, $k=3$, DÖNGÜSEL); soluk şerit sağda döngüsel sarma kopyasıdır. Her el için yalnız a/b/c sütunları gösterilen mini frekans tablosu (26 sayıdan ilgili üçü) sağda yer alır. el0 → el1 geçişinde **çıkan** kart `a` (−1, soluk daire) ve **giren** kart `c` (+1, amber daire) tabloyu O(1)’de günceller — sıfırdan saymaya gerek yok. el0, el4 ve el5 aynı tabloya ($a{:}2, b{:}1$) sahiptir (amber çerçeveli) → **en sık el (3 kez)**. İki eli karşılaştırmak = 26 sayıyı karşılaştırmak = O(1) (sabit alfabe).

9.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ı:

Reduction (indirgeme): bir problemi (sequence), çözümünü zaten bildiğimiz başka bir probleme (set/hash) çevirmek.
Invariant (değişmez): veri yapısının doğruluğunu tümevarımla garanti eden, her işlemde korunan koşul (first..first+length−1).
“Expected → hashing, polynomial → radix sort”: problem ifadesindeki kelime ipuçlarını araca çevirmek.
Radix sort dönüşümleri: negatife n ekle, string’i base-n sayıya çevir, rasyoneli çapraz çarp veya ölçekle-yuvarla.
Two-finger: sıralı dizide, monoton ilerleyen iki parmakla $O(n)$ çift arama (ikili-aramanın $n \log n$’ini geçer).
Sliding window + frequency table: sabit alfabe (26) → her pencereyi $O(1)$’de güncelle; sıralı eli 26 sayıyla temsil et.

9.7 Sonraki

Ders 6 (L6) — İkili Ağaçlar, Bölüm 1

Sırada Ders 6 (L6): İkili Ağaçlar — Bölüm 1 var — Erik Demaine ile, sıralı diziyi (O(n) ekleme) ve hash tablosunu (worst-case O(n)) aşan dengeli bir yapıya — ikili ağaçlara — geçiyoruz: tüm işlemler worst-case O(log n). Bu oturumdaki değişmez (invariant) ve two-finger sezgileri, ağaç işlemlerinin doğruluğunu kurarken doğrudan işine yarayacak.

Builder Notu — reduction = adapter pattern; sliding window = stream processing

İki araç, yazılım mühendisliğinde doğrudan karşılık bulur. Reduction, bir API’yi başka bir API üzerine kurmaktır: tıpkı bir adapter pattern’in mevcut bir arayüzü (set) beklenen bir arayüze (sequence) sarması gibi — yeni mantık değil, mevcut yeteneğin yeniden paketlenmesi. Sliding window ise stream processing’in kalbidir: sonsuz/uzun bir akışta sabit boyutlu pencerenin özetini her adımda sıfırdan değil artımlı (çıkan −, giren +) güncellemek. CNN konvolüsyon kernel’i de sabit bir pencereyi görüntü üzerinde gezdirir — ama paylaşılan yalnızca pencere geometrisidir: konvolüsyon her konumda dot-product’ı sıfırdan hesaplar; bu dersin yük taşıyan özelliği olan O(1) artımlı güncelleme ise stream/windowed-aggregation tarafına özgüdür.

--- title: "Problem Oturumu 3" subtitle: "Ders 4-5'in uygulaması: hashing ve doğrusal sıralamanın dört uygulaması — indirgeme, değişmez, radix dönüşümleri, two-finger ve kayan pencere" --- ::: {.callout-note title="Oturum bilgisi"} - **Demaine'in videosu:** [YouTube — Problem Session 3](https://www.youtube.com/watch?v=g0bXSXuLVb0) (≈60 dk) - **OCW sayfası:** [MIT 6.006 Problem Session 3](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/problem-session-3/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 8 (Problem Oturumu 3) - **Hoca:** Erik Demaine - **Okuma süresi:** ≈26 dk ::: ## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d08} Üçüncü problem oturumu (Erik Demaine), son iki haftanın konularını uygular: **hashing** (Ders 5) ve **doğrusal-zamanlı sıralama** (counting/radix sort, Ders 4-5). Demaine, her problem için izlediği yöntemi açıkça gösterir: kelime problemini biçimsel bir algoritma hedefine çevir, fikirler üret, sonra detayları kontrol et. Bu üç adımlı disiplin, dört problemin de ortak iskeletidir. > *"convert the word problem into a concise formal algorithms thing... come up with ideas... check the details."* — Demaine, 0:46 İki anahtar ipucu tüm oturuma damga vurur (@fig-concept-map): bir problem ifadesinde "**expected**" (beklenen) görürsen rastgelelik söz konusudur ve elindeki tek rastgelelik aracı **hashing**'dir; "**nice polynomial**" (sabit üslü polinom, $u \le n^c$) görürsen **radix sort** dene. Dört problem birer "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir. > *"'expected' is always a good keyword, because it means randomization is involved... the only form of randomization you will use is essentially hashing."* — Demaine, 6:10 ```{mermaid} %%| label: fig-concept-map %%| echo: false %%| fig-cap: "Problem Oturumu 3'ün kavram haritası: kök (PS3) dört probleme dallanır ve iki anahtar ipucu düğümü tüm araç seçimini yönlendirir. Problem 1 hash tablosundan dizi kurar (indirgeme + değişmez); Problem 2 dört farklı anahtarı doğrusal sıralar (radix dönüşümleri); Problem 3 küp toplamını çözer (hash vs two-finger); Problem 4 poker ellerini sayar (kayan pencere + frekans tablosu). Soldaki iki ipucu — 'expected' bekleneni görünce hashing, 'nice polynomial' sabit üslü polinom görünce radix sort — Demaine'in problem ifadesinden araca giden tercüme kuralıdır." flowchart TD R["Problem Oturumu 3 (Ders 4-5 uygulaması)"] --> P1["Problem 1 Hash Tablosundan Dizi"] R --> P2["Problem 2 Critter Sort (4 anahtar)"] R --> P3["Problem 3 Küp Toplamı"] R --> P4["Problem 4 Poker (Sliding Window)"] H1["ipucu: 'expected' (beklenen)"] -.-> HASH["→ hashing kullan"] H2["ipucu: 'nice polynomial' (sabit üslü, u ≤ n^c)"] -.-> RADIX["→ radix sort dene"] HASH -.-> P1 HASH -.-> P3 RADIX -.-> P2 RADIX -.-> P3 RADIX -.-> P4 classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937 classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937 classDef hint fill:#ffffff,stroke:#d97706,stroke-width:1.5px,color:#1f2937 classDef tool fill:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937 class R root class P1,P2,P3,P4 prob class H1,H2 hint class HASH,RADIX tool ``` ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 8 (PS3) motoru (_engine_PS3.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 HashSequence / cube_sum_two_finger_trace / hand_tables + 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: 4 problem fonksiyonu burada self-contained inline'dır → # render dizininden bağımsız (kurs paritesi: PS2 emsali gibi sys.path import YOK). # ============================================================================ 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" # --------------------------------------------------------------------------- # radix_sort — L5 motorundan birebir (PS3 motoru import eder; burada inline). # Anahtarları 0..u−1 tamsayı varsayar; base-tabanlı counting sort geçişleriyle # kararlı (stable) sıralar. Negatif anahtar ValueError (kaydırma zorunluluğu). # --------------------------------------------------------------------------- def _counting_sort(items, key_fn, base, digit): """Tek bir basamağa (digit) göre kararlı counting sort (radix'in iç döngüsü).""" n = len(items) out = [None] * n count = [0] * base for it in items: d = (key_fn(it) // (base ** digit)) % base count[d] += 1 for i in range(1, base): count[i] += count[i - 1] for it in reversed(items): d = (key_fn(it) // (base ** digit)) % base count[d] -= 1 out[count[d]] = it return out def radix_sort(ints, base): """Negatif-olmayan tamsayıları base-tabanlı radix sort ile sıralar (kararlı).""" if not ints: return [] if any(x < 0 for x in ints): raise ValueError("radix_sort: negatif anahtar yok — önce kaydır") base = max(2, base) mx = max(ints) out = list(ints) digit = 0 while base ** digit <= mx: out = _counting_sort(out, lambda x: x, base, digit) digit += 1 return out # --------------------------------------------------------------------------- # _engine_PS3.py — Problem 1: Hash tablosundan dizi (reduction + invariant) # Anahtar fikir: öğenin anahtarı = sıradaki indeksi. `first` değişkeni başa # O(1) ekleme için (negatif anahtara izin); indeks i → anahtar first+i. # INVARIANT (Demaine 26:23): anahtarlar TAM OLARAK {first .. first+length−1}. # --------------------------------------------------------------------------- class HashSequence: """Sequence arayüzünü black-box set'e (dict ile simüle) İNDİRGEME (Demaine 3:17).""" def __init__(self, iterable=()): self._d = {} # black-box set simülasyonu: anahtar -> değer self._first = 0 self.build(iterable) def build(self, X): items = list(X) self._d = {i: x for i, x in enumerate(items)} self._first = 0 def __len__(self): return len(self._d) def get_at(self, i): return self._d[self._first + i] # find(first+i) — O(1) beklenen def set_at(self, i, x): if self._first + i not in self._d: raise IndexError("set_at: indeks aralık dışı") self._d[self._first + i] = x def insert_at(self, i, x): items = self.to_list() # iter ile çıkar — O(n) items.insert(i, x) self.build(items) # build ile yeniden kur — O(n) def delete_at(self, i): items = self.to_list() v = items.pop(i) self.build(items) return v def insert_first(self, x): self._first -= 1 # negatif anahtara izin ver self._d[self._first] = x def insert_last(self, x): self._d[self._first + len(self._d)] = x # anahtar = first + length def delete_first(self): v = self._d.pop(self._first) self._first += 1 return v def delete_last(self): return self._d.pop(self._first + len(self._d) - 1) def invariant_ok(self): """Anahtarlar == {first .. first+length−1} (Demaine'in değişmezi).""" n = len(self._d) return set(self._d.keys()) == set(range(self._first, self._first + n)) def to_list(self): return [self._d[self._first + i] for i in range(len(self._d))] # --------------------------------------------------------------------------- # _engine_PS3.py — Problem 3: Küp toplamı (hash vs two-finger) # (b) two-finger: h'den büyükleri at → radix sort → i=0/j=son iki parmak. # s[i]+s[j] > h → j−−; ≤ h → aday kaydet, i++. Her parmak diziyi BİR kez = O(n). # --------------------------------------------------------------------------- def cube_sum_two_finger_trace(xs, h): """fig-two-finger-cube için adım izi: her adımda (i, j, toplam, karar, best).""" ys = [x for x in xs if 0 <= x <= h] ys = radix_sort(ys, base=max(2, len(ys))) if ys else [] steps = [] i, j = 0, len(ys) - 1 best = None while i < j: t = ys[i] + ys[j] if t > h: steps.append({"i": i, "j": j, "sum": t, "move": "j--", "best": best}) j -= 1 else: if best is None or t > best[0]: best = (t, ys[i], ys[j]) steps.append({"i": i, "j": j, "sum": t, "move": "i++", "best": best}) i += 1 return {"sorted": ys, "steps": steps, "best": best} # --------------------------------------------------------------------------- # _engine_PS3.py — Problem 4: Poker (sliding window + frekans tablosu) # Her i için döngüsel k-kartlık elin frekans tablosu (26 sayı). İlk eli O(k)'de # say; sonra SLIDING WINDOW: çıkan kart −1, giren kart +1 → her sonraki el O(1). # --------------------------------------------------------------------------- def hand_tables(deck, k): """Her i için i. elden başlayan DÖNGÜSEL k-kartlık elin frekans tablosu (26 sayı).""" n = len(deck) if not (1 <= k <= n): raise ValueError("hand_tables: 1 ≤ k ≤ n olmalı") freq = [0] * 26 for t in range(k): freq[deck[t]] += 1 # ilk el — O(k) tables = [tuple(freq)] for i in range(1, n): freq[deck[i - 1]] -= 1 # çıkan: önceki pencerenin ilk kartı freq[deck[(i + k - 1) % n]] += 1 # giren: yeni pencerenin son kartı tables.append(tuple(freq)) return tables ``` ## Problem 1: Hash Tablosundan Dizi {#sec-problem-1-d08} **İfade.** Bir hash tablosu (set: build $O(n)$ beklenen, find $O(1)$ beklenen, insert/delete $O(1)$ beklenen amortize) **black box** olarak verilir. Bununla bir **dizi (sequence)** kur: get/set_at $O(1)$ beklenen, insert/delete_at $O(n)$ beklenen, insert/delete first/last $O(1)$ beklenen amortize. ::: {.callout-tip title="Yaklaşım — İndirgeme (reduction): diziyi set'e çevir"} Bu bir **indirgemedir (reduction)**: sequence problemini, çözümünü zaten bildiğimiz set problemine çeviriyoruz. İlk hamle, zorlukları ayırmaktır. `insert_at`/`delete_at` için $O(n)$ bütçesi var → her seferinde tüm yapıyı **yeniden kurmak** serbest. Asıl ustalık gerektiren kısım, uçlardaki ($O(1)$ amortize) işlemlerdir; orada bir indeks hilesi gerekir. ::: > *"this is what we call a reduction... we're reducing the sequence problem to the set problem."* — Demaine, 3:17 **Çözüm.** Anahtar fikir: her öğeye **anahtar = sıradaki indeksi** ver, böylece set'te saklanabilir. - **get_at(i):** `find(first + i).value`. **set_at(i, x):** `find(first + i)` ile nesneyi bul, value'sunu x yap. $O(1)$ beklenen. - **insert/delete_at(i):** iter ile öğeleri bir diziye çıkar, kaydır, `build` ile yeniden kur. $O(n)$ — bütçe içinde. - **insert/delete_last:** anahtar = `first + length` (veya `first + length − 1`). $O(1)$. - **insert/delete_first:** sorun — indeks 0'a eklemek tüm anahtarları kaydırır ($O(n)$). Çözüm: bir **`first`** değişkeni tut (en küçük anahtar); başa eklerken `first`'ü azalt (negatif anahtarlara izin ver). İndeks i artık `first + i` anahtarına eşlenir. Aşağıdaki özet, motorun (`HashSequence`) çekirdek mantığını gösterir: `first` değişkeni ve `insert_first`'ün `first`'ü azaltışı, `insert_at`'in iter + build ile yeniden kurması. ```python class HashSequence: # diziyi black-box set'e indirger def __init__(self, iterable=()): self._d = {} # set: anahtar -> değer self._first = 0 # en küçük anahtar (negatif olabilir) self.build(iterable) def get_at(self, i): return self._d[self._first + i] # find(first+i) — O(1) beklenen def insert_first(self, x): self._first -= 1 # başa ekle: first AZALIR (negatif anahtar) self._d[self._first] = x # O(1) — hiçbir şey kaymaz def insert_last(self, x): self._d[self._first + len(self._d)] = x # anahtar = first + length — O(1) def insert_at(self, i, x): items = self.to_list() # iter ile çıkar — O(n) items.insert(i, x) self.build(items) # yeniden kur — O(n), bütçe içinde ``` Bu, bir **değişmez (invariant)** doğurur: anahtarlar her zaman `first` ile `first + length − 1` arasındadır. Demaine, değişmez yazmanın veri yapısının *neden doğru* olduğunu gösterdiğini vurgular; doğruluk her işlemin değişmezi koruduğunu göstererek tümevarımla ispatlanır. @fig-hash-invariant bu değişmezin `build → insert_first → insert_last → delete_first` boyunca nasıl korunduğunu adım adım izler. > *"This is what we call an invariant. Useful to write these things down so you can understand... why is your data structure correct?"* — Demaine, 26:23 **Karmaşıklık.** get/set_at $O(1)$ beklenen, insert/delete_at $O(n)$ beklenen, uç işlemleri $O(1)$ beklenen amortize. (Negatif anahtarlar, çift-katlama "folding" hilesiyle non-negatife eşlenebilir.) ```{python} #| label: fig-hash-invariant #| fig-cap: "Hash tablosundan Sequence İNDİRGEMESİ + değişmez (invariant) izi — Problem 1. Anahtar ekseni −2..4 (7 hücre); indeks i → anahtar (first + i) eşlemesi. **Satır 1 build** [x,y,z]: anahtarlar 0..2, first=0. **Satır 2 insert_first(w):** w başa eklenir, first −1'e iner ve −1 anahtarı doğar (amber) — hiçbir şey kaymadan O(1). **Satır 3 insert_last(v):** v sona eklenir, anahtar 3 = first+length doğar (amber). **Satır 4 delete_first:** en küçük anahtar (−1) atılır, first 0'a döner. Her satırın altındaki amber köşeli parantez **değişmezi** gösterir: anahtarlar her işlemden sonra TAM OLARAK first..first+n−1 aralığını doldurur — boşluk yok, taşma yok. Bu, veri yapısının doğruluğunu tümevarımla garanti eder (Demaine 26:23)." #| fig-width: 9.6 #| fig-height: 6.6 # fig-hash-invariant — PS3 Problem 1: hash'ten Sequence indirgemesi + değişmez. # 4 yatay satır (build → insert_first → insert_last → delete_first); her satır bir # HashSequence durumu, motordan GERÇEK okunur (hs._first, len, to_list, invariant_ok). # indeks i → anahtar first+i; değişmez aralığı first..first+n−1 amber bracket. # Setup globalleri: plt, FancyBboxPatch, COL_*, HashSequence. Figüre özgü çizim inline. _KEY_MIN, _KEY_MAX = -2, 4 # anahtar ekseni: 7 hücre (−2..4) _CELL_W, _CELL_H = 0.96, 0.80 _ROW_GAP = 2.05 def _key_x(key): """Anahtar değerini (−2..4) yatay x koordinatına çevirir.""" return (key - _KEY_MIN) * _CELL_W def _inv_row(ax, y, *, first, contents, highlight_key, row_label, op_label): """Bir HashSequence durumunu çizer: anahtar ekseni + dolu/boş hücreler + değişmez parantezi.""" n = len(contents) # indeks i → anahtar first+i; dolu anahtarlar = {first .. first+n−1} key_to_val = {first + i: contents[i] for i in range(n)} for key in range(_KEY_MIN, _KEY_MAX + 1): x = _key_x(key) if key in key_to_val: if key == highlight_key: fc, ec, lw = COL_AMBER_300, COL_AMBER_700, 2.6 # yeni eklenen öğe (amber dolgu) else: fc, ec, lw = COL_BG, COL_PRIMARY, 1.7 # mevcut dolu anahtar (slate) ax.add_patch(FancyBboxPatch( (x, y), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=3)) ax.text(x + _CELL_W * 0.46, y + _CELL_H * 0.5, str(key_to_val[key]), ha="center", va="center", fontsize=12.5, color=COL_TEXT, weight="bold", zorder=5) else: # boş anahtar — soluk kesikli kutu ax.add_patch(FancyBboxPatch( (x, y), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.1, linestyle=(0, (3, 3)), zorder=2)) # anahtar etiketi (hücre altında): 0 referansı amber, diğerleri slate klab_color = COL_AMBER_700 if key == 0 else COL_SLATE_500 ax.text(x + _CELL_W * 0.46, y - 0.22, str(key), ha="center", va="center", fontsize=8.5, color=klab_color, weight="bold" if key == 0 else "normal", zorder=5) # değişmez aralığı first..first+n−1 ALTINDA amber köşeli parantez (bracket) lo_x = _key_x(first) hi_x = _key_x(first + n - 1) + _CELL_W * 0.92 yb = y - 0.46 # parantez üst kenarı (anahtar etiketlerinin altı) drop = 0.16 # köşe yüksekliği ax.plot([lo_x, lo_x, hi_x, hi_x], [yb, yb - drop, yb - drop, yb], color=COL_ACCENT, linewidth=2.4, solid_capstyle="round", zorder=4) ax.text((lo_x + hi_x) * 0.5, yb - drop - 0.20, f"anahtarlar = {{{first} .. {first + n - 1}}}", ha="center", va="top", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5) # sol satır etiketi (işlem adı) ax.text(_key_x(_KEY_MIN) - 0.45, y + _CELL_H * 0.5, row_label, ha="right", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5) # sağ: first=K, n=M etiketi + işlem notası rx = _key_x(_KEY_MAX) + _CELL_W * 0.92 + 0.40 ax.text(rx, y + _CELL_H * 0.62, f"first = {first} · n = {n}", ha="left", va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=5) ax.text(rx, y + _CELL_H * 0.18, op_label, ha="left", va="center", fontsize=8.8, color=COL_SLATE_500, style="italic", zorder=5) # --- senaryoyu motorda GERÇEK çalıştır, her durumdan sonra oku --- hs = HashSequence(["x", "y", "z"]) s0 = (hs._first, len(hs), hs.to_list(), hs.invariant_ok()) hs.insert_first("w") s1 = (hs._first, len(hs), hs.to_list(), hs.invariant_ok()) hs.insert_last("v") s2 = (hs._first, len(hs), hs.to_list(), hs.invariant_ok()) hs.delete_first() s3 = (hs._first, len(hs), hs.to_list(), hs.invariant_ok()) rows = [ # (first, contents, highlight_key, row_label, op_label) (s0[0], s0[2], None, "build", "[x, y, z] kur → anahtarlar 0..2"), (s1[0], s1[2], -1, "insert_first", "w başa → first=−1, anahtar −1 eklendi"), (s2[0], s2[2], 3, "insert_last", "v sona → anahtar 3 = first+n eklendi"), (s3[0], s3[2], None, "delete_first", "ilk (anahtar −1) at → first=0, anahtarlar 0..3"), ] fig, ax = plt.subplots(figsize=(9.6, 6.6)) fig.patch.set_facecolor(COL_WHITE) n_rows = len(rows) y_rows = [(-r) * _ROW_GAP for r in range(n_rows)] for r, (first, contents, hkey, rlabel, olabel) in enumerate(rows): _inv_row(ax, y_rows[r], first=first, contents=contents, highlight_key=hkey, row_label=rlabel, op_label=olabel) # üst başlık: indeks → anahtar eşleme formülü x_mid = (_key_x(_KEY_MIN) + _key_x(_KEY_MAX) + _CELL_W * 0.92) * 0.5 fig.suptitle( "Hash tablosundan Sequence: indeks i → anahtar (first + i)", color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975) ax.text(x_mid, y_rows[0] + _CELL_H + 0.62, "set'teki anahtar = sıradaki konum; insert_first negatif anahtara izin verir " "(first−−)", ha="center", va="center", fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=5) # alt not: değişmez tanımı (Demaine atfı) y_note = y_rows[-1] - 1.18 ax.text(x_mid, y_note, "değişmez: anahtarlar TAM OLARAK first .. first+n−1 " "(her işlemden sonra korunur · Demaine 26:23)", ha="center", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5) ax.set_xlim(_key_x(_KEY_MIN) - 3.0, _key_x(_KEY_MAX) + _CELL_W * 0.92 + 5.2) ax.set_ylim(y_note - 0.5, y_rows[0] + _CELL_H + 1.05) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## Problem 2: Critter Sort {#sec-problem-2-d08} **İfade.** n nesneyi dört farklı anahtar türüne göre sırala; her biri için en hızlı doğru algoritmayı bul. (a) tam sayılar $-n..n$; (b) 26-harfli, uzunluğu $\le 10 \cdot \log n$ olan string'ler; (c) tam sayılar $0..n^2$; (d) rasyoneller $w/f$, $0 < w < f < n^2$. ::: {.callout-tip title="Yaklaşım — Her Anahtarı radix sort'un Kabul Ettiği Tamsayıya Dönüştür"} Hepsinde radix sort denenir, ama her biri bir **dönüşüm** ister: radix sort yalnızca $0..u-1$ aralığında tamsayı anahtar alır ve doğrusal kalması için $u \le n^c$ (sabit üslü) olmalıdır. İş, her anahtar türünü bu kalıba sokan doğru dönüşümü bulmaktır — negatifi kaydır, string'i tek sayıya çevir, rasyoneli çapraz çarp veya ölçekle. ::: **Çözüm.** Dört şık: - **(a) $-n..n$:** Negatifleri "folding" ile araya serpmek sırayı bozar (Demaine'in özellikle uyardığı tuzak). Doğru hamle: **her anahtara n ekle** → $0..2n$. Radix sort, $u = 2n+1$ → **doğrusal**. - **(b) String'ler:** Her harfi bir basamağa eşle, sonra tüm string'i **base-n tek sayıya** çevir (en önemli harf en yüksek basamak; kısa string'leri sonda doldur). String uzunluğu $10 \cdot \log n$ olsa da, base-n radix sort her counting-sort geçişinde $\log n$ harfi birden işler → yalnızca 10 geçiş ($u = n^{10}$) → **doğrusal**. (Harf-harf base-26 tuple sort olsaydı $\log n$ geçiş gerekir = $n \log n$, yavaş.) > *"Tuple sort is the thing... sort by the last thing, then sort by the previous thing... You can also think of this as radix sorting on a number written in base 26."* — Demaine, 33:53 - **(c) $0..n^2$:** Doğrudan radix sort (iki counting-sort geçişi, $u = n^2$) → **doğrusal**. - **(d) Rasyoneller $w/f$:** İki yol. (1) **Merge sort + çapraz çarpım:** $w_i/f_i$ ile $w_j/f_j$'yi kıyaslamak için bölme yerine $w_i \cdot f_j$ ile $w_j \cdot f_i$'yi karşılaştır (paydalar pozitif olduğundan işaret korunur) → $O(n \log n)$. (2) **Doğrusal:** İki farklı oran en az $1/n^4$ uzaktadır ($|w_i f_j - w_j f_i| \ge 1$, payda $< n^4$); her oranı $n^4$ ile ölçekleyip tabana yuvarla ($w_i \cdot n^4 \mathbin{//} f_i$) → farklı oranlar farklı tamsayılara gider; $w_i < f_i$ olduğundan anahtarlar $\lfloor w_i \cdot n^4 / f_i \rfloor < n^4$, yani $u \le n^4$ (bölmeden önceki ara çarpım $w_i \cdot n^4$ bile $< n^6$ — her iki sınır da sabit-üslü), radix sort → **doğrusal**. > *"Merge sort is always a good answer. It's not the best answer."* — Demaine, 40:43 ::: {.callout-tip title="Builder Notu — pad değeri harf kodlarından KÜÇÜK olmalı"} Şık (b)'de Notion harfleri $0..25$'e eşlemeyi önerir, ama kısa string'leri sonda **pad** ile doldururken dikkat gerekir: pad = 0 ve `'a'` = 0 olsaydı `ab` ile `aba` aynı sayıya giderdi (`ab` + pad = `ab` + `a`), leksikografik sıra bozulurdu. Motor bu yüzden harfleri **$1..26$** kodlar ve **pad = 0** kullanır (taban 27) — pad tüm harflerden küçük kaldığından `ab` < `aba` korunur. İfade düzeyinde bağlayıcı olan, leksikografik doğru sıralamadır; kodlama detayı ona hizmet eder. ::: **Karmaşıklık.** (a), (b), (c) doğrusal; (d) merge sort ile $O(n \log n)$ veya ölçekleme + radix sort ile **doğrusal**. ## Problem 3: Küp Toplamı {#sec-problem-3-d08} **İfade.** n tam sayı (küp kenar uzunlukları) verilir; toplamı h olan iki sayı bul. (a) tam çözüm, **doğrusal beklenen** zaman. (b) tam çift yoksa h'ye **en yakın küçük(-eşit)** çifti, **doğrusal en-kötü-durum** zamanında bul. ::: {.callout-tip title="Yaklaşım — 'expected' → hash, 'en-kötü-durum' → radix + two-finger"} İki şık iki ipucuyla ayrışır. (a) "**beklenen**" geçer → randomizasyon → **hashing**. (b) "**en-kötü-durum**" geçer → hash yasak (worst-case garantisi yok); ama $h = 600 \cdot n^6$ sabit bir polinomdur → **radix sort** ipucu, ardından sıralı dizide **two-finger** ile çift arama. ::: **Çözüm.** **(a) Hash ile:** Tüm sayıları bir hash tablosuna koy (build $O(n)$ beklenen). Sonra her $s_i$ için `find(h − s_i)` çağır — n çağrı, her biri $O(1)$ beklenen. > *"Subtract h from si and see whether that exists."* — Demaine, 1:00:38 **(b) Two-finger ile:** Önce h'den büyük tüm sayıları **at** (asla çözümde olamazlar, sayılar negatif değil). Kalanlar $\le h$ olduğundan radix sort'la **sırala** (doğrusal). Sonra **iki parmak**: i = 0 (en küçük), j = son (en büyük). $s_i + s_j > h$ ise $j{-}{-}$ (toplam çok büyük); $\le h$ ise aday listesine kaydet ve $i{+}{+}$ (daha büyük toplam dene). Her parmak diziyi yalnızca bir kez kateder. > *"The two-finger algorithm... This is the big idea. You're doing it all the time in this class."* — Demaine, 1:10:34 @fig-two-finger-cube bu izi $[21, 5, 13, 8, 2, 34]$ girdisi ve $h = 30$ üzerinde gösterir: 34 > 30 olduğundan **elenir**, kalanlar sıralı $[2, 5, 8, 13, 21]$ olur. İki parmak **4 adımda** ilerler; en iyi aday $(29, 8, 21)$, yani $8 + 21 = 29 \le 30$ — h'yi geçmeyen en büyük çift. Doğruluk bir **değişmezle** ispatlanır: her adımda, j'nin sağındaki ve i'nin solundaki tüm çiftler ya çok büyüktür ya da görülen en iyi adaydan küçük-eşittir. **Karmaşıklık.** (a) doğrusal beklenen (hash); (b) doğrusal en-kötü-durum (radix sort + two-finger). İkili-arama yaklaşımı $O(n \log n)$ verirdi. ```{python} #| label: fig-two-finger-cube #| fig-cap: "İki parmak (two-finger) küp toplamı izi — Problem 3b İMZA figürü. Ham girdi $[21, 5, 13, 8, 2, 34]$, hedef $h = 30$. **34 > h** olduğundan elenir (üzeri çizili); kalanlar radix sort ile sıralı $[2, 5, 8, 13, 21]$ olur. Sol parmak `i` (amber) en küçükten, sağ parmak `j` (koyu amber) en büyükten başlar. **Adım 1** ($2+21=23 \\le 30$): aday, i++. **Adım 2** ($5+21=26 \\le 30$): aday, i++. **Adım 3** ($8+21=29 \\le 30$): EN İYİ aday, i++. **Adım 4** ($13+21=34 > 30$): toplam fazla, j--. Sonuç **best = (29, 8, 21)** — h'yi geçmeyen en büyük çift. Her parmak diziyi yalnız bir kez katettiği için toplam O(n) (ikili-arama O(n log n) yerine)." #| fig-width: 9.6 #| fig-height: 6.6 # fig-two-finger-cube — PS3 Problem 3b (Küp Toplamı) İMZA: two-finger O(n) izi. # cube_sum_two_finger_trace (gizli setup'taki _engine_PS3) + Slate+Amber (COL_*). # DETERMİNİSTİK girdi: [21,5,13,8,2,34], h=30 → 34 elenir, sıralı [2,5,8,13,21], # 4 adım, best=(29,8,21). Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, # COL_*, cube_sum_two_finger_trace. Figüre özgü çizim yardımcıları burada inline. _CELL_W, _CELL_H = 0.94, 0.74 _ROW_GAP = 1.55 def _sorted_row(ax, y, values, x0, *, i_cur, j_cur, counted_best, row_label, sum_text, decision_text, is_best): """Bir two-finger adımını çizer: sıralı dizi hücreleri + i/j parmak okları + sağda toplam & karar metni. En iyi aday satırı amber çerçeveyle işaretlenir.""" n = len(values) xs = [x0 + k * _CELL_W for k in range(n)] centers = [] for k, v in enumerate(values): x = xs[k] if k == i_cur: fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6 # sol parmak (i) elif k == j_cur: fc, ec, lw = COL_AMBER_300, COL_AMBER_700, 2.4 # sağ parmak (j) else: fc, ec, lw = COL_BG, COL_SLATE_400, 1.3 # pasif hücre 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(v), ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(cx, y - 0.18, str(k), ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=4) # i parmağı (sol, amber) — aşağı bakan ok, hücrenin üstünde cxi = centers[i_cur][0] ax.add_patch(FancyArrowPatch( (cxi, y + _CELL_H + 0.42), (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, color=COL_ACCENT, weight="bold", zorder=5) # j parmağı (sağ, koyu amber) — aşağı bakan ok cxj = centers[j_cur][0] ax.add_patch(FancyArrowPatch( (cxj, y + _CELL_H + 0.42), (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, color=COL_AMBER_600, weight="bold", zorder=5) # sol satır etiketi ax.text(x0 - 0.40, y + _CELL_H * 0.5, row_label, ha="right", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) # sağ: toplam + karar metni txt_x = xs[-1] + _CELL_W + 0.35 karar_col = COL_AMBER_700 if "aday" in decision_text else COL_SLATE_500 ax.text(txt_x, y + _CELL_H * 0.5, f"{sum_text} {decision_text}", ha="left", va="center", fontsize=9.5, color=karar_col, weight="bold", zorder=5) # en iyi aday satırı: amber çerçeve + yıldız if is_best: left = x0 - 0.20 width = (xs[-1] + _CELL_W * 0.92) - left + 0.30 ax.add_patch(FancyBboxPatch( (left, y - 0.28), width, _CELL_H + 0.94, boxstyle="round,pad=0.02,rounding_size=0.08", fc="none", ec=COL_ACCENT, linewidth=2.4, zorder=1, linestyle=(0, (5, 2)))) ax.text(xs[-1] + _CELL_W * 0.92 + 0.10, y + _CELL_H + 0.30, "★ EN İYİ", ha="left", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=6) return centers raw = [21, 5, 13, 8, 2, 34] h = 30 tr = cube_sum_two_finger_trace(raw, h) srt = tr["sorted"] # [2, 5, 8, 13, 21] steps = tr["steps"] # 4 adım best = tr["best"] # (29, 8, 21) fig, ax = plt.subplots(figsize=(9.6, 6.6)) fig.patch.set_facecolor(COL_WHITE) x0 = 0.0 n = len(srt) xs = [x0 + k * _CELL_W for k in range(n)] # -------------------------------------------------------------------- # En üst: ham girdi şeridi (34 hücresi soluk + üzeri çizgi = filtrelendi) # -------------------------------------------------------------------- y_raw = 2.6 raw_xs = [x0 + k * _CELL_W for k in range(len(raw))] for k, v in enumerate(raw): x = raw_xs[k] filtered = v > h fc = COL_WHITE if filtered else COL_BG ec = COL_SLATE_400 if filtered else COL_PRIMARY ax.add_patch(FancyBboxPatch( (x, y_raw), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=1.3, zorder=2)) cx, cy = x + _CELL_W * 0.46, y_raw + _CELL_H * 0.5 tcol = COL_SLATE_400 if filtered else COL_TEXT ax.text(cx, cy, str(v), ha="center", va="center", fontsize=11.5, color=tcol, weight="bold", zorder=4) if filtered: # üzeri çizgi (h'den büyük → elendi) ax.plot([x + _CELL_W * 0.04, x + _CELL_W * 0.88], [y_raw + _CELL_H * 0.5, y_raw + _CELL_H * 0.5], color=COL_AMBER_700, linewidth=2.0, zorder=5) ax.text(cx, y_raw + _CELL_H + 0.20, f"> h={h}", ha="center", va="bottom", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5) ax.text(x0 - 0.40, y_raw + _CELL_H * 0.5, "ham girdi", ha="right", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) ax.text(raw_xs[-1] + _CELL_W + 0.35, y_raw + _CELL_H * 0.5, f"h={h} üzeri elenir", ha="left", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=5) # radix sort oku (ham → sıralı) y_sorted_top = 1.55 arr_x = raw_xs[len(raw) // 2] ax.add_patch(FancyArrowPatch( (arr_x, y_raw - 0.06), (arr_x, y_sorted_top + _CELL_H + 0.06), arrowstyle="-|>", mutation_scale=16, color=COL_AMBER_600, linewidth=2.2, zorder=5)) ax.text(arr_x + 0.18, (y_raw + y_sorted_top + _CELL_H) * 0.5 + 0.05, "radix sort → O(n)", ha="left", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5) # sıralı şerit for k, v in enumerate(srt): x = xs[k] ax.add_patch(FancyBboxPatch( (x, y_sorted_top), _CELL_W * 0.92, _CELL_H, boxstyle="square,pad=0.0", fc=COL_BG, ec=COL_PRIMARY, linewidth=1.5, zorder=2)) ax.text(x + _CELL_W * 0.46, y_sorted_top + _CELL_H * 0.5, str(v), ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(x + _CELL_W * 0.46, y_sorted_top - 0.18, str(k), ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=4) ax.text(x0 - 0.40, y_sorted_top + _CELL_H * 0.5, "sıralı", ha="right", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) # -------------------------------------------------------------------- # 4 adım satırı # -------------------------------------------------------------------- sum_strs = [] dec_strs = [] for st in steps: a, b = srt[st["i"]], srt[st["j"]] sum_strs.append(f"{a} + {b} = {st['sum']}") if st["move"] == "i++": dec_strs.append(f"≤ {h} → aday, i++") else: dec_strs.append(f"> {h} → i fazla, j--") # en iyi adım: best toplamını üreten i++ adımı (adım 3, sum=29) best_sum = best[0] best_step_idx = None for r, st in enumerate(steps): if st["move"] == "i++" and st["sum"] == best_sum: best_step_idx = r # son eşleşen = best'in kaydedildiği adım y_first = 0.0 y_rows = [y_first - r * _ROW_GAP for r in range(len(steps))] for r, st in enumerate(steps): _sorted_row(ax, y_rows[r], srt, x0, i_cur=st["i"], j_cur=st["j"], counted_best=(r == best_step_idx), row_label=f"Adım {r + 1}", sum_text=sum_strs[r], decision_text=dec_strs[r], is_best=(r == best_step_idx)) # -------------------------------------------------------------------- # En altta best sonuç kutusu # -------------------------------------------------------------------- y_best = y_rows[-1] - _ROW_GAP - 0.05 box_left = x0 - 0.20 box_w = (xs[-1] + _CELL_W * 0.92) - box_left + 0.30 ax.add_patch(FancyBboxPatch( (box_left, y_best), box_w, _CELL_H + 0.10, boxstyle="round,pad=0.02,rounding_size=0.10", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2)) ax.text(box_left + 0.25, y_best + (_CELL_H + 0.10) * 0.5, f"best = (toplam={best[0]}, küçük={best[1]}, büyük={best[2]})", ha="left", va="center", fontsize=11, color=COL_AMBER_700, weight="bold", zorder=4) ax.text(box_left + box_w * 0.5, y_best - 0.22, "h'ye en yakın-küçük(-eşit) çift", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=4) # -------------------------------------------------------------------- # başlık + alt-başlık # -------------------------------------------------------------------- fig.suptitle( "İki parmak (two-finger): her parmak diziyi BİR kez kateder → O(n)", color=COL_TEXT, fontsize=13, weight="bold", y=0.975) ax.text((xs[0] + xs[-1]) * 0.5, y_raw + _CELL_H + 0.60, "i sola→sağa kayarken j yalnız sola kayar · küp toplamı = h " "(toplamı h'yi geçmeyen en büyük çift)", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=5) ax.set_xlim(x0 - 2.4, xs[-1] + _CELL_W + 4.2) ax.set_ylim(y_best - 0.65, y_raw + _CELL_H + 1.0) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## Problem 4: Poker — Kayan Pencere ve Frekans Tablosu {#sec-problem-4-d08} **İfade.** n kartlık bir deste (her kartta 26 harften biri). Bir "el" = i. konumdan başlayıp **döngüsel** k kart al, sonra **sırala**. (a) İki indeks i, j için ellerin eşit olup olmadığını **sabit zamanda** söyleyen bir yapı kur. (b) En sık görülen eli bul. ::: {.callout-tip title="Yaklaşım — Sıralı el = frekans tablosu; pencereyi O(1)'de kaydır"} El sıralandığından, hangi harfin nerede olduğu değil, her harften **kaç tane** olduğu önemlidir. 26 harf olduğundan her el bir **frekans tablosuyla** (26 sayı) temsil edilir. Bu tablo, base-$(n+1)$ yazılmış 26 basamaklı bir sayıdır; $u = (n+1)^{26}$ sabit üslü bir polinomdur → radix sort uygulanabilir. Ardışık eller bir kart farkıyla aktığından, tablo her seferinde sıfırdan değil **kayan pencere** ile $O(1)$'de güncellenir. ::: **Çözüm.** **(a) Kayan pencere (sliding window):** İlk k kartın frekans tablosunu hesapla (26 sayım). Pencereyi bir kaydır: çıkan kartın sayacını azalt, giren kartın sayacını artır → $O(1)$'de bir sonraki elin tablosu. Her i için tabloyu kopyala (26 sayı, sabit). İki eli karşılaştırmak = 26 sayıyı karşılaştırmak → **$O(1)$**. > *"It's called a sliding window technique, where you compute it for the first k guys. And then you remove this item and add this item."* — Demaine, 1:24:21 Aşağıdaki özet, motorun (`hand_tables`) kayan pencere çekirdeğini gösterir: ilk el $O(k)$, her sonraki el çıkan/giren tek kartla $O(1)$. ```python def hand_tables(deck, k): # her i için döngüsel k-kartlık el n = len(deck) freq = [0] * 26 # 26 harf → frekans tablosu for t in range(k): freq[deck[t]] += 1 # ilk el — O(k) tables = [tuple(freq)] for i in range(1, n): freq[deck[i - 1]] -= 1 # çıkan kart: −1 (kayan pencere) freq[deck[(i + k - 1) % n]] += 1 # giren kart: +1 (döngüsel) tables.append(tuple(freq)) # bir sonraki el — O(1) return tables ``` **(b) En sık el:** Tüm frekans tablolarını (her biri $(n+1)^{26}$ aralığında bir sayı) **radix sort** ile sırala (doğrusal, sabit üslü polinom). Tek bir taramayla eşit ardışık grupları say → en sık (ve istenirse leksikografik en iyi) eli bul. @fig-sliding-window bu izi deste $a\,b\,a\,c\,b\,a$ ($n = 6$, $k = 3$, döngüsel) üzerinde gösterir: el0 → el1 geçişinde çıkan `a` (−1), giren `c` (+1). Eller arasında el0, el4 ve el5 aynı tabloya ($a{:}2, b{:}1$) sahiptir; bu üç tekrar onu **en sık el** (3 kez) yapar. **Karmaşıklık.** (a) yapı kurma $O(n)$ (kayan pencere), karşılaştırma $O(1)$; (b) radix sort + tarama → **$O(n)$**. ```{python} #| label: fig-sliding-window #| fig-cap: "Kayan pencere (sliding window) + frekans tablosu izi — Problem 4. Deste $a\\,b\\,a\\,c\\,b\\,a$ ($n=6$, $k=3$, DÖNGÜSEL); soluk şerit sağda döngüsel sarma kopyasıdır. Her el için yalnız a/b/c sütunları gösterilen mini frekans tablosu (26 sayıdan ilgili üçü) sağda yer alır. el0 → el1 geçişinde **çıkan** kart `a` (−1, soluk daire) ve **giren** kart `c` (+1, amber daire) tabloyu O(1)'de günceller — sıfırdan saymaya gerek yok. el0, el4 ve el5 aynı tabloya ($a{:}2, b{:}1$) sahiptir (amber çerçeveli) → **en sık el (3 kez)**. İki eli karşılaştırmak = 26 sayıyı karşılaştırmak = O(1) (sabit alfabe)." #| fig-width: 10.0 #| fig-height: 6.8 # fig-sliding-window — PS3 Problem 4 (Poker): döngüsel kayan pencere + frekans tablosu. # hand_tables (gizli setup'taki _engine_PS3) + Slate+Amber (COL_*). DETERMİNİSTİK # girdi: deck=[0,1,0,2,1,0] (a,b,c), k=3 → el0=el4=el5=(a2,b1) en sık (3 kez). # Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, COL_*, hand_tables. # Figüre özgü çizim yardımcıları burada inline. _LETTERS = ["a", "b", "c"] # kart kodu 0/1/2 → harf _CELL = 0.86 # deste şeridi hücre genişliği/yüksekliği def _deck_strip(ax, deck, x0, y, *, faded=False): """Deste şeridini (n hücre, harfler) çizer. faded=True → döngüsel sarma kopyası (soluk).""" n = len(deck) centers = [] for k, code in enumerate(deck): x = x0 + k * _CELL if faded: fc, ec, lw, tc = COL_WHITE, COL_SLATE_400, 1.1, COL_SLATE_400 else: fc, ec, lw, tc = COL_BG, COL_PRIMARY, 1.6, COL_TEXT ax.add_patch(FancyBboxPatch( (x, y), _CELL * 0.94, _CELL * 0.94, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2)) cx, cy = x + _CELL * 0.47, y + _CELL * 0.47 centers.append((cx, cy)) ax.text(cx, cy, _LETTERS[code], ha="center", va="center", fontsize=13, color=tc, weight="bold", zorder=4) # global pozisyon etiketi (sarma kopyada n..2n-1) pos = k if not faded else k + n ax.text(cx, y - 0.20, str(pos), ha="center", va="center", fontsize=7.5, color=COL_SLATE_400 if faded else COL_SLATE_500, zorder=4) return centers def _freq_table(ax, x_left, y_top, table, *, hot=False): """Mini frekans tablosu: yalnız a/b/c sütunları (26 sayıdan ilgili 3'ü).""" cw, ch = 0.40, 0.40 counts = [table[i] for i in range(3)] # a,b,c sayıları (motordan dilimle) ec = COL_ACCENT if hot else COL_SLATE_400 lw = 2.4 if hot else 1.2 bg = COL_AMBER_100 if hot else COL_WHITE # dış çerçeve (3 sütun × 2 satır) ax.add_patch(FancyBboxPatch( (x_left, y_top - 2 * ch), 3 * cw, 2 * ch, boxstyle="square,pad=0.0", fc=bg, ec=ec, linewidth=lw, zorder=2)) for c in range(3): x = x_left + c * cw # iç dikey ayraç if c > 0: ax.plot([x, x], [y_top - 2 * ch, y_top], color=ec, linewidth=0.8, zorder=3) # harf başlığı ax.text(x + cw * 0.5, y_top - ch * 0.5, _LETTERS[c], ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=4) # sayım ax.text(x + cw * 0.5, y_top - ch * 1.5, str(counts[c]), ha="center", va="center", fontsize=11, color=COL_AMBER_700 if hot else COL_TEXT, weight="bold", zorder=4) # yatay ayraç (başlık | sayım) ax.plot([x_left, x_left + 3 * cw], [y_top - ch, y_top - ch], color=ec, linewidth=0.8, zorder=3) return 3 * cw deck = [0, 1, 0, 2, 1, 0] # a b a c b a k = 3 n = len(deck) tables = hand_tables(deck, k) # MOTORDAN — 6 adet 26'lık tuple most = {0, 4, 5} # amber çerçeveli eller fig, ax = plt.subplots(figsize=(10.0, 6.8)) fig.patch.set_facecolor(COL_WHITE) # ---- Üst: deste şeridi iki kez (döngüsel sarmayı göstermek için 2. kopya soluk) ---- y_deck = 0.0 c_main = _deck_strip(ax, deck, 0.0, y_deck, faded=False) c_wrap = _deck_strip(ax, deck, n * _CELL, y_deck, faded=True) centers = c_main + c_wrap # global indeks: 0..n-1 gerçek, n..2n-1 sarma kopya ax.text(-0.55, y_deck + _CELL * 0.47, "deste", ha="right", va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=5) ax.text(n * _CELL + (n * _CELL) * 0.5, y_deck + _CELL + 0.30, "döngüsel sarma kopyası (soluk)", ha="center", va="center", fontsize=8.5, color=COL_SLATE_400, style="italic", zorder=5) # ---- 6 pencere çerçevesi + altta mini frekans tablosu ---- win_gap = 1.92 table_cw = 0.40 row_y0 = -1.55 # ilk pencere satırının üst referansı for i in range(n): y_row = row_y0 - i * win_gap hot = i in most # pencerenin kapsadığı global hücre indeksleri (döngüsel: sarma kopya üstünden) cells = [i + d for d in range(k)] # i..i+k-1, sarma için n..2n-1 kopyayı kullan xs = [centers[c][0] for c in cells] win_lo = min(xs) - _CELL * 0.5 win_hi = max(xs) + _CELL * 0.5 # pencere çerçevesi (deste şeridi üzerinde değil; satır başında özet çerçeve) fr_ec = COL_ACCENT if hot else COL_PRIMARY fr_lw = 2.4 if hot else 1.4 # bağlantı: pencerenin desteki konumunu gösteren ince dikey kılavuzlar for c in cells: cx, _ = centers[c] ax.plot([cx, cx], [y_deck - 0.20, y_row + _CELL * 0.5 + 0.55], color=COL_AMBER_300 if hot else COL_SLATE_400, linewidth=0.7, linestyle=(0, (2, 3)), zorder=0, alpha=0.7) # el etiketi + pencere kutusu (kapsadığı 3 hücreyi yeniden çiz, vurgulu) ax.text(-0.55, y_row + _CELL * 0.5, f"el{i}", ha="right", va="center", fontsize=9.5, color=fr_ec, weight="bold", zorder=5) for slot, c in enumerate(cells): code = deck[c % n] cx = win_lo + 0.5 * _CELL + slot * _CELL ax.add_patch(FancyBboxPatch( (cx - _CELL * 0.45, y_row), _CELL * 0.90, _CELL * 0.90, boxstyle="square,pad=0.0", fc=COL_AMBER_100 if hot else COL_BG, ec=fr_ec, linewidth=fr_lw, zorder=2)) ax.text(cx, y_row + _CELL * 0.45, _LETTERS[code], ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(cx, y_row - 0.16, str((i + slot) % n if (i + slot) >= n else i + slot), ha="center", va="center", fontsize=7, color=COL_SLATE_400, zorder=4) # mini frekans tablosu (sağ tarafta) tbl_x = win_hi + 0.55 _freq_table(ax, tbl_x, y_row + _CELL * 0.95, tables[i], hot=hot) if hot: ax.text(tbl_x + 3 * table_cw + 0.28, y_row + _CELL * 0.45, "= en sık el", ha="left", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5) # ---- Pencere geçişi el0 → el1: çıkan kart (−1, soluk) + giren kart (+1, amber) ---- # el0 = kart 0,1,2 ; el1 = kart 1,2,3 → çıkan = kart 0 (a), giren = kart 3 (c) y0 = row_y0 y1 = row_y0 - win_gap # çıkan kart: kart 0 (deste hücre), soluk daire + "−1" cx_out, cy_out = centers[0] ax.add_patch(plt.Circle((cx_out, cy_out), _CELL * 0.46, fill=False, ec=COL_SLATE_500, linewidth=2.0, linestyle=(0, (2, 2)), zorder=6)) ax.add_patch(FancyArrowPatch( (cx_out, cy_out - _CELL * 0.5), (cx_out - 0.10, y1 + _CELL + 0.20), arrowstyle="-|>", mutation_scale=13, color=COL_SLATE_500, linewidth=1.8, zorder=6, connectionstyle="arc3,rad=-0.25")) ax.text(cx_out - 0.55, (cy_out + y1) * 0.5, "çıkan a : −1", ha="right", va="center", fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=7) # giren kart: kart 3 (deste hücre), amber daire + "+1" cx_in, cy_in = centers[3] ax.add_patch(plt.Circle((cx_in, cy_in), _CELL * 0.46, fill=False, ec=COL_ACCENT, linewidth=2.4, zorder=6)) ax.add_patch(FancyArrowPatch( (cx_in, cy_in - _CELL * 0.5), (cx_in + 0.10, y1 + _CELL + 0.20), arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT, linewidth=2.2, zorder=6, connectionstyle="arc3,rad=0.25")) ax.text(cx_in + 0.58, (cy_in + y1) * 0.5, "giren c : +1", ha="left", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=7) # el0 → el1 geçiş etiketi ax.text((n * _CELL) + 2.05, (y0 + y1) * 0.5 + _CELL * 0.2, "el0 → el1:\nO(1) güncelleme", ha="left", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=7) # ---- Başlık + alt-başlık ---- fig.suptitle( "Kayan pencere (sliding window): her el bir öncekinden O(1) — çıkan −1, giren +1", color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975) ax.text((n * _CELL), y_deck + _CELL + 0.78, "deste a b a c b a (n=6, k=3, DÖNGÜSEL) · el0 = el4 = el5 → en sık el (3 kez)", ha="center", va="center", fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=5) # ---- Alt not ---- y_bot = row_y0 - (n - 1) * win_gap - 1.05 ax.text((n * _CELL), y_bot, "iki eli karşılaştırmak = 26 sayıyı karşılaştırmak = O(1) (sabit alfabe)", ha="center", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5) ax.set_xlim(-2.4, 2 * n * _CELL + 3.6) ax.set_ylim(y_bot - 0.5, y_deck + _CELL + 1.15) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## Ne Öğrendik? {#sec-ne-ogrendik-d08} ::: {.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. **Reduction (indirgeme):** bir problemi (sequence), çözümünü zaten bildiğimiz başka bir probleme (set/hash) çevirmek. 2. **Invariant (değişmez):** veri yapısının doğruluğunu tümevarımla garanti eden, her işlemde korunan koşul (`first..first+length−1`). 3. **"Expected → hashing, polynomial → radix sort":** problem ifadesindeki kelime ipuçlarını araca çevirmek. 4. **Radix sort dönüşümleri:** negatife n ekle, string'i base-n sayıya çevir, rasyoneli çapraz çarp veya ölçekle-yuvarla. 5. **Two-finger:** sıralı dizide, monoton ilerleyen iki parmakla $O(n)$ çift arama (ikili-aramanın $n \log n$'ini geçer). 6. **Sliding window + frequency table:** sabit alfabe (26) → her pencereyi $O(1)$'de güncelle; sıralı eli 26 sayıyla temsil et. ::: ## Sonraki {#sec-sonraki-d08} ::: {.callout-warning title="Ders 6 (L6) — İkili Ağaçlar, Bölüm 1"} Sırada **Ders 6 (L6): İkili Ağaçlar — Bölüm 1** var — Erik Demaine ile, sıralı diziyi (O(n) ekleme) ve hash tablosunu (worst-case O(n)) aşan dengeli bir yapıya — **ikili ağaçlara** — geçiyoruz: tüm işlemler worst-case O(log n). Bu oturumdaki **değişmez (invariant)** ve **two-finger** sezgileri, ağaç işlemlerinin doğruluğunu kurarken doğrudan işine yarayacak. ::: ::: {.callout-tip title="Builder Notu — reduction = adapter pattern; sliding window = stream processing"} İki araç, yazılım mühendisliğinde doğrudan karşılık bulur. **Reduction**, bir API'yi başka bir API üzerine kurmaktır: tıpkı bir **adapter pattern**'in mevcut bir arayüzü (set) beklenen bir arayüze (sequence) sarması gibi — yeni mantık değil, mevcut yeteneğin yeniden paketlenmesi. **Sliding window** ise **stream processing**'in kalbidir: sonsuz/uzun bir akışta sabit boyutlu pencerenin özetini her adımda sıfırdan değil artımlı (çıkan −, giren +) güncellemek. CNN konvolüsyon kernel'i de sabit bir pencereyi görüntü üzerinde gezdirir — ama paylaşılan yalnızca pencere *geometrisidir*: konvolüsyon her konumda dot-product'ı **sıfırdan** hesaplar; bu dersin yük taşıyan özelliği olan **O(1) artımlı güncelleme** ise stream/windowed-aggregation tarafına özgüdür. :::