4 Problem Oturumu 1

Ders 1-2’nin uygulaması: asimptotik sıralama, sequence black box, çift uçlu dinamik dizi ve yerinde bağlı liste ters çevirme

Oturum bilgisi

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

4.1 Bu Problem Oturumu Ne Hakkında?

6.006’da iki tür öğretim vardır: ders (lecture) temel materyali (veri yapıları, algoritmalar) sunar; problem oturumu (problem session) ise o materyalin uygulamasını gösterir. Jason Ku’nun deyişiyle, problemlerin “hissi” temel materyalden çok farklıdır — problemlere yaklaşmanın, ancak çalışarak öğrenilen püf noktaları vardır.

Bu ilk oturum, Ders 1-2’nin kavramlarını uygular: asimptotik analiz (Problem 1), sequence arayüzü ve özyineleme (Problem 2), dinamik dizi (Problem 3) ve bağlı liste manipülasyonu (Problem 4). Dört problem birer “İfade → Yaklaşım → Çözüm → Karmaşıklık” akışıyla işlenir. Ortak araçların haritası Şekil 4.1 içinde özetlenir.

flowchart TD
    R["Problem Oturumu 1<br/>(Ders 1-2 uygulaması)"] --> P1["Problem 1<br/>Asimptotik Sıralama"]
    R --> P2["Problem 2<br/>Sequence Black Box"]
    R --> P3["Problem 3<br/>Çift Uçlu Dinamik Dizi"]
    R --> P4["Problem 4<br/>Son Yarıyı Yerinde Ters"]
    P1 --> T1["Asimptotik karşılaştırma<br/>(log n)ᵃ ≪ nᵇ ≪ cⁿ · Stirling"]
    P2 --> T2["Black-box arayüz<br/>+ özyineleme + değişmez"]
    P3 --> T3["Charging argument<br/>(O(1) amortize)"]
    P4 --> T4["Yerinde işaretçi<br/>manipülasyonu (O(1) alan)"]

    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 4.1: Problem Oturumu 1’in kavram haritası: dört problem (üst sıra) ve her birinin öğrettiği taşınabilir araç (alt sıra). Problem 1 asimptotik karşılaştırma (Stirling + hiyerarşi), Problem 2 black-box arayüz disiplini + özyineleme, Problem 3 charging argument (amortize), Problem 4 yerinde işaretçi manipülasyonu kazandırır. Hepsi Ders 1-2 temeline dayanır.

Bir genel uyarı tüm oturuma damga vurur: çözümü kod değil, kelimelerle anlat. Ku, kafasında kod derleyemediğini söyler; problem setlerinde de net sözel açıklama beklenir.

“the problem sets that you will work on… applications of that material… there’s usually a much different feel between those problems then the underlying foundational material.” — Ku, 1:04

“I want you to explain in words to me, and we want you to explain in words in your LaTeX submissions what it is the algorithm is doing.” — Ku, 30:37

4.2 Problem 1: Asimptotik Sıralama

İfade. Bir fonksiyon listesini asimptotik büyüme hızına göre (yavaştan hızlıya) sırala. Asimptotik olarak eşit olan fonksiyonlar küme parantezi {} içinde gruplanır. Örneğin $n$, $\sqrt{n}$, $n + \sqrt{n}$ için cevap: $\sqrt{n}$, sonra $\{n,\ n + \sqrt{n}\}$.

Yaklaşım — Tanıdık Forma İndirge, Sonra Hiyerarşiyi Uygula

Her fonksiyonu tanıdık bir forma (polinom-benzeri) çevir, sonra şu hiyerarşiyi uygula: logaritmik faktörler polinom faktörlerden, polinomlar da üstellerden yavaş büyür. Karmaşık ifadeler (faktöriyel, binom katsayısı) için Stirling yaklaşımı kullanılır. Bir fonksiyonu sınıflandıramıyorsan, onu faktöriyel/binom tanımına aç, Stirling uygula, sadeleştir — ortaya polinom-benzeri bir form çıkar ve karşılaştırma kolaylaşır.

Çözüm. Üç temel araç bu problemin tüm varyantlarını çözer:

Log–polinom kimliği: Herhangi pozitif $a$, $b$ için $(\log n)^a \ll n^b$. Yani logaritmanın herhangi bir kuvveti, herhangi bir polinomdan kesinlikle (little-o anlamında) yavaştır. İspat yöntemi: iki fonksiyonun oranının limitini (kolaylık için logaritmasını) $n \to \infty$ için al.

“this log n to any power is asymptotically less than any polynomial for any positive a and b.” — Ku, 7:11

Stirling yaklaşımı: $n! \approx \sqrt{2\pi n}\,(n/e)^n$. Bu, asimptotik değil gerçek bir limit eşitliğidir. Logaritması alınınca $\log(n!) = \Theta(n \log n)$ çıkar — sınıfta sık kullanılır.
Binom katsayısı: $\binom{n}{k} = n! / (k!\,(n-k)!)$. İki örnek: $C(n, 3) = n(n-1)(n-2)/6 = \Theta(n^3)$; $C(n, n/2)$, Stirling ile sadeleştirilince $\Theta(2^n / \sqrt{n})$ verir.

Bu araç kutusunun görsel özeti — kesin hiyerarşi ve Stirling’in $\log(n!)$ üzerindeki etkisi — Şekil 4.2 içinde gösterilir.

Karmaşıklık. Bu bir analiz problemidir (çalışma süresi değil): araç, fonksiyonları kapalı, karşılaştırılabilir forma indirgemek. Sonuç bir sıralamadır, bir koşma zamanı değil.

Şekil 4.2: Problem 1 araç kutusu: log-y ekseninde **kesin** asimptotik hiyerarşi $(\log n)^2 \ll n^{0.5} \ll n \ll 2^n$. Logaritmik faktörler (en açık slate) her polinomun ($n^{0.5}$, $n$ — orta/koyu slate) altında kalır; polinomlar da üstelin (amber, **en hızlı**) altındadır — bu sıralama *her* pozitif $a$, $b$ ve $c>1$ için geçerlidir. Üstel eğri log eksende düz bir doğru olur ($\log 2^n = n\log 2$) ve $n$ büyüdükçe diğerlerinin hepsini ezici biçimde geride bırakır; üç yavaş eğri tabanda kümelenir çünkü hepsi üstelin yanında ihmal edilebilir kalır. Sağ-alttaki kutu **Stirling** sonucunu özetler: $\log(n!) = \Theta(n\log n)$ — $\sqrt{2\pi n}\,(n/e)^n$ yaklaşımının logaritması $n\log n - n$ baskın terimini verir; $n=64$ için $\ln(64!) = 205{,}17$ ile Stirling $205{,}17$ yalnız **%0,0006** sapar (asimptotik değil, gerçek bir limit eşitliği).

4.3 Problem 2: Sequence Arayüzünü Black Box Olarak Kullanma

İfade. Sana bir sequence veri yapısı veriliyor ve içini göremiyorsun (black box). Yalnızca dört işlemi var, hepsi sabit zaman: insert_first, insert_last, delete_first, delete_last (delete’ler sildikleri öğeyi döndürür). Bu işlemleri kullanarak (a) swap_ends ve (b) shift_left(D, K) yaz.

Yaklaşım — Arayüzü Onurlandır, Özyinelemeyle Değişmez Koru

İçeriği değil, yalnızca dış işlemleri kullan — bu, arayüz/gerçekleştirim ayrımının pratiğidir. Sabit-zamandan uzun işlemler için döngü veya özyineleme kullan; Ku özyinelemeyi tercih eder çünkü her adımda yalnızca sabit miktarda bilgiyle (bir değişmez + küçük durum analizi) uğraşmak argümanı kolaylaştırır.

