LINEBURG


<< Пред. стр.

страница 2
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

лать один? Записать два текста рядом, один за другим? К сожалению,
после этого уже невозможно будет определить, где кончается первый
текст и начинается второй. Чередовать буквы первого и второго тек-
ста? Но, если тексты разной длины, снова не удастся разделить полу-
ченный текст на два исходных*).
Попробуем теперь применить более сложный приём. Запишем
первый текст, удваивая каждую его букву. Например, текст
Универсальная программа
(знак обозначает пробел) запишется так:
УУннииввееррссааллььннааяя ппррооггррааммммаа
После первого текста запишем разделитель «аб». Потом запишем вто-
рой текст без изменений. Допустим, что второй текст выглядит так:
Сложность текста
*) Вспомним, когда в алгоритме сложения «столбиком» мы из пары чисел делали
один текст для работы программы на нём, мы использовали разделитель «, » — запя-
тую и пробел, но это было возможно, поскольку в записи самих чисел эти два символа
встречаться не могли.
9
Тогда окончательный результат будет таким:
УУннииввееррссааллььннааяя ппррооггррааммммааабСложность текста
Покажем, что по такой записи можно однозначно восстановить
оба текста. Будем читать из полученной строки по два символа. Если
прочитанные символы совпадают, то они представляют один символ
первого текста (рис. 4). Если в некоторый момент мы натолкнёмся на
два различных символа, то это означает, что мы дошли до разделителя
«аб», который при восстановлении текстов нужно выбросить. После
разделителя прочитаем по одному символу второй текст.
УУ нн ии вв … мм аа аб С л…т а

У н и в…м а С л…т а


разделитель
первый второй
текст текст


Рис. 4

Оказывается, существуют способы кодировать пару текстов од-
ним текстом, причём делать это экономно, добавляя не слишком мно-
го новых букв, так чтобы длина кода была довольно близка к сумме
длин исходных текстов.
З а д а ч а. Насколько длина кода пары текстов может быть близ-
кой к сумме их длин?
Будем считать, что мы уже научились из двух текстов делать
один. После этого можно построить программу U, которая применя-
ется к паре текстов П и X, а результатом её работы будет П(X). Это
тоже один из важнейших фактов теории алгоритмов.
Факт. Существует универсальная программа, которая, получая
на вход программу П и текст X, применяет П к X.
Это утверждение не кажется очень сложным, хотя полные фор-
мальные доказательства его довольно громоздки.

СЛОЖНОСТЬ ТЕКСТА.
СЛУЧАЙНЫЕ И НЕСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Не так давно, в середине 60-х годов XX века, было выяснено,
что математика текстов может быть использована для прояснения
наших представлений о природе случайности. Начнём с обсуждения
того, что нам самим кажется случайным, а что неслучайным.
Предположим, что мы бросаем монету и записываем результаты
в виде последовательности из нулей и единиц: если выпадает орёл,
пишем ноль, а если решка — единицу. Может ли получиться такая
10
последовательность:
0110110010111010110100100000011110100111? (2)
Наверное, может. А такая:
0000000000000000000000000000000000000000? (3)
Вряд ли.
Почему, глядя на эти последовательности, мы сразу понимаем:
так бывает, а вот так — не бывает? Первый приходящий в голову
ответ: потому что первая последовательность «вероятна», а вторая —
«невероятна». Однако обе последовательности имеют одинаковую ве-
роятность! (Равную 2 n , где n — длина последовательности.) Чем
случайные последовательности отличаются от неслучайных? Попыт-
ка прояснить этот вопрос привела к такому важному понятию как
сложность конечной последовательности, или сложность текста.
Сейчас мы временно отложим вопрос о случайности и поговорим
о сложности текстов.
Бывает, что короткий текст описывает длинный. Например,
текст
миллион слов «да»,
состоящий из 17 символов, является описанием текста длиной
два миллиона символов.
Пусть П — какая-нибудь программа. Cложностью текста S при
способе описания П называется наименьшая длина текста Т, тако-
го что П(Т) = S. Текст Т при этом называется описанием текста S.
Иными словами, мы берём текст S, рассматриваем все его описа-
ния, из которых программа П может получить S, и среди них ищем
самое короткое. Например,
миллион слов «да» и пятьсот тысяч слов «дада»
— два описания одного текста, но первое описание короче.
Заметим, что для последовательности (3) мы сразу можем ука-
зать короткое описание, в отличие от последовательности (2). Есте-
ственно ожидать, что у большинства последовательностей нет корот-
ких описаний. Такие последовательности и называются случайными.
Это понятие случайности (его в 1960-х годах ввёл Андрей
Николаевич Колмогоров) оказывается очень интересным и продук-
тивным.
Докажите, что существует способ, который даёт почти самые ко-
роткие описания для всех последовательностей. Более подробно, су-
ществует такой способ K, что сложность любого текста S при способе
описания K меньше, чем его сложность при любом другом способе
описания П плюс некоторая постоянная, зависящая только от П.
(Эту теорему доказал А. Н. Колмогоров.)
11
Построение этого способа описания K использует конструкцию
универсальной программы, о которой говорилось ранее. Попробуйте
сами построить этот способ. У вас получится!

