Главная » Просмотр файлов » markov_teorija_algorifmov

markov_teorija_algorifmov (522344), страница 33

Файл №522344 markov_teorija_algorifmov (Марков - Теория алгоритмов) 33 страницаmarkov_teorija_algorifmov (522344) страница 332013-09-14СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 33)

е. нельзя ли построить такой нормальный алгорифм Й в алфавите А, что для любого слова Р в А будет й (Р) Ц[Р-. Ответ на этот вопрос оказывается, вообще говоря, отрицательным, как показывает следующее утверждение; 3.1, Если алфавит А содержит более одной буквы, то не существует никакого нормального алгорифма й в А, который для любого слова Р в А удовлетворял бы условию й(Р) ж[Р . В самом деле, пусть й — такой чормальный алгорифм. Покажем, что 3.2. Если слово Р таково, что Р з [Р, то Й: Р ( — [Р Действительно, пусть РЯР .

Тогда Й: Р)=[Р ) или й: Р)= [Р . В первомслучае, содной стороны,й([Р ) ~[Р а с другой стороны, й ([Р ) 7А[[Р . Но [[Р Б Р, и, таким *) См. В ЗНЗ. иц з зз зз] АЛГОРИФМЫ ПОБУКВЕННОГО КОДИРОВАНИЯ образом, Р Х [Р, что противоречит условию. Следовательно, й: Р )= [Р, и потому существует слово (г такое, что й: Р ~ 1г и й: Я )- [Р [3 25,7]. Возьмем такое Я. й: Я=.[Р и, значит, Й(®32[Р . С другой стороны, Й вЂ” обращающий алгорифм, и поэтому Й(Я)я.[Я . Таким образом, [Р Х[~, и, значит, Р л.

Я, откуда Й' Р )- [Р , что и требовалось доказать. Продолжим теперь доказательство утверждения 3.1. Так как алфавит А содержит более одной буквы, то имеются слова Р в А такие, что Рд' [Р . Отсюда следует, что в схеме Й имеются заключительные формулы подстановок. Возьмем первую из них. Пусть это будет формула у- у. Выберем в алфавите А две буквы Б и Ч такие, что У не начинаегся $ и что $ 1Г' з1.

Рассмотрим слово МУРР Легко видеть, что 1"ЕУЧ ми[У з„и потому [$Ул1 ~г'$Уз1, так что Й: $Ул1 1- з1[У э, причем активной на слове $Уз1 является именно формула У- )Г, так как ее левая часть входит в ~Уть а все предшествующие формулы подстановок простые. Предположим, что У м.Л. Тогда $Уз1.В'. $з1 и й: эз) )- )ГЕП. Отсюда з1$Х)Г~П, и, значит, ~Хз1, что противоречит выбору Б и з1. Следовательно, у -,РЛ. Но если У ~Л, то аль У зе з1 †перв вхождение слова У в слово $Уз1, и потому й: $Ул) 1- ° $рз1. Следовательно, з)[У 5ХУ/Ч, и, значит, ~Х ть что снова противоречит выбору $ и т1. Следовательно, неверно, что У ~г Л.

Таким образом, мы, с одной стороны, доказали, что У л1' Л, а с другой стороны, опровергли предположение о том, что У г Л. Значит, неверно, что для любого Р в А Й(Р) я.[Р, что и доказывает 3.1. Заметим, что если алфавит А однобуквенный или пустой, то тождественный нормальный алгорифм в А, определяемый схемой является обращающим. й 33. Алгорифмы побуквенного кодирования и двойного проектирования 1, Поставим в соответствие каждой букве $ алфавита А определенное слово Кг в этом алфавите.

Заменяя в произвольном слове Р в А каждую букву э поставленным ей 172 НОРМАЛЬНЫЕ АЛГОРИТМЫ !ГЛ. ГН в соответствие словом Кь мы получим слово в алфавите А — результахп замены букв $ словами Кд в слове Р. Результат замены букв Б словами Кз в слове Р мы будем обозначать символом Ф (Р). Более точное — „рабочее" — опре- деление этой операции мы дадим посредством равенств Ф(Л) Л, Ф(Р$) — Ф(Р) Кз, где Р означает произвольное слово в А, а $ — любую букву алфавита.

Легко видеть (это доказывается методом праной индук- ции), что для любых слов Р и Я в алфавите А Ф(Р0) -Ф(Р) Ф(()). Кроме того, Ф($)'хК. Нетрудно построить нормальный алгорифм над алфавитом А, выполняющий замену букв $ словами Кы т. е. перерабатывающий всякое слово Р в А в слово Ф (Р). В самом деле, пусть а не принадлежит А. Зададим нормальный алгорифм мд в Аа сокращенно записанной схемой а$ — Кда а — .

где $ пробегает А. Покажем, что для любого Р в А Йд (Р) Х Ф (Р). Из рассмотрения схемы (1) имеем 1.1. Йд. 'Р ) — аР. 1.2. Асд. Ф(Р) а$Я )- Ф(Р5) аЯ. 1.3. Йд. Ра )- ° Р. Далее, имеем 1.4. Йд'. аРЯ ~= Ф (Р) аЦ. Доказывается правой индукцией по Р с использова- нием 1.2. 1.б. Агд: аР)=Ф(Р) а. Частный случай 1.4 при ЯХЛ.

Из 1.1, 1.5 и 1.3 следует (2). Действительно, 'пд Р ) а~ [1 ° 11 ) Ф(Р) а [1.51 )- Ф(Р) [1.31, АЛГОРНФМЫ ПОБУКВЕННОГО КОДНРОВАННЯ дам 173 т. е мд. Р~= Ф(Р), дед (Р) ХФ(Р), откуда Тот же результат дает более простой нормальный алгорифм в А, определяемый сокращенно записанной схемой й-! в которой 5 пробегает алфавит А' ). 2. Важным частным случаем замены букв словами является выбрасывание некоторых букв.

Это — тот частный случай, когда К1ХЛ для некоторых букв $ и КБХ$ для остальных $. В связи с этой операцией в дальнейшем будет применяться следующая терминология. Пусть А — расширение алфавита Б. Результат выбрасывания букв алфавита А" Б из слова Р в А мы называем проекцией слово Р на алфавит Б и обозначаем через [РБ (см. % 19.3). Построение проекций слов в А на Б мы будем называть операцией проектирования из А на Б. ,Соответствующим частным случаем алгорифма йд является нормальный алгорифм в Аа с сокращенно записанной схемой аз $а ац- а где $ пробегает алфавит Б, а ц — алфавит А'~Б. Однако более простой нормальный алгорифм в А с сокращенно записанной схемой Д что и требовалось доказать.

Рассмотрим случай, когда ( есть буква алфавита А и любой букве $ этого алфавита в качестве Ке сопоставляется слово ) . Очевидно, что в этом случае для любого слова Р в А ~А (Р) ['~ НОРМАЛЬНЫЕ ЛЛГОРИФМЫ 1гл. ! н где $ пробегает А' Б, очевидно, достигает той же цели— он перерабатывает всякое слово в алфавите А в проекцию этого слова на алфавит Б и, следовательно, вполне экви- валентен кл относительно А. 3. П кого сло . Пусть А и Б — алфавиты без общих букв. Дл ля всяова Р в объединении этих алфавитов возможно построить как проекцию [РА на алфавит А, так и проек- цию [Рв на алфавит Б. Покажем, что нормальный алго- рифм Вх в в алфавите АБ с сокращенно записанной схемой (т1$ - $Ч, где й пробегает А, а т1 пробегает Б, переоабатывает вся- кое слово Р в алфавите АБ в слово [Рх[Рй. Для этого условимся прежде всего называть высотой слова Р в алфавите АБ число вхождений в Р слов вида т)Д$, где $ — буква А, т1 — буква Б, а 1;1 — любое слово в АБ.

Высоту слова Р будем обозначать символом [Р'. Докажем некоторые леммы. 3.1. Если Р,— слово в АБ, ~ — буква Б, то (1) [Р -[~") В самом деле, соотнесем всякому вхождению (2) 5 !К т1Я ть Т слова вида т11;1Я ($ — буква А, т1 — буква Б) в Р вхождение (3) 5 !к !ЯК !х Т~ зом того же слова в )с». Вхождение (3) будем называт б вхождения (2). Очевидно, что разные вхождения слов вида ЧЯ (э — буква А, Ч вЂ” буква Б) в )с имеют разные образы. Р ассмотрим, с другой стороны, какое-нибудь вхождение (4) Уж!1яжр слова вида т111ч (й — буква А, т1 — буква Б) в Тс!",.

Имеем (5) и )ВРАЛ~, Здесь $ф'.!., так как $ — буква А, !,— буква Б. Поэтому $'~'Л и )» оканчивается буквой ~, т. е. (6) ух йгь. см. 4 18.!О. е) Относительно применяемой ниже арнфметичесией символики З за! ЛЛГОРИФМЫ ПОВРКВЕННОГО КОДИРОВХНИЯ 175 Имеем УЧЖ~'я.(с [(6) (6)1 откуда следует, что (7) У !К т111 $ !К (т' есть вхождение т1Я в Я. В силу (6) вхождение (4) есть образ вхождения (7). Таким образом, всякое вхождение слова вида !Д$ ($ — буква А, ц — буква Б) в 7(~ есть образ некоторого вхождения того же слова в К. Следовательно, соотнеся каждому вхождению слова вида т)(Д (5 — буква А, т1 — буква Б) в )с его образ, мы тем самым установили взаимно однозначное соответствие между вхождениями таких слов в )с, с одной стороны, и их вхождениями в Я~ — с другой.

Поэтому имеет место равенство (1), что и требовалось доказать. 3.2. Если тс — слово в АБ, Г,— буква А, то (6) [)!1Г = [Р'+ [[Р"-з. В самом деле, определим образ вхождения слова вида тф$ ($ — буква А, 9 — буква Б) в )с, как в доказательстве предыдущей леммы. Вхождения слов этого вида в Я(,, являющиеся образами вхождений таких слов в )с, будем называть вхождениями 1-го рода. Они находятся во взаимно однозначном соответствии со вхождениями слов вида т1К (й — буква А, т1 — буква Б) в К, и число их поэтому равно ф'.

Поставим далее в соответствие каждому вхождению (9) 3 * 3 * Т какой-нибудь буквы т алфавита Б в слово Р вхождение (1()) Ежтт1ж слова 1(Т~ в тсь. Вхождение (10) также будем называть образом вхождения (9). Так как Ь вЂ” буква А, образ всякого вхождения буквы алфавита Б в Я есть вхождение слова вида тЩ (5 †бук А, т1 †бук Б) в й!~, Разные вхождения букв алфавита Б в К, очевидно, имеют разные образы, т. е.

соответствие между этими вхождениями и их образамн взаимно однозначно. Будем называть вхождениями 2-го рода образы вхождений букв алфавита Б в слово Р. Число вхождений 2-го рода равно числу вхождений букв алфавита Б в )ч', т. е. оно равно [[1~аз. Ни одно вхождение 1-го рода не может быть вхождением 2-го рода, так как вхождения 1-го рода имеют непустое правое крыло, а вхождения 2-го рода — пустое правое крыло.

!76 [гл. Ри НОРМАЛЬНЫБ АЛГОРИФМЫ Всякое вхождение слова вида т!Я ($ — буква А, т!— буква Б) в ЯЬ является вхождением 1-го или 2-го рода. Действительно, рассмотрим какое-нибудь вхождение (4) слова этого вида в ттЬ". Если )»~ЕЛ, то, рассуждая„как в доказательстве предыдущей леммы, убеждаемся, что (4) есть образ некоторого вхождения того же слова в 1с, т. е. вхождение 1-го рода. Если УХЛ, то (4) является, очевидно, ОбраЗОМ ВХОждЕНИя У»вт!»К!Е буКВЫ т! авфаВИта Б В 1С, т. Е.

вхождением 2-го рода. Таким образом, число вхождений слов вида т)Щ (Б— буква А, т! — буква Б) в Рть" равно сумме чисел вхождений 1-го рода и 2-го рода, т. е. сумме чисел [)т' и П)тва, что и выражается равенством (8). 3.3. Если К вЂ” слово в АБ, а Ь вЂ” буква этого алфавита, то [РР [)»в 1 (ПЕБд Х П~ла) В самом деле, ПЬАа есть 1, если ь — буква А, и О если ь — буква Б. В силу этого З.З следует из 3.1 и 3.2.

Характеристики

Тип файла
DJVU-файл
Размер
4,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6366
Авторов
на СтудИзбе
310
Средний доход
с одного платного файла
Обучение Подробнее