“if I break it down so that I solve a slightly smaller problem recursively, and then do a constant amount of work and maintain some invariant, then it’s very easy to argue things about it.” — Ku, 40:03

Çözüm.

(a) swap_ends — ilk ve son öğeyi değiştir: her ikisini sil, geçici değişkenlerde tut, ters yerlere geri ekle.

swap_ends(D):
    x1 = D.delete_first()
    x2 = D.delete_last()
    D.insert_first(x2)
    D.insert_last(x1)

(b) shift_left(D, K) — ilk $K$ öğeyi sona taşı ($K$’inci öğe son olur, $K+1$’inci ilk olur). Özyinelemeli:

shift_left(D, K):
    if K < 1 or K > len(D) - 1:   # taban durum / sınır kontrolü
        return
    x = D.delete_first()
    D.insert_last(x)
    shift_left(D, K - 1)          # bir küçük örnek

Her çağrı bir öğeyi öne alır ve $K$’yi 1 azaltır; taban durumda ($K < 1$) durur. Değişmez korunduğu için doğruluk kolayca tümevarımla görülür. Bu black-box disiplini, bir sonraki problemde (Problem 3) tam tersini yapmanın — yani arayüzün altındaki veri yapısını tasarlamanın — neden değer taşıdığını da gösterir.

Karmaşıklık. swap_ends sabit sayıda $O(1)$ işlem → $O(1)$. shift_left, $K$ kez sabit iş → $O(K)$.

4.4 Problem 3: Çift Uçlu Dinamik Dizi

İfade. “İki dünyanın en iyisi” bir veri yapısı tasarla: en kötü durumda $O(1)$ indeksleme (dizi gibi) ve sequence’in her iki ucunda $O(1)$ amortize ekleme/silme. Tek başına dinamik dizi sonda amortize $O(1)$ ama başta $O(n)$’dir; bağlı liste iki uçta $O(1)$ ama indeksleme $O(n)$’dir.

Yaklaşım — Sıfırdan Tasarla ya da Hazıra İndirge

İki yol vardır: (1) dinamik diziyi sıfırdan yeniden tasarla (çift uçlu); (2) hazır bir dinamik diziye indirgeme (reduction) yap. Her ikisinin de çekirdeği aynı sezgidir: pahalı bir yeniden-inşadan önce mutlaka lineer sayıda ucuz işlem garanti et — bu, charging argument’ın özüdür.

Çözüm.

Yöntem 1 — Çift uçlu dinamik dizi (dynamic deque). Diziyi her iki uçta da fazladan boş yerle (her birinde lineer miktarda) tut. Böylece hem önden hem sondan eklerken, lineer sayıda işlem yapana kadar yeniden boyutlandırma gerekmez. Yeniden boyutlandırırken (büyütme veya küçültme) her iki uçta yine lineer fazla yer bırak — bu, charging argument’ın çalışmasını garanti eder: bir pahalı yeniden-inşadan önce mutlaka lineer sayıda ucuz işlem yapılmış olur (silmede de israfı önlemek için $\tfrac14$ doluluğa inince küçült).

“I have to do a linear number of cheap things before I have to do an expensive thing again.” — Ku, 1:00:09

Yöntem 2 — Dinamik diziye indirgeme. İki dinamik dizi kullan; birini ters yönde gör. Saklanacak sequence’i ortadan ikiye böl; her yarı bir dinamik dizidir (biri normal, biri ters). Önden/sondan işlemler artık birer dinamik dizi ucu işlemi olur (biraz indeks aritmetiğiyle). Tek incelik: bir dizi boşalırsa, diğerini ikiye böl ve iki yeni diziye yeniden dağıt — bu yeniden-inşanın maliyeti, biriken amortize bütçeden karşılanır.

Karmaşıklık. İndeksleme $O(1)$ en kötü durum (saf ofset aritmetiği); her iki uçta ekleme/silme $O(1)$ amortize; alan, saklanan öğe sayısında lineer ($O(n)$).

4.5 Problem 4: Bağlı Listenin Son Yarısını Ters Çevirme

İfade. $2n$ düğümlü tek yönlü (singly) bir bağlı liste verilir. Son $n$ düğümün sırasını yerinde (in-place) ters çevir. Yeni düğüm oluşturma yok; sabit (constant) ek alandan fazlasını kullanma — yani öğeleri bir diziye kopyalayıp geri yazamazsın, sadece mevcut düğümlerin işaretçilerini değiştirebilirsin.

Yaklaşım — Üç Adıma Böl, Önceki Düğümü Hatırla

Üç adıma böl: (1) $n$’inci düğümü bul, (2) $n+1$’den $2n$’e kadar olan düğümlerin next işaretçilerini ters çevir, (3) uçları yeniden bağla. İşaretçi ters çevirirken, “önceki” düğümü hatırlamak gerekir; aksi halde liste kopar ve düğümlere erişim kaybolur (garbage-collected dillerde sızıntı, diğerlerinde memory leak). Adım-adım işaretçi izi Şekil 4.3 içinde gösterilir.

Çözüm.

$n$’inci düğümü bul: $n = \text{size} / 2$. Baştan $n-1$ kez next takip et → a = $n$’inci düğüm. b = a.next (ters çevrilecek bloğun başı).
İşaretçileri ters çevir: İki imleç tut — x (yeniden bağlanacak düğüm) ve x_p (ondan önceki). x_p, x = a, b ile başla. $n$ kez: x_n = x.next (sonrakini sakla), x.next = x_p (geriye bağla), sonra x_p, x = x, x_n (kaydır).
Uçları temizle: Döngü sonunda x_p ters bloğun yeni başı (c) olur. a.next = c (ilk blok yeni başa bağlanır), b.next = None (eski baş, artık son, sonlanır).

reorder(L):
    n = L.size // 2
    a = L.head
    for _ in range(n - 1):
        a = a.next
    b = a.next
    x_p, x = a, b
    for _ in range(n):
        x_n = x.next
        x.next = x_p
        x_p, x = x, x_n
    a.next = x_p      # x_p = c
    b.next = None

Şekil 4.3’in beş aşaması, bu pseudocode’un $2n = 8$ düğümlük bir liste üzerinde nasıl yürüdüğünü — pivot a’nın bulunması, bloğun ters çevrilmesi ve uçların yeniden bağlanması — somut olarak izler.

Karmaşıklık. $n$’inci düğümü bulma $O(n)$, ters çevirme $O(n)$, temizlik $O(1)$ → toplam $O(n)$; ek alan $O(1)$ (yalnızca birkaç imleç).

Şekil 4.3: Son yarıyı **yerinde** ters çevirme izi ($2n=8$ düğüm, son $n=4$). **(1)** Orijinal liste $1\to\cdots\to8$, `head`. **(2)** $a=$ 4. düğüm (pivot), $b=a.\text{next}=5$ (ters çevrilecek bloğun başı). **(3)** Bloğun (5,6,7,8) `next` işaretçileri tersine çevrilir — **amber** geri-oklar artık $8\to7\to6\to5\to4$ yönünde; $a$’nın `next`’i geçici olarak $\varnothing$. **(4)** Uçlar yeniden bağlanır: `a.next = 8` ve `b.next = None` (eski baş artık son). **(5)** Sonuç $1\to2\to3\to4\to8\to7\to6\to5$ — ek alan $O(1)$ (yalnız birkaç imleç), zaman $O(n)$. İmleç ters çevrilirken “önceki” düğümü hatırlamak şarttır, yoksa liste kopar.

Builder Notu — Yerinde Algoritmalar ve Memory Leak

