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ı...
İki oyuncunun sırayla hamle yaptığı bir oyunda bütün olasılıkları gezmek ilk bakışta doğal görünür. Fakat taş yığınları büyüdüğünde oyun ağacı küçük bir çalı olmaktan çıkıp dijital bir ormana dönüşür. Kombinatoryal oyun teorisi, uygun koşullardaki bir oyunun durumunu XOR işlemiyle tek bir sayıya indirerek kazananı belirlememizi sağlar.
Devamı...Bir şirkette çalışanları görevlere, öğrencileri projelere veya gönüllüleri etkinliklere dağıttığımızı düşünelim. Herkes her işe uygun olmayabilir; üstelik bir kişi yalnızca bir göreve atanabilir. Bütün olası dağılımları denemek kısa sürede kombinasyon cehennemine dönüşür. Hopcroft-Karp algoritması, bu karmaşayı iki parçalı çizge modeliyle düzenler ve mümkün olan en fazla sayıda eşleşmeyi verimli biçimde bulur.
Devamı...İnternet omurgası, elektrik şebekesi veya şehirler arası yol ağı düşünelim. Bazı istasyonların kapanması yalnızca küçük bir aksaklık yaratırken bazıları bütün ağı iki parçaya ayırabilir. Graf teorisi, ağın bu kritik düğüm ve bağlantılarını kesme noktaları ve köprüler kavramlarıyla belirler. Üstelik bunu her elemanı tek tek kaldırıp ağı tekrar sınamadan, verimli bir DFS algoritmasıyla gerçekleştirebiliriz.
Devamı...Binlerce basamaklı iki sayıyı klasik yöntemle çarpmak, her basamağı diğer sayının bütün basamaklarıyla eşleştirmeyi gerektirir. Bu yaklaşım küçük sayılarda sorunsuzdur; ancak veri büyüdükçe işlem sayısı hızla artar. Hızlı Fourier Dönüşümü, yani FFT, sayıları polinom gibi yorumlayarak çarpımı frekans uzayına taşır ve yaklaşık $O(n \log n)$ zamanda tamamlar. Kısacası FFT, devasa çarpma işlemini akıllıca organize edilmiş küçük işlemlere dönüştürür.
Devamı...Bir matris üzerinde sürekli hücre güncelleyip dikdörtgen alanların toplamını sorgulamak, ilk bakışta iç içe döngülerle çözülebilecek masum bir problem gibi görünür. Ancak matris büyüdükçe bu yaklaşım bilgisayarınıza küçük çaplı bir sabır testi uygular. İki boyutlu Fenwick Ağacı, diğer adıyla 2D Binary Indexed Tree, nokta güncellemelerini ve alan toplamı sorgularını logaritmik maliyetle bir araya getirerek bu sorunu zarifçe çözer.
Devamı...