Bir metindeki farklı alt dizgileri tek tek saklamaya kalkarsak, kısa sürede bellek canavarı üretiriz. Uzunluğu $N$ olan bir dizginin $O(N^2)$ adet alt dizgi aralığı bulunabilir. Suffix Automaton ya da kısaca SAM, bütün bu alt dizgileri en fazla $2N-1$ durum kullanarak temsil eder ve soldan sağa tek geçişte, yani $O(N)$ zamanda kurulabilir.
Devamı...Geleneksel testlerde genellikle belirli bir girdi seçer, beklenen çıktıyı yazar ve sonucu karşılaştırırız. Peki seçmediğimiz binlerce girdi ne olacak? Property-Based Testing, birkaç mutlu örneğe güvenmek yerine yazılımın her geçerli durumda koruması gereken kuralları tanımlar. Test aracı da çok sayıda veri üreterek bu kuralları bozmaya çalışır; adeta kodumuza yaratıcı ve biraz da huysuz bir denetçi göndeririz.
Devamı...Bir uygulamanın çalışıyor olması, sağlıklı olduğu anlamına gelmez. Kullanıcılar yavaşlıktan yakınırken sunucunun neşeyle “200 OK” demesi mümkündür. Observability, yani gözlemlenebilirlik; sistemin iç durumunu dışarıya ürettiği sinyallerden anlayabilme yeteneğidir. Bu sinyallerin klasik üçlüsü log, metric ve trace verileridir. Tek başlarına faydalı, birlikte kullanıldıklarında ise dijital bir dedektif ekibi kadar etkilidirler.
Test ekranındaki bütün işaretlerin yeşil olması insana huzur verir. Fakat yeşil testler, kodun doğru çalıştığını kanıtlamaktan çok mevcut beklentilerin karşılandığını söyler. Peki testlerimiz kritik bir hata karşısında gerçekten kırılıyor mu? Mutation testing, yani mutasyon testi, üretim koduna kontrollü küçük hatalar ekleyerek bu soruya oldukça eğlenceli ve zaman zaman acımasız bir cevap verir.
Devamı...İşleri çalışanlara, öğrencileri projelere veya sürücüleri teslimatlara atamak istediğimizi düşünelim. Her aday yalnızca belirli seçeneklerle eşleşebiliyorsa problemimiz bir iki parçalı graf eşleşmesi problemine dönüşür. Tek tek eşleşme aramak kolay görünse de veri büyüdüğünde klasik yöntemler nefes nefese kalır. Hopcroft-Karp ise artırma yollarını toplu biçimde işleyerek sahneye çıkar ve karmaşıklığı $O(E\sqrt{V})$ seviyesine indirir.
Devamı...
Bir kullanıcı “Öde” düğmesine bastı, internet bağlantısı kısa süreliğine koptu ve istemci aynı isteği yeniden gönderdi. Müşteriden iki kez para mı çekmeliyiz? Elbette hayır! İşte idempotency, aynı işlemin birden fazla kez talep edilmesine rağmen sistemin nihai durumunun yalnızca bir kez çalıştırılmış gibi kalmasını sağlayan tasarım ilkesidir.
Devamı...Bir ağaçta “$u$ ile $v$ arasındaki düğümlerin toplamı nedir?” veya “bu yol üzerindeki bütün değerleri artır” gibi işlemler ilk bakışta masum görünür. Ancak her sorguda yolu adım adım yürümek, çarpık bir ağaçta $O(n)$ zaman harcatabilir. Heavy-Light Decomposition, kısaca HLD, ağacı değiştirmek yerine yolları akıllıca numaralandırır ve zor görünen yol işlemlerini segment ağacının sevdiği dizi aralıklarına dönüştürür.
Devamı...Bir bilgisayar ağında tek bir kablonun kopması sistemi iki parçaya ayırabilir mi? Ya da bir sosyal ağdaki tek bir kullanıcının ayrılması topluluklar arasındaki iletişimi kesebilir mi? Graf teorisindeki köprüler, eklem noktaları ve çift bağlantılı bileşenler, ağların bu dramatik zayıflıklarını ortaya çıkarmamızı sağlar.
Devamı...Bir satranç motoru geleceği gerçekten görmez; olası hamleleri dallanan dev bir ağaç üzerinde sistematik biçimde dener. Ancak bütün dalları incelemek, daha açılışta hesaplama kaynaklarını tüketir. Alpha-beta budaması, sonuca etki etmeyeceği matematiksel olarak kanıtlanan dalları keserek motorun aynı sürede çok daha derine inmesini sağlayan akıllı makastır.
Bir şehre yeni itfaiye istasyonları yerleştirdiğimizi düşünelim. Her mahalle hangi istasyona daha yakın? İstasyonları birleştirerek düzgün ve çakışmayan bir iletişim ağı nasıl kurabiliriz? İlk sorunun cevabı Voronoi diyagramı, ikincisinin güçlü adaylarından biri ise onun geometrik ikizi olan Delaunay nirengisidir. Bu iki yapı; haritacılıktan oyun geliştirmeye, robot rotalarından kablosuz ağlara kadar şaşırtıcı ölçüde geniş bir kullanım alanına sahiptir.
Devamı...Bir masanın üzerindeki çubukları, taşları veya eşleşebilen kartları sırayla kaldırdığınızı düşünün. Kurallar basit görünür: Hamle yapamayan kaybeder. Fakat hangi hamlenin kazandıracağını bulmak, özellikle bağımsız oyun parçaları birleştiğinde, sezgiden fazlasını gerektirir. Grundy sayıları ya da diğer adıyla nimber, her oyun durumunu tek bir sayıyla özetleyerek bu karmaşayı yönetilebilir bir matematik problemine dönüştürür.
Devamı...Dinamik programlama bazen doğru bağıntıyı bulduğumuz anda bizi sevindirir, ardından $O(N^3)$ zaman karmaşıklığıyla moralimizi bozar. Özellikle bir aralığı en uygun noktadan bölmeye dayanan problemlerde aynı geçişler tekrar tekrar incelenir. Knuth optimizasyonu, optimum bölme noktalarının düzenli hareket ettiğini matematiksel olarak kanıtlayabildiğimiz durumlarda bu kübik maliyeti $O(N^2)$ seviyesine indiren zarif bir tekniktir.
Devamı...Bir sosyal ağda arkadaşlıklar kuruluyor, bozuluyor ve arada “Ali ile Ayşe hâlâ dolaylı olarak bağlantılı mı?” soruları geliyor. Graf sürekli değişirken her sorguda baştan DFS çalıştırmak mümkündür; fakat performansınız kısa sürede dramatik bir vedaya hazırlanır. Çevrimdışı dinamik bağlantılılık, tüm işlemleri önceden bilmenin avantajını kullanarak zamanı parçalara ayırır ve bağlantıları geri alınabilir bir DSU ile takip eder.
Devamı...Bir e-ticaret uygulamasında ürün satın almak ile ürün listesini görüntülemek aynı veri üzerinde çalışıyor gibi görünür. Ancak satın alma işlemi stok kontrolü, ödeme ve iş kuralları gerektirirken listeleme işlemi yalnızca hızlı ve zengin bir görünüm ister. CQRS, bu iki farklı ihtiyacı tek bir modelin omuzlarına yüklemek yerine okuma ve yazma taraflarını birbirinden ayırır.
Bir geliştirici kodunu depoya gönderdiğinde görünmez bir fabrika çalışmaya başlar: kaynak kod derlenir, testlerden geçirilir, paketlenir ve kontrollü biçimde kullanıcılarla buluşturulur. CI/CD pipeline adı verilen bu otomatik yolculuk, “Benim bilgisayarımda çalışıyordu!” cümlesini tarihe gömmeyi hedefleyen teknik aşamalar ile güvenlik kapılarından oluşur.
Bir mikroservis çöktüğünde sorun çoğu zaman yalnızca o servisle sınırlı kalmaz. Ona istek gönderen uygulamalar yanıt bekler, bağlantı havuzları dolar, iş parçacıkları tükenir ve masum servisler de domino taşları gibi devrilmeye başlar. Circuit Breaker Pattern, elektrik sigortasına benzeyen bir koruma mekanizması kurarak bu zincirleme felaketi durdurur.
Devamı...Bir tam sayının ikili gösteriminde kaç tane 1 bulunduğunu saymak ilk bakışta sıradan bir döngü problemi gibi görünür. Ancak düşük seviyeli programlamanın büyüsü, bazen bütün bitleri tek tek dolaşmak yerine yalnızca ilgilendiğimiz bitlere dokunabilmemizdir. Brian Kernighan algoritması, her turda sağdaki bir adet set bitini temizleyerek gereksiz döngüleri ortadan kaldıran zarif bir bit maskeleme hilesidir.
Bir alfabenin karakterlerini kullanarak belirli uzunlukta metinler üretmek kolaydır: alfabe boyutu $K$, metin uzunluğu $N$ ise toplam $K^N$ seçenek vardır. Ancak metnin içinde “abc”, “kedi” veya “virus” gibi yasaklı kelimelerin hiç geçmemesini istediğimizde işler karışır. Her dizgiyi tek tek üretip kontrol etmek astronomik derecede pahalıdır. Neyse ki Aho-Corasick otomatı ile dinamik programlamayı birleştirerek tüm geçerli dizgileri üretmeden sayabiliriz.
Devamı...
Bir şirket hiyerarşisindeki yöneticileri, dosya sistemindeki klasörleri veya bir oyundaki yetenek ağacını düşünün. Bu yapılarda “X düğümünün altındaki bütün değerlerin toplamı nedir?” gibi sorgular sıkça karşımıza çıkar. Ağacı her sorguda yeniden dolaşmak pahalıdır; Euler Turu Tekniği (ETT), alt ağaçları tek boyutlu ve kesintisiz dizi aralıklarına dönüştürerek segment ağacının süper güçlerinden yararlanmamızı sağlar.
Devamı...Bir ağaçta iki düğüm arasındaki mesafeyi hesaplamak kolaydır; fakat binlerce güncelleme ve sorgu geldiğinde işler hızla dallanıp budaklanır. Centroid Decomposition, ağacı dengeli biçimde parçalara ayırarak mesafe problemlerini yaklaşık $O(\log n)$ katman üzerinden çözmemizi sağlar. Kısacası ağacın fiziksel yapısını değiştirmeden, onun üzerinde ikinci ve dengeli bir “centroid ağacı” kurarız.