РЕШЕНИЯ И КОММЕНТАРИИ
К стр. 6.

О т в е т: можно. Будем выписывать строки в следующем порядке. Сначала пу-
стую строку и строку с одной чёрной клеткой на самом левом, первом месте. Затем
выпишем все строки, у которых не закрашены все клетки, кроме левых двух: таких
строк осталось 2. Потом все строки, у которых закрашены только некоторые из левых
трёх клеток (их осталось 4). Вообще, на n-м шаге (n 1) выписываются все строки, в ко-

n n n+1
? ? ?
… … … … …
? ? ?
? ?
? ?
?
Шаг 1 ?
? ?
?
… … … … …
? ?
? ?
?
?
?
? Шаг n ?
?
… ? ?
? ? ?
? ?
? ?
? ?
Шаг 2 ? ?
? ?
… … … … …
? ?
Шаг n+1
?
… … …
?
?
? ?
? ?
? ?
? ?
? ?
? … … …
?
? ?
?
?
?
Шаг 3 ?
?

? ?
? ?
? ?
? ?
? ?
? ?
? … … …
Рис. 5

торых закрашенные клетки все находятся на первых n местах, в количестве 2n 1 строк
(рис. 5). Нетрудно убедиться, что таким образом будут выписаны все возможные строки
с конечным числом чёрных клеток.


К стр. 10.

Обозначим через N(k) текст, кодирующий число k. Чтобы получить такой текст,
занумеруем символы нашего алфавита числами от 0 до n 1, где n — количество сим-
волов в нашем алфавите. Теперь просто запишем число k в системе счисления с осно-
ванием n и заменим все цифры в этой записи на соответствующие символы нашего
алфавита. Легко понять, что по такому тексту однозначно восстанавливается число k.
Как известно, длина числа k в системе счисления с основанием n равна logn (k + 1) *).
Если мы не будем писать в начале числа незначащие нули, то длина текста, коди-
рующего число k, равна logn (k +1) . При k = 0 будем считать, что N(k) — это пу-
стой текст, ведь мы выкидываем из числа все нули слева. Но это только вопрос дого-
ворённости.

*) x — это наименьшее целое число, не меньшее x.
12
Пусть X — длина текста X. Если бы нам удалось передать программе эту длину
вместе с текстом XY, то мы легко смогли бы восстановить текст X, просто прочитав
нужное количество символов сначала. Таким образом, вместо того, чтобы закодиро-
вать пару текстов X и Y, мы можем закодировать пару текстов N( X ) и XY. На пер-
вый взгляд такая замена никак не упрощает задачу, но это не совсем так по двум
причинам.
Во-первых, если мы просто удвоим все символы текста N( X ), припишем к ним
справа два разных символа из нашего алфавита, а потом припишем ещё и текст XY,
мы сможем, как это делали раньше, восстановить тексты N( X ) и XY, а значит, и тек-
сты X и Y. Таким образом, мы закодировали пару текстов X и Y текстом длиной
2 logn ( X + 1) +2+ X + Y , что почти всегда меньше, чем 2 X +2+ Y символов, ко-
торые получаются при использовании старого способа. Ниже мы ещё улучшим этот
новый способ кодирования пары текстов.
Во-вторых, длина текста N( X ) сильно зависит от длины текста X. Как это
можно использовать? Можно придумать ещё один способ кодирования. Пусть
l = X + Y (= XY ). Тогда X может принимать всего l + 1 значение — от 0 до l. Все эти
числа кодируются различными текстами, длина максимального из которых равна
logn (l + 1) . На самом деле можно считать, что все тексты имеют такую длину, ведь
если число записывается менее чем logn (l + 1) символами, то мы всегда можем при-
писать слева несколько незначащих нулей. Таким образом, нам надо закодировать два
текста: один длины l, а другой — logn (l + 1) . Казалось бы, что и это никак не упрощает
задачу. На самом деле нам даже не надо ничего кодировать — нужно просто записать
сначала текст длины logn (l +1) , а потом приписать к нему справа текст длины l.
Как же мы сможем понять, где кончается первый текст и начинается второй?
Посмотрим, какой информацией мы располагаем. У нас есть текст, и мы хотим найти,
где в нём закодирован первый текст, а где — второй. В самом тексте мы ничего найти
не можем. Но дополнительной информацией нам будет служить его длина. В самом
деле, наш текст имеет длину logn (l + 1) + l, а зная это число можно однозначно вос-
становить l, так как при увеличении l на единицу число logn (l + 1) +l тоже возрастает
(иногда на единицу, а иногда на двойку). Значит, зная logn (l + 1) + l, можно найти
число l, т. е. разделить наш текст на два, которые он кодировал. Теперь мы знаем X
и XY, а значит, и сами тексты X и Y. Для любой пары текстов X и Y суммарной длины l
этот алгоритм кодирует их, используя только logn (l + 1) «лишних» символов. Если,
например n =3, а X = Y =1 000 000, то наш алгоритм использует лишь 14 «лишних»
символов!


Оказывается, приведённый выше алгоритм в некотором смысле оптимален. Име-
ется в виду, что любой другой способ кодирования двух текстов, так чтобы их после
этого можно было однозначно восстановить, не может быть всегда лучше нашего. Ины-
ми словами, для любого числа l найдутся такие два текста X и Y суммарной длины
не больше l, что этот другой алгоритм закодирует их, используя не менее logn (l + 1)
«лишних» символов.
Пусть какой-то алгоритм умеет кодировать все пары текстов X и Y суммарной дли-
ны не больше l, используя не более k «лишних» символов. Подсчитаем, сколько всего
существует таких пар текстов. Пусть X + Y =m, где 0 m l. Посмотрим внимательно
на текст XY. Из каждого такого текста длины m получается m + 1 различных пар тек-
стов X и Y — X может быть первыми m символами этого текста, первыми m 1 символа-
ми, …, первым 1 символом, первыми 0 символами. При этом из разных текстов длины m
будут получаться разные пары текстов X и Y. Легко понять, что каждая пара текстов X
и Y получится ровно из одного текста длины m, а именно, из текста XY. Всего существу-
ет nm текстов длины m, значит, пар текстов X и Y суммарной длины m ровно (m + 1)nm .
13
Таким образом, количество пар текстов X и Y суммарной длины не больше l равно
l
Sl = (i+ 1)ni .
i=0

Вычислим Sl . С одной стороны, Sl+1 = Sl + (l + 2)nl+1 , а с другой,
l+1 l l
Sl+1 = 1 + (i+1)ni =1 + ((i+ 1) + 1)ni+1 = 1 + n ((i+ 1)ni + ni ) =
i=1 i=0 i=0
l
n(nl+1 1)
= 1 + nSl + n ni = 1 + nSl + .
n1
i=0

Отсюда находим, что
(l + 2)nl+1 nl+2 1 .
Sl =
n1 (n 1)2
Каждой паре текстов X и Y должен соответствовать свой текст не длиннее l +k
символов. Всего таких текстов
1.
l+k+1
Tl+k =1 + n + n2 + … + nl+k = n
n1
Из-за того, что можно провести однозначное декодирование, Tl+k Sl , или, что то же
самое, (n 1)Tl+k (n 1)Sl . Имеем:
nl+2 1 ,
nl+k+1 1 (l + 2)nl+1
n1
т. е.
1 nl
n n l =l+2
(l +2) 1
nk l.
n1 n1
А поскольку число nk — натуральное, выполняется неравенство nk l + 1, откуда сле-
дует, что
k logn (l + 1) или k logn (l + 1) .
Что и требовалось.


В приведённом алгоритме количество «лишних» символов зависит от суммар-
ной длины текстов X и Y. Это подразумевает некоторое равноправие текстов X и Y.
Однако, часто бывает, что тексты имеют различную природу, например, текст X мо-
жет быть значительно короче, чем Y. Тогда приведённый алгоритм будет не всегда
оптимален. Поэтому хотелось бы найти экономный алгоритм, при использовании ко-
торого количество «лишних» символов зависело бы только от X *). Два таких ал-
горитма уже были рассмотрены: они использовали X + 2 и 2 logn ( X + 1) + 2 «лиш-
них» символов соответственно. Видно, что второй алгоритм экономичнее первого. Это
связанно с тем, что пару текстов X и Y заменили на пару N( X ) и XY. Логично бы-
ло бы сделать такую замену ещё раз, а именно, заменить пару N( X ) и XY на пару
N( N( X ) ) и N( X )XY, по которой тексты N( X ) и XY, а значит, и тексты X и Y вос-
станавливаются однозначно. Но N( X ) 0 (иначе N( X ) — пустой текст, и такая за-
мена не даёт никакого выигрыша). Поэтому ещё лучше вместо текста N( N( X ) ) взять
текст N( N( X ) 1). Таким образом, из пары текстов A0 = N( X ) и B0 = XY получится

*) Например, такой алгоритм будет использоваться в решении следующего
упражнения.
14
пара A1 = N( N( X ) 1) и B1 =N( X )XY. Количество «лишних» символов при её коди-
ровании равно
2 logn logn ( X + 1) +2+ logn ( X + 1) .
Эту формулу можно упростить, если заметить, что

logn logn x = logn logn x

(докажите это). Количество «лишних» символов получается равным

2 logn logn ( X + 1) +2+ logn ( X + 1) ,

что почти всегда меньше 2 logn ( X + 1) + 2.
Если теперь заменить пару A1 и B1 на A2 = N( A1 1) и B2 = A1 B1 , то можно по-
лучить ещё более экономичный алгоритм. До каких же пор имеет смысл делать такие
замены? Ясно, что когда очередной текст Ak будет иметь длину 1, продолжать заме-
ны бессмысленно. С другой стороны, если Ak = 1, то не нужно удваивать символы Ak
и тратить два символа на разделитель, так как можно просто восстановить текст Ak —
его длина один символ. По Ak и Bk можно восстановить Ak 1 и Bk 1 , по Ak 1 и Bk 1 —
Ak 2 и Bk 2 , и т. д. до A0 и B0 , а по A0 и B0 — X и Y. Теперь можно сформулировать
и сам алгоритм кодирования. Надо получить текст A0 = N( X ), по нему — текст A1 =
= N( A0 1), затем A2 =N( A1 1), и вообще получать текст Ai+1 = N( Ai 1) до тех пор,
пока длина очередного Ak не окажется равной единице. После этого запишем текст

