Dinamik programlama bazen doğru bağıntıyı bulduğumuz anda bitmiş gibi görünür. Sonra zaman karmaşıklığını hesaplarız ve karşımıza tatsız bir $O(nk)$ çıkar! Neyse ki geçişler belirli bir pencere içindeki minimum veya maksimum değere dayanıyorsa, çift uçlu kuyruk yani deque yardımımıza yetişebilir.
Bir fonksiyonun yalnızca Int döndürdüğünü değil, pozitif bir Int, tam olarak üç elemanlı bir liste veya belirli bir denklemi sağlayan sonuç döndürdüğünü tip seviyesinde ifade edebilseydik ne olurdu? Dependent Types, yani bağımlı tipler, tiplerin değerlere bağlı olmasına izin vererek bu fikri gerçeğe dönüştürür. Böylece tip denetleyici, kodun kapısında bekleyen bir güvenlik görevlisinden matematik ödevimizi kontrol eden son derece titiz bir asistana dönüşür.
Bir dizi düşünün: elemanların hem soldan sağa sırasını korumak hem de onları önceliklerine göre bir ağaca yerleştirmek istiyoruz. İlk bakışta “Ağaç mı yapıyoruz, diziyi mi saklıyoruz?” diye sorabilirsiniz. Cartesian Tree tam olarak bu iki dünyayı birleştirir: dizinin sırasını bozmadan heap özelliği taşıyan bir ikili ağaç üretir. Üstelik bunu doğrusal zamanda yapmak mümkündür.
Devamı...Bir dosyayı açtığınızda işletim sistemi milyonlarca kayıt arasından doğru disk bloğunu şaşırtıcı bir hızla bulur. Bu numaranın arkasında çoğu zaman ikili arama ağacı değil, tek düğümüne adeta küçük bir mahalle sığdırabilen B-ağacı veya onun akrabaları vardır. Çünkü disk dünyasında pahalı olan karşılaştırma yapmak değil, verinin bulunduğu bloğa fiziksel ya da mantıksal olarak ulaşmaktır.
Bir metinde tek kelime aramak kolaydır; fakat yasaklı sözcükler, virüs imzaları veya anahtar kelimelerden oluşan dev bir listeyi aramak istediğimizde işler değişir. Her kelime için metni baştan sona taramak, aynı yolu binlerce kez yürümeye benzer. Aho-Corasick algoritması ise kelimeleri ortak bir veri yapısında birleştirerek metni yalnızca bir kez tarar.
Devamı...Bir dağın zirvesini bulmak istediğinizi düşünün; ancak sis yüzünden yalnızca bulunduğunuz noktaların yüksekliğini ölçebiliyorsunuz. Her yeri adım adım dolaşmak yerine dağı düzenli biçimde daraltabilirsiniz. Ternary Search, yani üçlü arama, tam olarak bu fikri kullanarak tek tepeli fonksiyonların minimum veya maksimum noktasını bulur.
Devamı...
Yönlü bir grafın içinde birbirine karşılıklı olarak ulaşabilen düğüm gruplarını bulmak, bağımlılık analizinden sosyal ağlara kadar pek çok alanda karşımıza çıkar. Tarjan algoritması, bu grupları yani güçlü bağlı bileşenleri yalnızca tek bir derinlik öncelikli arama sürecinde keşfeder. Üstelik bunu yaparken yanında yalnızca bir yığın, birkaç dizi ve etkileyici derecede zarif bir fikir taşır.
Devamı...Bilgisayarsal geometri problemleri ilk bakışta ürkütücüdür: Doğrular kesişir, dikdörtgenler üst üste biner ve noktalar düzleme dağılır. Sweep Line, yani tarama doğrusu algoritması, bu iki boyutlu karmaşayı hareket eden hayali bir doğru ve sıralanmış olaylar yardımıyla yönetilebilir hâle getirir. Kısacası bütün düzleme aynı anda bakmak yerine, önemli değişiklikleri sırayla işleriz.
Devamı...Simplex algoritması, doğrusal optimizasyon problemlerini çözmek için 1947 yılında George Dantzig tarafından geliştirildi. İlginç olan şu: Algoritmanın en kötü durumdaki çalışma süresi üstel olabilir, fakat gerçek hayattaki problemlerde çoğunlukla son derece hızlıdır. Kısacası Simplex, teorik karnesi biraz problemli olsa da iş hayatında sürekli terfi alan o gizemli çalışan gibidir.
Devamı...Rekabetçi programlama; belirli süre ve bellek sınırları altında algoritmik problemler çözme pratiğidir. Bir bakıma satranç, matematik olimpiyatı ve klavye yarışının aynı masaya oturmuş hâlidir. Doğru uygulandığında düşünme becerisini keskinleştirir; yanlış hedeflerle yapıldığında ise yazılım geliştirmenin yalnızca hızlı kod yazmaktan ibaret olduğu yanılgısını doğurabilir.
Devamı...Bir algoritmanın karar verirken yazı tura attığını düşünün. İlk bakışta bu yaklaşım, ciddi bir mühendislik yönteminden çok şans oyununa benzeyebilir. Oysa rastgele seçimler; kötü girdilerden kaçınmak, karmaşık kararları basitleştirmek ve yüksek performansa daha az kodla ulaşmak için güçlü bir araçtır. Randomized algorithms dünyasında rastgelelik, belirsizlik yaratan bir kusur değil, kontrollü biçimde kullanılan bir kaynaktır.
Devamı...
Bazı algoritma soruları bizden doğrudan “en iyi cevap nedir?” diye sorar; fakat cevabı tek hamlede hesaplamak neredeyse imkânsızdır. Parametrik arama bu soruyu daha kolay bir soruya dönüştürür: “Verilen bir cevap mümkün mü?” Böylece karanlıkta cevabı tahmin etmek yerine, mümkün ve imkânsız bölgeler arasındaki sınırı sistematik biçimde buluruz.
Devamı...Tek başına kod yazarken zihnimizde küçük bir tiyatro döner: Kodu yazar, kontrol eder, hata yapar ve bazen aynı hataya on dakika boyunca şaşkınlıkla bakarız. Pair programming, yani eşli programlama, bu tiyatroya ikinci bir oyuncu ekler. İki geliştirici aynı problem üzerinde çalıştığında yalnızca iş bölümü yapılmaz; düşünme biçimleri görünür hâle gelir, geri bildirim hızlanır ve öğrenme sosyal bir sürece dönüşür.
Devamı...Rastgelelik yalnızca zar atarken işimize yaramaz; bazen bir algoritmayı daha hızlı, daha basit veya pratik hâle getirir. Olasılıksal algoritmaların iki ünlü ailesi olan Monte Carlo ve Las Vegas, rastgeleliği farklı bedeller karşılığında kullanır: İlki çalışma süresini sınırlar fakat küçük bir yanlışlık riskini kabul eder; ikincisi ise doğru cevabı garanti eder ancak ne zaman biteceği konusunda biraz gizemli davranır.
Devamı...Bazı algoritma soruları kendilerini “öğrencileri projelere ata”, “işçileri görevlere yerleştir” veya “sunucuları isteklere bağla” diye tanıtır. Kılıkları farklı olsa da ortak hedef şudur: Birbiriyle uyumlu çiftlerden, hiçbir öğeyi iki kez kullanmadan mümkün olduğunca çok seçmek. İşte bu cümleyi fark ettiğimiz anda problem, maksimum eşleştirme grafına dönüşmeye başlar.
Devamı...Bir fabrikanın hangi üründen kaç tane üretmesi gerektiğini, bir kargo şirketinin araçlarını nasıl dağıtacağını veya sınırlı bütçenin projeler arasında nasıl paylaştırılacağını düşünün. Bütün bu soruların ortak noktası, belirli kısıtlar altında en iyi kararı aramalarıdır. Lineer programlama, matematiği adeta bir karar verme pusulasına dönüştürerek bu tür optimizasyon problemlerini sistematik biçimde çözmemizi sağlar.
Devamı...Bir sosyal ağda herkes birbirini takip etmeyebilir; Ayşe, Berk’i takip ederken Berk Ayşe’yi takip etmiyor olabilir. Buna rağmen bazı kullanıcı gruplarında herkes diğerlerine dolaylı yollardan ulaşabilir. Yönlü grafların içindeki bu gizli ve sıkı topluluklara güçlü bağlı bileşenler denir. Kosaraju algoritması, grafı iki kez dolaşarak bu toplulukları şaşırtıcı derecede zarif biçimde ortaya çıkarır.
Devamı...
Bir şehrin yol ağını, bilgisayar ağını veya sosyal bağlantıları bir graf olarak düşündüğümüzde bazı bağlantılar diğerlerinden çok daha kritiktir. Tek bir yol kapandığında şehir ikiye ayrılıyorsa o yol bir köprü, tek bir istasyon devre dışı kaldığında ağ parçalanıyorsa o istasyon bir articulation point yani eklem noktasıdır. Gelin grafın nabzını tutup bu kritik damarları nasıl bulacağımızı inceleyelim.
Devamı...
Bir şehir turu planladığınızı düşünün: Her şehre tam bir kez uğrayacak, ancak başladığınız yere dönmek zorunda olmayacaksınız. Haritada bazı şehirler arasında doğrudan yol bulunmadığında işler hızla karışır. Graf teorisindeki Hamilton yolu problemi, tam olarak bu turun mümkün olup olmadığını sorar. Tanımı tek cümleye sığsa da çözümü bilgisayarları ciddi biçimde terletebilir.
Devamı...Bir veri yapısında ilerlerken aynı noktaya tekrar uğruyorsanız, muhtemelen bir çevrimin içine düşmüşsünüzdür. Ziyaret edilen elemanları bir kümede saklamak işe yarar; ancak ek bellek tüketir. Floyd’un çevrim bulma algoritması ise yalnızca iki işaretçi kullanarak döngüyü yakalar. Üstelik bunu hem bağlı listelerde hem de her elemanın bir sonraki konumu gösterdiği dizilerde yapabilir.
Devamı...