WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 |

УУннииввееррссааллььннааяя ппррооггррааммммааабСложность текста Покажем, что по такой записи можно однозначно восстановить оба текста. Будем читать из полученной строки по два символа. Если прочитанные символы совпадают, то они представляют один символ первого текста (рис. 4). Если в некоторый момент мы натолкнёмся на два различных символа, то это означает, что мы дошли до разделителя «аб», который при восстановлении текстов нужно выбросить. После разделителя прочитаем по одному символу второй текст.

УУ нн ии вв … мм аа аб С л … т а У н и в … м а С л … т а первый второй текст текст Рис. Оказывается, существуют способы кодировать пару текстов одним текстом, причём делать это экономно, добавляя не слишком много новых букв, так чтобы длина кода была довольно близка к сумме длин исходных текстов.

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

Факт. Существует универсальная программа, которая, получая на вход программу П итекст X, применяетП к X.

Это утверждение не кажется очень сложным, хотя полные формальные доказательства его довольно громоздки.

СЛОЖНОСТЬ ТЕКСТА.

СЛУЧАЙНЫЕ И НЕСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ Не так давно, в середине 60-х годов XX века, было выяснено, что математика текстов может быть использована для прояснения наших представлений о природе случайности. Начнём с обсуждения того, что нам самим кажется случайным, а что неслучайным.

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

0110110010111010110100100000011110100111 (2) Наверное, может. А такая:

0000000000000000000000000000000000000000 (3) Вряд ли.

Почему, глядя на эти последовательности, мы сразу понимаем:

так бывает, а вот так — не бывает Первый приходящий в голову ответ: потому что первая последовательность «вероятна», а вторая — «невероятна». Однако обе последовательности имеют одинаковую вероятность! (Равную 2 n, где n — длина последовательности.) Чем случайные последовательности отличаются от неслучайных Попытка прояснить этот вопрос привела к такому важному понятию как сложность конечной последовательности, илисложность текста.

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

Бывает, что короткий текст описывает длинный. Например, текст миллион слов «да», состоящий из 17 символов, является описанием текста длиной два миллиона символов.

Пусть П — какая-нибудь программа. Cложностью текста S при способе описания П называется наименьшая длина текста Т, такого что П(Т)=S. Текст Т при этом называется описанием текста S.

Иными словами, мы берём текст S, рассматриваем все его описания, из которых программа П может получить S, и среди них ищем самое короткое. Например, миллион слов «да» и пятьсот тысяч слов «дада» — два описания одного текста, но первое описание короче.

Заметим, что для последовательности (3) мы сразу можем указать короткое описание, в отличие от последовательности (2). Естественно ожидать, что у большинства последовательностей нет коротких описаний. Такие последовательности и называются случайными.

Это понятие случайности (его в 1960-х годах ввёл Андрей Николаевич Колмогоров) оказывается очень интересным и продуктивным.

Докажите, что существует способ, который даёт почти самые короткие описания для всех последовательностей. Более подробно, существует такой способ K, что сложность любого текста S при способе описания K меньше, чем его сложность при любом другом способе описания П плюс некоторая постоянная, зависящая только от П.

(Эту теорему доказал А. Н. Колмогоров.) Построение этого способа описания K использует конструкцию универсальной программы, о которой говорилось ранее. Попробуйте сами построить этот способ. У вас получится! РЕШЕНИЯ И КОММЕНТАРИИ Кстр. 6.

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

Пусть — длина текста X. Если бы нам удалось передать программе эту длину X вместе с текстом XY, то мы легко смогли бы восстановить текст X, просто прочитав нужное количество символов сначала. Таким образом, вместо того, чтобы закодировать пару текстов X и Y, мы можем закодировать пару текстов N( X ) и XY. На первый взгляд такая замена никак не упрощает задачу, но это не совсем так по двум причинам.

Во-первых, если мы просто удвоим все символы текста N( X ), припишем к ним справа два разных символа из нашего алфавита, а потом припишем ещё и текст XY, мы сможем, как это делали раньше, восстановить тексты N( X ) иXY, азначит, итексты X и Y. Таким образом, мы закодировали пару текстов X и Y текстом длиной 2 logn( X +1) +2+ + что почти всегда меньше, чем 2 X +2+ символов, ко X Y, Y торые получаются при использовании старого способа. Ниже мы ещё улучшим этот новый способ кодирования пары текстов.

Во-вторых, длина текста N( X ) сильно зависит от длины текста X. Как это можно использовать Можно придумать ещё один способ кодирования. Пусть l= + (= Тогда может принимать всего l+1 значение — от 0 до l. Все эти X Y XY ). X числа кодируются различными текстами, длина максимального из которых равна 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, а = =1 000 000, то наш алгоритм использует лишь 14 «лишних» X Y символов! Оказывается, приведённый выше алгоритм в некотором смысле оптимален. Имеется в виду, что любой другой способ кодирования двух текстов, так чтобы их после этого можно было однозначно восстановить, не может быть всегда лучше нашего. Иными словами, для любого числа l найдутся такие два текста X и Y суммарной длины не больше l, что этот другой алгоритм закодирует их, используя не менее logn(l+1) «лишних» символов.

Пусть какой-то алгоритм умеет кодировать все пары текстов X и Y суммарной длины не больше l, используяне более k «лишних» символов. Подсчитаем, сколько всего существует таких пар текстов. Пусть + =m, где0 m l. Посмотрим внимательно X Y на текст 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.

Таким образом, количество пар текстов X и Y суммарной длины не больше l равно l Sl = (i+1)ni.

i=Вычислим 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=l n(nl+ 1) =1+nSl +n ni =1+nSl +.

n i=Отсюда находим, что (l+2)nl+nl+ Sl =.

n (n 1)Каждой паре текстов X и Y должен соответствовать свой текст не длиннее l+k символов. Всего таких текстов nl+k+ Tl+k =1+n+n2 +…+nl+k =.

n Из-за того, что можно провести однозначное декодирование, Tl+k Sl, или, что то же самое, (n 1)Tl+k (n 1)Sl. Имеем:

nl+ nl+k+1, 1 (l+2)nl+n т. е.

nk (l+2) n n l =l+2 1 1 n l l.

n 1 n А поскольку число nk — натуральное, выполняется неравенство nk l+1, откуда следует, что k logn(l+1) или k logn(l+1).

Что и требовалось.

В приведённом алгоритме количество «лишних» символов зависит от суммарной длины текстов X и Y. Это подразумевает некоторое равноправие текстов X и Y.

Однако, часто бывает, что тексты имеют различную природу, например, текст X может быть значительно короче, чем Y. Тогда приведённый алгоритм будет не всегда оптимален. Поэтому хотелось бы найти экономный алгоритм, при использовании которого количество «лишних» символов зависело бы только от Два таких ал X *).

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

пара 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 =A1B1, то можно получить ещё более экономичный алгоритм. До каких же пор имеет смысл делать такие замены Ясно, что когда очередной текст Ak будет иметь длину 1, продолжать замены бессмысленно. С другой стороны, если =1, то не нужно удваивать символы A A k k и тратить два символа на разделитель, так как можно просто восстановить текст 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=AkAk 1…A00XY, где 0 — символ с номером ноль. Зачем он нужен Для того, чтобы можно было понять, что начинается непосредственно текст X, а не очередная длина. В самом деле, никакой из текстов Ai не может начинаться с нуля, так как Ai суть числа, у которых первый символ точно не ноль. Следует отметить, что число ноль кодируется пустым текстом.

Более того, среди A1, …, Ak не может быть пустых текстов, так как если Ai пуст, то текст Ai 1 имел бы единичную длину, а значит, k=i 1 и текст Ai вообще не мог использоваться (по определению k). Если A0 является пустым текстом, то =0 и наш X текст S есть не что иное, как A00XY =0Y, аk=0.

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

Приведём ещё алгоритм декодирования текстов X и Y по тексту S, оставляя читателю самому проверить его корректность.

1. Запомни число 0.

2. Прочитай один символ текста S. Если это символ с номером 0, то следующие столько символов из S, какое число в памяти — это текст X, а остальныенепрочитанные символы — Y. Иначе припиши к прочитанному символу справа ещё столько символов текста S, какое число находится в памяти. Полученный текст расшифруй как число в системе счисления с основанием n, а полученное число запомни.

3. Если тексты X и Y найдены, то закончи работу. Иначе перейди к пункту 2.

К стр. 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 ВЫПУСК В. М. Т и х о м и р о в. Великие Э. Б. В и н б е р г. Симметрия математики прошлого и их ве- многочленов.

ликие теоремы.

ВЫПУСК В.Г.Сурдин. ДинамиказвёздВЫПУСК ных систем.

А. А. Б о л и б р у х. Проблемы Гильберта (100 лет спустя).

ВЫПУСК В. О. Б у г а е н к о. Уравнения ВЫПУСК Пелля.

Д. В. А н о с о в. Взгляд на матеВЫПУСК матику и нечто из неё.

В. И. А р н о л ь д. Цепные дроби.

ВЫПУСК ВЫПУСК В. В. П р а с о л о в. Точки БрокаВ. М. Т и х о м и р о в. Дифференра и изогональное сопряжение.

циальное исчисление (теория и приложения).

ВЫПУСК Н. П. Д о л б и л и н. ЖемчужиВЫПУСК ны теории многогранников.

В. А. С к в о р ц о в. Примеры метрических пространств.

ВЫПУСК ВЫПУСК А. Б. С о с и н с к и й. Мыльные плёнки и случайные блуждания. В. Г. С у р д и н. Пятая сила.

ВЫПУСК ВЫПУСК А. В. Ж у к о в. О числе p.

И. М. П а р а м о н о в а. Симметрия в математике.

ВЫПУСК А. Г. Мякишев. Элементы ВЫПУСК геометрии треугольника.

В. В. О с т р и к, М. А. Ц ф а с м а н.

ВЫПУСК Алгебраическая геометрия И. В. Я щ е н к о. Парадоксы и теория чисел: рациональные теории множеств.

и эллиптические кривые.

ВЫПУСК ВЫПУСК И. Х. С а б и т о в. Объёмы многоБ. П. Г е й д м а н. Площади многранников.

гоугольников.

ВЫПУСК ВЫПУСК А. Л. С е м ё н о в. Математика А.Б.С о с и н с к и й. Узлы и косы. текстов.

— учреждён Московским комитетом образования, префектурой Центрального административного округа Москвы, Отделением математики РАН, Математическим институтом им. В. А. Стеклова РАН, Московским государственным университетом им. М. В. Ломоносова, Независимым Московским университетом.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.