Diziler, toplamlar, kardinalite ve algoritmalara giriş

Bu hafta üç ayrı konu bir arada: diziler ve toplamlar (sequences and sums), kümelerin büyüklüğü (cardinality) ve algoritmalara giriş. Vizede toplam hesabı kesin bir puan kaynağıdır: hesap makinesi yok, o yüzden sayılar elle hesaplanacak kadar küçük olur ve formülleri bilmek yeter. Kardinaliteden genelde “bu küme sayılabilir mi, bijection ver” türü kısa bir parça gelir. Algoritmalar kısmı gelecek haftanın Big-O konusunun zemini: sözde kodu okuyup izlemeyi (trace) öğreneceksin.

Altın kurallar:

1. Toplamı parçala: $\sum (ak + b) = a\sum k + \sum b$.
2. Alt sınır 1 değilse: 1’den üst sınıra topla, 1’den (alt sınır − 1)‘e kadarını çıkar.
3. Geometrik toplamda terim sayısını say. $j = 0..n$ ise $n + 1$ terim.
4. Sayılabilir = elemanları 1., 2., 3. diye tek tek sıralayabiliyorum.
5. Algoritma izlerken her değişkeni tabloya yaz. Kafadan yapma.

Diziler (sequences)

Dizi: tam sayılardan (genelde $\{0, 1, 2, \dots\}$ ya da $\{1, 2, 3, \dots\}$) bir kümeye fonksiyon. $n$‘inci terimi $a_n$.

Bir yineleme bağıntısını (recurrence relation) çözmek, $a_n$‘yi sadece $n$ cinsinden yazan bir closed formula bulmak demektir. Basit yöntem iterasyon: birkaç terimi yaz, kalıbı gör, tümevarımla doğrula. $a_n = a_{n-1} + 3$, $a_0 = 5$ için $a_n = 5 + 3n$.

Terimlerden formül bulma sırası: farklar sabit mi (aritmetik)? Oranlar sabit mi (geometrik)? Kareler, küpler, $2^n$, $n!$ ile karşılaştır. Her terim öncekinin iki katı artı bir mi?

Toplamlar (summations)

$\sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n$

$k$ index of summation, $m$ alt sınır, $n$ üst sınır. İndeksin adı önemsiz: $\sum_{k=1}^5 k^2 = \sum_{j=1}^5 j^2$.

Ezber formüller

Geometrik formülün neden doğru olduğunu bir kere gör: $S = a + ar + \dots + ar^n$. $rS = ar + \dots + ar^{n+1}$. Çıkar: $rS - S = ar^{n+1} - a$, yani $S = \tfrac{a(r^{n+1} - 1)}{r - 1}$. Ortadaki bütün terimler birbirini götürdü.

İndeks kaydırma (shifting the index)

$\sum_{k=4}^{8} k^2$‘yi $j = k - 3$ ile yaz: $k = 4 \Rightarrow j = 1$, $k = 8 \Rightarrow j = 5$, terim $(j + 3)^2$.

$\sum_{k=4}^{8} k^2 = \sum_{j=1}^{5} (j+3)^2 = 16 + 25 + 36 + 49 + 64 = 190.$

Daha hızlısı: $\sum_{1}^{8} k^2 - \sum_{1}^{3} k^2 = 204 - 14 = 190$.

Çift toplam ve çarpım

Çift toplamda iç toplamı önce hesapla (dış indeks sabitmiş gibi davran), sonra dış toplamı. Bu, iç içe iki for döngüsüyle aynı:

total := 0
for i := 1 to 3
    for j := 1 to 4
        total := total + (2i − j)

Çarpım gösterimi: $\prod_{i=1}^{4} 2i = 2 \cdot 4 \cdot 6 \cdot 8 = 384$. $n! = \prod_{i=1}^{n} i$.

TUZAK · $\sum_{k=m}^{n}$‘de terim sayısı. $k = 10$‘dan $30$‘a kadar $30 - 10 + 1 = 21$ terim var, 20 değil. Sabit terimin toplamında bu fark puan kaybettirir: $\sum_{k=10}^{30} 2 = 42$.

Kardinalite (cardinality)

Sonlu kümelerde büyüklük eleman sayısıdır. Sonsuz kümeleri karşılaştırmak için sayamazsın; bunun yerine eşleştirirsin. $\lvert A \rvert = \lvert B \rvert$ ancak $A$‘dan $B$‘ye bir bijection varsa.

• Countable (sayılabilir): sonlu ya da $\mathbb{Z}^+$ ile aynı kardinalitede (countably infinite). Elemanlarını $a_1, a_2, a_3, \dots$ diye, hiçbirini atlamadan listeleyebilirsin.
• Uncountable (sayılamaz): sayılabilir değil.

Sonsuz otel sezgisi: stadyumda $1, 2, 3, \dots$ diye numaralanmış sonsuz koltuk var. Kümenin her elemanına bir koltuk verebiliyorsan (kimse açıkta kalmadan, iki kişi aynı koltuğa oturmadan) küme sayılabilir.

Sayılabilir kümeler