İşaretçi ters çevirmede bir düğüme referans kaybedersen, garbage-collected bir dilde (Python) GC onu toplar; C gibi dillerde bu bir memory leak’tir. Yerinde (in-place) algoritmalar, gömülü sistemler ve düşük-bellek ortamlarında kritiktir: ekstra dizi ayırmaya bütçe yoktur.

İleriye → ML / tensör işlemleri: PyTorch’taki _ son ekli işlemler (add_, relu_) tam olarak bu sezgidir — yeni tensör ayırmadan mevcut belleği yerinde değiştirmek; büyük modellerde bellek tasarrufunun anahtarı.
İleriye → embedded / firmware: Mikrodenetleyicilerde yığın (heap) ayırma çoğu zaman yasaktır; veri yapıları yerinde dönüştürülür.

Tek cümle: Yerinde dönüşüm, “yeni alan ayırma — var olanı yeniden bağla” disiplinidir.

4.6 Ne Öğrendik?

Altı Taşınabilir Araç

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

Asimptotik karşılaştırma araçları: $(\log n)^a \ll n^b \ll c^n$ hiyerarşisi; faktöriyel/binom için Stirling yaklaşımı ($\log(n!) = \Theta(n \log n)$).
Black box / arayüz disiplini: Bir veri yapısını yalnızca dış işlemleriyle kullanıp üzerine yeni işlemler kurmak.
Özyineleme stratejisi: Sabit iş + bir küçük örneğe indirgeme; değişmezle kolay doğruluk argümanı.
Charging argument (amortize): Pahalı bir işlemden önce lineer sayıda ucuz işlem garanti ederek $O(1)$ amortize elde etme.
Yerinde işaretçi manipülasyonu: Sabit ek alanla bağlı liste yeniden bağlama; referans kaybı = sızıntı.
İletişim kuralı: Algoritmayı koddan önce kelimelerle anlat.

Dört problemin zaman, ek alan ve anahtar sonuç açısından maliyet özeti Şekil 4.4 içinde tek bakışta toplanır.

Şekil 4.4: PS1’in dört probleminin maliyet özeti tek bakışta. Satırlar dört problem, sütunlar **Zaman · Ek Alan · Anahtar Sonuç**. Hücreler maliyet sınıfına göre renklenir: yeşilimsi hücreler $O(1)$ sabit (en iyi), amber-çerçeveli açık hücreler $O(1)$ amortize / yerinde (neredeyse en iyi), dolu amber hücreler $O(n)$ / $O(K)$ girdiye bağlı, nötr hücreler ise çalışma-süresi olmayan analiz. P1 bir araç-kutusudur (çalışma süresi yok): asimptotik hiyerarşi $(\log n)^a \ll n^b \ll c^n$ ve $\log(n!)=\Theta(n\log n)$. P2 yalnız dört $O(1)$ uç işlemiyle `swap_ends`’i $O(1)$, `shift_left`’i özyinelemeyle $O(K)$ kurar — $O(1)$ ek alan. P3 ofset aritmetiğiyle $O(1)$ **en-kötü** indeksleme ile charging argument’a dayanan iki-uçta $O(1)$ **amortize** ekleme/silmeyi birleştirir (alan $O(n)$). P4 son yarıyı yalnız üç imleçle, yeni düğüm üretmeden çevirir: zaman $O(n)$, ek alan $O(1)$ **yerinde**. Amber çerçeve, amortize ve yerinde kazanımları işaretler.

4.7 Sonraki

Ders 4 (L3) — Kümeler ve Sıralama

Sırada Ders 4 (L3): Kümeler ve Sıralama var — Justin Solomon ile küme (set) arayüzüne ve onu çözmenin ilk adımı olan sıralamaya (insertion, selection, merge sort) geçiyoruz. Bu oturumda gördüğün asimptotik karşılaştırma araçları, sıralama algoritmalarının çalışma sürelerini analiz ederken doğrudan işine yarayacak.

