Bir soy ağacında iki kişinin ortak atasını aramak kolay görünebilir; ancak yüz binlerce düğümlü bir ağaçta binlerce sorgu sorulduğunda işler hızla karışır. Lowest Common Ancestor (LCA), iki düğümün ikisine de ata olan en derin düğümü bulur. Binary Lifting ise ön işleme yaparak bu sorguyu oldukça hızlı cevaplamamızı sağlar.
Devamı...Bilgisayarların zar atması sandığımız kadar gizemli değildir. Çoğu zaman makine, önceki bir sayıyı belirli sabitlerle işleyerek yeni bir sayı üretir. Lineer Kongrüansiyel Üreteç, yani LCG, bu yaklaşımın en eski ve anlaşılır örneklerinden biridir. Hızlı ve öğretici olmasına rağmen güvenlik söz konusu olduğunda bıraktığı matematiksel izler, onu dijital dünyanın fazlasıyla tahmin edilebilir falcısına dönüştürür.
Özyineleme, bir fonksiyonun problemi küçülterek kendisini çağırmasıdır. Zarif görünür; fakat her çağrı bellekte yeni bir yığın çerçevesi oluşturduğunda binlerce adım sonra programımız dramatik biçimde “Stack Overflow!” diye bağırabilir. Kuyruk özyinelemesi (tail recursion), özyinelemeli çağrıyı fonksiyonun son işlemi hâline getirerek çalışma zamanına bu çerçeveleri yeniden kullanma fırsatı verir.
Devamı...Bir sayı dizisinin hem düzgün parantez ifadelerini hem de çokgenlerin üçgenlere ayrılma biçimlerini sayması ilk bakışta matematiksel bir tesadüf gibi görünebilir. Oysa Katalan sayıları, farklı görünen bu problemlerin altında aynı dallanma ve özyineleme yapısının bulunduğunu gösterir. Dizi $1, 1, 2, 5, 14, 42, 132, \ldots$ biçiminde ilerler ve kombinatoriğin adeta İsviçre çakısıdır.
Bir dizide yüz binlerce kez “şu aralığın toplamı nedir?” diye sormak, her seferinde elemanları tek tek dolaşıyorsak bilgisayarı gereksiz yere maratona çıkarır. Karekök Ayrıştırması, yani Square Root Decomposition, diziyi yaklaşık eşit büyüklükte bloklara bölerek bu sorguları hızlandırır. Segment ağacına göre daha az kod, daha kolay hata ayıklama ve şaşırtıcı derecede iyi performans sunması da cabasıdır.
Devamı...Bazı matematik soruları uzun denklemler, karmaşık olasılıklar veya sayfalar dolusu hesaplama gerektiriyormuş gibi görünür. Oysa bazen çözüm, birkaç güvercini birkaç yuvaya yerleştirmekten ibarettir. Güvercin Yuvası İlkesi, şaşırtıcı derecede basit olmasına rağmen sayı teorisinden algoritmalara kadar pek çok alanda güçlü ispatlar kurmamızı sağlar.
Devamı...Bir üniversitede Veri Yapıları dersini almadan Algoritmalar dersine, Algoritmalar dersini tamamlamadan da İleri Programlama dersine kayıt olamadığınızı düşünün. Dersler arasındaki bu ön koşullar, hangi işin diğerinden önce yapılması gerektiğini gösteren bir bağımlılık ağıdır. Kahn algoritması, böyle bir ağı derinlik öncelikli arama kullanmadan, kuyruk yardımıyla geçerli bir sıraya dizer.
Bir boyutlu Kadane algoritması, sayı dizisindeki maksimum toplamlı kesintisiz aralığı doğrusal zamanda bulur. Peki sayılar tek sıra yerine bir matrisin hücrelerine dağılmışsa? Bu kez hedefimiz; satırları ve sütunları kesintisiz olan, toplamı mümkün olduğunca büyük bir dikdörtgen seçmektir. Neyse ki Kadane’yi çöpe atmıyoruz: Matrisi akıllıca sıkıştırarak problemi tekrar tek boyuta indiriyoruz.
Bir kâğıda rastgele noktalar çizdiğinizi ve hepsini çevreleyecek biçimde bir lastik bant geçirdiğinizi düşünün. Bandı bıraktığınızda yalnızca en dıştaki noktalara tutunur ve dışbükey bir çokgen oluşturur. Dışbükey zarf adı verilen bu sınır; harita uygulamalarından görüntü işlemeye, robot hareket planlamasından oyun geliştirmeye kadar pek çok alanda kullanılır. Graham Taraması ise zarfı, noktaları kutupsal açılarına göre düzenleyip sistematik biçimde eleyerek bulur.
Bir sayıyla aralarında asal kaç pozitif tam sayı bulunduğunu bilmek, ilk bakışta yalnızca matematik olimpiyatlarında işe yarayan bir beceri gibi görünebilir. Oysa Euler Totient fonksiyonu; modüler aritmetikten RSA şifrelemesine, periyodik sayı bulmacalarından programlama yarışmalarına kadar pek çok yerde karşımıza çıkar. Üstelik doğru formül öğrenildiğinde yüzlerce sayıyı tek tek kontrol etmek yerine asal çarpanlarla sonuca hızla ulaşabiliriz.
Devamı...Bir tahtayı domino taşlarıyla kaplamak ilk bakışta basit bir yapboz gibi görünür. Ancak tahta büyüdükçe olası yerleşimleri tek tek denemek, bilgisayarı kısa sürede matematiksel bir bataklığa sürükler. Profil maskeleme, satır satır veya sütun sütun ilerleyerek yalnızca sınırdaki doluluk bilgisini saklar; böylece devasa bir arama ağacını küçük ve tekrar kullanılabilir durumlara dönüştürür.
Devamı...Bir kasanın şifresi doğrudan verilmek yerine “3 ile bölündüğünde 2, 5 ile bölündüğünde 3, 7 ile bölündüğünde 2 kalanını bırakıyor” şeklinde saklansaydı ne yapardınız? Matematik olimpiyatlarında sıkça karşımıza çıkan bu tür şifrelerin anahtarı, farklı modüler bilgilerden tek bir ortak sayı üreten Çin Kalan Teoremidir.
Devamı...
Harita uygulamalarından oyun motorlarına kadar birçok sistem, iki doğru parçasının kesişip kesişmediğini hızlıca bilmek ister. İlk akla gelen yöntem eğimleri hesaplamak ve doğruların denklemlerini çözmek olabilir. Fakat bu yaklaşım dik doğrularda özel durumlar, bölme işlemleri ve kayan nokta hataları üretir. Neyse ki vektörel çapraz çarpım sayesinde sinüs, kosinüs ya da açı hesaplamadan yalnızca çıkarma ve çarpma işlemleriyle sağlam bir kesişim testi yapabiliriz.
Devamı...Elimizde pozitif tam sayılardan oluşan bir liste ve hedef toplam $T$ var. Soru basit: Bazı elemanları en fazla bir kez seçerek toplamı tam olarak $T$ yapabilir miyiz? Bu masum soru, Alt Küme Toplamı Problemi’nin karar sürümüdür ve NP-tamdır. Yine de hedef kapasite küçük olduğunda dinamik programlama sayesinde problem, pratikte oldukça uysal bir hâle gelir.
Devamı...Bazı problemlerde seçenekler yalnızca doğru veya yanlış olabilir; fakat seçenekler arasındaki koşullar işleri hızla karıştırır. “Ali gelirse Ayşe gelmesin” ya da “Sunucu A çalışmıyorsa B mutlaka çalışsın” gibi kuralların tümünü aynı anda sağlayan bir durum arıyorsak karşımızda büyük olasılıkla bir 2-SAT problemi vardır. Güzel haber şu: Bu mantık bulmacası, çizgeler sayesinde doğrusal zamanda çözülebilir.
Devamı...Bir metnin içinde belirli bir deseni aramak, arama motorlarından DNA analizine kadar pek çok alanda karşımıza çıkar. Her konumda karakterleri baştan karşılaştıran basit yöntem kolay anlaşılır olsa da büyük verilerde yavaş kalabilir. Z-Algoritması ise daha önce yapılan karşılaştırmaları akıllıca kullanarak eşleştirme işlemini doğrusal zamanda tamamlar ve KMP’ye güçlü bir alternatif sunar.
Aynı React bileşenini, test iskeletini veya hata yakalama bloğunu tekrar tekrar yazıyorsanız parmaklarınız gereksiz mesai yapıyor olabilir. Visual Studio Code snippet’ları, sık kullandığınız kod şablonlarını JSON biçiminde tanımlayıp birkaç karakterle çağırmanızı sağlar. Böylece kopyala-yapıştır arşivlerinde kaybolmadan daha hızlı ve tutarlı kod üretebilirsiniz.
Devamı...Bir sayı dizisindeki tüm alt dizileri deneyerek maksimum XOR sonucunu aramak kolaydır; ne var ki bu yöntem büyük verilerde bilgisayarı küçük çaplı bir varoluş krizine sürükler. Önek XOR değerlerini bit düzeyinde saklayan bir Trie, aynı problemi çok daha verimli biçimde çözmemizi sağlar. Üstelik yalnızca maksimum değeri değil, bu değeri oluşturan alt dizinin sınırlarını da bulabiliriz.
Devamı...Bir Telegram botu geliştirdiğinizde mesajları nasıl alacağınız konusunda iki temel seçeneğiniz vardır: polling ve webhook. İkisi de aynı güncellemeleri teslim eder; ancak bunu yaparken ağ trafiği, işlemci kullanımı, gecikme ve altyapı gereksinimleri bakımından farklı davranır. Kısacası polling kapıyı sürekli çalıp “Yeni mesaj var mı?” diye sorarken webhook, mesaj geldiğinde kapı zilinin çalmasını bekler.
Devamı...
Bir sosyal ağda Ayşe, Berk’e; Berk, Cem’e; Cem de Ayşe’ye ulaşabiliyorsa bu üçlü, yönler farklı olsa bile kendi içinde güçlü bir iletişim halkası oluşturur. Tarjan algoritması, yönlü çizgelerdeki bu halkaları yalnızca bir derinlik öncelikli arama geçişiyle keşfeder. Böylece bağımlılık analizi, ağ incelemesi ve döngü tespiti gibi işlemleri oldukça verimli hâle getirir.
Devamı...