Kategoriler
Yerellik İlkesi

Algoritmik Karmaşıklık

Leibniz 1686’da belki de kendi metafiziğinin en önemli eserini veriyor. Metafizik üzerine Konuşmalar‘ı önermeler halinde yazıyor Leibniz. Amacı, evreni mekanik şekilde açıklamak ve bu mekanik sistemde Tanrı kavramını da dışlamamak.

Tüm eser baştan sona önemli ve ayrıntılı bir analizi hak ediyor. Ancak biz sadece altıncı önermeye bakacağız. Leibniz’in meşhur mürekkep lekesi deneyi. Bir sayfanın üzerine damlamış mürekkep lekelerini düşünün. Onlarcası olabilir aynı sayfa üzerinde. Ve bu lekelerin hepsini birleştiren bir çizgi çizebiliriz. Bu bazen düz bir çizgi olur, bazen bir çember, bazen de nokta sayısı (mürekkep lekelerinin sayısı) derecesinden bir polinom.

Leibniz diyor ki, bu mürekkep lekelerini modellemek demek, onları basit bir çizgiyle ifade edebilmek demektir. Eğer tüm lekeleri birleştiren çizginizin denklemi çok karmaşıksa, örneğin 100 tane noktayı 99. dereceden bir polinomla birleştirmişseniz, verdiğiniz model aslında pek de bir işe yaramaz diyor Leibniz. Daha doğrusu pek de anlamlı bir model değil, yani fenomeni anladık diyemeyiz çok karmaşık bir matematiksel fonksiyona indirgediğimizde.

20. yüzyılın ortalardında buna benzer tartışmalar yeniden alevleniyor. Gregory Chaitin ve Ray Solomonoff diyorlar ki, bilim aslında basit modeller ile eldeki veriyi açıklamaktır. Ancak “basit” kelimesini (kavramını) kullanmamızı sağlayacak formel bir zemin yok. Bu sebeple o formel zemini icat etmeleri gerekiyor birilerinin. Chaitin ve Andrey Kolmogorov, birbirlerinden bağımsız olarak, algoritmik karmaşıklık kavramını ortaya atıyorlar. Akıllarındaki şey şu, bir bilgisayar düşünün. O bilgisayarın spesifik bir çıktı üretmesini istiyorsunuz. Örneğin Fibonacci sayılarını yazdırabilir veya pi’nin basamaklarını tek tek ekrana sıralayabilir. Bilgisayar, bu işi yababilmek için bir şekilde kodlanmalı. İşte bu kodun uzunluğuna algoritmik karmaşıklık diyorlar.

Bilgisayar bilimlerinde (mühendislik ve yazılım vs de dahil) zamansal ve mekansal karmaşıklık (time-space complexity) çok çalışılır. Algoritmaların zamansal karmaşıklıkları önemlidir çünkü kullanıcıların bilgisayarlarında çalışabilecek türden algoritmalar isteriz. Örneğin izlediğimiz kodekli filmlerde her saniye 24 kare çözülüyor bilgisayarımız tarafından demektir. 24 kareyi bir saniye içerisinde çözemeyecek algoritmalar istemeyiz bu yüzden. Aklınıza gelebilecek her türden yazılımda zamansal karmaşıklık öyle veya böyle göz önünde bulundurulur programlayanlar tarafından.

Daha az dikkat edilir ancak bir de mekansal karmaşıklık vardır. Algoritma çalışırken ne kadar yer kullanacak. Yani bir anlamda ne kadar hafıza kullanması gerekiyor. Örneğin bir sıralama algoritması, 1 milyon tane sayı verildiğinde her bir sayıyı sürekli hafızasında tutacak mı, yoksa bir kısmını sıralayıp da bellekten silecek mi. Klasik yapay zeka alanındaki algoritmalarda bu da çok önemli bir konu haline geliyor. Bir satranç motorunu düşünelim. Her turda 20 hamlelik bir ortalama dallanma hesaplıyor olsun bu motor. Beyazın ilk hamlesinde 20 olasılığı göz önünde bulunduracaktır algoritma. Siyahın ilk hamlesinde bu sayı 400’e çıkacaktır. Ve birkaç hamle sonra, örneğin siyahın beşinci hamlesinde senaryo sayımız 20^10 yani 10240 tane milyar edecektir.

Algoritmik karmaşıklık ise pek öğretilmez bilgisayar mühendislerine. Çünkü algoritmik karmaşıklığı çalışmanın, diğerleri kadar pratik bir faydası yoktur. Ancak, modellemenin doğasına göz atacaksak, bizim için zaruridir algoritmik karmaşıklığı anlamak.

Devam edecek…

One reply on “Algoritmik Karmaşıklık”

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google fotoğrafı

Google hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.