Колмогоровская сложность

Эта статья или раздел нуждается в переработке.
Пожалуйста, улучшите её в соответствии с правилами написания статей.

Неформально, колмогоровская сложность последовательности из нулей и единиц — это длина самой короткой программы, которая может породить эту последовательность. Это один из немногих разделов теоретической информатики, где Россия (в основном, МГУ) впереди планеты всей.

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

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

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

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home