algorithmic complexity
-
verilen bir bilgisayar c icin, bir bitstring'i hesaplayan en kisa programin uzunlugu. h(s) = min{ | p| : c(p) = s } bu bilgisayar eger bir evrensel bilgisayarsa h(s) undecidabledir. eger gzipgibi evrensel olmayan bir sikistirici soz konusu ise tam olarak hesaplanabilir. eger h(s) bitstring'in uzunluguna yakin ise o zaman bitstring random'dir. (sikistirilmasi imkansiz demektir!)
ornegin 01010101010101...... diye giden sonsuz bir dizi dusunelim. bu string cok basit bir programla (tek bir for loop'u ornegin) uretilebilir, bu yuzden algorithmic complexity'si dusuktur. ama sonlu ama daha karmasik bir diziyi 1001011101101011001111....0 uretmek icin daha buyuk bir program gerekecektir. bu yuzden h(s) bit dizisinin karmasikliginin bir olcusu olarak dusunulur.
algorithmic complexity bagimsiz olarak kolmogorov, chaitin ve solomonoff tarafindan icat edilmistir. algorithmic complexity shannonin icat ettigi klasik information theoryden daha temel bir information theory'e algorithmic information theorye yol acar. ayni zamanda gelecegi tahmin eden programlar icin onemlidir, yapay zeka teorisinde ogrenme algoritmalarinda uygulanmistir.
benzer kavramlar arasinda minimum description length ve minimum message length yer alir. descriptive complexity olarak da bilinir. -
kendisine algoritmik entropi ya da kolmogorov karmaşıklığı da denir. hesaplanamazlığıyla ilgili güzel bir yazıya şuradan ulaşılabilir.
https://cannuman.wordpress.com/…i-sevmeyi-ogrendim/
ekşi sözlük kullanıcılarıyla mesajlaşmak ve yazdıkları entry'leri
takip etmek için giriş yapmalısın.
hesabın var mı? giriş yap