Algoritmalar İçin Ön Bilgiler
Algoritmalar dersi Java ile programlamayı, temel veri yapılarını, ayrık matematiği, ispat tekniklerini, toplamları ve logaritmaları, olasılığı ve saymayı bir araya getirir. Bu sayfadaki 33 konu, dersin üzerine kurulduğu ön bilgileri altı grupta toplar.
Her kartta kısa bir açıklama, küçük bir örnek, konunun kullanıldığı slaytlara bağlantılar ve bir kontrol sorusu bulunur; sorunun üzerine tıklanınca yanıtı açılır.
Java ve programlama
Sunumlardaki kodları okumak, izlemek ve çözümleri Java ile yazmak için gereken bilgiler.
Java temelleri: türler, koşullar, döngüler
Sunumlardaki kodlar Java ile yazılmıştır; bu yüzden bir döngünün kaç kez döndüğünü ve her değişkenin nasıl değiştiğini kâğıt üzerinde izleyebilmek gerekir. int türünün yaklaşık ±2,1 milyarlık sınırı ve tam sayı bölmesi (7 / 2 = 3) sık rastlanan hata kaynaklarıdır.
Neden önemliKod izleme slaytlarının hepsi bu yapıları kullanır; ikili aramadaki klasik taşma hatası da int sınırından kaynaklanır.
Kontrol sorusu
int a = 7, b = 2; double d = a / b; d'nin değeri nedir?
3.0. Bölme tam sayılar üzerinde yapılır (3), sonuç ancak ondan sonra double türüne çevrilir. 3.5 elde etmek için (double) a / b yazılır.
int sum = 0;
for (int i = 1; i <= 10; i++) {
if (i % 2 == 0) sum += i; // çift sayılar toplanır
}
System.out.println(sum); // 30
long big = 50_000L * 50_000; // int olsaydı taşardı
System.out.println(big); // 2500000000Diziler ve iki boyutlu diziler
Sıralama, arama ve dinamik programlama tablolarının hepsi diziler üzerinde çalışır. İndislerin 0'dan length − 1'e kadar gittiği, bir dizinin metoda referansla geçtiği ve iki boyutlu bir dizide satır satır gezinildiği bilinmelidir.
Neden önemliSıralama algoritmaları dizi üzerinde yerinde çalışır, DP tabloları iki boyutlu dizidir, komşuluk matrisi de iki boyutlu bir dizidir.
Kontrol sorusu
int[] a = {3, 1, 2}; satırından sonra a[3] okunursa ne olur?
ArrayIndexOutOfBoundsException fırlatılır; geçerli indisler 0, 1 ve 2'dir.
int[] a = new int[5]; // [0, 0, 0, 0, 0]
a[a.length - 1] = 9; // son öğe
int[][] dp = new int[3][4]; // 3 satır, 4 sütun
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[i].length; j++)
dp[i][j] = i + j;
System.out.println(dp[2][3]); // 5Dizgiler ve karakterler
Dizgi algoritmalarının Java kodları String nesneleri üzerinde çalışır. s.length() uzunluğu, s.charAt(i) i. karakteri verir; indisler dizilerde olduğu gibi 0'dan başlar. String değiştirilemez (immutable): s + c her seferinde yeni bir nesne kurar, bu yüzden döngü içinde dizgi biriktirmek için StringBuilder kullanılır. char türü 16 bitlik bir tam sayıdır; ch - 'a' bir küçük harfi 0–25 aralığında bir indise çevirir ve bir karakter, sayma dizisinde doğrudan indis olarak kullanılabilir. İki dizginin içeriği == ile değil equals ile, sözlük sırası ise compareTo ile karşılaştırılır.
Neden önemliKaba kuvvet, KMP, Boyer-Moore ve Rabin-Karp kodları charAt ile karakter karşılaştırır; trie düğümleri çocuğunu ch - 'a' ile seçer, hash fonksiyonu ve basamak sıralaması karakter kodlarını sayı gibi kullanır.
Kontrol sorusu
"kedi".compareTo("kek") negatif mi, pozitif mi döner?
Negatif. İlk iki karakter eşittir; üçüncü konumda 'd' (100) ile 'k' (107) karşılaştırılır ve 100 − 107 = −7 döner.
String s = "algoritma";
System.out.println(s.length()); // 9
System.out.println(s.charAt(0)); // a
int idx = s.charAt(2) - 'a'; // 'g' → 6
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) sb.append(s.charAt(i));
System.out.println(idx + " " + sb); // 6 amtirogla
System.out.println("abc".equals("ab" + "c")); // trueMetotlar ve parametre aktarımı
Algoritmalar genellikle metot olarak yazılır: girdi parametredir, sonuç dönüş değeridir. Java her şeyi değerle aktarır; ancak diziler ve nesneler için kopyalanan değer bir referanstır, bu yüzden metot içindeki bir takas çağıranın dizisini değiştirir.
Neden önemliBütün sıralama algoritmaları öğeleri takas eden ya da kaydıran yardımcı metotlar kullanır; bölümleme metodu pivotun son konumunu döndürür.
Kontrol sorusu
Metot içinde a = new int[10]; yazmak çağıranın dizisini değiştirir mi?
Hayır. Yalnız metodun yerel referansı yeni diziye bağlanır; çağıran eski diziyi görmeye devam eder.
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t; // çağıranın dizisi değişir
}
static void increment(int x) { x++; } // çağıranın değişkeni değişmez
int[] d = {5, 7};
swap(d, 0, 1); // d = [7, 5]
int y = 1;
increment(y); // y hâlâ 1
System.out.println(d[0] + " " + y); // 7 1Özyineleme ve çağrı yığını
Birleştirme sıralaması, hızlı sıralama, DFS, geri izleme ve böl ve fethet algoritmaları özyinelemelidir (recursion). Her çağrının kendi yerel değişkenleriyle çağrı yığınına (call stack) eklendiği, taban durum (base case) unutulursa StackOverflowError oluştuğu ve özyineleme derinliğinin bellek tükettiği bilinmelidir.
Neden önemliHızlı üs alma, birleştirme sıralaması, özyinelemeli DFS ve geri izleme şablonu doğrudan özyinelemeyle yazılır.
Kontrol sorusu
power(2, 10) çağrısında, ilk çağrı da sayılırsa power metodu kaç kez çalışır?
5 kez: n = 10, 5, 2, 1, 0.
static int power(int a, int n) { // a üzeri n, n >= 0
if (n == 0) return 1; // taban durum
int half = power(a, n / 2); // problem yarıya iner
return (n % 2 == 0) ? half * half : half * half * a;
}
System.out.println(power(2, 10)); // 1024; derinlik yaklaşık log2(n)Sınıflar, nesneler ve karşılaştırıcılar
Kenar, düğüm, iş ya da eşya gibi kavramlar küçük sınıflarla gösterilir. Sıralama ve öncelikli kuyruklar öğeleri karşılaştırmak için bir compareTo metoduna ya da bir Comparator'a gerek duyar: Kruskal'da kenarlar ağırlığa göre, etkinlik seçiminde etkinlikler bitiş zamanına göre sıralanır.
Neden önemliAçgözlü algoritmaların çoğu bir sıralamayla başlar; Dijkstra ve Prim öncelikli kuyruğa karşılaştırılabilir nesneler koyar.
Kontrol sorusu
compareTo içinde return w - o.w; yazmak neden risklidir?
Büyük pozitif ve negatif değerlerde çıkarma int sınırını aşıp işareti ters çevirebilir; Integer.compare taşmaz.
static class Edge implements Comparable<Edge> {
final int u, v, w;
Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
public int compareTo(Edge o) { return Integer.compare(w, o.w); }
}
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 7));
edges.add(new Edge(1, 2, 3));
Collections.sort(edges); // ağırlığa göre artan
edges.sort((a, b) -> Integer.compare(b.w, a.w)); // azalan: Comparator
System.out.println(edges.get(0).w); // 7Java koleksiyonları
Sunumlardaki Java kodları hazır yapıları sık kullanır: komşuluk listeleri için ArrayList, BFS kuyruğu ve DFS yığını için ArrayDeque, Dijkstra ve Prim için PriorityQueue, bellekleme için HashMap. Her temel işlemin maliyetini bilmek, bir algoritmanın toplam çalışma süresini doğru hesaplamanın ön koşuludur.
Neden önemliBFS bir kuyrukla, Dijkstra bir öncelikli kuyrukla, bellekleme bir eşlemeyle (map) yazılır.
Kontrol sorusu
PriorityQueue'da add ve poll ne kadar sürer? contains(x) ve remove(x) ne kadar sürer?
add ve poll O(log n) sürer; contains(x) ve remove(x) iç diziyi baştan sona taradığı için O(n) sürer.
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
int first = queue.poll(); // 1 (ilk giren ilk çıkar)
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[1], y[1]));
pq.add(new int[] {7, 40});
pq.add(new int[] {3, 15});
int[] smallest = pq.poll(); // [3, 15]
Map<Integer, Long> memo = new HashMap<>();
memo.put(10, 55L);
System.out.println(first + " " + smallest[0] + " " + memo.get(10)); // 1 3 55Sözde kodu okuma ve izleme
Sunumlar ve ders kitapları algoritmaları çoğu zaman sözde kodla (pseudocode) verir: ← atamadır, diziler 1'den başlayabilir ve “for j ← 2 to n” son değeri de kapsar. Java'ya çevirirken bu farkları gözetmek ve her değişkenin her adımdaki değerini bir izleme tablosuna yazabilmek gerekir.
Neden önemliÇizge, akış ve dal sınır algoritmaları önce sözde kodla, sonra Java ile verilir.
Kontrol sorusu
Yukarıdaki sözde kod 0'dan başlayan indisli Java'ya çevrilince döngüler nasıl yazılır?
Dış döngü for (int j = 1; j < n; j++) olur, iç koşul da i >= 0 && A[i] > key biçimini alır.
INSERTION-SORT(A, n)
for j ← 2 to n
key ← A[j]
i ← j − 1
while i > 0 and A[i] > key
A[i + 1] ← A[i]
i ← i − 1
A[i + 1] ← keyTest ve hata ayıklama
Doğru bir fikir de özenle gerçeklenip test edilmelidir. Boş girdi, tek öğe, tekrarlanan değerler, sıralı ve ters sıralı diziler, bağlantısız çizgeler ve taşmaya yol açabilecek büyük değerlerle test etmek alışkanlık olmalıdır.
Neden önemliHer bölümün “sık yapılan hatalar” slaytı bu tür uç durumları toplar.
Kontrol sorusu
İkili aramada mid = (low + high) / 2 ne zaman yanlış sonuç verir?
low + high toplamı int aralığını aşınca toplam taşar ve negatif olur; low + (high − low) / 2 güvenlidir.
int[] empty = {}, one = {4}, equal = {2, 2, 2}, rev = {5, 4, 3, 2, 1};
for (int[] t : new int[][] {empty, one, equal, rev}) {
int[] k = t.clone();
Arrays.sort(k);
for (int i = 1; i < k.length; i++)
if (k[i - 1] > k[i]) throw new AssertionError("sıralı değil");
}
System.out.println("tüm testler geçti");Temel veri yapıları
Algoritmaların üzerinde çalıştığı yapılar ve temel işlemlerinin maliyeti. Bu yapılar önkoşul olan Veri Yapıları dersinde ayrıntılı olarak işlenir.
Bağlı listeler
Dizi gibi bir sırayı saklar, ancak öğeler bellekte bitişik değildir; her düğüm bir sonrakini gösterir. Başa ekleme O(1), i. öğeye erişim O(n) sürer. Komşuluk listeleri, hash tablolarındaki zincirleme ve LRU önbelleğinin O(1) gerçeklemesi bağlı listelere dayanır.
Neden önemliZincirlemeli hash tabloları ve O(1) LRU önbelleği bağlı liste kullanır.
Kontrol sorusu
Tek yönlü bağlı listede son öğeyi silmek neden O(n) sürer?
Sondan bir önceki düğümün next alanı null yapılmalıdır; o düğüme ulaşmak için baştan yürümek gerekir.
static class Node {
int value; Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
Node head = null;
for (int x = 1; x <= 3; x++) head = new Node(x, head); // 3 → 2 → 1
for (Node n = head; n != null; n = n.next) System.out.print(n.value + " ");Yığınlar ve kuyruklar
Yığın (stack) son giren ilk çıkar (LIFO), kuyruk (queue) ilk giren ilk çıkar (FIFO) ilkesiyle çalışır; ikisinde de temel işlemler O(1) sürer. DFS bir yığınla (ya da özyinelemenin çağrı yığınıyla), BFS bir kuyrukla çalışır; geri izleme seçimleri yığın sırasıyla geri alır.
Neden önemliYinelemeli DFS açık bir yığın kullanır; BFS ve Edmonds-Karp kuyruk kullanır.
Kontrol sorusu
1, 2, 3 bu sırayla hem bir kuyruğa hem bir yığına ekleniyor. Her birinden ilk hangi öğe çıkar?
Kuyruktan ilk 1, yığından ilk 3 çıkar.
Deque<Character> stack = new ArrayDeque<>();
for (char c : "abc".toCharArray()) stack.push(c);
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) sb.append(stack.pop());
System.out.println(sb); // cbaHeap ve öncelikli kuyruklar
Bir min-heap'te her düğüm çocuklarından küçüktür, bu yüzden en küçük öğe köktedir. Dizi olarak saklandığında i. düğümün çocukları 2i + 1 ve 2i + 2'de, ebeveyni (i − 1) / 2'dedir. Ekleme ve en küçüğü çıkarma O(log n) sürer; heap sort, Dijkstra, Prim, Huffman ve çevrim içi ortanca bu yapıya dayanır.
Neden önemliHeap sort, Dijkstra'nın karmaşıklığı, Huffman ağacının kurulması ve çevrim içi ortanca heap'e dayanır.
Kontrol sorusu
n öğeyi tek tek ekleyerek heap kurmak O(n log n) sürer. Aşağıdan yukarı heap kurma ne kadar sürer?
O(n); düğümlerin çoğu yapraklara yakın olduğu için toplam aşağı itme işi doğrusal kalır.
dizi: [2, 5, 3, 9, 6, 4]
indis: 0 1 2 3 4 5
2'nin çocukları: 5 ve 3 (indis 1, 2)
5'in çocukları: 9 ve 6 (indis 3, 4)
3'ün çocuğu: 4 (indis 5)Hash tabloları
Hash tablosu bir anahtarı hash fonksiyonuyla (hash function) dizi indisine dönüştürür; ekleme ve arama ortalamada O(1) sürer. İki anahtar aynı hücreye düştüğünde çakışma (collision) zincirlemeyle ya da doğrusal yoklamayla çözülür; yük faktörü (load factor) arttıkça performans düşer. Bellekleme, “ziyaret edildi” kümeleri ve Rabin-Karp'ın hash karşılaştırması bu fikre dayanır.
Neden önemliHash ile arama, Rabin-Karp ve bellekleme hash tablosu kullanır.
Kontrol sorusu
Hash tablosunda en kötü durumdaki arama süresi nedir ve ne zaman ortaya çıkar?
O(n); bütün anahtarlar aynı hücreye (aynı zincire) düştüğünde.
int m = 7;
int[] keys = {10, 17, 24};
for (int k : keys) System.out.print(k % m + " "); // 3 3 3 → çakışma
Set<String> visited = new HashSet<>();
visited.add("A");
System.out.println(visited.contains("A")); // trueAğaçlar ve ikili arama ağaçları
n düğümlü bir ağacın n − 1 kenarı vardır ve herhangi iki düğüm arasında tam olarak bir yol bulunur. Kök, ebeveyn, çocuk, yaprak, derinlik ve yükseklik terimleri DFS/BFS ağaçlarında, MST'lerde, union-find yapısında, trie'lerde ve durum uzayı ağaçlarında aynen kullanılır. İkili arama ağacı küçük anahtarları sol alt ağaçta, büyük anahtarları sağ alt ağaçta tutar; ağaç dengeliyse arama O(log n) sürer.
Neden önemliBFS ağacı, kapsayan ağaçlar, trie'ler ve durum uzayı ağaçları aynı terimlerle anlatılır.
Kontrol sorusu
Yüksekliği h olan bir ikili ağaçta en çok kaç düğüm bulunabilir?
2^(h+1) − 1 (tek düğümün yüksekliği 0 alınırsa).
8 yükseklik 2; yapraklar 1, 6, 14
/ \
3 10 3'ün ebeveyni 8, çocukları 1 ve 6
/ \ \
1 6 14 ortada sıralı (inorder) gezinme: 1 3 6 8 10 14Çizge gösterimleri
Çizge düğümlerden ve kenarlardan oluşur; kenarlar yönlü ya da yönsüz, ağırlıklı ya da ağırlıksız olabilir. Komşuluk matrisi (adjacency matrix) V² bellek kullanır ve bir kenar sorgusunu O(1) sürede yanıtlar; komşuluk listesi (adjacency list) O(V + E) bellek kullanır ve seyrek çizgelerde gezinmeyi O(V + E) sürede yapar. Derece, yol, döngü, bağlantılılık ve iki parçalılık terimleri tanıdık olmalıdır.
Neden önemliBütün çizge bölümleri ve dal sınırdaki TSP örnekleri bir çizge gösterimini varsayar.
Kontrol sorusu
10.000 düğümlü ve 30.000 kenarlı bir yol ağına hangi gösterim uygundur?
Komşuluk listesi: matris 10⁸ hücre ister, liste ise yönsüz bir çizge için yaklaşık V + 2E = 70.000 kayıt tutar.
int V = 4;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {{0, 1}, {0, 2}, {2, 3}};
for (int[] e : edges) { // yönsüz: iki yön de eklenir
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
System.out.println(adj.get(0)); // [1, 2]Ayrık matematik ve ispat
Algoritmaları tanımlamak ve doğruluklarını kanıtlamak için kullanılan dil.
Kümeler, fonksiyonlar ve bağıntılar
Algoritmalar küme diliyle anlatılır: G = (V, E), ziyaret edilmiş düğümler kümesi, MST'deki (S, V − S) kesimi, sırt çantasında seçilen eşyaların alt kümesi. Birleşim, kesişim, fark, Kartezyen çarpım ve alt kümeler; bir fonksiyonun tanım ve değer kümesi; bağıntıların yansıma, simetri ve geçişme özellikleri bilinmelidir.
Neden önemliKesim özelliği, Floyd-Warshall'ın geçişli kapanışı ve dal sınırdaki olurlu çözümler kümelerle tanımlanır.
Kontrol sorusu
n öğeli bir kümenin kaç alt kümesi vardır ve hangi kaba kuvvet yöntemi bu kadar maliyetlidir?
2ⁿ; alt küme toplamında ya da 0/1 sırt çantasında bütün seçimleri tek tek denemek.
A = {1, 2, 3}, B = {2, 3, 4}
A ∪ B = {1, 2, 3, 4} A ∩ B = {2, 3} A \ B = {1}
|A × B| = 3 · 3 = 9 A'nın alt küme sayısı: 2³ = 8
"ulaşılabilir" bağıntısı yansıyan ve geçişlidir; yönsüz çizgede simetrik de olur.Mantık ve niceleyiciler
Döngü koşulları, budama koşulları ve tanımlar mantıksal önermelerdir. “Her n ≥ n₀ için f(n) ≤ c · g(n)” gibi niceleyicili cümleleri okuyabilmek, bir önermenin değilini doğru almak (De Morgan) ve “p ⇒ q” ile “q ⇒ p” önermelerini ayırt edebilmek gerekir.
Neden önemliBüyük O niceleyicilerle tanımlanır; eklemeli sıralamanın iç döngüsü bileşik bir koşulda durur.
Kontrol sorusu
“Her düğümün en az bir komşusu vardır” önermesinin değili nedir?
“Hiç komşusu olmayan en az bir düğüm vardır.” ∀ ile ∃ yer değiştirir ve içteki önermenin değili alınır.
¬(a ∧ b) ≡ ¬a ∨ ¬b (De Morgan)
while (i > 0 && A[i] > x) döngüsünden çıkış koşulu: i <= 0 || A[i] <= x
f(n) = O(g(n)) ⇔ ∃c > 0, ∃n₀, ∀n ≥ n₀ : f(n) ≤ c · g(n)İspat teknikleri: doğrudan ispat, çelişki, karşı örnek
Bir algoritmanın her girdide doğru çalıştığını ispatla, yanlış olduğunu ise tek bir karşı örnekle gösteririz. Açgözlü algoritmaların doğruluğu çoğunlukla çelişkiyle ya da değiştirme argümanıyla (exchange argument) ispatlanır; “açgözlü para üstü her zaman en iyisini verir” iddiası ise bir karşı örnekle çürür.
Neden önemliAçgözlü seçimlerin doğruluğu, MST'nin kesim özelliği ve 2-yaklaşım oranları ispatla gösterilir.
Kontrol sorusu
√2'nin irrasyonel olduğunun ispatında hangi teknik kullanılır?
Çelişki: √2 = p/q en sade kesir varsayılınca hem p'nin hem q'nun çift olması gerekir; bu, varsayımla çelişir.
İddia: açgözlü para üstü her madeni para sisteminde en az sayıda para verir.
Karşı örnek: paralar {1, 3, 4}, tutar 6
açgözlü: 4 + 1 + 1 → 3 para
en iyi: 3 + 3 → 2 para ⇒ iddia yanlıştır.Tümevarım ve döngü değişmezleri
Tümevarım, P(1)'in doğru olduğunu ve P(k) ⇒ P(k + 1) olduğunu göstererek bir önermeyi her n için kanıtlar. Döngü değişmezi (loop invariant) bunun algoritmalara uyarlanmış biçimidir: döngüden önce doğru olan (başlangıç), her yinelemede korunan (koruma) ve döngü bitince sonucu veren (sonlanma) bir önermedir. Özyinelemeli algoritmaların doğruluğu da tümevarımla ispatlanır.
Neden önemliSıralama algoritmalarının doğruluğu ve yineleme bağıntılarının çözümleri tümevarımla gösterilir.
Kontrol sorusu
1 + 3 + 5 + … + (2n − 1) = n² eşitliği tümevarımla nasıl gösterilir?
n = 1 için 1 = 1². Eşitlik k için doğruysa k + 1 için toplam k² + (2k + 1) = (k + 1)² olur.
Eklemeli sıralama, değişmez: "j. yinelemenin başında A[0..j−1] sıralıdır."
Başlangıç: j = 1 → A[0..0] tek öğedir, sıralıdır.
Koruma: A[j] yerine kaydırılır → A[0..j] sıralıdır.
Sonlanma: j = n → A[0..n−1], yani dizinin tamamı sıralıdır.Analiz araçları
Çalışma sürelerini hesaplamak için toplamlar, logaritmalar ve büyüme hızları.
Toplam gösterimi ve seriler
İç içe döngülerin ve özyineleme ağaçlarının maliyeti bir toplam olarak yazılır. Üç seri temeldir: aritmetik seri karesel büyür; oranı 1'den küçük geometrik seri bir sabite yakınsar, oranı 1'den büyük olan ise en büyük terimi mertebesindedir; harmonik seri logaritmik büyür.
Neden önemliDöngü sayma, özyineleme ağacının düzeylerini toplama ve rastgele hızlı sıralamanın beklenen karşılaştırma sayısı bu serileri kullanır.
Kontrol sorusu
for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) döngüsünün gövdesi kaç kez çalışır?
1 + 2 + 4 + … < 2n kez, yani Θ(n) (geometrik seri).
Σ (i = 1..n) i = n(n + 1) / 2 = Θ(n²)
Σ (i = 0..k) 2^i = 2^(k+1) − 1 (1 + 2 + 4 + … + 2^k)
Σ (i = 0..∞) (1/2)^i = 2
H(n) = Σ (i = 1..n) 1/i ≈ ln n = Θ(log n)Logaritma ve üs kuralları
Girdisini yarıya indiren her algoritma (ikili arama, birleştirme sıralaması, heap) logaritmik derinlik üretir: n'yi 1'e indirmek log₂ n kez yarılamak demektir. Üs ve logaritma kuralları, logaritma tabanının asimptotik olarak önemsiz olduğu ve 2¹⁰ ≈ 10³ yaklaşımı bilinmelidir.
Neden önemliİkili aramanın adım sayısı, ana teoremdeki n^(log_b a) terimi ve Karatsuba'nın n^1.585 üssü logaritmayla hesaplanır.
Kontrol sorusu
Bir milyar öğeli sıralı bir dizide ikili arama en çok yaklaşık kaç karşılaştırma yapar?
Yaklaşık 30, çünkü 2³⁰ ≈ 1,07 · 10⁹.
log2(1024) = 10 log2(10^6) ≈ 20 log2(10^9) ≈ 30
a^(m+n) = a^m · a^n (a^m)^n = a^(m·n) log(x·y) = log x + log y
n^(log_b a) = a^(log_b n) ana teoremde karşımıza çıkar
log_3 n = log_2 n / log_2 3 taban yalnız sabit bir çarpanı değiştirirTaban ve tavan
Bir dizi ikiye bölündüğünde yarılarda ⌊n/2⌋ ve ⌈n/2⌉ öğe bulunur; Java'da n / 2 pozitif sayılar için tabanı verir. Taban ve tavan ikili aramanın orta indisinde, heap'teki ebeveyn indisinde, ikili ağacın yüksekliğinde ve yaklaşım oranlarında karşımıza çıkar.
Neden önemliBirleştirme sıralamasının bölme adımı, ikili aramanın orta indisi ve heap'in indis hesapları taban ve tavanı kullanır.
Kontrol sorusu
Java'da −7 / 2 kaçtır? ⌊−7/2⌋ kaçtır?
Java −3 verir (sıfıra doğru keser), oysa ⌊−3,5⌋ = −4'tür. Negatif sayılarda tabanı Math.floorDiv verir.
⌊7/2⌋ = 3 ⌈7/2⌉ = 4 ⌊n/2⌋ + ⌈n/2⌉ = n
n düğümlü heap'in yüksekliği ⌊log2 n⌋: n = 10 → 3
Java: 7 / 2 == 3, (7 + 2 − 1) / 2 == 4 pozitif a, b için: ⌈a/b⌉ = (a + b − 1) / bAsimptotik büyüme
Büyük n için baskın terim belirleyicidir: 3n² + 100n + 7 = Θ(n²). Büyüme sınıflarını sıralayabilmek ve saniyede kabaca 10⁸–10⁹ basit işlem varsayarak hangi karmaşıklığın hangi n için uygulanabilir olduğunu kestirebilmek gerekir. O üst sınır (upper bound), Ω alt sınır (lower bound), Θ ise sıkı sınırdır (tight bound).
Neden önemliHer bölüm algoritmaları karmaşıklıklarına göre karşılaştırır; büyüme sınıfları hangi yöntemin hangi girdi boyutuna uygun olduğunu belirler.
Kontrol sorusu
Sonunda hangisi daha hızlı büyür: n¹⁰⁰ mü, 1,01ⁿ mi?
1,01ⁿ; tabanı 1'den büyük her üstel fonksiyon sonunda her polinomu geçer.
n = 10^6 için yaklaşık işlem sayıları
n log2 n ≈ 2 · 10^7 → bir saniyenin altında
n² = 10^12 → saatler
2^n : n = 60 bile ≈ 10^18 eder → uygulanamazYineleme bağıntıları
Özyinelemeli bir algoritmanın çalışma süresi kendi cinsinden yazılır: birleştirme sıralaması iki yarıyı çözer ve doğrusal sürede birleştirir, bu yüzden T(n) = 2T(n/2) + n olur. Bir bağıntıyı açarak ya da özyineleme ağacının her düzeyindeki işi toplayarak çözmeye alışık olmak, ana teoremi izlemeyi çok kolaylaştırır.
Neden önemliYineleme bağıntıları ana teoremle çözülür; her böl ve fethet algoritması bir bağıntıyla analiz edilir.
Kontrol sorusu
İkili aramanın yineleme bağıntısı ve çözümü nedir?
T(n) = T(n/2) + O(1); çözümü Θ(log n)'dir.
T(n) = 2T(n/2) + n
düzey 0: n = n
düzey 1: n/2 + n/2 = n
düzey 2: 4 · n/4 = n
… log2 n düzey ⇒ T(n) = Θ(n log n)
T(n) = T(n − 1) + 1 ⇒ Θ(n) T(n) = 2T(n − 1) + 1 ⇒ Θ(2^n)Olasılık ve sayma
Arama uzaylarının büyüklüğünü ve rastgele algoritmaların davranışını ölçmek için.
Kombinatorik: permütasyonlar ve kombinasyonlar
Kaba kuvvetin, geri izlemenin ve dal sınırın maliyeti arama uzayının büyüklüğüdür; bunu saymak için çarpma kuralı, n! permütasyon, C(n, k) kombinasyon ve 2ⁿ alt küme gerekir. Örneğin n şehirli TSP'de başlangıç şehri sabitlenince (n − 1)! tur vardır.
Neden önemliPermütasyon üretme, TSP'nin kaba kuvvet çözümü ve n-vezir arama ağacının büyüklüğü sayarak bulunur.
Kontrol sorusu
8 × 8 bir tahtaya her satırda bir vezir olacak biçimde 8 vezir kaç yolla yerleştirilir? Sütunlar da farklı olmak zorundaysa kaç yolla?
8⁸ = 16.777.216 yolla; sütunlar da farklıysa 8! = 40.320 yolla.
P(n, k) = n! / (n − k)! C(n, k) = n! / (k! · (n − k)!)
C(5, 2) = 10 5! = 120 2^10 = 1024
n = 10 şehir: 9! = 362.880 tur n = 20 şehir: 19! ≈ 1,2 · 10^17 turOlasılığın temelleri
Rastgele algoritmaların başarı ve hata olasılıklarını hesaplamak için örnek uzay, olay, tümleyen, bağımsız olaylar ve koşullu olasılık gerekir. Önemli bir kalıp: tek bir deneme p olasılıkla başarısız oluyorsa, k bağımsız denemenin hepsi p^k olasılıkla başarısız olur; Monte Carlo algoritmalarının hatası böyle küçültülür.
Neden önemliMiller–Rabin testinin ve Karger algoritmasının hata analizi tam olarak bu kalıbı kullanır.
Kontrol sorusu
Bir algoritma tek çalıştırmada doğru yanıtı 1/2 olasılıkla buluyor. 10 bağımsız çalıştırmadan en az birinin doğru yanıtı bulma olasılığı nedir?
1 − (1/2)¹⁰ = 1023/1024 ≈ 0,999.
P(A ∪ B) = P(A) + P(B) − P(A ∩ B)
A ve B bağımsız ⇔ P(A ∩ B) = P(A) · P(B)
Miller–Rabin: tur başına hata ≤ 1/4 ⇒ 20 turdan sonra ≤ (1/4)^20 ≈ 9 · 10^−13Beklenen değer ve beklenen değerin doğrusallığı
Rastgele hızlı sıralamanın beklenen O(n log n) çalışma süresi gibi sonuçlar beklenen değer (expected value) olarak ifade edilir. Beklenen değerin doğrusallığı, E[X + Y] = E[X] + E[Y], değişkenler bağımlı olsa bile geçerlidir; karmaşık bir sayımı 0/1 gösterge değişkenlerinin toplamına ayırıp olasılıklarını toplamak standart bir tekniktir.
Neden önemliRastgele hızlı sıralamanın, QuickSelect'in ve rastgele sayfalamanın analizleri beklenen değerle yapılır.
Kontrol sorusu
Rastgele hızlı sıralamanın en kötü durumu O(n²)'dir. Neden “beklenen O(n log n)” denir?
Pivot rastgele seçildiği için çalışma süresi bir rastgele değişkendir; her girdi için ortalaması O(n log n)'dir ve O(n²) yalnız çok küçük bir olasılıkla ortaya çıkar.
Zar: E[X] = (1 + 2 + … + 6) / 6 = 3,5
n öğenin rastgele bir permütasyonunda yerinde kalan öğe sayısı X:
X = X1 + … + Xn, Xi = 1 (i. öğe yerinde kalırsa), P(Xi = 1) = 1/n
E[X] = n · (1/n) = 1
Başarı olasılığı p olan bir denemeyi ilk başarıya kadar tekrarlamak: E[deneme sayısı] = 1/pDiğer matematik ve kavramlar
Belirli bölümlerde kullanılan matrisler, modüler aritmetik, bit işlemleri, optimizasyon ve eş zamanlılığın temelleri.
Matris işlemleri
İki n × n matrisin doğrudan çarpımı, iç içe üç döngüde n³ çarpma yapar; Strassen bu sayıyı blok matrislerle azaltır. Komşuluk matrisleri, Floyd-Warshall'ın uzaklık tablosu ve kuvvet yinelemesindeki (power iteration) matris–vektör çarpımı için satır–sütun çarpımını, birim matrisi ve bir matrisi bloklara bölmeyi bilmek gerekir.
Neden önemliMatris çarpımı karmaşıklık analizindeki O(n³) örneği, Strassen algoritmasının konusu ve kuvvet yinelemesinin temel adımıdır.
Kontrol sorusu
[[1, 2], [3, 4]] · [[0, 1], [1, 0]] çarpımı nedir?
[[2, 1], [4, 3]]; bu permütasyon matrisiyle sağdan çarpmak sütunların yerini değiştirir.
static int[][] multiply(int[][] a, int[][] b) {
int n = a.length;
int[][] c = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j]; // toplam n³ çarpma
return c;
}
int[][] c = multiply(new int[][] {{1, 2}, {3, 4}}, new int[][] {{0, 1}, {1, 0}});
System.out.println(Arrays.deepToString(c)); // [[2, 1], [4, 3]]Düzlem geometrisi ve uzaklık ölçüleri
Düzlemdeki iki nokta arasındaki Öklid uzaklığı √((x₁ − x₂)² + (y₁ − y₂)²), ızgarada yalnız yatay ve dikey adımlarla ölçülen Manhattan uzaklığı ise |x₁ − x₂| + |y₁ − y₂|'dir. Bir uzaklık ölçüsü üçgen eşitsizliğini sağlıyorsa d(a, c) ≤ d(a, b) + d(b, c) olur: üçüncü bir noktaya uğramak yolu hiçbir zaman kısaltmaz. A'dan B'ye ve A'dan P'ye giden vektörlerin çapraz çarpımı (B.x − A.x)(P.y − A.y) − (B.y − A.y)(P.x − A.x) tam sayılarla hesaplanır; işareti P'nin AB doğrusunun solunda mı, sağında mı, yoksa üzerinde mi olduğunu söyler. Uzaklıkları yalnız karşılaştırmak için karekök almaya gerek yoktur, karelerini karşılaştırmak aynı sonucu verir.
Neden önemliA* algoritmasının sezgiselleri Öklid ve Manhattan uzaklığıdır; dışbükey örtü yönelim testine, en yakın nokta çifti Öklid uzaklığına, metrik TSP'nin 2-yaklaşımı üçgen eşitsizliğine dayanır.
Kontrol sorusu
A = (0, 0) ve B = (3, 4) için Öklid ve Manhattan uzaklıkları nedir? P = (1, 5) noktası AB doğrusunun hangi tarafındadır?
Öklid uzaklığı √(9 + 16) = 5, Manhattan uzaklığı 3 + 4 = 7'dir. Çapraz çarpım 3 · 5 − 4 · 1 = 11 > 0 olduğu için P, A'dan B'ye bakıldığında doğrunun solundadır.
static double oklid(int x1, int y1, int x2, int y2) {
return Math.hypot(x1 - x2, y1 - y2);
}
static int manhattan(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
static long capraz(int ax, int ay, int bx, int by, int px, int py) {
return (long) (bx - ax) * (py - ay) - (long) (by - ay) * (px - ax);
}
System.out.println(oklid(0, 0, 3, 4)); // 5.0
System.out.println(manhattan(0, 0, 3, 4)); // 7
System.out.println(capraz(0, 0, 3, 4, 1, 5)); // 11 (P solda)Modüler aritmetik ve OBEB
Hash fonksiyonları, Rabin-Karp'ın kayan hash'i, sözde rastgele sayı üreteçleri ve Miller–Rabin testi modüler aritmetikle çalışır. Toplama ve çarpmaların her adımında kalanı almanın sonucu değiştirmediğini, OBEB'in Öklid algoritmasıyla nasıl hesaplandığını ve asal sayının tanımını bilmek gerekir.
Neden önemliÖklid algoritması, kayan hash, Miller–Rabin ve sözde rastgele sayılar modüler aritmetik kullanır.
Kontrol sorusu
(17 · 23) mod 5 değeri, çarpmadan önce kalanlar alınarak nasıl hesaplanır?
17 mod 5 = 2 ve 23 mod 5 = 3; 2 · 3 = 6 ve 6 mod 5 = 1.
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
System.out.println(gcd(48, 18)); // 6
long M = 1_000_000_007L, h = 0;
for (char c : "abc".toCharArray()) h = (h * 31 + c) % M; // kayan hash'in temeli
System.out.println(h); // 96354İkili sayılar ve bit işlemleri
Bilgisayarlar sayıları ikili tabanda saklar; 2'nin kuvvetleri, kaydırmalar ve maskeler pek çok algoritmayı kısaltır. Bir tam sayının bitleri bir alt kümeyi gösterebilir; 1 << k ifadesi 2^k değerini verir, x & (x − 1) ise en düşük 1 bitini sıfırlar. n-vezir probleminde O(1) güvenlik testi ve küçük n için bütün alt kümeler üzerinde gezinmek bit maskeleriyle yapılır.
Neden önemliBasamak sıralaması basamak basamak çalışır; n-vezir çözümü bit maskeleri kullanır.
Kontrol sorusu
13'ün ikili gösterimi nedir? 13 >> 1 ve 13 & 1 kaçtır?
1101₂; 13 >> 1 = 6 (110₂) ve 13 & 1 = 1 (sayı tektir).
int n = 3;
for (int mask = 0; mask < (1 << n); mask++) { // 2³ = 8 alt küme
StringBuilder s = new StringBuilder("[");
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) != 0) s.append(i);
System.out.print(s.append("] "));
}
// [] [0] [1] [01] [2] [02] [12] [012]
System.out.println((16 & (16 - 1)) == 0); // true: 16, 2'nin bir kuvvetidirKarar ve optimizasyon problemleri
Açgözlü, dinamik programlama, yaklaşım ve dal sınır algoritmaları optimizasyon problemlerini çözer: kısıtları sağlayan çözümler (olurlu çözümler) arasından amaç fonksiyonunu en büyük ya da en küçük yapanı ararız. Aynı problemin karar biçimi (“değeri en az K olan bir çözüm var mı?”) P, NP ve NP-tamlık tartışmasında kullanılır. Bir enbüyükleme probleminde her olurlu çözümün değeri, optimum için bir alt sınırdır.
Neden önemliSırt çantası problemi, NP-zorluk, yaklaşım oranları ve dal sınırdaki sınırlar hep bu dille ifade edilir.
Kontrol sorusu
Bir enbüyükleme probleminde açgözlü bir algoritma değeri 40 olan olurlu bir çözüm buluyor; kesirli gevşetmenin değeri 46. Optimum hangi aralıktadır?
40 ≤ OPT ≤ 46: olurlu çözüm bir alt sınır, gevşetme bir üst sınır verir.
0/1 sırt çantası, kapasite W = 5
eşyalar (ağırlık, değer): 1 = (2, 3), 2 = (3, 4), 3 = (4, 5)
olurlu: {1, 2} → ağırlık 5, değer 7 olurlu değil: {2, 3} → ağırlık 7
optimizasyon: en büyük değer nedir? → 7
karar: değeri ≥ 8 olan olurlu bir seçim var mı? → hayırEş zamanlılığın temelleri
Paralel algoritmalar bölümü, işin birkaç iş parçacığına (thread) nasıl bölündüğünü ve sonuçların nasıl birleştirildiğini Java ile gösterir. İş parçacığının ne olduğunu, aynı değişkeni korumasız güncelleyen iki iş parçacığının yarış durumuna (race condition) yol açtığını ve programın sıralı kısmının hızlanmayı sınırladığını sezgisel olarak bilmek yeterlidir.
Neden önemliYarış durumu, fork/join ile paralel sıralama ve Amdahl yasası bu fikirlerin üzerine kurulur.
Kontrol sorusu
Bir programın %20'si sıralı kalıyorsa, sınırsız sayıda işlemciyle elde edilebilecek en büyük hızlanma nedir?
1 / 0,2 = 5 kat (Amdahl yasası).
final AtomicInteger counter = new AtomicInteger();
Runnable job = () -> { for (int i = 0; i < 100_000; i++) counter.incrementAndGet(); };
Thread t1 = new Thread(job), t2 = new Thread(job);
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(counter.get()); // her zaman 200000; korumasız int++ daha az verebilirArama ve süzgece uyan konu yok.