Bir sanat galerisinde geceleri dolaşan tek şey güvenlik görevlisi değil, geometridir! Duvarlarla çevrili çokgen biçimindeki bir mekânın tamamını kameralarla gözetlemek istediğimizi düşünelim. Kameraları nereye koymalı ve kaç tane kullanmalıyız? İlk bakışta basit görünen bu soru, hesaplamalı geometrinin en ünlü problemlerinden biri olan Sanat Galerisi Problemini ortaya çıkarır.
Devamı...
Bir avuç birim kareyi kenarlarından birleştirerek kaç farklı şekil oluşturabilirsiniz? İlk bakışta çocuk oyuncağı gibi görünen bu soru, kombinatorik ve algoritma dünyasında şaşırtıcı derecede derin bir probleme dönüşür. Poliominolar, diğer adıyla kare hayvanlar, basit kurallardan karmaşık sayma problemlerinin nasıl doğduğunu gösteren harika matematiksel canlılardır.
Devamı...
Cebinizde 1, 5, 10 ve 25 kuruşluk madeni paralar olduğunu düşünün. 37 kuruş ödemek için hangi paraları seçersiniz? İnsan zihni genellikle önce en büyük paraya uzanır. Ancak bu doğal yaklaşım her para sisteminde en iyi sonucu vermez. Para problemi, hedeflenen bir miktarı mevcut kupürlerle ve mümkün olan en az sayıda madeni parayla oluşturmayı amaçlayan klasik bir optimizasyon problemidir.
Devamı...Bir valize kıyafet, depoya kutu ya da işlemci üzerine transistör yerleştirirken aynı soruyla karşılaşırız: Sınırlı bir alanı nasıl daha verimli kullanabiliriz? Paketleme problemleri, basit görünen şekillerin şaşırtıcı derecede karmaşık düzenler oluşturduğu optimizasyon problemleridir. Özellikle çember ve kare paketleme; matematikten lojistiğe, üretimden bilgisayar bilimlerine kadar pek çok alanda karşımıza çıkar.
Devamı...Bir şehir turunda en kısa rotayı bulmak, sınav programını çakışmasız hazırlamak veya büyük bir lojistik ağını optimize etmek ilk bakışta sıradan görevler gibi görünebilir. Ancak girdi büyüdükçe bu problemlerin bazıları bilgisayarları adeta matematiksel bir bataklığa sürükler. Karmaşıklık teorisi, problemlerin ne kadar zor olduğunu ve kaynak ihtiyacının girdi boyutuyla nasıl değiştiğini inceler.
Satranç oynayan bir programın milyonlarca olasılık arasından mantıklı bir hamle seçmesi sihir değildir; rakibin de mümkün olan en iyi karşılığı vereceğini varsayan sistematik bir aramadır. Minimaks, iki oyunculu ve sıfır toplamlı oyunlarda bu düşünceyi modele dönüştürür. Alfa-beta budama ise sonucu değiştirmeyecek dalları erkenden eleyerek aynı karara çok daha az hesaplamayla ulaşır.
Bir deniz kabuğunun kıvrımlarını, eğrelti otunun yapraklarını veya uzaktan bakıldığında kıyı şeridinin bitmek bilmeyen girintilerini düşünün. Fraktallar, küçük parçaları bütüne benzeyen ve yakınlaştırıldıkça yeni ayrıntılar sunan geometrik yapılardır. Mandelbrot ve Julia kümeleri ise bu büyüleyici dünyayı yalnızca basit bir denklem, karmaşık sayılar ve bolca yineleme kullanarak bilgisayar ekranına taşır.
Devamı...Bir fabrikanın sınırlı ham maddelerle hangi üründen kaç tane üretmesi gerektiğini düşünün. Kârı artırmak istiyoruz; ancak işçilik, bütçe ve makine süresi sonsuz değil. Lineer programlama, bu tür kararları matematiksel bir modele dönüştürür. Simpleks yöntemi ise uygun çözümler arasında gezinerek en iyi noktayı bulur. Kısacası, kaynaklar az ama beklentiler yüksekse sahne simpleksindir!
Bir orduda altı farklı rütbeden ve altı farklı alaydan toplam 36 subay bulunduğunu düşünün. Euler’in sorusu ilk bakışta masumdur: Bu subaylar, her satırda ve sütunda her rütbe ile her alay tam bir kez görünecek biçimde $6 \times 6$ bir kareye yerleştirilebilir mi? Küçük bir sudoku havası taşıyan bu soru, kombinatoriğin en ünlü çıkmazlarından birine dönüşmüştür.
Devamı...Bir eğrelti otunun kıvrımlarını veya ağacın dallanma biçimini birkaç harf ve matematiksel kuralla oluşturabileceğinizi düşünün. L-Sistemleri, karmaşık doğal formları tek tek çizmek yerine onların büyüme mantığını tarif eder. Böylece küçük bir başlangıç ifadesi, birkaç yineleme sonunda dijital bir bahçeye dönüşebilir.
Bir haritadaki en yakın kafeyi, renk uzayındaki en benzer tonu veya oyun dünyasında karaktere en yakın nesneyi bulmak istediğinizi düşünün. Tüm noktaları tek tek karşılaştırmak kolaydır; ancak veri büyüdüğünde işlem kısa sürede kaplumbağa hızına iner. kD-ağacı, çok boyutlu noktaları akıllıca bölerek arama sırasında ilgisiz bölgeleri elememizi sağlayan uzamsal bir veri yapısıdır.
Devamı...Takvim uygulamasına bakmadan 29 Ekim 1923’ün hangi güne denk geldiğini bulabilir misiniz? Ebedi takvim algoritmaları, geçmişteki veya gelecekteki bir tarihin haftanın gününü yalnızca aritmetik işlemlerle hesaplar. İşin içinde artık yıllar, ayların farklı uzunlukları ve modüler aritmetik olsa da temel fikir şaşırtıcı derecede düzenlidir.
Bir satranç tahtasını boşluk bırakmadan domino taşlarıyla kaplamak ilk bakışta basit bir yapboz gibi görünür. Ancak tahtadan bazı kareler çıkarıldığında problem, kombinatoriğin en zarif sorularından birine dönüşür. Üstelik çözüm için her olasılığı denemek yerine boyama, değişmez ve graf teorisi gibi güçlü fikirlerden yararlanabiliriz.
Devamı...Bilgisayarlar, telefonlar ve oyun konsolları dışarıdan son derece karmaşık görünür. Ancak bu cihazların derinliklerine indiğimizde karşımıza yalnızca iki değer çıkar: 0 ve 1. Boole cebri, bu iki değer arasındaki ilişkileri matematiksel olarak açıklarken AND, OR ve NOT kapıları da aynı işlemleri elektronik devrelerde gerçekleştirir. Kısacası milyarlarca transistörün düzenlediği dijital konser, üç temel notayla başlar.
Devamı...
Bir logodaki kusursuz kıvrımın veya bir yazı karakterindeki zarif yayın arkasında çoğu zaman Bézier eğrileri vardır. Bu eğriler, yüzlerce pikseli tek tek yerleştirmek yerine birkaç kontrol noktasıyla akıcı şekiller oluşturmamızı sağlar. Üstelik yalnızca Illustrator, Figma ve Inkscape gibi tasarım araçlarında değil; animasyonlardan fontlara, oyunlardan robot hareketlerine kadar geniş bir alanda kullanılır.
Devamı...Bir haritada size en yakın hastaneyi bulmak, baz istasyonlarının kapsama alanlarını tahmin etmek veya dağınık ölçüm noktalarından düzgün bir arazi modeli üretmek aynı geometrik soruya dayanabilir: Düzlemdeki noktalar arasında komşuluk ve yakınlık nasıl tanımlanır? Voronoi diyagramları ile Delaunay üçgenlemeleri, bu soruya birbirini tamamlayan iki zarif cevap verir. Biri düzlemi bölgelere ayırırken diğeri noktaları anlamlı kenarlarla birleştirir.
Bir ondalık sayıyı kesre dönüştürmek bazen basit, bazen de şaşırtıcı derecede zordur. Örneğin $0{,}5=1/2$ hemen görülürken, $3{,}1415926$ için hangi kesrin “iyi” olduğu pek açık değildir. Sürekli kesirler, bir sayıyı iç içe geçmiş tam sayıların yardımıyla temsil eder ve küçük paydalı, son derece başarılı yaklaşık kesirleri sistematik biçimde üretir.
Devamı...Bir grup şehri yollarla, bilgisayarı kablolarla veya elektronik bileşenleri iletken hatlarla bağlamak istediğinizi düşünün. İlk akla gelen çözüm, verilen noktalar arasında en kısa bağlantıları seçmektir. Steiner Ağacı Problemi ise daha yaratıcı davranır: Ağa yeni kavşaklar ekleyerek toplam uzunluğu daha da azaltabilir. Kısacası bazen hedefe daha kısa yoldan ulaşmak için önce yeni bir durak inşa etmek gerekir!
Devamı...Bir GPS rotası, kıyı şeridi veya dijital çizim binlerce noktadan oluşabilir. Bu noktaların hepsini saklamak doğruluğu artırıyor gibi görünse de dosya boyutunu, çizim süresini ve işlem maliyetini büyütür. Ramer-Douglas-Peucker (RDP) algoritması, eğrinin görsel karakterini mümkün olduğunca korurken gereksiz noktaları kaldırır. Kısacası eğriye “Hangi noktalar gerçekten önem taşıyor?” diye sorar.
Devamı...Bir şehirdeki tüm mahalleleri fiber kabloyla bağlamak istediğinizi düşünün. Her bağlantının farklı bir maliyeti var ve hedefiniz, hiçbir mahalleyi yalnız bırakmadan mümkün olan en az kabloyu kullanmak. İşte Minimum Yayılma Ağacı algoritmaları tam olarak bu problemi çözer. Kruskal kenarları sıraya dizer, Prim tek bir noktadan büyür, Borůvka ise bütün bileşenleri aynı anda harekete geçirir.