--- title: "Problem Oturumu 1" subtitle: "Ders 1-2'nin uygulaması: asimptotik sıralama, sequence black box, çift uçlu dinamik dizi ve yerinde bağlı liste ters çevirme" --- ::: {.callout-note title="Oturum bilgisi"} - **Ku'nun videosu:** [YouTube — Problem Session 1](https://www.youtube.com/watch?v=IPSaG9RRc-k) (≈60 dk) - **OCW sayfası:** [MIT 6.006 Problem Session 1](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/problem-session-1/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 3 (Problem Oturumu 1) - **Hoca:** Jason Ku - **Okuma süresi:** ≈26 dk ::: ## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d03} 6.006'da iki tür öğretim vardır: **ders (lecture)** temel materyali (veri yapıları, algoritmalar) sunar; **problem oturumu (problem session)** ise o materyalin *uygulamasını* gösterir. Jason Ku'nun deyişiyle, problemlerin "hissi" temel materyalden çok farklıdır — problemlere yaklaşmanın, ancak çalışarak öğrenilen püf noktaları vardır. Bu ilk oturum, Ders 1-2'nin kavramlarını uygular: **asimptotik analiz** (Problem 1), **sequence arayüzü ve özyineleme** (Problem 2), **dinamik dizi** (Problem 3) ve **bağlı liste manipülasyonu** (Problem 4). Dört problem birer "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir. Ortak araçların haritası @fig-ps1-concept-map içinde özetlenir. ```{mermaid} %%| label: fig-ps1-concept-map %%| echo: false %%| fig-cap: "Problem Oturumu 1'in kavram haritası: dört problem (üst sıra) ve her birinin öğrettiği taşınabilir araç (alt sıra). Problem 1 asimptotik karşılaştırma (Stirling + hiyerarşi), Problem 2 black-box arayüz disiplini + özyineleme, Problem 3 charging argument (amortize), Problem 4 yerinde işaretçi manipülasyonu kazandırır. Hepsi Ders 1-2 temeline dayanır." flowchart TD R["Problem Oturumu 1 (Ders 1-2 uygulaması)"] --> P1["Problem 1 Asimptotik Sıralama"] R --> P2["Problem 2 Sequence Black Box"] R --> P3["Problem 3 Çift Uçlu Dinamik Dizi"] R --> P4["Problem 4 Son Yarıyı Yerinde Ters"] P1 --> T1["Asimptotik karşılaştırma (log n)ᵃ ≪ nᵇ ≪ cⁿ · Stirling"] P2 --> T2["Black-box arayüz + özyineleme + değişmez"] P3 --> T3["Charging argument (O(1) amortize)"] P4 --> T4["Yerinde işaretçi manipülasyonu (O(1) alan)"] 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 ``` Bir genel uyarı tüm oturuma damga vurur: çözümü **kod değil, kelimelerle** anlat. Ku, kafasında kod derleyemediğini söyler; problem setlerinde de net sözel açıklama beklenir. > *"the problem sets that you will work on... applications of that material... there's usually a much different feel between those problems then the underlying foundational material."* — Ku, 1:04 > *"I want you to explain in words to me, and we want you to explain in words in your LaTeX submissions what it is the algorithm is doing."* — Ku, 30:37 ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 3 (PS1) motoru (_engine_PS1.py) + Slate+Amber viz (_viz.py) # Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede # tanımlanan growth_p1_funcs / log_factorial / reorder_trace + COL_* + apply_style # vb. globalleri 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: Node/LinkedList (D2) + PS1 fonksiyonları burada # self-contained inline'dır → render dizininden bağımsız. # ============================================================================ import math 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 (üstel/hızlı, ters blok işaretçileri) 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" def apply_style(ax): """Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için).""" ax.set_facecolor(COL_WHITE) ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8) for spine in ax.spines.values(): spine.set_color(COL_SLATE_400) ax.tick_params(colors=COL_TEXT) ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT) ax.yaxis.label.set_color(COL_TEXT) return ax # --------------------------------------------------------------------------- # _engine_PS1.py — Problem 1: asimptotik araçlar (Stirling + büyüme hiyerarşisi) # --------------------------------------------------------------------------- def growth_p1_funcs(a=2.0, b=1.0, c=2.0): """Problem 1 büyüme fonksiyonları: (log n)ᵃ, nᵇ, cⁿ (fig + hiyerarşi demosu). Notion: "(log n)ᵃ ≪ nᵇ ≪ cⁿ" — logaritmik faktörler polinomdan, polinomlar üstellerden yavaş büyür (her pozitif a, b ve c > 1 için). """ return { "(log n)ᵃ": lambda n: (math.log2(n)) ** a if n > 1 else 0.0, "nᵇ": lambda n: float(n) ** b, "cⁿ": lambda n: float(c) ** n, } def log_factorial(n): """log(n!) gerçek değeri (doğal log). Θ(n log n) demosu için referans.""" if n < 1: raise ValueError("log_factorial: n ≥ 1 olmalı") return math.lgamma(n + 1) # lgamma(n+1) = ln(n!) — taşmasız, kesin def log_factorial_stirling(n): """Stirling üzerinden log(n!): ln(√(2πn)) + n·ln(n) − n (= Θ(n log n)).""" if n < 1: raise ValueError("log_factorial_stirling: n ≥ 1 olmalı") return 0.5 * math.log(2.0 * math.pi * n) + n * math.log(n) - n # --------------------------------------------------------------------------- # _engine.py (D2) — Node + LinkedList (Problem 4 için; self-contained inline) # --------------------------------------------------------------------------- class Node: """Bağlı liste düğümü: bir `item` alanı + bir `next` işaretçisi (D2 §7).""" def __init__(self, item, next=None): self.item = item self.next = next class LinkedList: """Tek yönlü bağlı liste (D2 §7-8): head + tail augmentation ile.""" def __init__(self): self.head = None self.tail = None self.n = 0 def length(self): return self.n def insert_last(self, x): node = Node(x, None) if self.tail is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node self.n += 1 def to_list(self): out = [] node = self.head while node is not None: out.append(node.item) node = node.next return out # --------------------------------------------------------------------------- # _engine_PS1.py — Problem 4: reorder + reorder_trace (fig-reverse-trace için) # --------------------------------------------------------------------------- def build_linked_list(values): """Verilen değerlerden tek-yönlü bağlı liste kur (insert_last, O(1) tail augment).""" L = LinkedList() for v in values: L.insert_last(v) return L def reorder_trace(values): """fig-reverse-trace için: reorder'ın before/after durumu + adım-adım işaretçi izi. 2n düğümlü listeyi `values`'tan kurar, son n düğümün next işaretçilerini yerinde ters çevirir; her ters-çevirme adımında imleç durumunu kaydeder. Notion pseudocode'u (reorder) birebir — yeni düğüm yok, O(1) ek alan. """ L = build_linked_list(values) before = L.to_list() n = L.length() // 2 steps = [] pivot_item = None block_head_item = None if n > 0: a = L.head for _ in range(n - 1): a = a.next b = a.next pivot_item = a.item block_head_item = b.item if b is not None else None x_p, x = a, b for s in range(n): x_n = x.next from_next = x_n.item if x_n is not None else None to_next = x_p.item if x_p is not None else None x.next = x_p steps.append({ "step": s + 1, "x": x.item, "from_next": from_next, "to_next": to_next, }) x_p, x = x, x_n a.next = x_p b.next = None L.tail = b after = L.to_list() return { "before": before, "after": after, "n": n, "pivot": pivot_item, "block_head": block_head_item, "steps": steps, } ``` ## Problem 1: Asimptotik Sıralama {#sec-problem-1-d03} **İfade.** Bir fonksiyon listesini asimptotik büyüme hızına göre (yavaştan hızlıya) sırala. Asimptotik olarak *eşit* olan fonksiyonlar küme parantezi `{}` içinde gruplanır. Örneğin $n$, $\sqrt{n}$, $n + \sqrt{n}$ için cevap: $\sqrt{n}$, sonra $\{n,\ n + \sqrt{n}\}$. ::: {.callout-tip title="Yaklaşım — Tanıdık Forma İndirge, Sonra Hiyerarşiyi Uygula"} Her fonksiyonu **tanıdık bir forma** (polinom-benzeri) çevir, sonra şu hiyerarşiyi uygula: logaritmik faktörler polinom faktörlerden, polinomlar da üstellerden yavaş büyür. Karmaşık ifadeler (faktöriyel, binom katsayısı) için **Stirling yaklaşımı** kullanılır. Bir fonksiyonu sınıflandıramıyorsan, onu faktöriyel/binom tanımına aç, Stirling uygula, sadeleştir — ortaya polinom-benzeri bir form çıkar ve karşılaştırma kolaylaşır. ::: **Çözüm.** Üç temel araç bu problemin tüm varyantlarını çözer: - **Log–polinom kimliği:** Herhangi pozitif $a$, $b$ için $(\log n)^a \ll n^b$. Yani logaritmanın herhangi bir kuvveti, herhangi bir polinomdan kesinlikle (little-o anlamında) yavaştır. İspat yöntemi: iki fonksiyonun oranının limitini (kolaylık için logaritmasını) $n \to \infty$ için al. > *"this log n to any power is asymptotically less than any polynomial for any positive a and b."* — Ku, 7:11 - **Stirling yaklaşımı:** $n! \approx \sqrt{2\pi n}\,(n/e)^n$. Bu, asimptotik değil *gerçek* bir limit eşitliğidir. Logaritması alınınca $\log(n!) = \Theta(n \log n)$ çıkar — sınıfta sık kullanılır. - **Binom katsayısı:** $\binom{n}{k} = n! / (k!\,(n-k)!)$. İki örnek: $C(n, 3) = n(n-1)(n-2)/6 = \Theta(n^3)$; $C(n, n/2)$, Stirling ile sadeleştirilince $\Theta(2^n / \sqrt{n})$ verir. Bu araç kutusunun görsel özeti — kesin hiyerarşi ve Stirling'in $\log(n!)$ üzerindeki etkisi — @fig-asymptotic-tools içinde gösterilir. **Karmaşıklık.** Bu bir *analiz* problemidir (çalışma süresi değil): araç, fonksiyonları kapalı, karşılaştırılabilir forma indirgemek. Sonuç bir sıralamadır, bir koşma zamanı değil. ```{python} #| label: fig-asymptotic-tools #| fig-cap: "Problem 1 araç kutusu: log-y ekseninde **kesin** asimptotik hiyerarşi $(\\log n)^2 \\ll n^{0.5} \\ll n \\ll 2^n$. Logaritmik faktörler (en açık slate) her polinomun ($n^{0.5}$, $n$ — orta/koyu slate) altında kalır; polinomlar da üstelin (amber, **en hızlı**) altındadır — bu sıralama *her* pozitif $a$, $b$ ve $c>1$ için geçerlidir. Üstel eğri log eksende düz bir doğru olur ($\\log 2^n = n\\log 2$) ve $n$ büyüdükçe diğerlerinin hepsini ezici biçimde geride bırakır; üç yavaş eğri tabanda kümelenir çünkü hepsi üstelin yanında ihmal edilebilir kalır. Sağ-alttaki kutu **Stirling** sonucunu özetler: $\\log(n!) = \\Theta(n\\log n)$ — $\\sqrt{2\\pi n}\\,(n/e)^n$ yaklaşımının logaritması $n\\log n - n$ baskın terimini verir; $n=64$ için $\\ln(64!) = 205{,}17$ ile Stirling $205{,}17$ yalnız **%0,0006** sapar (asimptotik değil, gerçek bir limit eşitliği)." #| fig-width: 8.6 #| fig-height: 5.6 # DETERMİNİSTİK: sabit n aralığı (2..64), seed yok. growth_p1_funcs / log_factorial / # log_factorial_stirling / apply_style / COL_* gizli setup hücresinden (inline _engine_PS1+_viz) gelir. nmax = 64 ns = list(range(2, nmax + 1)) # _engine_PS1 büyüme yardımcıları: a=2 → (log n)², b=0.5 → n^0.5, c=2 → 2ⁿ. pf = growth_p1_funcs(a=2.0, b=0.5, c=2.0) f_log, f_sqrt, f_exp = pf["(log n)ᵃ"], pf["nᵇ"], pf["cⁿ"] # Eğriler YAVAŞ→HIZLI: slate gradyanı (soluk→koyu, polinomlar) + amber (üstel, en hızlı). curves = [ ("(log n)²", f_log, COL_SLATE_400, 2.0), ("n^0.5", f_sqrt, COL_SLATE_500, 2.0), ("n", lambda n: float(n), COL_PRIMARY, 2.0), ("2ⁿ", f_exp, COL_ACCENT, 2.8), ] fig, ax = plt.subplots(figsize=(8.6, 5.6)) fig.patch.set_facecolor(COL_WHITE) apply_style(ax) for name, fn, color, lw in curves: ys = [fn(n) for n in ns] ax.semilogy(ns, ys, label=name, color=color, linewidth=lw, zorder=4 if name == "2ⁿ" else 3) ax.set_xlabel("n (girdi boyutu)", fontsize=10.5) ax.set_ylabel("büyüme (log ölçek)", fontsize=10.5) ax.set_xlim(2, nmax) ax.legend(loc="upper left", fontsize=10, framealpha=0.92, title="yavaş → hızlı", title_fontsize=9.5) fig.suptitle( "Asimptotik araç kutusu — kesin hiyerarşi (log-y ekseni)", color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985, ) ax.set_title( r"$(\log n)^2 \ll n^{0.5} \ll n \ll 2^n$ — log faktör < her polinom < üstel", color=COL_SLATE_500, fontsize=10.5, pad=8, ) # Stirling anotasyonu: log(n!) = Θ(n log n) (gerçek vs Stirling, n=nmax → %0,0006 sapma). lf_exact = log_factorial(nmax) lf_stir = log_factorial_stirling(nmax) rel_err = abs(lf_stir - lf_exact) / lf_exact ax.text( 0.985, 0.045, (r"Stirling: $\log(n!) = \Theta(n \log n)$" + "\n" + f"n={nmax}: ln(n!)={lf_exact:.1f} ≈ Stirling {lf_stir:.1f} " + f"(hata %{rel_err * 100:.2f})"), transform=ax.transAxes, ha="right", va="bottom", fontsize=9, 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), ) # Üstel eğriyi etiketle (amber = en hızlı patlama). ax.text( nmax * 0.62, f_exp(int(nmax * 0.62)) * 1.6, "üstel — en hızlı (amber)", color=COL_AMBER_700, fontsize=9, weight="bold", ha="center", style="italic", zorder=6, ) plt.tight_layout(rect=(0, 0, 1, 0.94)) plt.show() ``` ## Problem 2: Sequence Arayüzünü Black Box Olarak Kullanma {#sec-problem-2-d03} **İfade.** Sana bir **sequence** veri yapısı veriliyor ve içini göremiyorsun (black box). Yalnızca dört işlemi var, hepsi sabit zaman: `insert_first`, `insert_last`, `delete_first`, `delete_last` (delete'ler sildikleri öğeyi döndürür). Bu işlemleri kullanarak (a) `swap_ends` ve (b) `shift_left(D, K)` yaz. ::: {.callout-tip title="Yaklaşım — Arayüzü Onurlandır, Özyinelemeyle Değişmez Koru"} İçeriği değil, yalnızca dış işlemleri kullan — bu, arayüz/gerçekleştirim ayrımının pratiğidir. Sabit-zamandan uzun işlemler için **döngü veya özyineleme** kullan; Ku özyinelemeyi tercih eder çünkü her adımda yalnızca *sabit miktarda* bilgiyle (bir değişmez + küçük durum analizi) uğraşmak argümanı kolaylaştırır. ::: > *"if I break it down so that I solve a slightly smaller problem recursively, and then do a constant amount of work and maintain some invariant, then it's very easy to argue things about it."* — Ku, 40:03 **Çözüm.** **(a) `swap_ends`** — ilk ve son öğeyi değiştir: her ikisini sil, geçici değişkenlerde tut, ters yerlere geri ekle. ```python swap_ends(D): x1 = D.delete_first() x2 = D.delete_last() D.insert_first(x2) D.insert_last(x1) ``` **(b) `shift_left(D, K)`** — ilk $K$ öğeyi sona taşı ($K$'inci öğe son olur, $K+1$'inci ilk olur). Özyinelemeli: ```python shift_left(D, K): if K < 1 or K > len(D) - 1: # taban durum / sınır kontrolü return x = D.delete_first() D.insert_last(x) shift_left(D, K - 1) # bir küçük örnek ``` Her çağrı bir öğeyi öne alır ve $K$'yi 1 azaltır; taban durumda ($K < 1$) durur. Değişmez korunduğu için doğruluk kolayca tümevarımla görülür. Bu black-box disiplini, bir sonraki problemde (Problem 3) tam tersini yapmanın — yani arayüzün *altındaki* veri yapısını tasarlamanın — neden değer taşıdığını da gösterir. **Karmaşıklık.** `swap_ends` sabit sayıda $O(1)$ işlem → **$O(1)$**. `shift_left`, $K$ kez sabit iş → **$O(K)$**. ## Problem 3: Çift Uçlu Dinamik Dizi {#sec-problem-3-d03} **İfade.** "İki dünyanın en iyisi" bir veri yapısı tasarla: en kötü durumda **$O(1)$ indeksleme** (dizi gibi) *ve* sequence'in **her iki ucunda $O(1)$ amortize** ekleme/silme. Tek başına dinamik dizi sonda amortize $O(1)$ ama başta $O(n)$'dir; bağlı liste iki uçta $O(1)$ ama indeksleme $O(n)$'dir. ::: {.callout-tip title="Yaklaşım — Sıfırdan Tasarla ya da Hazıra İndirge"} İki yol vardır: (1) dinamik diziyi sıfırdan yeniden tasarla (çift uçlu); (2) hazır bir dinamik diziye **indirgeme** (reduction) yap. Her ikisinin de çekirdeği aynı sezgidir: pahalı bir yeniden-inşadan önce mutlaka lineer sayıda ucuz işlem garanti et — bu, **charging argument**'ın özüdür. ::: **Çözüm.** **Yöntem 1 — Çift uçlu dinamik dizi (dynamic deque).** Diziyi her *iki* uçta da fazladan boş yerle (her birinde lineer miktarda) tut. Böylece hem önden hem sondan eklerken, lineer sayıda işlem yapana kadar yeniden boyutlandırma gerekmez. Yeniden boyutlandırırken (büyütme veya küçültme) her iki uçta yine lineer fazla yer bırak — bu, charging argument'ın çalışmasını garanti eder: bir pahalı yeniden-inşadan önce mutlaka lineer sayıda ucuz işlem yapılmış olur (silmede de israfı önlemek için $\tfrac14$ doluluğa inince küçült). > *"I have to do a linear number of cheap things before I have to do an expensive thing again."* — Ku, 1:00:09 **Yöntem 2 — Dinamik diziye indirgeme.** İki dinamik dizi kullan; birini **ters** yönde gör. Saklanacak sequence'i ortadan ikiye böl; her yarı bir dinamik dizidir (biri normal, biri ters). Önden/sondan işlemler artık birer dinamik dizi ucu işlemi olur (biraz indeks aritmetiğiyle). Tek incelik: bir dizi **boşalırsa**, diğerini ikiye böl ve iki yeni diziye yeniden dağıt — bu yeniden-inşanın maliyeti, biriken amortize bütçeden karşılanır. **Karmaşıklık.** İndeksleme **$O(1)$ en kötü durum** (saf ofset aritmetiği); her iki uçta ekleme/silme **$O(1)$ amortize**; alan, saklanan öğe sayısında lineer ($O(n)$). ## Problem 4: Bağlı Listenin Son Yarısını Ters Çevirme {#sec-problem-4-d03} **İfade.** $2n$ düğümlü tek yönlü (singly) bir bağlı liste verilir. Son $n$ düğümün sırasını **yerinde** (in-place) ters çevir. Yeni düğüm oluşturma yok; sabit (constant) ek alandan fazlasını kullanma — yani öğeleri bir diziye kopyalayıp geri yazamazsın, sadece mevcut düğümlerin işaretçilerini değiştirebilirsin. ::: {.callout-tip title="Yaklaşım — Üç Adıma Böl, Önceki Düğümü Hatırla"} Üç adıma böl: (1) $n$'inci düğümü bul, (2) $n+1$'den $2n$'e kadar olan düğümlerin `next` işaretçilerini ters çevir, (3) uçları yeniden bağla. İşaretçi ters çevirirken, "önceki" düğümü hatırlamak gerekir; aksi halde liste kopar ve düğümlere erişim kaybolur (garbage-collected dillerde sızıntı, diğerlerinde memory leak). Adım-adım işaretçi izi @fig-reverse-trace içinde gösterilir. ::: **Çözüm.** 1. **$n$'inci düğümü bul:** $n = \text{size} / 2$. Baştan $n-1$ kez `next` takip et → `a` = $n$'inci düğüm. `b` = `a.next` (ters çevrilecek bloğun başı). 2. **İşaretçileri ters çevir:** İki imleç tut — `x` (yeniden bağlanacak düğüm) ve `x_p` (ondan önceki). `x_p, x = a, b` ile başla. $n$ kez: `x_n = x.next` (sonrakini sakla), `x.next = x_p` (geriye bağla), sonra `x_p, x = x, x_n` (kaydır). 3. **Uçları temizle:** Döngü sonunda `x_p` ters bloğun yeni başı (`c`) olur. `a.next = c` (ilk blok yeni başa bağlanır), `b.next = None` (eski baş, artık son, sonlanır). ```python reorder(L): n = L.size // 2 a = L.head for _ in range(n - 1): a = a.next b = a.next x_p, x = a, b for _ in range(n): x_n = x.next x.next = x_p x_p, x = x, x_n a.next = x_p # x_p = c b.next = None ``` @fig-reverse-trace'in beş aşaması, bu pseudocode'un $2n = 8$ düğümlük bir liste üzerinde nasıl yürüdüğünü — pivot `a`'nın bulunması, bloğun ters çevrilmesi ve uçların yeniden bağlanması — somut olarak izler. **Karmaşıklık.** $n$'inci düğümü bulma $O(n)$, ters çevirme $O(n)$, temizlik $O(1)$ → toplam **$O(n)$**; ek alan **$O(1)$** (yalnızca birkaç imleç). ```{python} #| label: fig-reverse-trace #| fig-cap: "Son yarıyı **yerinde** ters çevirme izi ($2n=8$ düğüm, son $n=4$). **(1)** Orijinal liste $1\\to\\cdots\\to8$, `head`. **(2)** $a=$ 4. düğüm (pivot), $b=a.\\text{next}=5$ (ters çevrilecek bloğun başı). **(3)** Bloğun (5,6,7,8) `next` işaretçileri tersine çevrilir — **amber** geri-oklar artık $8\\to7\\to6\\to5\\to4$ yönünde; $a$'nın `next`'i geçici olarak $\\varnothing$. **(4)** Uçlar yeniden bağlanır: `a.next = 8` ve `b.next = None` (eski baş artık son). **(5)** Sonuç $1\\to2\\to3\\to4\\to8\\to7\\to6\\to5$ — ek alan $O(1)$ (yalnız birkaç imleç), zaman $O(n)$. İmleç ters çevrilirken \"önceki\" düğümü hatırlamak şarttır, yoksa liste kopar." #| fig-width: 11 #| fig-height: 7.4 # fig-reverse-trace — PS1 Problem 4: 2n=8 düğümlü listenin son n=4 düğümünü # YERİNDE ters çevirme izi (5 aşama). reorder_trace (setup'taki _engine_PS1) + # draw_linked_list stili (item|next kutuları + oklar). amber = ters blok işaretçileri. # Figüre özgü çok-satırlı çizim yardımcıları burada inline (setup globalleri: plt, # FancyBboxPatch, FancyArrowPatch, COL_*, reorder_trace). _NODE_W, _NODE_H, _GAP = 1.25, 0.78, 0.62 _ITEM_FRAC = 0.60 _SLOT = _NODE_W + _GAP def _rt_node(ax, x, y, item, *, active=False, pivot=False): on = active or pivot ec = COL_ACCENT if on else COL_PRIMARY fc_item = COL_AMBER_100 if (active or pivot) else COL_BG lw = 2.3 if on else 1.5 ax.add_patch(FancyBboxPatch( (x, y), _NODE_W * _ITEM_FRAC, _NODE_H, boxstyle="square,pad=0.0", fc=fc_item, ec=ec, linewidth=lw, zorder=2)) ax.add_patch(FancyBboxPatch( (x + _NODE_W * _ITEM_FRAC, y), _NODE_W * (1 - _ITEM_FRAC), _NODE_H, boxstyle="square,pad=0.0", fc=COL_BG, ec=ec, linewidth=lw, zorder=2)) ax.text(x + _NODE_W * _ITEM_FRAC * 0.5, y + _NODE_H * 0.5, str(item), ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=4) ax.text(x + _NODE_W * (_ITEM_FRAC + (1 - _ITEM_FRAC) * 0.5), y + _NODE_H * 0.5, "next", ha="center", va="center", fontsize=6.5, color=COL_SLATE_500, zorder=4) return (x + _NODE_W * 0.5, y + _NODE_H * 0.5) def _rt_row(ax, y, values, *, active_idx=(), pivot_idx=None, next_links=None, amber_links=(), tail_none_idx=None, row_title=None, annot=None, show_head=True): n = len(values) xs = [i * _SLOT for i in range(n)] centers = [] amber_set, active_set = set(amber_links), set(active_idx) for i, v in enumerate(values): centers.append(_rt_node(ax, xs[i], y, v, active=(i in active_set), pivot=(pivot_idx is not None and i == pivot_idx))) if next_links is None: next_links = {i: (i + 1 if i < n - 1 else None) for i in range(n)} for src, dst in next_links.items(): sx, sy = xs[src] + _NODE_W, y + _NODE_H * 0.5 hot = src in amber_set col = COL_ACCENT if hot else COL_SLATE_400 lw = 2.4 if hot else 1.4 if dst is None: ax.text(sx + _GAP * 0.55, sy, "∅", ha="center", va="center", fontsize=12, color=COL_SLATE_500, zorder=4) continue tx, ty = xs[dst], y + _NODE_H * 0.5 if dst == src + 1: ax.add_patch(FancyArrowPatch( (sx, sy), (tx, ty), arrowstyle="-|>", mutation_scale=13, color=col, linewidth=lw, zorder=3)) else: rad = 0.42 if dst < src else -0.42 startx = sx if dst > src else xs[src] + _NODE_W * _ITEM_FRAC * 0.5 starty = sy if dst > src else y + _NODE_H ax.add_patch(FancyArrowPatch( (startx, starty), (tx + _NODE_W * 0.5, y + _NODE_H), arrowstyle="-|>", mutation_scale=13, color=col, linewidth=lw, zorder=3, connectionstyle=f"arc3,rad={rad}")) if tail_none_idx is not None: sx = xs[tail_none_idx] + _NODE_W ax.text(sx + _GAP * 0.55, y + _NODE_H * 0.5, "∅", ha="center", va="center", fontsize=12, color=COL_SLATE_500, zorder=4) if show_head: hx = centers[0][0] ax.text(hx, y + _NODE_H + 0.30, "head", ha="center", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5) ax.add_patch(FancyArrowPatch( (hx, y + _NODE_H + 0.18), (hx, y + _NODE_H + 0.01), arrowstyle="-|>", mutation_scale=10, color=COL_AMBER_700, linewidth=1.6, zorder=5)) if row_title is not None: ax.text(-2.75, y + _NODE_H * 0.5, row_title, ha="left", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) if annot: for idx, txt in annot: ax.text(xs[idx] + _NODE_W * 0.5, y - 0.30, txt, ha="center", va="center", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=5) return centers # --- Deterministik iz: 2n=8 düğüm, son n=4 (reorder_trace, _engine_PS1) --- tr = reorder_trace([1, 2, 3, 4, 5, 6, 7, 8]) n = tr["n"] # 4 before, after = tr["before"], tr["after"] # [1..8] -> [1,2,3,4,8,7,6,5] a_idx, b_idx = n - 1, n # a = 4. düğüm (idx 3), b = 5 (idx 4) fig, ax = plt.subplots(figsize=(11, 7.4)) row_gap = 1.62 y_rows = [(-r) * row_gap for r in range(5)] # (1) Orijinal _rt_row(ax, y_rows[0], before, row_title="1) Orijinal") ax.text(_SLOT * 7 + _NODE_W, y_rows[0] + _NODE_H * 0.5, " 1→2→3→4→5→6→7→8 (2n=8)", ha="left", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic") # (2) a, b bul _rt_row(ax, y_rows[1], before, pivot_idx=a_idx, active_idx=(b_idx,), annot=[(a_idx, "a (4. düğüm)"), (b_idx, "b = a.next = 5")], row_title="2) a, b bul", show_head=False) # (3) Bloğu ters çevir — amber geri-oklar 8→7→6→5→4; a.next geçici ∅ _rt_row(ax, y_rows[2], before, active_idx=(b_idx, b_idx + 1, b_idx + 2, b_idx + 3), next_links={0: 1, 1: 2, 2: 3, a_idx: None, b_idx: a_idx, b_idx + 1: b_idx, b_idx + 2: b_idx + 1, b_idx + 3: b_idx + 2}, amber_links=(b_idx, b_idx + 1, b_idx + 2, b_idx + 3), tail_none_idx=a_idx, row_title="3) Bloğu ters çevir", annot=[(b_idx, "geri: 5→6→7→8 işaretçileri tersine")], show_head=False) # (4) Uçları bağla — a.next=8, b.next=None _rt_row(ax, y_rows[3], before, active_idx=(b_idx, b_idx + 1, b_idx + 2, b_idx + 3), pivot_idx=a_idx, next_links={0: 1, 1: 2, 2: 3, a_idx: b_idx + 3, b_idx: None, b_idx + 1: b_idx, b_idx + 2: b_idx + 1, b_idx + 3: b_idx + 2}, amber_links=(a_idx, b_idx + 1, b_idx + 2, b_idx + 3), row_title="4) Uçları bağla", annot=[(a_idx, "a.next = 8"), (b_idx, "b.next = None")], show_head=False) # (5) Sonuç 1,2,3,4,8,7,6,5 _rt_row(ax, y_rows[4], after, row_title="5) Sonuç", annot=[(4, "ters blok"), (7, "yeni son")], show_head=False) ax.text(_SLOT * 7 + _NODE_W, y_rows[4] + _NODE_H * 0.5, " 1→2→3→4→8→7→6→5", ha="left", va="center", fontsize=8.5, color=COL_AMBER_700, style="italic", weight="bold") fig.suptitle( "Son yarıyı yerinde ters çevirme: 2n=8 düğüm, son n=4 (amber = ters blok işaretçileri)", color=COL_TEXT, fontsize=12.5, y=0.99, ) ax.set_xlim(-2.9, _SLOT * 7 + _NODE_W + 3.6) ax.set_ylim(y_rows[-1] - 0.9, y_rows[0] + _NODE_H + 0.85) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Yerinde Algoritmalar ve Memory Leak"} İşaretçi ters çevirmede bir düğüme referans kaybedersen, garbage-collected bir dilde (Python) GC onu toplar; C gibi dillerde bu bir **memory leak**'tir. Yerinde (in-place) algoritmalar, gömülü sistemler ve düşük-bellek ortamlarında kritiktir: ekstra dizi ayırmaya bütçe yoktur. - **İleriye → ML / tensör işlemleri:** PyTorch'taki `_` son ekli işlemler (`add_`, `relu_`) tam olarak bu sezgidir — yeni tensör ayırmadan mevcut belleği yerinde değiştirmek; büyük modellerde bellek tasarrufunun anahtarı. - **İleriye → embedded / firmware:** Mikrodenetleyicilerde yığın (heap) ayırma çoğu zaman yasaktır; veri yapıları yerinde dönüştürülür. Tek cümle: *Yerinde dönüşüm, "yeni alan ayırma — var olanı yeniden bağla" disiplinidir.* ::: ## Ne Öğrendik? {#sec-ne-ogrendik-d03} ::: {.callout-important title="Altı Taşınabilir Araç"} Bu oturum, Ders 1-2'nin teorisini dört somut problemde uyguladı ve altı taşınabilir araç kazandırdı: 1. **Asimptotik karşılaştırma araçları:** $(\log n)^a \ll n^b \ll c^n$ hiyerarşisi; faktöriyel/binom için Stirling yaklaşımı ($\log(n!) = \Theta(n \log n)$). 2. **Black box / arayüz disiplini:** Bir veri yapısını yalnızca dış işlemleriyle kullanıp üzerine yeni işlemler kurmak. 3. **Özyineleme stratejisi:** Sabit iş + bir küçük örneğe indirgeme; değişmezle kolay doğruluk argümanı. 4. **Charging argument (amortize):** Pahalı bir işlemden önce lineer sayıda ucuz işlem garanti ederek $O(1)$ amortize elde etme. 5. **Yerinde işaretçi manipülasyonu:** Sabit ek alanla bağlı liste yeniden bağlama; referans kaybı = sızıntı. 6. **İletişim kuralı:** Algoritmayı koddan önce *kelimelerle* anlat. ::: Dört problemin zaman, ek alan ve anahtar sonuç açısından maliyet özeti @fig-complexity-summary içinde tek bakışta toplanır. ```{python} #| label: fig-complexity-summary #| fig-cap: "PS1'in dört probleminin maliyet özeti tek bakışta. Satırlar dört problem, sütunlar **Zaman · Ek Alan · Anahtar Sonuç**. Hücreler maliyet sınıfına göre renklenir: yeşilimsi hücreler $O(1)$ sabit (en iyi), amber-çerçeveli açık hücreler $O(1)$ amortize / yerinde (neredeyse en iyi), dolu amber hücreler $O(n)$ / $O(K)$ girdiye bağlı, nötr hücreler ise çalışma-süresi olmayan analiz. **P1** bir araç-kutusudur (çalışma süresi yok): asimptotik hiyerarşi $(\\log n)^a \\ll n^b \\ll c^n$ ve $\\log(n!)=\\Theta(n\\log n)$. **P2** yalnız dört $O(1)$ uç işlemiyle `swap_ends`'i $O(1)$, `shift_left`'i özyinelemeyle $O(K)$ kurar — $O(1)$ ek alan. **P3** ofset aritmetiğiyle $O(1)$ **en-kötü** indeksleme ile charging argument'a dayanan iki-uçta $O(1)$ **amortize** ekleme/silmeyi birleştirir (alan $O(n)$). **P4** son yarıyı yalnız üç imleçle, yeni düğüm üretmeden çevirir: zaman $O(n)$, ek alan $O(1)$ **yerinde**. Amber çerçeve, amortize ve yerinde kazanımları işaretler." #| fig-width: 12 #| fig-height: 6.4 def draw_complexity_summary(ax): """PS1'in 4 probleminin maliyet özeti — bespoke tablo (draw_cost_matrix idiom'u). Satırlar = 4 problem; sütunlar = Zaman | Ek Alan | Anahtar Sonuç. Hücreler maliyet sınıfına göre renklenir: O(1) yeşilimsi-slate (en iyi), O(1) amortize / yerinde amber-çerçeve, O(n)/O(K) amber dolgu, analiz/— nötr slate. """ # O(1)=hızlı için yeşilimsi-slate (draw_cost_matrix ile birebir "iyi" tonu) COL_GOOD = "#cfe8da" COL_GOOD_EC = "#3f7d5e" # Her hücre: (metin, sınıf). sınıf ∈ {good, amort, slow, neutral, mixed} cols = ["Problem", "Zaman", "Ek Alan", "Anahtar Sonuç"] rows = [ ("P1 · Asimptotik Sıralama", [("— (analiz)", "neutral"), ("—", "neutral"), ("(log n)ᵃ ≪ nᵇ ≪ cⁿ, log(n!)=Θ(n log n)", "neutral")]), ("P2 · Sequence Black Box", [("swap_ends O(1)\nshift_left O(K)", "mixed"), ("O(1)", "good"), ("yalnız 4 uç işlemi · özyineleme", "neutral")]), ("P3 · Çift Uçlu Dinamik Dizi", [("index O(1) en-kötü\niki-uç O(1) amortize", "amort"), ("O(n)", "slow"), ("ofset aritmetiği + charging", "neutral")]), ("P4 · Son Yarıyı Yerinde Ters", [("O(n)", "slow"), ("O(1) (yerinde)", "amort"), ("3 imleç · yeni düğüm yok", "neutral")]), ] def style_for(cls): if cls == "good": return COL_GOOD, COL_GOOD_EC, 1.8 if cls == "amort": return COL_AMBER_100, COL_ACCENT, 2.4 # amber-çerçeve vurgu (amortize/yerinde) if cls == "slow": return COL_AMBER_300, COL_AMBER_700, 1.6 if cls == "neutral": return COL_BG, COL_SLATE_400, 1.2 # karışık (P2 zaman: O(1) + O(K)) — biri sabit biri girdiye bağlı; nötr-açık return COL_BG, COL_SLATE_500, 1.4 # Geometri label_w = 5.4 # sol problem-etiket sütunu col_w = [3.7, 3.0, 7.0] # Zaman | Ek Alan | Anahtar Sonuç cell_h = 1.5 x_starts = [label_w] for w in col_w[:-1]: x_starts.append(x_starts[-1] + w) total_w = label_w + sum(col_w) # --- Başlık satırı (Slate) --- head_y = 0.0 ax.add_patch(FancyBboxPatch( (0, head_y), label_w * 0.985, cell_h * 0.9, boxstyle="square,pad=0.0", fc=COL_PRIMARY, ec=COL_PRIMARY, linewidth=1.6, zorder=2)) ax.text(label_w * 0.5, head_y + cell_h * 0.45, cols[0], ha="center", va="center", fontsize=12, color=COL_WHITE, weight="bold", zorder=4) for c in range(3): x = x_starts[c] ax.add_patch(FancyBboxPatch( (x, head_y), col_w[c] * 0.985, cell_h * 0.9, boxstyle="square,pad=0.0", fc=COL_PRIMARY, ec=COL_PRIMARY, linewidth=1.6, zorder=2)) ax.text(x + col_w[c] * 0.49, head_y + cell_h * 0.45, cols[c + 1], ha="center", va="center", fontsize=12, color=COL_WHITE, weight="bold", zorder=4) # --- Veri satırları (yukarıdan aşağı) --- for r, (plabel, cells) in enumerate(rows): y = -(r + 1) * cell_h ax.add_patch(FancyBboxPatch( (0, y), label_w * 0.985, cell_h * 0.92, boxstyle="square,pad=0.0", fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=2)) ax.text(label_w * 0.5, y + cell_h * 0.5, plabel, ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4) for c, (text, cls) in enumerate(cells): x = x_starts[c] fc, ec, lw = style_for(cls) ax.add_patch(FancyBboxPatch( (x, y), col_w[c] * 0.985, cell_h * 0.92, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2)) if c == 2: ax.text(x + col_w[c] * 0.04, y + cell_h * 0.5, text, ha="left", va="center", fontsize=9.5, color=COL_TEXT, zorder=4) else: fs = 9.3 if "\n" in text else 10.5 ax.text(x + col_w[c] * 0.49, y + cell_h * 0.5, text, ha="center", va="center", fontsize=fs, color=COL_TEXT, weight="bold", zorder=4) # --- Renk lejantı (alt) --- n_rows = len(rows) leg_y = -(n_rows + 1) * cell_h - 0.35 legend_items = [ (COL_GOOD, COL_GOOD_EC, "O(1) — sabit (en iyi)"), (COL_AMBER_100, COL_ACCENT, "O(1) amortize / yerinde — neredeyse en iyi"), (COL_AMBER_300, COL_AMBER_700, "O(n) / O(K) — girdiye bağlı"), (COL_BG, COL_SLATE_400, "analiz / yok"), ] lx = 0.0 sw = 0.55 for fc, ec, label in legend_items: ax.add_patch(FancyBboxPatch( (lx, leg_y), sw, sw, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=1.8, zorder=3)) ax.text(lx + sw + 0.18, leg_y + sw * 0.5, label, ha="left", va="center", fontsize=9.2, color=COL_TEXT, zorder=3) lx += sw + 0.22 + len(label) * 0.205 ax.set_xlim(-0.3, total_w + 0.3) ax.set_ylim(leg_y - 0.4, cell_h + 0.3) ax.set_aspect("equal") ax.axis("off") return ax fig, ax = plt.subplots(figsize=(12, 6.4)) draw_complexity_summary(ax) ax.set_title( "PS1 dört problemin maliyet özeti: bir analiz aracı + üç veri-yapısı garantisi", color=COL_TEXT, fontsize=13, pad=14, ) plt.tight_layout() plt.show() ``` ## Sonraki {#sec-sonraki-d03} ::: {.callout-warning title="Ders 4 (L3) — Kümeler ve Sıralama"} Sırada **Ders 4 (L3): Kümeler ve Sıralama** var — Justin Solomon ile **küme (set)** arayüzüne ve onu çözmenin ilk adımı olan **sıralamaya** (insertion, selection, merge sort) geçiyoruz. Bu oturumda gördüğün **asimptotik karşılaştırma araçları**, sıralama algoritmalarının çalışma sürelerini analiz ederken doğrudan işine yarayacak. :::