Algoritmalar · Ünite 1

Algoritmalar: Temel Kavramlar

1. Algoritma nedir?

Algoritma, bir problemi çözmek ya da bir hesabı yapmak için yazılmış, sırası belli ve sonu olan adımlar listesi. Veriyi girdi olarak alır, adımları uygular, sonunda bir çıktı verir. Bilgisayar programı da aslında bu adımların bilgisayarın çalıştırabileceği hâlidir.

Girdi → kurallar → çıktı. Örnek: bir sayı listesini sıralamak.

Sayılarla ifade edilebilen problemlere hesaplamalı problem denir. «Bu listeyi küçükten büyüğe diz» tipik bir örnek; bu işi yapan algoritmalara sıralama algoritması denir.

Örnek: çıkararak bölme

Bölme aslında art arda çıkarmadır. 23'ü 4'e bölelim: 23'ten 4 çıkar (19), bir daha (15), bir daha (11), (7), (3). 5 kez çıkarabildik, geriye 3 kaldı → bölüm 5, kalan 3. Algoritma şöyle yazılır:

→Bölüneni, böleni al; bölümü 0 yap.
→Bölen 0 ise «sıfıra bölme hatası» yaz ve dur.
→Bölünen bölenden büyük ya da eşit olduğu sürece: bölünenden böleni çıkar, bölümü 1 artır.
→Bölümü ve kalanı (son bölüneni) yaz, dur.

Üçüncü adımdaki gibi bir şart sağlandığı sürece tekrar eden kod parçasına döngü denir.

Kısa tarihçe

→Babil ve Mısır matematikçileri binlerce yıl önce bölme için adım adım yöntemler kullanıyordu.
→Antik Yunan: asal sayılar için Eratosten Kalburu, en büyük ortak bölen için Öklid algoritması.
→9. yüzyıl: Kindî, şifre kırmak için harf sıklığı analizini kullandı.
→Kelimenin kökü: 9. yüzyılda Harezm'de yaşamış el-Harezmî. Cebir kitabı, bilinen ilk algoritma derlemesi sayılır.
→Modern tanım: Hilbert'in 1928'de sorduğu karar problemiyle başladı. Church'ün Lambda Cebiri ve Turing Makinesi (1936) bu çabanın ürünleri.

2. İyi bir algoritmanın altı özelliği

Özellik	Ne demek?
Girdi	Hangi veriyle çalışacağı net tanımlı olmalı (ör. «pozitif sayı listesi»).
Çıktı	Ne üreteceği belli olmalı: türü, miktarı.
Açıklık	Her adım tek anlamlı olmalı. «a x b» çarpım mı, üç değişken mi? a·b gibi net yazılmalı.
Sonluluk	Bir noktada durmalı: ya sonucu verir ya da «çözüm yok» der.
Başarım ve performans	Sonuca ulaşmalı (başarım) ve bunu gereksiz adım atmadan, kaynağı az harcayarak yapmalı (performans).
Bağımsızlık	Belirli bir dile ya da cihaza bağlı olmamalı; her dilde yazılabilmeli.

Verimlilik: zaman ve alan

Bilgisayarın en değerli iki kaynağı işlemci zamanı ve bellek (RAM). Algoritmanın verimliliği bu ikisini ne kadar harcadığına göre ölçülür.

→Zaman karmaşıklığı: kaç işlemci çevrimi harcadığı. Saniye değil çevrim sayılır, çünkü işlemcilerin hızı farklı: 1 GHz'lik işlemci saniyede 1 milyar çevrim yapar. 500 çevrimlik algoritma 800 çevrimlikten daha verimlidir.
→Alan karmaşıklığı: ne kadar bellek kullandığı. Her değişken, her fonksiyon çağrısı yer kaplar. Kendini 1000 kez çağıran bir fonksiyon, 1000 kat yer ayırtır.