S =Ak Ak 1 …A0 0XY,

где 0 — символ с номером ноль. Зачем он нужен? Для того, чтобы можно было понять,
что начинается непосредственно текст X, а не очередная длина. В самом деле, никакой
из текстов Ai не может начинаться с нуля, так как Ai суть числа, у которых первый
символ точно не ноль. Следует отметить, что число ноль кодируется пустым текстом.
Более того, среди A1 , …, Ak не может быть пустых текстов, так как если Ai пуст,
то текст Ai 1 имел бы единичную длину, а значит, k = i 1 и текст Ai вообще не мог
использоваться (по определению k). Если A0 является пустым текстом, то X = 0 и наш
текст S есть не что иное, как A0 0XY = 0Y, а k = 0.
При использовании этого алгоритма количество «лишних» символов равно

1 +( logn ( X +1) + logn logn ( X + 1) + … + logn … logn ( X + 1) ),
k + 1 раз
если X 0, и равно 1, если X =0. Важно отметить, что этот способ не оптимальный, но
даёт очень хорошие результаты. Так, при n = 3 и X =1 000 000 количество «лишних»
символов равно 18 вне зависимости от текста Y .
Приведём ещё алгоритм декодирования текстов X и Y по тексту S, оставляя чи-
тателю самому проверить его корректность.

1. Запомни число 0.
2. Прочитай один символ текста S. Если это символ с номером 0, то следующие
столько символов из S, какое число в памяти — это текст X, а остальные не-
прочитанные символы — Y. Иначе припиши к прочитанному символу справа
ещё столько символов текста S, какое число находится в памяти. Полу-
ченный текст расшифруй как число в системе счисления с основанием n,
а полученное число запомни.
3. Если тексты X и Y найдены, то закончи работу. Иначе перейди к пункту 2.
15
К стр. 11.
На самом деле, идея построения достаточно проста. Мы уже научились строить
универсальную программу U, применение которой к программе П и тексту X даёт
П(X):
U(П, X) = П(X).
Пусть у нас имеется произвольный способ описания П. Тогда U(П, X) = П(X) = S для
любого описания X текста S, т. е. пара текстов (П, X) является описанием текста S
при способе U. Даже не вдаваясь в детали оптимального по длине кодирования пары
текстов, при тривиальном, рассмотренном нами способе, для пары текстов: П длины k
и X длины l — длина кода пары равнялась 2k + l + 2. Так что сложность описания
текста S при способе U превосходит сложность при любом другом способе П не более
чем на 2k + 2, где k — длина текста самого способа П — это и есть константа, зависящая
только от способа П.
БИБЛИОТЕКА
«МАТЕМАТИЧЕСКОЕ ПРОСВЕЩЕНИЕ»


ВЫПУСК 1 ВЫПУСК 11
В. М. Т и х о м и р о в. Великие Э. Б. В и н б е р г. Симметрия
математики прошлого и их ве- многочленов.
ликие теоремы. ВЫПУСК 12
В. Г. С у р д и н. Динамика звёзд-
ВЫПУСК 2
ных систем.
А. А. Б о л и б р у х. Проблемы
Гильберта (100 лет спустя). ВЫПУСК 13
В. О. Б у г а е н к о. Уравнения
ВЫПУСК 3 Пелля.
Д. В. А н о с о в. Взгляд на мате-
ВЫПУСК 14
матику и нечто из неё.
В. И. А р н о л ь д. Цепные дроби.
ВЫПУСК 4
ВЫПУСК 15
В. В. П р а с о л о в. Точки Брока-
В. М. Т и х о м и р о в. Дифферен-
ра и изогональное сопряжение.
циальное исчисление (теория и
приложения).
ВЫПУСК 5
Н. П. Д о л б и л и н. Жемчужи- ВЫПУСК 16

<< Пред. стр.

страница 2
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign