Zametki na polyah (akor168) wrote,
Zametki na polyah
akor168

Categories:

Про теорию сложности

Сложная эта штука теория сложности.

http://polit.ru/article/2014/03/04/shen_about_kolmogorov/

Вот вроде бы само определение Колмогоровской сложности очень естественно. Однако у меня всегда был затык уже на этапе - а что такое программа языка относительно которого вычисляется, и как оно соотносится с практикой.

Но это все вообще непринципиально. Мне другое интересно всегда было - что можно сказать об колмогоровской сложности больших упорядоченных массивов информации, вроде художественных фильмов или текстов. И как это соотносится с результатами стандартных архиваторов. Вот чисто интуитивно - колмогоровская сложность фильма должна быть гораздо меньше просто набора несвязанных картинок. Но вот насколько меньше...
Subscribe

  • 3-0 vs 42-0

    To put the magnitude of the U.S. defeat in context, losing 3-0 in soccer is the equivalent of losing 42-0 in football. Реально улыбнуло, поскольку…

  • Анекдоты: полная потеря смысла при пересказе

    Знаете, когда обсуждается сложность перевода с одного языка на другой, обычно рассказывается пример с круглым столом где каждый знает языки двух…

  • полезность регулярных проф-заметок

    Терри Тао пишет аж в 2013 году(в комментах) про полезность ведения ЖЖ собственного блога, в котором можно записывать прочитанные результаты,…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments