Bin Sayfalık Sözlükte Bir Kelime
1.000 sayfalık basılı bir sözlükte "pergel" kelimesini arıyorsunuz. Birinci sayfadan başlayıp tek tek çevirmek işe yarar ama en kötü durumda 1.000 sayfaya bakarsınız. Kimse böyle yapmaz. Sözlüğü ortadan açar, "p" harfinin önde mi arkada mı kaldığına bakar, yarısını gözden çıkarırsınız.
Her bakışta aday sayfa sayısı yarıya iner: 1.000, 500, 250, 125, … . $2^{10} = 1.024$ olduğu için en çok 10 bakışta kelimeye ulaşırsınız. İlk yönteme doğrusal arama, ikincisine ikili arama denir. İkinci yöntemin bir ön şartı var: liste sıralı olmalı. Karışık dizilmiş bir sözlükte ortadan açmanın hiçbir anlamı yoktur.
Az önce yaptığınız şey bir algoritmaydı: bir problemi çözmek için izlenen, sayısı sonlu, sırası belli ve her adımı açık olan işlemler dizisi. Aynı problem için birden çok algoritma yazılabilir; hangisinin daha iyi olduğunu adım sayısı söyler.
Akış Şemasının Dili
Algoritmalar çoğu zaman şekillerle çizilir:
- Elips (oval): başla / bitir
- Paralelkenar: veri girişi ya da çıktı
- Dikdörtgen: işlem ($c \leftarrow a + b$ gibi)
- Eşkenar dörtgen: karar; her zaman iki çıkışı vardır, "evet" ve "hayır"
Bir sayının işaretini söyleyen algoritmayı düşünün. "$x > 0$ ise pozitif yaz" adımı tek başına eksiktir: $x = -4$ ya da $x = 0$ girilirse algoritma ne yapacağını bilmez. Kararların bütün durumları kapsaması gerekir: $x > 0$ ise "pozitif", değilse $x = 0$ mı diye ikinci karar; evet ise "sıfır", hayır ise "negatif".
Döngüyü Kâğıt Üstünde Çalıştırmak
Aşağıdaki algoritma ne yazdırır?
$i \leftarrow 1$, $t \leftarrow 0$; $i \leq 4$ olduğu sürece: $t \leftarrow t + i$, $i \leftarrow i + 1$; sonunda $t$'yi yaz.
Kafadan tahmin etmek yerine bir izleme tablosu tutun:
| Tur | $i$ (başta) | $t$ (sonda) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 3 | 6 |
| 4 | 4 | 10 |
Dördüncü turun sonunda $i = 5$ olur, koşul bozulur ve döngü biter. Çıktı: 10. Döngünün bitiş koşulu yazılmasaydı $i$ sonsuza kadar artar, algoritma hiç sonlanmazdı; bu da "sonluluk" özelliğini bozar.
Bir de değer takası: $a = 3$, $b = 5$ iken iki değeri yer değiştirmek istiyoruz. Sık yapılan hata doğrudan $a \leftarrow b$, $b \leftarrow a$ yazmaktır. İlk adımda $a$ 5 olur, 3 kaybolur; ikinci adımda $b$ yine 5 alır. Doğrusu geçici bir kutu kullanmak: $t \leftarrow a$, $a \leftarrow b$, $b \leftarrow t$. Sonuç $a = 5$, $b = 3$.
En Küçüğü Bul, Başa Al
5, 2, 9, 1 listesini küçükten büyüğe dizen bir yöntem: kalan kısmın en küçüğünü bul, kalan kısmın başına al, tekrarla.
- En küçük 1; 5 ile yer değiştir: 1, 2, 9, 5
- Kalan 2, 9, 5 içinde en küçük 2; zaten başta: 1, 2, 9, 5
- Kalan 9, 5 içinde en küçük 5; 9 ile yer değiştir: 1, 2, 5, 9
Liste sıralandı. Bu yönteme seçerek sıralama denir. Sıralanmış bir liste, ilk bölümdeki ikili aramanın kullanılabilmesini sağlar; iki algoritma birbirini tamamlar.
Karar Kutusundaki Mantık: Önermeler
Akış şemasındaki her karar, doğru (D) ya da yanlış (Y) olan bir önermedir. $p$: "$5 > 3$" (D) ve $q$: "$2 > 7$" (Y) olsun.
- $p \wedge q$ ("ve"): ikisi de doğruysa doğrudur. Burada Y.
- $p \vee q$ ("veya"): en az biri doğruysa doğrudur. Burada D.
- $p \Rightarrow q$ ("ise"): yalnız D ⇒ Y durumunda yanlıştır. Burada Y.
Niceleyiciler: $\forall$ "her", $\exists$ "en az bir" demektir. $\forall x \in \mathbb{R},\ x^2 \geq 0$ doğrudur. $\exists x \in \mathbb{N},\ x + 3 = 1$ yanlıştır, çünkü tek aday $x = -2$ doğal sayı değildir.
Olumsuzlamada sık yapılan hata: "Bütün öğrenciler kitap okudu" önermesinin değili "Hiçbir öğrenci kitap okumadı" değildir. Önermeyi yanlış yapmak için tek bir okumayan öğrenci yeter: doğru olumsuzlama "Bazı öğrenciler kitap okumadı" olur. "Her" olumsuzlanınca "en az bir", "en az bir" olumsuzlanınca "hiçbir" gelir.
Harf Kaydırarak Şifrelemek
Eski ama öğretici bir algoritma: her harfi alfabede belirli sayıda ileri kaydır. Türk alfabesinde (29 harf) iki sıra ileri kaydırınca A → C, L → N olur; "ALA" kelimesi "CNC" biçiminde yazılır. Z'den sonra başa dönülür: Y → A, Z → B.
Şifreyi çözmek için aynı adımlar ters yönde uygulanır. Anahtar (kaydırma sayısı) bilinmiyorsa en fazla 28 deneme yeter; bu yüzden bu yöntem bugün güvenli sayılmaz. Bilgisayar her harfi ikilik sistemde saklar: örneğin 13 sayısı $8 + 4 + 1$ olduğu için $1101_{(2)}$ yazılır.
Sınav ipucu: Döngü sorularında cevabı tahmin etmeyin, tablo kurun ve koşulun hangi turda bozulduğunu işaretleyin. Önerme sorularında "ise" bağlacını görünce tek yanlış satırı (D ⇒ Y) hatırlayın; öbür üç satırın hepsi doğrudur.
Sık sorulanlar
Algoritmanın sonlu olması ne demektir?
Adımların sayısının belli olması ve algoritmanın er geç durmasıdır. Bitiş koşulu olmayan döngü bu özelliği bozar.
İkili arama neden daha hızlıdır?
Her karşılaştırmada aday sayısını yarıya indirir. 1.000 kayıtlık sıralı bir listede en çok 10 karşılaştırma yeter, çünkü 2¹⁰ = 1.024.
"Bütün öğrenciler geldi" önermesinin olumsuzu nedir?
"Bazı öğrenciler gelmedi." Önermeyi yanlış yapmak için gelmeyen bir öğrenci yeterlidir; "hiçbir öğrenci gelmedi" demek fazlasını iddia eder.
Akış şemasında karar hangi simgeyle gösterilir?
Eşkenar dörtgenle. Bu simgeden "evet" ve "hayır" olmak üzere iki çıkış bulunur.