İleri Algoritmalar · Ön Bilgiler

İleri Algoritmalar İçin Ön Bilgiler

İleri Algoritmalar dersi Algoritmalar dersinin devamıdır; karmaşıklık analizi, sıralama, arama, çizge ve dizgi algoritmaları bilindiği varsayılır. Ders 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 20 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.

Diziler ve iki boyutlu diziler

0'dan başlayan indis · length · int[][]

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 önemli

Sı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.

Örnek (Java)
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]);      // 5

Özyineleme ve çağrı yığını

taban durum · özyinelemeli çağrı · derinlik

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 önemli

Hı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.

Örnek (Java)
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

class · Comparable · Comparator · generics

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 önemli

Aç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.

Örnek (Java)
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);                // 7

Java koleksiyonları

ArrayList · HashMap · ArrayDeque · PriorityQueue

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 önemli

BFS bir kuyrukla, Dijkstra bir öncelikli kuyrukla, bellekleme bir eşlemeyle (map) yazılır.

Kullanıldığı yerlerBölüm 3 · Bellekleme İzleme

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.

Örnek (Java)
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 55

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

düğüm · next · başa O(1) ekleme

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 önemli

Zincirlemeli hash tabloları ve O(1) LRU önbelleği bağlı liste kullanır.

Kullanıldığı yerlerBölüm 8 · LRU: O(1) Uygulama

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.

Örnek (Java)
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 + " ");

Heap ve öncelikli kuyruklar

tam ikili ağaç · dizi yerleşimi · O(log n)

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 önemli

Heap 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.

Örnek
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)

Ağaçlar ve ikili arama ağaçları

kök · ebeveyn · çocuk · yaprak · yükseklik

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 önemli

BFS ağacı, kapsayan ağaçlar, trie'ler ve durum uzayı ağaçları aynı terimlerle anlatılır.

Kullanıldığı yerlerBölüm 4 · Durum Uzayı Ağacı

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).

Örnek
        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

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

∪ ∩ \ · |A| · f: A → B · bağıntı

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 önemli

Kesim özelliği, Floyd-Warshall'ın geçişli kapanışı ve dal sınırdaki olurlu çözümler kümelerle tanımlanır.

Kullanıldığı yerlerBölüm 5 · Temel Kavramlar

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.

Örnek
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.

İspat teknikleri: doğrudan ispat, çelişki, karşı örnek

doğrudan ispat · çelişkiyle ispat · 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 önemli

Aç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.

Örnek
İ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.

Analiz araçları

Çalışma sürelerini hesaplamak için toplamlar, logaritmalar ve büyüme hızları.

Toplam gösterimi ve seriler

aritmetik · geometrik · harmonik

İç 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 teriminin mertebesindedir; harmonik seri logaritmik büyür.

Neden önemli

Dö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).

Örnek
Σ (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ı

log₂ n · üs kuralları · taban değiştirme

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.

Kullanıldığı yerlerBölüm 1 · Karatsuba Analizi

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⁹.

Örnek
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ştirir

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

çarpma kuralı · n! · C(n, k) · 2ⁿ

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 önemli

Permü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.

Örnek
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 tur

Olasılığın temelleri

örnek uzay · bağımsızlık · koşullu olasılık

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 önemli

Miller–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.

Örnek
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^−13

Beklenen değer ve beklenen değerin doğrusallığı

rastgele değişken · E[X] · gösterge değişkeni

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 önemli

Rastgele 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.

Örnek
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/p

Diğ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

satır–sütun çarpımı · birim matris · blok biçim

İ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 önemli

Matris ç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.

Örnek (Java)
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

Öklid uzaklığı · Manhattan uzaklığı · üçgen eşitsizliği · çapraz çarpım

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 önemli

A* 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.

Örnek (Java)
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

a mod m · (a · b) mod m · OBEB · asal sayı

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.

Kullanıldığı yerlerBölüm 7 · Miller–Rabin: Kod

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.

Örnek (Java)
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

& | ^ ~ << >> · 2'nin kuvvetleri · alt küme maskeleri

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 önemli

Basamak sıralaması basamak basamak çalışır; n-vezir çözümü bit maskeleri kullanır.

Kullanıldığı yerlerBölüm 4 · O(1) Güvenlik Testi

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).

Örnek (Java)
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 kuvvetidir

Karar ve optimizasyon problemleri

amaç fonksiyonu · kısıt · olurlu çözüm · alt/üst sınır

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 önemli

Sı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.

Örnek
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ır

Eş zamanlılığın temelleri

iş parçacığı · paylaşılan değişken · eş zamanlama

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 önemli

Yarış 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ı).

Örnek (Java)
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 verebilir