Uzun bir metnin içinde belirli bir kelimeyi aramak, samanlıkta iğne bulmaya benzeyebilir. Her konumu karakter karakter karşılaştırmak mümkün olsa da Rabin-Karp algoritması daha yaratıcı davranır: Kalıbı ve metin parçalarını sayısal birer parmak izine dönüştürür. Parmak izleri farklıysa ayrıntılara bakmadan yoluna devam eder; aynıysa gerçek karakterleri kontrol eder.
Devamı...Bir dizinin ortancasını bulmak için akla gelen ilk yöntem diziyi sıralamaktır. Ancak yalnızca belirli bir sıradaki elemanla ilgileniyorsak bütün diziyi sıralamak, tek bir kitabı bulmak için kütüphanenin tamamını yeniden dizmeye benzer. Quickselect algoritması, Quick Sort’un bölümleme fikrini kullanarak diziyi tamamen sıralamadan ortalama $O(n)$ zamanda k. en küçük elemanı bulur.
Devamı...
Bir projedeki görevleri yalnızca yapılacaklar listesine yazmak yeterli değildir; bazı görevler diğerleri tamamlanmadan başlayamaz. Kritik Yol Metodu, yani CPM, bu bağımlılıkları analiz ederek projenin mümkün olan en kısa tamamlanma süresini ve gecikmesine tahammül edilemeyen görevleri bulur. Kısacası CPM, proje planının “hangi görev gecikirse alarm çalar?” sorusuna matematiksel bir cevap verir.
Devamı...
Bir sosyal ağda Ayşe, Berk’in paylaşımlarına; Berk, Ceren’in paylaşımlarına; Ceren de Ayşe’nin paylaşımlarına ulaşabiliyorsa bu üçlü kapalı bir iletişim bölgesi oluşturur. Yönlü graflarda bu tür karşılıklı erişilebilir düğüm gruplarına güçlü bağlı bileşen denir. Kosaraju-Sharir algoritması, yalnızca iki derinlik öncelikli arama yaparak bu gizli toplulukları ortaya çıkarır.
Devamı...Bir grup insanın daire şeklinde dizildiğini, belirli aralıklarla bir kişinin elendiğini ve bu işlemin yalnızca tek kişi kalana kadar sürdüğünü düşünün. Kulağa biraz acımasız bir sandalye kapmaca oyunu gibi gelen Josephus Problemi, döngüsel yapıları, indeks hesaplarını ve algoritmik düşünmeyi öğrenmek için kullanılan klasik bir bilgisayar bilimi problemidir.
Bir metindeki bütün karakterlere aynı uzunlukta bit dizileri vermek kolaydır; ancak pek ekonomik değildir. Huffman sıkıştırması, sık karşılaşılan karakterlere kısa, nadir karakterlere uzun kodlar atayarak ortalama veri boyutunu azaltır. Böylece algoritma, adeta çok konuşan karakterlere kestirme yol verirken seyrek görünenleri manzaralı ama uzun rotaya gönderir.
Devamı...Bir sözlükteki milyonlarca kelimeyi sıralamanız gerektiğini düşünün. Klasik algoritmalar kelimeleri tekrar tekrar karşılaştırırken LSD ve MSD, karakterleri doğrudan anahtar olarak kullanır. Böylece “hangisi küçük?” sorusunu sürekli sormak yerine karakterlerin dağılımından yararlanırlar. Sonuç, uygun koşullarda karşılaştırmalı sıralamalardan belirgin biçimde daha hızlı çalışan bir yaklaşımdır.
Bir şehir haritasında sürekli aynı kavşağa dönebiliyorsanız rota bulmak biraz baş ağrıtabilir. Yönlendirilmiş Asiklik Graf (Directed Acyclic Graph veya DAG) ise bu karmaşayı ortadan kaldırır: Okları takip ederek başladığınız düğüme geri dönemezsiniz. Bu döngüsüz yapı sayesinde en kısa yolları, Dijkstra’nın öncelik kuyruğuna bile ihtiyaç duymadan oldukça zarif biçimde hesaplayabiliriz.
Bir metin içinde kelime ararken her karakteri sırayla karşılaştırmak güvenilir olsa da her zaman akıllıca değildir. Boyer-Moore algoritması, kalıbı sağdan sola inceleyip uyuşmazlıklardan bilgi çıkararak gereksiz karşılaştırmaları atlar. Kısacası yalnızca “eşleşmedi” demez; “buradan birkaç adım öteye sıçrayabilirim” diyerek aramayı hızlandırır.
Devamı...Bir para birimini diğerine, onu da başka bir para birimine çevirip başlangıçtaki paranızdan daha fazlasıyla geri dönebilir misiniz? Teorik olarak evet! Arbitraj, farklı döviz kurları arasındaki tutarsızlıklardan risksiz kâr elde etme fikridir. Bu finans problemini bir graf problemine dönüştürdüğümüzde ise sahneye Bellman-Ford algoritması ve onun meşhur negatif döngü tespiti çıkar.
Devamı...Bir seçimde en çok oyu alan adayın kazanacağını düşünmek doğaldır. Ancak seçmenler yalnızca tek aday belirtmek yerine adayları tercih sırasına koyduğunda işler değişir. Oyları nasıl puanladığımız veya adayları nasıl karşılaştırdığımız, aynı tercihlerden farklı kazananlar çıkarabilir. Borda ve Condorcet yöntemleri, bu şaşırtıcı durumun en güzel örneklerindendir.
Devamı...Bir algoritmadaki tek bir işlemin pahalı olması, algoritmanın genel olarak verimsiz olduğu anlamına gelmez. Bazen nadiren gerçekleşen maliyetli işlemler, çok sayıdaki ucuz işlem arasında kaybolur. Amortize analiz, tam da bu tabloya bakarak bir işlem dizisinin uzun vadeli ortalama maliyetini hesaplamamızı sağlar.
Devamı...Union-Find, elemanların hangi gruba ait olduğunu hızlıca belirlemek ve iki grubu birleştirmek için kullanılan klasik bir veri yapısıdır. Ancak grupları düşünmeden birleştirirsek ortaya uzun, ince ve performans düşmanı ağaçlar çıkabilir. Ağırlıklı Hızlı-Birleşme (Weighted Quick-Union), küçük ağacı büyük ağacın altına bağlayarak bu sorunu oldukça zarif biçimde çözer.
Devamı...Bir labirentte çıkışı aradığınızı düşünün. Dijkstra algoritması, hedefin hangi yönde olduğunu önemsemeden çevresindeki yolları sabırla inceler. A* ise aynı işi yaparken hedefe doğru ne kadar yaklaştığını tahmin eden bir pusula kullanır. Bu sezgisel yaklaşım, doğru koşullarda en kısa yolu korurken gereksiz düğümleri ziyaret etmeyi azaltabilir.
Devamı...İkili arama ağaçları hızlı arama sunar; fakat anahtarlar sıralı geldiğinde ağaç bir çubuk gibi uzayabilir. 2-3 arama ağaçları bu sorunu, her düğümde bir yerine birden fazla anahtar saklayarak çözer. Daha da ilginci, kırmızı-siyah ağaçlar bu çok anahtarlı yapının ikili ağaç kılığına girmiş hâli olarak yorumlanabilir.
Bir lig fikri ilk bakışta oldukça basittir: Her takım, diğer bütün takımlarla karşılaşsın. Ancak maçları haftalara dağıtmaya başladığımızda aynı takımın bir turda iki maça çıkması, bazı eşleşmelerin tekrarlanması veya bir takımın sürekli deplasmanda oynaması gibi sorunlar ortaya çıkar. Neyse ki Round-Robin, yani döner turnuva algoritması, bu organizasyon bilmecesini düzenli ve verimli biçimde çözer.
Devamı...
Bir fabrikanın ürünlerini farklı şehirlere göndermek kolay görünebilir: Kamyonları doldur, adresleri belirle ve yola çık! Fakat birden fazla üretim merkezi, değişen talepler ve farklı taşıma maliyetleri devreye girdiğinde işler hızla karmaşıklaşır. Taşımacılık problemi, kaynakların hedeflere ihtiyaçları karşılayacak biçimde ve mümkün olan en düşük toplam maliyetle dağıtılmasını sağlayan özel bir doğrusal programlama modelidir.
Devamı...Sudoku’daki boş karelere bakıp “Buraya kesin 7 gelir!” demek kolaydır; bilgisayara neden 7 gelmesi gerektiğini anlatmak ise işin algoritmik kısmıdır. Sudoku ve Futoshiki, çözümün belirli kuralları aynı anda sağlaması gereken kısıt tatmin problemleridir. Bu yazıda kuralları matematiksel olarak modelleyecek ve Python ile genel amaçlı bir backtracking çözücüsü geliştireceğiz.
Bir sayı tablosunun bütün satırları, sütunları ve köşegenleri aynı toplamı veriyorsa ortada matematiksel bir sihir var demektir. Ancak tavşan da şapka da yok: Sihirli kareler ve onların üç boyutlu akrabaları olan sihirli küpler, kombinatorik düzenleme algoritmalarına dayanır. Bu yapılar; algoritmik düşünme, arama yöntemleri ve kısıt programlama için oldukça eğlenceli çalışma alanlarıdır.
Devamı...
Bir doğal sayıyı pozitif tam sayıların toplamı olarak kaç farklı biçimde yazabiliriz? İlk bakışta basit görünen bu soru, sayı teorisinin ünlü tam sayı parçalanması problemidir. Örneğin 4 sayısı; $4$, $3+1$, $2+2$, $2+1+1$ ve $1+1+1+1$ biçimlerinde yazılabilir. Dolayısıyla sonuç 5’tir. Ancak sayı büyüdükçe olasılıklar roket gibi artar ve elle listeleme yöntemi hızla kullanışsız hâle gelir.
Devamı...