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ı...Bir metnin bütün ardışık alt dizgelerini saklamak istediğimizi düşünelim. İlk fikir, her alt dizgeyi ayrı ayrı üretmek olabilir; ancak uzunluğu $n$ olan bir dizgenin $O(n^2)$ farklı konumu vardır. Son Ek Otomatı, diğer adıyla Suffix Automaton (SAM), bu devasa koleksiyonu en fazla $2n-1$ durum kullanarak temsil eden deterministik ve yönsüz döngüsüz bir otomattır. Kısacası bütün alt dizgeleri cebine koyar, ama valiz parası ödemez.
Bir kelimeyi tersten okuduğumuzda yine aynı kelimeyle karşılaşıyorsak elimizde bir palindrom vardır: kazak, ada veya kabak gibi. Peki milyonlarca karakter içeren bir metindeki bütün farklı palindromik alt metinleri bulmak istersek ne olur? Her aralığı tek tek denemek yerine Eertree, diğer adıyla Palindromik Ağaç, bu simetrik parçaları oldukça zarif biçimde saklar.
Sayı teorisinde bazı fonksiyonlar kendilerini doğrudan göstermek yerine bölenleri üzerinden ipucu verir. Elimizde bir sayının tüm bölenlerine ait değerlerin toplamı bulunur; fakat asıl fonksiyonu keşfetmemiz gerekir. Möbius dönüşümü, tam da bu matematiksel bilmeceyi çözen güçlü bir tersine çevirme tekniğidir.
Devamı...
Bir ağaçta “işaretli en yakın düğüm hangisi?” veya “uzaklığı tam $K$ olan kaç düğüm çifti var?” gibi sorular ilk bakışta masum görünür. Fakat her sorguda bütün ağacı dolaşmak, $N$ düğüm ve $Q$ sorgu için $O(NQ)$ maliyet doğurabilir. Merkezcil ayrıştırma, ağacı dengeli parçalara bölerek her düğümün yalnızca logaritmik sayıda temsilciyle ilişki kurmasını sağlar. Kısacası ağacı keser, fakat mesafe bilgisini kaybetmez.
Devamı...Fibonacci dizisinin milyarıncı elemanı istendiğinde klasik döngünüz süre sınırına doğru hüzünlü bir yolculuğa çıkar. Neyse ki doğrusal tekrarlayan diziler, matrisler aracılığıyla tek bir dönüşüm şeklinde modellenebilir. Bu dönüşümün kuvvetini hızlı üs alma yöntemiyle hesapladığımızda $O(n)$ adımlık işi $O(\log n)$ zamanda tamamlarız. Başka bir deyişle milyarlarca adım, yaklaşık otuz matris çarpımına dönüşür.
Devamı...