Algoritmik axborot nazariyasi

Algoritmik axborot nazariyasi ― bu nazariy informatika vositalaridan foydalangan holda murakkablikning mohiyatini tushunishga harakat qiladigan informatika sohasidir. Asosiy gʻoya qatorning murakkabligini (yoki tavsiflovchi murakkabligi, Kolmogorov murakkabligi, Kolmogorov-Xaytin murakkabligi) berilgan qatorni chiqaradigan eng qisqa dastur uzunligi sifatida aniqlashdan iborat. Qisqa dasturlar orqali chiqarilishi mumkin boʻlgan qatorlar uncha murakkab sanalmaydi. Ushbu xulosa hayratlanarli darajada chuqurdir va Gyodelning toʻliqsizlik teoremasi va Tyuringning osilgan muammosi kabi ayrim natijalarning mumkin emasligini isbotlash va tashkil qilish uchun ishlatilishi mumkin.

Bu soha 1960-yillarning oxirida Andrey Kolmogorov, Rey Solomonov va Gregori Xaytin tomonidan ishlab chiqilgan. Kolmogorov murakkabligi yoki algoritmik maʼlumotlarning bir nechta variantlari mavjuddir. Eng koʻp ishlatiladigani oʻz-oʻzini chegaralovchi dasturlarga asoslangan va asosan Leonid Levinga (1974) amal qiladi.

Statistik va induktiv xulosalar hamda mashinalarni oʻrganish uchun minimal xabar uzunligi (MXU) tamoyili 1968-yilda Kristofer Uolles va D. M. Boulton tomonidan ishlab chiqilgan. MXU — Bayes ehtimolligi (u oldingi fikrlarni oʻz ichiga oladi) va axborot-nazariy. U statistik oʻzgarmaslikning zaruriy xususiyatlariga ega (xulosa qayta parametrlash bilan oʻzgartiriladi, masalan, qutb koordinatalaridan dekart koordinatalariga oʻtkazish kabi), statistik muvofiqlik (hatto juda murakkab muammolar uchun ham MXU har qanday asosiy modelga yaqinlashadi) va samaradorlik (MXU modeli iloji boricha tezroq har qanday yaqinroq haqiqiy model bilan toʻqnashadi). Kristofer Uolles va D. L. Dou 1999-yilda MXU va algoritmik axborot nazariyasi (yoki Kolmogorov murakkabligi) oʻrtasidagi formal aloqani koʻrsatdi.

Yana qarang

• Kolmogorov murakkabligi
• Algoritmik axborot nazariyasidagi muhim nashrlar

Havolalar

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin’s online publications
• Solomonoff’s IDSIA page
• Schmidhuber’s generalizations of algorithmic information
• Li & Vitanyi’s textbook
• Tromp’s lambda calculus computer model offers a concrete definition of K()
• Minimum Message Length and Kolmogorov Complexity (by C.S. Wallace and D.L. Dowe, Computer Journal, Vol. 42, No. 4, 1999).
• David Dowe's Minimum Message Length (MML) and Occam’s razor pages.
• P. Grunwald, M. A. Pitt and I. J. Myung (ed.), °FF-A2ED-02 °FC49FEBE7C&ttype=2&tid=10478 Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.
• Algorithmic Information Theory (pdf).
• Вяткин В.Б. Задача оценки негэнтропии отражения системных объектов и традиционные подходы к количественному определению информации (материалы из диссертации)