Algoritmalara Giriş — MIT 6.006’dan
ML Builder için Türkçe Notlar
1 Bu kitap nedir?
Bu, MIT 6.006 — Introduction to Algorithms (Spring 2020) ders serisinin Türkçe ders notlarıdır. Hedef, videoları izlerken paralel okunabilecek; sonradan tek başına da yeterli olabilecek bir referans seti üretmek.
Kurs üç hoca tarafından, üç farklı sesle anlatılır:
- Jason Ku — akademik, tahta + marker, Sokratik; “önce soruyu sınıfa taşı”.
- Erik Demaine — enerjik, görselleştiren; “I love algorithms.”
- Justin Solomon — informal, problem oturumları ve çizge teorisi.
Serinin bir iddiası var: bir algoritma yazmak işin yalnızca yarısıdır. Diğer yarısı, o algoritmanın doğru ve verimli olduğunu — bir bilgisayara değil, bir insana ikna edecek netlikte — kanıtlamaktır. 6.006 boyunca her ders bu iki yarıyı birlikte öğretir.
- Seri: MIT 6.006 Introduction to Algorithms, Spring 2020 (OCW)
- YouTube playlist: 6.006 Spring 2020 (32 video)
- Hocalar: Jason Ku, Erik Demaine, Justin Solomon
- Çeviri ve genişletme: Phase 2 (TR + ML Builder / OMSCS köprüleri)
2 Nasıl Okumalı
Sıralı oku. Kurs kümülatiftir — her ünite bir öncekinin kurduğu kavramları kullanır. Üç büyük ünite vardır: veri yapıları (diziler, hashing, ağaçlar, yığınlar), çizge algoritmaları (BFS, DFS, en kısa yollar), ve dinamik programlama. Aralara serpiştirilmiş problem oturumları (PS) her bloğu pekiştirir; üç quiz tekrarı sınav öncesi sentez yapar.
Önerilen akış: önce videoyu izle, sonra ilgili dersi oku, en sonunda bir problemi kendin çöz. Bu set videoyu destekler, ikame etmez.
6.006’nın kalbi koddan çok ispat ve iletişimdir. Her dersteki tümevarım argümanını, asimptotik analizi ve “neden doğru” gerekçesini atlama. Bir algoritmayı tarif seviyesinde — sınıftaki bir arkadaşına anlatabileceğin netlikte — yazabiliyorsan, onu anlamışsındır.
3 32 Ders
Kurs 32 videodan oluşur: 21 ders (lecture) + 3 quiz tekrarı + 8 problem oturumu. Aşağıdaki sıra videoların orijinal akışıdır.
| # | Tip | Ders |
|---|---|---|
| 1 | L1 | Algoritmalar ve Hesaplama |
| 2 | L2 | Veri Yapıları ve Dinamik Diziler |
| 3 | PS1 | Problem Oturumu 1 |
| 4 | L3 | Kümeler ve Sıralama |
| 5 | L4 | Hashing |
| 6 | PS2 | Problem Oturumu 2 |
| 7 | L5 | Doğrusal Zamanlı Sıralama |
| 8 | PS3 | Problem Oturumu 3 |
| 9 | L6 | İkili Ağaçlar — Bölüm 1 |
| 10 | L7 | İkili Ağaçlar — Bölüm 2: AVL |
| 11 | PS4 | Problem Oturumu 4 |
| 12 | L8 | İkili Yığınlar (Binary Heaps) |
| 13 | L9 | Çizgeler ve Enine Arama (BFS) |
| 14 | Quiz 1 Review | Quiz 1 Gözden Geçirme |
| 15 | L10 | Derinlemesine Arama (DFS) |
| 16 | L11 | Ağırlıklı En Kısa Yollar |
| 17 | PS5 | Problem Oturumu 5 |
| 18 | L12 | Bellman-Ford |
| 19 | L13 | Dijkstra |
| 20 | PS6 | Problem Oturumu 6 |
| 21 | L14 | Tüm-Çiftler En Kısa Yollar (Johnson) |
| 22 | Quiz 2 Review | Quiz 2 Gözden Geçirme |
| 23 | L15 | Dinamik Programlama 1: SRTBOT |
| 24 | L16 | Dinamik Programlama 2: LCS, LIS, Oyunlar |
| 25 | PS8 | Problem Oturumu 8 |
| 26 | L17 | Dinamik Programlama 3: Floyd-Warshall, Parantezleme |
| 27 | L18 | Dinamik Programlama 4: Pseudopolinom, Subset Sum |
| 28 | L19 | Hesaplama Karmaşıklığı: P, NP, NP-Tamlık |
| 29 | PS9 | Problem Oturumu 9 |
| 30 | PS10 | Quiz 3 Gözden Geçirme |
| 31 | L20 | Toparlanma ve Sonraki Dersler |
| 32 | L21 | Son Ders — Algoritmalar Her Yerde |
Not: Phase 2 üretimi Ders 1 (Algoritmalar ve Hesaplama) ile başlar. Kalan dersler aynı şablonla eklenir.
4 Notasyon
- Asimptotik sınırlar: \(O(\cdot)\) üst sınır, \(\Omega(\cdot)\) alt sınır, \(\Theta(\cdot)\) sıkı sınır.
- Büyüme hiyerarşisi: \(1 \ll \log n \ll n \ll n \log n \ll n^2 \ll n^c \ll 2^n\) — soldan sağa hızlı büyür; polinom ve altı “verimli”.
- Girdi boyutu (\(n\)): her zaman “eleman sayısı” değildir; bir çizge için genellikle \(V + E\) (düğüm + kenar).
- Çizge: \(G = (V, E)\) — düğüm kümesi \(V\), kenar kümesi \(E\).
- Mesafe: \(\delta(s, v)\) — \(s\)’ten \(v\)’ye en kısa yol uzunluğu.
Tüm matematik MathJax 3 ile render ediliyor.
5 Builder Ekseni — Neden Bu Ders?
Bu kursun pratik değeri ML değil, mühendislik temeli ve ölçek:
| 6.006 kavramı | İleriye / Geriye köprü |
|---|---|
| O / Θ / Ω, DP, çizge dili | OMSCS CS 6515 (Graduate Algorithms) ile birebir örtüşür |
| “Büyük N’de hangi karmaşıklık geçer” | Kompetitif programlama sezgisi |
| Hash tablosu, en kısa yol, öncelik kuyruğu | Sistem tasarımı: routing, cache, scheduler |
list/dict’in gizli zaman maliyeti |
Geriye → Phase 1 Python (time.perf_counter ile ampirik doğrulama) |
| Asimptotik mertebeler (log, exp) | Geriye → Phase 1 Calculus (büyüme oranları) |
| Randomized algoritma, beklenen-zaman | Geriye → Phase 1 Stat 110 (hashing, quicksort) |
6 Yazım Kuralları
- Türkçe terminoloji + parantez içinde İngilizce orijinal ilk geçtiğinde: “ikili ilişki (binary relation)”, “tümevarım (induction)”, “hesaplama modeli (word RAM)”.
- Hocalardan alıntılar İngilizce orijinal hâliyle, blockquote içinde, zaman damgasıyla verilir.
- Builder Notu callout’ları ML köprüsünü (geriye + ileriye) ve OMSCS bağını taşır.
- Öğretim kodu (pseudocode, Python örnekleri) görünür kod bloklarında; figürler (çizge, büyüme eğrisi, bellek şeması) algoritmayı görselleştiren, kaynağı gizli üretici hücrelerdir.
- Kontrol Soruları collapse’lu — cevap kapalı başlar, okur kendi düşündükten sonra açar.
- Egzersizler cevapsız — en az bir kodlama/ispat egzersizi.
Tek başına bu set yetmez — Ku, Demaine ve Solomon’un canlı anlatımının yerine geçemez. Önce videoyu izle, sonra ilgili dersi oku, son olarak bir problemi kendin çöz. Set videoyu destekler, ikame etmez.