Birkaç bin çevrim küçük görünebilir, ama hava durumu tahmini, oyunlar ya da şifreleme milyarlarca veriyle çalışır. Orada küçük bir israf bile ciddi maliyet ya da hiç sonuç alamamak demek.

3. Algoritma türleri

Tür, aslında problemi çözerken izlenen strateji. Aynı problem farklı stratejilerle çözülebilir.

Arama motoru ve şifreleme

→Arama motoru algoritmaları: «ankara VE kitapçı» gibi kelime ve işleçleri alır, veri tabanında arar, uygun sonuçları önerir.
→Şifreleme algoritmaları: veriyi anahtarla okunamaz hâle getirir, anahtarla geri açar. AES şifreleme ve çözmede aynı anahtarı kullanır (simetrik). RSA genel (public) ve özel (private) olmak üzere iki ayrı anahtar kullanır.

Açgözlü (greedy)

Her adımda o an en iyi görünen seçimi yapar, geriye dönüp bakmaz. Hızlıdır ama en iyi sonucu garanti etmez.

Özyinelemeli (recursive)

Fonksiyon problemi çözmek için kendi kendini çağırır. Klasik örnek faktöriyel: 4! = 4 · 3!, 3! = 3 · 2!… ta ki 1! = 1'e kadar. Sonra değerler geri dönerken çarpılır: 1 → 2 → 6 → 24.

Kaba güç (brute-force)

Strateji yok, bütün ihtimalleri tek tek dener. 4 haneli bir şifreyi 0000'dan 9999'a kadar denemek gibi: en fazla 10.000 deneme. Sitelerdeki CAPTCHA doğrulaması, bu tür otomatik denemeleri engellemek için var.

Sıralama

Veriyi belli bir kurala göre dizer; sıralı veri hem okunması hem aranması kolay veridir. Çok sık yapıldığı için birçok stratejisi var: kabarcık, seçmeli, hızlı sıralama, tümleştirerek ayıklama…

Kabarcık sıralaması (bubble sort) en kolay anlaşılanı: yan yana iki sayıya bakar, yanlış sıradaysa yerlerini değiştirir. Listeyi baştan sona tekrar tekrar tarar; hiç değişiklik yapmadığı turda durur.

1. tur: en büyük sayı kabarcık gibi sona çıkıyor.

2. turda 7 ile 4 yer değiştirir → 2 4 7 9. 3. turda hiç değişiklik olmaz, algoritma durur. 4 elemanlı listede her tur 3 karşılaştırma yapar (eleman sayısının bir eksiği).

Gerileme (backtracking)

Bir seçim yapar, ilerler; çıkmaza girerse son seçime geri dönüp başka bir değer dener. Sudoku buna çok uygun: bir kutuya 4 yazdın, ilerde bir satırda iki tane 6 çıktı mı? Geri dön, o 4'ü değiştir. Kaba gücün akıllandırılmış hâli sayılır.

Böl ve fethet (divide and conquer)

→Böl: problemi küçük parçalara ayır.
→Fethet: her parçayı ayrı çöz.
→Birleştir: parça çözümlerini birleştirip ana çözümü elde et.

Klasik örnek tümleştirerek ayıklama (merge sort): liste tek elemanlı parçalar kalana kadar ikiye bölünür, sonra parçalar sıralı biçimde birleştirilerek sıralı tam liste kurulur.

Dinamik programlama

Bu da problemi alt problemlere böler, ama farkı şu: çözdüğü alt problemlerin sonucunu saklar ve aynısı tekrar lazım olunca baştan hesaplamaz. Özünde özyinelemenin hızlandırılmış hâlidir.

Örnek Fibonacci dizisi: her terim önceki iki terimin toplamı → 0, 1, 1, 2, 3, 5, 8, 13… Düz özyinelemeyle fib(4)'ü hesaplarken aynı işler tekrar tekrar yapılır:

Kırmızı kollar aynı hesabın tekrarı.

Çözüm: sonuçları bir diziye yazmak. Fonksiyon önce diziye bakar; değer varsa hemen döndürür, yoksa hesaplar ve diziye yazar. Bu tekniğe memoization (sonucu not alıp tekrar kullanma) denir.

Karıştırma (hashing)

Her uzunluktaki girdiyi sabit uzunlukta bir çıktıya (hash değeri) dönüştürür. MD5 32, SHA256 64 karakterlik çıktı verir. Girdideki tek bir harfin büyük-küçük olması bile çıktıyı tamamen değiştirir.

Asıl özelliği: geri çevrilemez. Bu yüzden siteler şifreni değil, şifrenin hash değerini saklar; girişte de hash'leri karşılaştırır.

Rastgele (randomized)

Zaman ve bellek kısıtlıysa her ihtimali denemek yerine rastgele örnekler seçer. Kesin sonuç garanti etmez ama kabul edilebilir bir sonucu hızlıca verir. Bir şehirdeki herkesle konuşmak yerine rastgele seçilmiş birkaç yüz kişiyle anket yapmak gibi.

Ünlü örneği Monte Carlo yöntemi: bir karenin içine rastgele noktalar at, çeyrek çemberin içine düşenleri say. π ≈ 4 × (içeridekiler / toplam). Nokta sayısı arttıkça sonuç 3,14'e yaklaşır.

Hepsi bir arada

Tür	Tek cümlede
Arama motoru	Kelimeye göre veri tabanında arar.
Şifreleme	Anahtarla kilitler, anahtarla açar.
Açgözlü	Her adımda o anın en iyisini seçer.
Özyinelemeli	Kendini daha küçük girdiyle çağırır.
Kaba güç	Bütün ihtimalleri dener.
Sıralama	Veriyi kurala göre dizer.
Gerileme	Çıkmazda geri dönüp başka yol dener.
Böl ve fethet	Böler, çözer, birleştirir.
Dinamik programlama	Ara sonuçları saklar, tekrar hesaplamaz.
Karıştırma	Sabit uzunlukta, geri çevrilemez özet üretir.
Rastgele	Rastgele örneklerle yaklaşık sonuç bulur.

Kendini test et!

Cevabı görmek için soruya dokun.

1.17'yi 5'e çıkarma yoluyla bölen algoritma kaç kez döner, bölüm ve kalan kaç olur?
✓ 17 → 12 → 7 → 2: üç kez döner. Bölüm 3, kalan 2.
2.Bir algoritma bazı girdilerde hiç durmuyorsa hangi özelliği ihlal eder?
✓ Sonluluk.
3.Zaman karmaşıklığı neden saniyeyle değil işlemci çevrimiyle ölçülür?
✓ İşlemcilerin hızı farklı olduğu için aynı algoritma farklı bilgisayarlarda farklı sürede biter. Çevrim sayısı ise cihazdan bağımsızdır.
4.(5, 1, 4) listesine kabarcık sıralamasının 1. turu uygulanınca liste ne olur?
✓ 5 ile 1 yer değiştirir → (1, 5, 4); 5 ile 4 yer değiştirir → (1, 4, 5).
5.Dinamik programlamayı düz özyinelemeden ayıran fark nedir?
✓ Alt problemlerin sonuçlarını saklayıp yeniden kullanır; aynı hesabı tekrar yapmaz.
6.Sitelerin şifreni değil hash değerini saklaması neden güvenlidir?
✓ Hash geri çevrilemez; veri tabanı ele geçse bile orijinal şifreye ulaşılamaz.
7.AES ile RSA arasındaki anahtar farkı nedir?
✓ AES şifreleme ve çözmede aynı anahtarı kullanır (simetrik). RSA genel ve özel olmak üzere iki ayrı anahtar kullanır.

Kaynak: Anadolu Üniversitesi Açıköğretim Fakültesi, «Algoritmalar» ders kitabı, Ünite 1. Bu not kitabın yerine geçmez; konuyu kendi cümlelerimle, yapay zekâ desteğiyle özetledim.