Бесплатно скачать, заказать диплом, курсовую, диссертацию Наборы конечный объектов с заданными информационными соотношениями между ними

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Наборы конечный объектов с заданными информационными соотношениями между ними

Количество страниц	70

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23530.doc

Содержание	Содержание Введение 2 1 Информационное расстояние 18 1.1 Минимальное перекрытие с точностью №O(logK(x,y))... 19 1.2 Конденсация информации... 23 1.3 Минимальное перекрытие с точностью доО(1оёф,2/))... 26 1.4 Шенноновская и алгоритмическая теории информации ... 33 2 Неделимые слова 35 3 Системы слов с большой взаимной сложностью 40 3.1 Положительный результат ... 41 3.2 Точность положительного результата... 53 3.3 Еще одна попытка обобщить основной результат... 55 4 Неупрощаемые программы 61 4.1 Игровой подход... 62 4.2 Вероятностный подход... 65 Используемые обозначения 68 Литература 70 Введение Актуальность темы. А. Н. Колмогоров в работе [1] выделил три похода к определению понятия "количество информации": комбинаторный, вероятностный и алгоритмический. Вероятностный подход основан на понятии энтропии Шеннона тогда как алгоритмический - на введенном Колмогоровым понятии алгоритмической сложности. Классическая теория информации Шеннона рассматривает случайные величины, в то время как алгоритмическая теория информации Колмогорова имеет дело с индивидуальными объектами. Тем не менее, многие утверждения могут, после соответствующей переформулировки, быть перенесены из первой теории во вторую (примеры можно найти в работах [8], [11]; также см. Теорему 1.6, приведенную далее, доказанную Ан. А. Мучником и опубликованную в [9]). Получающиеся аналоги, как и все результаты теории алгоритмической сложности, имеют асимптотический характер и выполнены лишь с определенной точностью. Наилучшая возможная точность - до аддитивной константы. Однако большинство известных результатов вышеописанного типа выполнены с точностью до аддитивного члена порядка логарифма алгоритмической сложности рассматриваемых объектов. Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах. В настоящей работе нас интересует вопрос о том, выполнены ли эти аналоги с большей точностью. Это становится существенным, если мы интересуемся сложными объектами, которые мало (по сравнению со своей сложностью) отличаются друг от друга. Если нам все же важно количество информации, необходимое для преобразования одного из этих объектов в другой, необходимо более тонкое рассмотрение, а именно рассмотрение с точностью до аддитивного члена, зависящего от условной алгоритмической сложности. Введение 3 Если упомянутые алгоритмические аналоги теорем классической теории информации перестают быть верными с большей точностью, можно будет сказать, что алгоритмическая теория информации является более тонким инструментом, чем шенноновская (платой за это является ее асимптотичность). Мы показываем, что это так на примере известной теоремы Вольфа-Слепяна из классической теории информации, аналог которой (Теорема 1.6) перестает быть верным с большей точностью (Теорема 1.7). Вторая тема настоящей работы связана с определением понятия информационного расстояния между двумя конечными объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5], посвященной этому вопросу, рассматривают различные определения этого понятия. Одним из этих определений является длина кратчайшей программы, переводящей первый объект во второй, а второй - в первый. Авторы показывают, что всегда можно найти пару кратчайших программ, переводящих первый объект во второй, и второй - в первый соответственно, максимально "перекрывающихся", т.е. имеющих максимально возможную общую информацию (это означает, что более короткая из этих программ "содержится" в более длинной) в очень сильном смысле. В связи с этим авторы [5] ставят вопрос о минимальном перекрытии: всегда ли найдутся абсолютно независимые (имеющие нулевую общую информацию) кратчайшие программы, переводящие первый объект во второй, и второй - в первый, соответственно? В настоящей работе дается полный ответ на этот вопрос (Теорема 1.5 и Теорема 1.1). А именно, этот вопрос имеет положительный ответ с точностью до аддитивного члена порядка логарифма сложностей объектов (Теорема 1.1). Ответ становится отрицательным с точностью до аддитивного члена порядка логарифма условных сложностей (Теорема 1.5). Далее, в данной работе также рассматривается вопрос о существовании "неделимых" объектов, т.е. таких, для разделения которых на нетривиальные части требуется значительная дополнительная информация. Доказано, что такие объекты существуют и найдена точная нижняя оценка для их сложности (Теорема 2.1). Следующим рассмотрен вопрос о существовании для данного фиксированного объекта такого конечного набора других объектов, который вместе с исходным объектом удовлетворял бы заранее заданному набору информационных соотношений. Этот вопрос, как и предыдущие, имеет два ва- Введение 4 рианта - в зависимости от желаемой степени точности. Мы рассматриваем один частный случай данного вопроса. В этом частном случае с высокой точностью выполнен положительный результат (Теорема 3.2, а также Теорема 3.3). Мы также доказываем некоторые утверждения о невозможности усиления положительного результата в различных направлениях (разделы 3.2 и 3.3). Последняя тема настоящей работы связана со следующим вопросом. Пусть даны два слова х и у и программа р, которая получив на вход ж, выдает у. Пусть эта программа не является кратчайшей среди всех программ, переводящих х в у. Хотелось бы узнать, всегда ли можно найти более короткую программу р', также переводящую х в у, простую при известной программе р. Существование такой р' означало бы "упрощаемость" программы р, т.е. этот вопрос можно назвать вопросом о существовании "неупрощаемых" программ. Мы доказываем, что такие примеры существуют (Теорема 4.1). Приводятся различные доказательства этого факта. Методы исследования. В работе применяются методы теории алгоритмов и игровые методы. Научная новизна. Все основные результаты работы являются новыми и состоят в следующем: 1. Исследован вопрос о существовании независимых программ, переводящих конструктивные объекты друг в друга. Решена задача о минимальном перекрытии, поставленная в [5]. 2. Получена нижняя оценка для точности, с которой выполнен алгоритмический аналог теоремы Вольфа-Слепяна из классической теории информации. 3. Доказано существование объектов, деление которых на нетривиальные части требует большой дополнительной информации ("неделимых" объектов). 4. Рассмотрен вопрос о существовании для данного объекта наборов других объектов, которые бы удовлетворяли заданным информационным соотношениям. Получены результаты в некоторых важных частных случаях. Введение 5 5. Доказано существование избыточных по длине программ, которые не задают более короткой программы, решающей ту же задачу ("неупрощаем ых" программ). Приложения. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоровской сложности и могут применяться в алгоритмической теории информации. Апробация работы. Основные результаты настоящей диссертации докладывались на следующих семинарах и конференциях: • научно-исследовательском семинаре по математической логике в МГУ под руководством академика РАН проф. С. И. Адяна и проф. В. А. Успенского; • семинаре "Колмогоровский семинар по сложности вычислений и сложности определений" под руководством Н. К. Верещагина, А. Б. Ромащенко, А. Л. Семенова и А. X. Шеня; • международной конференции 15th Annual IEEE Conference on Computational Complexity в 2000 г; • конференции "Ломоносовские чтения" в МГУ им. М. В. Ломоносова в 2000 г; • XXII Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 2000 г; • XXI Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 1999 г. Публикации. Основные результаты диссертации опубликованы в работах [12, 13, 14, 15]. Для полноты изложения в диссертации приводятся без доказательств Теорема 1.6 и Теорема о преобразовании, не принадлежащие автору. Первый из этих результатов получен Ан. А. Мучником и опубликован в работе [9]. Второй результат получен Ч. Беннетом, П. Гачем, М. Ли, П. Витаньи и В. Цуреком и опубликован в работе [5]. Также в главе 4 приведено вероятностное доказательство Теоремы 4.1, принадлежащее Ан. А. Мучнику. Введение Q Структура работы. Работа состоит из введения, 4 глав, списка используемых обозначений и списка литературы, содержащего 15 наименований. Общий объем диссертации - 71 страница. Теоремы и леммы нумеруются независимо. Номер состоит из номера главы и номера утверждения в ней. Номера теорем в предисловии совпадают с номерами тех же теорем в основном тексте диссертации. Опишем кратко содержание работы. Во введении дан краткий обзор работ, связанных с темой диссертации, и сформулированы основные результаты диссертации. Колмогоровская, или алгоритмическая, сложность слов была введена в 1965 году в работе А. Н. Колмогорова [1]. Пусть х и у - двоичные слова (конечные последовательности нулей и единиц). Неформально, колмогоровская сложность у относительно х определяется как длина самой короткой программы, которая получая на вход слово х, выдает слово у. Будем называть способом программирования любую частичную вычислимую функцию двух аргументов А (аргументы и значения А - двоичные слова). Значение А(р, х) будем интерпретировать как результат работы программы р на входе х. Если А(р, х) не определено, то будем говорить, что при способе программирования А программа р на входе х не выдает никакого результата. Теперь мы можем определить колмогоровскую сложность слова у относительно слова х при способе программирования А как: {min \|p\| , если существует такое р, что А(р, х) = у, А(р,х)=у со , если нет такого р, что А(р, х) = у. Надо обратить внимание на то, что определяемая таким образом сложность зависит от выбора способа программирования. Важным открытием Колмогорова стало существование оптимального способа программирования. Сформулируем данное утверждение точно. Будем говорить, что способ программирования А не хуже, чем способ программирования В, если 3CVx,yKA(y\x)^KB(y\x) + C. Согласно [1] существует оптимальный способ программирования, т. е. способ программирования С/, который не хуже любого другого. Оптимальный способ программирования не единствен. Если Uq и U\ -два оптимальных способа программирования, то они отличаются лишь на Введение ограниченную величину: ЗС Ух, у \| КиМх) - KUo(y\x) К т. е. асимптотически колмогоровские сложности относительно разных оптимальных способов программирования ведут себя одинаково. Некоторые оптимальные способы программирования могут иметь те или иные особые свойства. Однако в данной работе мы не будем интересоваться различиями между оптимальными способами программирования. Поэтому мы можем зафиксировать любой из них (назовем его U). В дальнейшем будем рассматривать только колмогоровскую сложность относительно выбранного оптимального способа программирования: Ки{у\х). При этом мы будем опускать индекс U, т. е. будем пользоваться обозначением К(у\х) := Ки{у\х). Величину К(у\х) будем называть колмогоровской сложностью слова у относительно слова х (или колмогоровской сложностью слова у при известном слове х). Заметим, что для любых х, у условная сложность К{у\х) конечна. Колмогоровской сложностью слова х назовем сложность х относительно пустого слова. Колмогоровскую сложность х будем обозначать К{х): К(х) := К(х\А). Кроме колмогоровской сложности слов будем рассматривать колмогоровскую сложность кортежей слов. Для этого мы должны выбрать некоторую вычислимую нумерацию всех кортежей слов, т. е. вычислимую биекцию между множеством всех кортежей двоичных слов и множеством двоичных слов. В выборе такой нумерации, так же как и в выборе оптимального способа программирования, имеется значительный произвол. Зафиксировав некоторую нумерацию кортежей, назовем колмогоровской сложностью кортежа слов (у\,..., уп) относительно кортежа слов (xi,.. .,хт) колмогоровскую сложность номера первого кортежа относительно номера второго кортежа. Данную сложность мы будем обозначать K(yi,...,yn\x\,...,хт). Ясно, что смена нумерации кортежей изменит колмогоровские сложности кортежей лишь на ограниченную величину. Заметим, что для любого конечного алфавита Л можно определить колмогоровскую сложность слов в данном алфавите (а также колмого- Введение 8 ровскую сложность кортежей слов в данном алфавите), выбрав произвольную нумерацию букв алфавита Л. Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах. Аналогично вышесказанному, можно говорить о колмогоровской сложности произвольных конструктивных объектов: конечных графов, элементов конечных полей, подпространств в конечномерном линейном пространстве над конечным полем и т. д., если выбрать вычислимую нумерацию данных объектов. При этом изменение нумерации приведет к изменению колмого-ровских сложностей рассматриваемых объектов лишь на ограниченную величину. Говоря о колмогоровской сложности тех или иных конструктивных объектов, мы всегда будем подразумевать, что для них зафиксирована некоторая вычислимая нумерация. Взаимная информация слов х и у определяется как разность между суммой колмогоровских сложностей слов х и у и колмогоровской сложностью пары (х,у): 1{х : у) := К(х) + К {у) - К(х,у). Необходимо отметить, что данное определение отличается от оригинального определения Колмогорова (они равносильны с точностью до аддитивного члена вида O(logK(x,y)), однако не до О(1(х : у))). Взаимная информация х и у показывает, насколько знание одного из этих слов упрощает задачу нахождения другого. Назовем слова хну независимыми если их взаимная информация 1{х : у) близка к 0. Это определение неформально и в каждом конкретном случае необходимо уточнять понимание "близости". Перечислим кратко другие важные свойства колмогоровской сложности и взаимной информации, которыми мы будем пользоваться в дальнейшем (подробнее см. [7] или [4]). • Существует константа с такая, что для любого числа / число слов х со сложностью К(х) ^ I меньше числа 2l+1 и не меньше числа 21~с: 21~с < ф{х\К{х) ^l}< 2/+1. (1) К(х) ^ ?(х) + 0(1), где ?(х) - длина слова х (список всех используемых обозначений можно найти на странице 68)1. 1 Это утверждение является более короткой записью следующего утверждения: ЭсУх К(х) ^ ?(х) + Введение • Для любой вычислимой функции f(x) найдется константа с такая, что K(f(x)) ^ К{х) + с для всех х, на которых / определена. • Выполнены неравенства К(х,у) < К(х,у) ^ для всех х, у (заметим, что члены 2 log K{y\x) и 2 log K{x) появляются здесь из-за необходимости закодировать пару программ с помощью одной программы). • К{х, у) > К(х) + К(у\х) - O(logK(x, у)), а значит \К(х,у) — К{х) — К{у\х)\ — O(\ogK(x,y)). • I(x:y)2-O(logK(x\y))t I{x:y)^-O(\ogK{y\x)). Договоримся называть слово х случайным или несоюимаемым если его колмогоровская сложность К(х) близка к ?(х) где С(х) - длина х. Это определение неформально и нуждается в уточнении в каждом случае. Оно отвечает интуитивному пониманию случайности так как из первых двух вышеприведенных свойств следует, что большинство слов любой фиксированной длины случайны. • Если слово х несжимаемо, то и любой префикс х' слова х также несжимаем, а именно 1(х') - К(х') ^ ?{х) - К{х) + 21og?(z') + 0(1). • Если р - самая короткая программа вычисляющая у по данному х, то р несжимаема, а именно с. В дальнейшем везде, где это возможно, мы будем использовать более короткую запись. Введение 10 На этом мы закончим необходимый обзор теории колмогоровской сложности и перейдем непосредственно к теме данной работы. Результаты настоящей работы можно разделить на несколько групп. Главной темой Главы 1 является рассмотрение вопросов, связанных с понятием информационного расстояния. Колмогоровская сложность является общепринятой мерой количества информации, содержащегося в индивидуальном конструктивном объекте. Хотелось бы определить подобную же меру для информационного расстояния между двумя объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5] рассматривают несколько естественных определений меры информационного расстояния и доказывают, что эти определения эквивалентны в сильном смысле. Интуитивно, информационное расстояние между словами х и у равно минимальному количеству информации, достаточному для того, чтобы вычислимо по х восстановить у и наоборот, вычислимо по у восстановить х. Чтобы быть расстоянием, такая мера D(x, у) должна удовлетворять аксиомам: • D(x, у) = 0 если и только если х = у; • D(x,y) + D(y,z) ^ D(x,z) (неравенство треугольника); • D(x,y) — D{y,x) (симметричность). Следуя [5], рассмотрим две возможные формализации этого понятия. Первой естественной мерой информационного расстояния между словами х и у является длина кратчайшей программы, которая получая на вход х, дает у и, обратно, получая на вход у, дает х. Обозначим эту меру di(x, у). Указанная кратчайшая программа должна воспользоваться имеющейся "общей частью" информации, необходимой для перехода от х к у и информации, необходимой для перехода от у к х. Хотелось бы знать, в каких пределах информация, необходимая для перехода от х к у может быть выбрана "перекрывающейся" с информацией, необходимой для перехода от у к я. В некоторых простых случаях может быть достигнуто полное перекрытие так, что одна и та же кратчайшая программа позволяет переходить как от х к у, так и наоборот. Например, если х и у - независимые случайные слова одинаковой длины п (с точностью до аддитивной константы К(х\у) = К(у\х) = п), то их побитовое исключающее "или" х © у Введение 11 является искомой кратчайшей программой для обоих вычислений (х при известном у и у при известном х). Рассмотрим теперь случай когда одно из этих вычислений требует больше информации, чем другое, например, К{у\х) > К(х\у). В этом случае кратчайшие программы не могут быть выбраны равными из-за разности их длин. В некоторых случаях перекрытие тем не менее может быть сделано полным в том смысле, что большая программа должна содержать всю информацию, содержащуюся в меньшей, наряду с некоторой дополнительной информацией. Прежде чем сформулировать главный результат работы [5], определим еще одну меру информационного расстояния между словами х, у как d(x,y) = max{K(x\y),K(y\x)}. В дальнейшем информационным расстоянием мы будем именовать величину d(x,y). Очевидно, что с точностью до аддитивного члена вида O(\ogd(x,y)) выполнены неравенства d(x,y) < Можно было бы предполагать, что в худшем случае перекрытие оказывается нулевым, то есть достигается равенство d\(x, у) = К(х\у)-\-К(у\х) + O(\ogd(x,y)), причем К(х\у) + К(у\х) значительно превосходит d(x,y). Однако оказывается, что для любых слов х,у выполнено равенство di(x, у) = d(x, у) + O(logd(x,у)). Это утверждение является прямым следствием следующей теоремы. Теорема о преобразовании [5]. Пусть слова х,у таковы, что К(у\х) ^ К{х\у)- Тогда найдутся слово d длины К{у\х) — К{х\у) и программа г длины К(х\у) + 2К((К(х\у), К(у\х))) + 0(1), которая получив на вход xd дает у и обратно, получив на вход у дает xd. Эта теорема утверждает существование кратчайших программ р и q, переводящих х в у, а у в х соответственно, "перекрывающихся" максимальным возможным способом. Действительно, имея р = (г, i(d)) и у, мы можем вычислить х, а имея q = (r,d) их мы вычислим у. Введение 12 В настоящей работе мы рассмотрим противоположный вопрос: всегда ли упомянутые кратчайшие программы р и q могут быть выбраны полностью независимыми, а именно, такими что взаимная информация I(p : q) близка к нулю. То есть, правда ли, что для каждой пары слов х, у найдутся программы р и q такие, что U(p,x) = у, U(q,y) = х, ?(р) « К(у\х), ?{q) « К(х\у) и I(p : q) « 0 (где приблизительные равенства выполнены с точностью до аддитивного члена вида О (log d(x,y)))l Эта задача была поставлена в [5]. •Ниже мы покажем, что ответ на этот вопрос отрицателен. Более того, существует пара слов х, у, для которых любые две программы минимальной длины, р, q, переводящие х в у и обратно, соответственно, имеют максимальное перекрытие, то есть K(p,q) = d(x,y) + O(\ogd(x,y)). Теорема 1.5. Для любого d найдется с такое, что для всех п выполнено следующее. Существуют слова х, у такие, что п ^ К(х\у), К(у\х) < п + 2 log log n + с и для всех слов p,q с длинами менее n + dlogn и таких, что U(p,x) = у, U{Qi У) — х> выполнено неравенство K(p,q) ^n+(2d + 7)logn + c. Однако, если потребовать чтобы равенства ?(р) « К(у\х), ?(q) » К(х\у), 1{р : q) « 0 выполнялись с точностью до аддитивного члена вида O(\ogK((x,y))) (вместо O(\ogd(x,у))), ситуация изменится кардинальным образом. В этом случае всегда найдется пара независимых программ Теорема 1.1. Для любых двух слов х, у найдутся программы р и q такие, что U(p,x) = у, U(q,y) = x, i(p) m K(y\x), ?(q) « К{х\у), и I(p:q) &0 (где приблизительные равенства выполнены с точностью до аддитивного члена вида O(\ogK(x,y))). В разделе 1.4 мы рассмотрим вопрос о связи между шенноновской и алгоритмической теориями информации. Между шенноновской теорией информации и теорией колмогоровской сложности имеется сильный параллелизм. Некоторые теоремы шенноновской теории информации имеют аналоги в теории колмогоровской сложности (см. например [2], [11], [8]). Одним из таких результатов является следующая теорема, доказанная Ан. А. Мучником. Введение 13 Теорема 1.6 (Ан. А. Мучник). Для любых слое х и у найдется слово р такое, что 1(р) « К(у\х), (2) К(у\х,р) « 0, (3) К(р\у) к 0, (4) где приблизительные равенства выполняются с точностью до аддитивного члена вида O(logK(y)). То есть для любой пары слов х,у найдется кратчайшая программа р, переводящая х в у, простая относительно у. Эта теорема является прямым аналогом теоремы Вольфа-Слепяна из шенноновской теории информации [3]. Однако Теорема 1.6 бессодержательна (т.е. очевидна) в случае когда слова хну отличаются мало, например когда К(у\х) имеет порядок О (log К (у)). Хотелось бы узнать, можно ли усилить теорему так, чтобы приблизительные равенства выполнялись с большей точностью, зависящей только от К(у\х). В настоящей работе мы даем отрицательный ответ на этот вопрос. А именно, верна следующая Теорема 1.7. Теорема 1.6 перестает быть верной, если потребовать выполнения приблизительных равенств (2)-(4) с точностью до аддитивного члена вида O(logK(y\x)). Из этого отрицательного результата в частности следует, что алгоритмическая теория информации богаче и в некоторых случаях является более тонким инструментом, чем шенноновская теория информации. Платой за это является асимптотический характер алгоритмической теории информации. В Главе 2 рассматривается вопрос о "разделении"информации. Рассмотрим следующий вопрос. Зафиксируем числа а и /3 такие, что а > О, /3>0иа + /?=1. Можно ли произвольное слово х разделить в пропорции а : /5? Формально это означает: верно ли, что для любого слова х найдется слово у такое, что К(у\х) « О, К (у) « аК(х), К(х\у) « (ЗК(х). Введение 14 Этот вопрос, как и предыдущие, имеет разные варианты в зависимости от желаемой степени точности. Легко видеть, что с точностью до O(\ogK(x,y)) ответ положителен. Достаточно перейти от слова х к кратчайшей программе, вычисляющей х и взять в качестве у начальный кусок этой программы длины аК(х). Можно было бы предположить, что результат остается верным и при точности 0(1), однако это не так. Из следующей теоремы следует отрицательный ответ при точности \| log log if (я). Теорема 2.1. Существует константа с > О такая, что для любого натурального числа к существует слово х такое, что К{х) ^ 3k, и удовлетворяющее условию: для любого слова у, если К(у\х) < к, то либо К (у) < к + с либо К(х\у) < к + с. Длина слова х равна Зк22 . При этом, существует константа с\ такая, что для каждого х удовлетворяющего вышеприведенному условию, выполнено Число таких х-ов конечно. Эта теорема утверждает существование слова х, неделимого ни в какой пропорции. Любое слово у, простое относительно х либо просто абсолютно, либо мало отличается от х. Она также дает нижнюю оценку на сложность такого примера. В Главе 3 мы рассмотрим следующий общий вопрос. Для данного слова xq мы хотим подобрать слова х\,Х2,. • • ,хт так, чтобы набор слов xq,x\, ... ,хт удовлетворял заранее заданным информационным соотношениям. В общем виде такой вопрос очень сложен и мы дадим ответы на некоторые из его частных случаев. Начнем со следующего частного вопроса. Верно ли, что для всякого числа п и слова х такого, что К(х) ^ п можно найти слово у для которого К(х\у) « п, К(у\х) « п. (5) Легко доказать, что с точностью до аддитивного члена вида O(\ogK(x)) ответ на этот вопрос положителен (Теорема 3.1), такое слово у всегда найдется. Но можно ли усилить это утверждение? В отличие от приведенных Введение 15 выше случаев, это сделать можно для точности O(logn), а в большинстве случаев даже до 0(1). А именно верна следующая Теорема 3.2. Существует константа с такая, что для любого п выполнено следующее: для любого слова х удовлетворяющего условию К(х) ^ 2п + с, найдется слово у такое, что обе условные сложности К(х\у) и К(у\х) располагаются между п и п-\- с: п < К(х\у), К{у\х) ^п + с. Эта теорема не покрывает случая п ^ К(х) ^ 2го, в котором однако можно применить уже упомянутую Теорему 3.1 и получить результат с точностью O(logn). Оба приведенных результата можно обобщить на случай любого конечного множества слов. В несколько ослабленном виде их можно сформулировать в одном утверждении. Теорема 3.4. Для каждого числа т найдется константа с такая, что для всякого п и всякого двоичного слова xq такого, что K{xq) > n выполнено следующее: существует набор слов х\,..., хт удовлетворяющий условию \K{xi[Xj) — п\ < 5 log n + с, 0 ^ г, j ^ ттг, г ф- j. Можно также изучить возможность дальнейшего усиления этого результата. В случае трех слов легко доказать следующую простую теорему. Теорема 3.7. Пусть даны число п и слово хо такие, что K(xq) ^ п. Тогда найдутся слова х\ и хч такие, что i\xj)ttn, i,je {0,1,2}, гфэ, K(xi\xj,xk) wn, i,j,k e {0,1,2}, г ^ j фк,гфк, где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogK(xo)). Встает вопрос: можно ли ее усилить, потребовав точности O(logn)? Из следующей теоремы следует отрицательный ответ на этот вопрос. Теорема 3.8. Существует константа с, для которой выполнено следующее. Пусть п и d - произвольные целые числа. Существует слово xq Введение 16 такое, что K{xq) ^ n + d u нет слое х\ и Х2, удовлетворяющих следующим неравенствам: К(х{\хо) ^n + d,ie {1,2}, 1ogn + c,z € {1,2}, , x\) > n + 2 logd. Глава 4 посвящена изучению вопроса о существовании "неупрощае-мых" программ. Пусть нам дана некоторая программа р которая, получая на вход слово х, выдает результат у. Нам хотелось бы найти другую программу р' с тем же свойством (на входе х выдавать у), имеющую меньшую колмогоровскую сложность. Мы также требуем чтобы р' легко получалась по р, т.е. чтобы колмогоровская сложность К(р'\р) была мала. Заметим, что когда мы говорим о программах, можно вместо колмогоровской сложности говорить о длине: р можно заменить на кратчайшую программу, вычисляющую р. Мы показываем что в некоторых случаях такой программы р' не существует, даже если длина р намного превышает условную сложность К(у\х). Это следует из следующей теоремы, которая приводится в более наглядной, но не в самой общей форме. Теорема 4.1. Существуют такие константы с\ < oi < сз, а тако/се с и е > 0, что для всякого натурального п найдутся слова х,у,р со следующими свойствами: (a) К (у \| х,р) ^ clogn ( слово р является описанием у при известном х с логарифмической точностью); (b) К (у \| х) ^ суп (сложность у при известном х мала...); (c) К{р) ^ сзгс (.. .по сравнению со сложностьюр); (d) не существует слова р', для которого К{р') ^ с^п, К(р' \ р) ^ еп и К{у \| х,р') ^ еп (... но не существует описания р', упрощающего р до промежуточной слоэюпости С2п). Мы приводим различные конструкции этого примера, использующие игровой и вероятностный подходы. Этот результат можно проинтерпретировать и другим способом. Будем называть слово р описанием слова у при известном х, если колмогоровская

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23530.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.