Свойства алгоритмической сложности

Примем без доказательства следующие утверждения:

1.2.1.

т. е. сложность последовательности х не превосходит ее длины.

1.2.2.

Интуитивно становится ясно, что представить последовательность в виде программы (иными словами, сжать ее) можно только в том случае, если она содержит какие-то частотные или иные закономерности. Если же их нет, то не существует и программы более короткой, чем сама последовательность: сложность последовательности в общем случае неограниченно растет с ее длиной.

1.2.3. В связи с этим рассмотрим еще одно свойство алгоритмической сложности. Возьмем множество всех двоичных последовательностей длины N. Тогда общее количество их будет 2м. Интерес представляет вопрос о том, какова доля последовательностей, которые могут быть представлены своими программами р так, что 1(р) < N. Программе

длиной в 1 бит будет соответствовать, очевидно, 21 последовательностей (понятно, что речь идет о тривиальных рядах нулей или единиц). При сжатии до 2, 3... N - к - 1 разрядов число соответствующих по- следовательностеи будет 2 , 2 ,... 2 , а общее число их

Таким образом, доля таких последовательностей составляет

Например, при к = 10 лишь одна из 210 = 1024 последовательностей допускает сжатие до 10 бит. Следовательно, подавляющее число последовательностей («почти все») несжимаемы, т. е. случайны.

1.2.4. Наконец, возникает естественный вопрос о способе вычисления алгоритмической сложности. Оказывается, что функция невы- числима, т. е. не существует алгоритма ее определения для произвольной символьной последовательности [7], однако существует общий способ сколь угодно хорошей оценки этой величины сверху. Рассмотрим это свойство АГф подробно.

Пусть 5 - количество символов в алфавите, а ТУ- общее их число в некоторой произвольной последовательности, причем символ с номером I (г = 1,2,..., ^) появляется в ней гщ раз, так что

Тогда число всевозможных последовательностей будет

Для того, чтобы задать порядковый номер каждой из них в двоичной системе счисления, необходимо log С{т, m2,..., ms) двоичных разрядов. Воспользовавшись формулой Стирлинга

где п - произвольное целое число, получим Заметив, что

последнее равенство перепишем в виде или в двоичной системе счисления

(здесь - модуль перехода от натуральных логарифмов к двоичным).

Итак, для представления номера последовательности необходимо logC(w1,w2,..., ms) двоичных разрядов.

Чтобы записать собственно последовательность, состоящую из

символов, достаточно не более sogN бит,

так как

Таким образом, для ее полной идентификации требуется запись длиной

Поскольку то при больших N

Поэтому в соответствии с 1.2.1 будем иметь:

Величина, стоящая справа от знака равенства, называется энтропией. Обозначив ее буквой Я и заменив частоты на вероятности

получим

Это означает, что сложность любой последовательности не превосходит ее энтропии.

Показано, что в последнем выражении для знак равенства имеет место почти всегда, т. е. для подавляющего большинства последовательностей [7]. (Дополнительные сведения об энтропии и ее применении приведены в Приложении 8.)

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >