Алгоритмические варианты понятия энтропии

• Автор: Шень, Александр
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 134 c. : ил

Предисловие.

Вопросы, рассматриваемые в диссертации, относятся к алгоритмической теории вероятностей . Обзор содержания диссертации дан во введении. Цифры в квадратных скобках означают ссылки на приведенный в конце диссертации список литературы.
Автор благодарит своего учителя Владимира Андреевича Успенского за постоянное внимание и поддержку.
~ 5 ~
В 1965 году А.Н.Колмогоров ввел понятие сложности, или энтропии35) конечного объекта (см. [~?~ , £$] ). Говоря неформально, энтропия объекта есть количество двоичных знаков, необходимых для описания (задания, определения) этого объекта. Разумеется, это количество зависит от выбора ; способа описания; таким образом, каждому способу описания соответствует своя функция сложности. Открытие Колмогорова как раз и состояло в том, что при естественном определении понятия "способ описания" среди всех таких способов существует оптимальный - такой, при котором сложность объектов меньше, чем при любом другом ( с точностью до ограниченного слагаемого). Если имеются два разных оптимальных способа описания, то соответствующие им сложности отличаются, очевидно, на ограниченное слагаемое. Таким образом, возможно дать не зависящее от выбора способа описания определение энтропии конечного объекта как его сложности при оптимальном способе описания, веденную Колмогоровым энтропию мы будем называть простой колмогоровской энтропией.
Позднее были цредложены другие варианты понятия энтропии конечного объекта - сложность (энтропия) разрешения (см. [$2 ), префиксная энтропия, монотонная энтропия (о двух последних см.
[1] ). Хотя эти понятия основаны на родственных идеях - все они тем или иным способом уточняют описанный выше замысел Колмогорова,- их формальные определения никак не были связаны друг с другом. Ниже предлагается некоторая общая схема, частх) Мы предпочитаем термин "энтропия", чтобы избежать смешения со "сложностями вычисления" (временной, емкостной и т.п.)

ными случаями которой являются все перечисленные (а также некоторые другие) варианты определения понятия энтропии конечного объекта.
Эта схема использует понятие ^о -пространства в смысле Ю.Л.Ершова [V] . Понятие -$-0 -пространства является чрезвычайно удобным средством для определения вычислимости отображений, область определения которых состоит из объектов более сложной природы, чем натуральные числа (функций, последовательностей и т.д.). Поясним это понятие на следующем важном примере.
Пусть мы имеем отображение ОЬ , область определения которого состоит из (частичных) функций ИЗ /Д/ В /IV . Цусть это отображение в каком-то смысле вычислимо. Естественно считать, что к любому моменту процесса вычисления значения ОС на функции ^ используется не вся информация о ^ (ибо как может алгоритмический процесс успеть использовать бесконечно много информации об ?!), а лишь конечное число равенств вида - ё. . Другими словами, значение отображения 01 на функции определяется значениями этого отображения на конечных частях £ . Ясно также, что
по мере увеличения использованной информации об ^ будет получаться все больше и больше информации о результате применения 01 к ^ (если этот результат также является функцией, то будут становиться известными ее значения во все большем числе точек).
Эти соображения показывают, что при определении понятия вычислимости для функций из некоторого множества X в другое множество У в множествах X и У естественно выделять "конечные" элементы (в примере - функции с конечными областями определения) и вводить отношение "элемент а1

тогда (УУ^^г-УУ) - (х±)) * С.
Пусть ^б-С(Хг)У) “ оптимальный способ описания объектов У с помощью объектов из • Рассмотрим способ описания Я = 6 объектов У с помощью объектов ИЗ Хз
Пусть и — ХУ> А> - задача в пространстве У , хА- конечны объект Ху , для которого &(хл)£А , ку ,?(Ч) + 4.
^ V / ' а
Пусть Х.± - конечный объект , для которого -и(-х,0)-£(-ех(х^)) +С + 1 • Тогда я (осЛ
и К/ <^) ^ £(хл.)$4-(е2.(*2.У)+с + ± (£*#&>+*)+£+и
<. У(Кх. £ (и-)) 4' С 1 (пользуемся монотонностью и условием Липшица). Поэтому и для оптимального способа кодирования верно аналогичное неравенство
Если мы интересуемся только энтропией монотонных задач, то условие (2) следует несколько видоизменить. Именно, справедливо следующее
Предложение 2. Пусть £: /Я-* Ш - монотонно,' возрастающая функция, удовлетворяющая условию Липшица. Тогда следующие свойства равносильны:
(1^ Для любого пространства У существует такое С . что для любой монотонной задачи о£ = <() /у имеет место неравенство К у е. 6-0 £ /£х2 £ м) + с.
(2 ) Существует такое с , что для всякого конечного объекта хх <= Xо- выполнено неравенство
*х*А « ^ ' 4а> ^ + £
(напомним, что /^ = -{хб-Хг I х £ Я-аЗ* ) •
Доказательство. Чтобы доказать импликацию (1/)=$<2/), нужно внести в доказательство импликации (г)=£>(2) следующее изменение: всюду задача <(Х2) заменяется на монотонную задачу ХХг)Г^. Доказательство (2/)=^>(1/) получается из доказательства импликации (2) :Ф(1) предыдущего предложения