• Pozitif çift sayılar: $f(n) = 2n$. Sonsuz bir küme kendi öz alt kümesiyle aynı büyüklükte olabilir; sonlu kümelerde bu imkânsız.
• $\mathbb{Z}$: sırayla $0, 1, -1, 2, -2, 3, -3, \dots$ listele (soru 8’deki fonksiyon).
• Pozitif rasyoneller $\mathbb{Q}^+$: $p/q$‘ları $p + q$ toplamına göre grupla. Her grup sonlu. Sadeleşmeyen kesirleri sırayla yaz, tekrar edenleri atla:

p+q = 2:  1/1
p+q = 3:  1/2, 2/1
p+q = 4:  1/3, 3/1           (2/2 = 1/1 atlandı)
p+q = 5:  1/4, 2/3, 3/2, 4/1
p+q = 6:  1/5, ...
Liste: 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, ...

Sayılabilir iki kümenin birleşimi ve sonlu ya da sayılabilir sayıda sayılabilir kümenin birleşimi sayılabilir.

$\mathbb{R}$ sayılamaz: Cantor’un köşegen yöntemi

Teorem: $(0, 1)$ aralığı sayılamaz (o yüzden $\mathbb{R}$ de).

Kanıt fikri (çelişki ile): $(0, 1)$‘deki bütün sayıların bir listesi olduğunu varsay. Listenin $i$‘inci sayısının $i$‘inci ondalık basamağına bak. Yeni bir sayı kur: $i$‘inci basamak, $i$‘inci sayının $i$‘inci basamağı 5 değilse 5, 5 ise 4. Bu sayı listedeki her sayıdan en az bir basamakta farklı, yani listede yok. Çelişki.

r1 = 0.[3]1415          köşegen basamakları: 3, 7, 1, 2, 4
r2 = 0.2[7]182          hiçbiri 5 değil → hepsini 5 yap
r3 = 0.14[1]42          yeni sayı: 0.55555...
r4 = 0.577[2]1          r_i'den i'inci basamakta farklı
r5 = 0.6931[4]

(Gerçek ispatta liste sonsuz ve her sayının sonsuz basamağı var; 5 ve 4 seçmek 0.4999… = 0.5 gibi çift gösterim sorununu önler.)

Sonuçlar: irrasyonel sayılar sayılamaz, $\mathcal{P}(\mathbb{Z}^+)$ sayılamaz. Bir alt kümesi sayılamaz olan küme de sayılamazdır.

Algoritmalara giriş

Algoritma: bir problemi çözmek için sonlu, kesin adımlar dizisi. Özellikleri: input, output, definiteness (her adım net), correctness (doğru sonuç), finiteness (sonlu adımda biter), effectiveness (her adım yapılabilir), generality (bir problem sınıfının tümüne uygulanır).

Maksimum bulma

procedure max(a1, a2, ..., an: integers)
max := a1
for i := 2 to n
    if max < ai then max := ai
return max

İz: 4, 9, 2, 11, 7 için max sırasıyla 4, 9, 9, 11, 11. Her eleman bir kez karşılaştırılır: $n - 1$ karşılaştırma.

Doğrusal arama ve ikili arama

Linear search: baştan sona tek tek bak. Liste sırasız olabilir. En kötü durumda $n$ elemanla karşılaştırma.

Binary search: liste sıralı olmalı. Her adımda aralığı ikiye böler:

procedure binary search(x: integer, a1 < a2 < ... < an)
i := 1; j := n
while i < j
    m := ⌊(i + j)/2⌋
    if x > am then i := m + 1
    else j := m
if x = ai then location := i else location := 0
return location

İz: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 listesinde $x = 72$:

Her turda aralık yarıya indiği için yaklaşık $\log_2 n$ tur yeter. 1.000.000 elemanda bile 20 civarı.

Sıralama: bubble sort ve insertion sort

Bubble sort: komşu elemanları karşılaştır, sıra bozuksa yer değiştir. Her geçişin sonunda en büyük kalan eleman sona yerleşir.

3, 2, 4, 1, 5
pass 1:  2, 3, 1, 4, 5      (5 zaten yerinde, 4 yerine oturdu)
pass 2:  2, 1, 3, 4, 5
pass 3:  1, 2, 3, 4, 5

Karşılaştırma sayısı her durumda $(n-1) + (n-2) + \dots + 1 = \tfrac{n(n-1)}{2}$.

Insertion sort: soldaki kısmı sıralı tut, sıradaki elemanı doğru yere sok. Kâğıt oyununda eldeki kartları dizmek gibi.

Açgözlü algoritma (greedy algorithm)

Her adımda o an en iyi görünen seçimi yap. Para üstü: sığan en büyük madeni parayı ver. 25, 10, 5, 1 sentlik paralarla açgözlü algoritma her zaman en az parayı verir (bu ispatlanabilir). Ama para seti değişince bozulabilir: 25, 10, 1 ile 30 sent için açgözlü 6 para verir, oysa 3 tane 10’luk yeter. “Açgözlü algoritma optimal mi?” sorusuna cevap ya ispat ya karşı örnektir.

Sık yapılan hatalar