Описательная сложность

Описательная сложность

Неформально, колмогоровская сложность последовательности из нулей и единиц — это длина самой короткой программы, которая может породить эту последовательность.

В дальнейшем, мы будем измерять длины всех объектов в битах. Для определения сложности мы начнём с элементарных замечаний. Начнём с описания бинарной последовательности (строки). Описание бинарной последовательности s — это просто программа, написанная как строка бит, которая производит последовательность s как результат. Принимая во внимание все возможные программы, которые генерируют последовательность s и выбирая кратчайшую, мы получим минимальное описание последовательности s, обозначаемое как d(s). (Если существует более одной программы одинаковой длины, выберем в качестве d(s) первую из них в лексикографическом порядке.) Колмогоровская сложность s, записывается K(s), и

K(s) = | d(s) | .

Другими словами, K(s) — это длина минимального описания s.

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Описательная сложность" в других словарях:

  • Колмогоровская сложность — В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность,… …   Википедия

  • Минералогия — (от Минерал и ...Логия         наука о природных химических соединениях минералах, их составе, свойствах, особенностях и закономерностях физического строения (структуры), а также об условиях образования и изменения в природе. Главная задача М.… …   Большая советская энциклопедия

  • Немецкая литература — Литература эпохи феодализма. VIII X века. XI XII века. XII XIII века. XIII XV века. Библиография. Литература эпохи разложения феодализма. I. От Реформации до 30 летней войны (конец XV XVI вв.). II От 30 летней войны до раннего Просвещения (XVII в …   Литературная энциклопедия

  • Соединённые Штаты Америки — (США)         (United States of America, USA).          I. Общие сведения          США государство в Северной Америке. Площадь 9,4 млн. км2. Население 216 млн. чел. (1976, оценка). Столица г. Вашингтон. В административном отношении территория США …   Большая советская энциклопедия

  • Великорусы — название Великая Россия искусственного происхождения; оно было составлено, по видимому, духовенством или, вообще, книжными людьми и начало входить в царский титул лишь в XVI веке. Впервые, кажется, оно встречается в Апостоле , первой книге,… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • РОМАН — детализированное повествование, которое, как правило, создает впечатление рассказа о реальных людях и событиях, на самом деле таковыми не являющихся. Какого бы объема он ни был, роман всегда предлагает читателю развернутое в цельном… …   Энциклопедия Кольера

  • ГОТЬЕ Теофиль — (Gautier, Theophile) ТЕОФИЛЬ ГОТЬЕ. Портрет работы Ж. Б.Клезинже (1853). (1811 1872), французский литератор. Родился 31 августа 1811 в Тарбе, образование получил в Париже. Занялся живописью, однако вскоре осознал ограниченность своих возможностей …   Энциклопедия Кольера

  • пастораль — и; ж. [франц. pastorale] Жанр в европейской литературе и искусстве 14 18 вв., характеризующийся идиллическим изображением жизни пастухов и пастушек на лоне природы; произведение этого жанра. * * * пастораль (франц. pastorale, от лат. pastoralis … …   Энциклопедический словарь

  • Дэт-метал — Направление: метал Истоки: трэш метал[1] ранний блэк метал[2] Место и время возникновения: середина 1980 х …   Википедия

  • Барри Линдон — Barry Lyndon Жанр …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»