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

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

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

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

3.4. Если Р и Д вЂ” слова в АБ, то (11) [Рй' *[Р'+[дв+(Пр хала). Фиксируем Р и докажем правой индукцией по а(, что всякое слово Я в АБ удовлетворяет равенству (11). Пустое слово удовлетворяет ему, так как, очевидно, [Л" О, ПЛ~.-О. Чтобы доказать лемму, нам поэтому надо лишь дока- зать, что соблюдение равенства (11) для какого-нибудь слова )с в АБ влечет соблюдение равенства [Р1»ввв,[Р»+ф~в 1 (ПРБдХПР~Ад) для любой буквы ь алфавита АБ. Итак, допустим, что равенство (11) соблюдается, причем Я есть слово Б АБ.

Пусть также Ь вЂ” буква АБ. Имеем (12) [[Ргхь [[РАа 1 [[вьхь (1з) ПРД ' = Првь+ ПД~, [Рд~' [рд» 1 (Прдэах П~Аа) [3 3) ° [Р'+ [д'+(Прад х Пдлд)+ ((ПР' + ПД ) х В" ) [(11), (1З)1 [р'+[д'+(Пд хц~ )+(Првьх(цд +П~"а)) [Р'+[)7Г 1 (ПрааХПК~Аа) [3 3 (12)1 что и требовалось доказать. ;,а асч АЛГОРИФМЫ ПОБУКББННОГО КОДИРОВАНИЯ !77 3.5. Для любых слов Р, (Е и Я в АБ ,;. [РСЕ)тв ~ [Рв + [('!в 1 [Рв+ (ЦРБдХ П()Аа) (ПрвахцЯАа) 1 (ПЯБахцДАа) В самом деле, имеем :,вв [Р()Р [Р1~! +[К +(ПРЯБахцйвд) [3 4~ -[Р +% +(ПРБдхПЮАа)+ Р +(ПРБ[() хцр"') [3.41 [рв„( [() 1 [1зв+ (Прад х П два)+ ((ПРБ'+ ПЯБд) х Пдль) -[ +я +[я +(Пр-хПЕ"')+ (Првь Х ПРАа)+(П Евь Х 1РАа) 3.6.

Если [Рв О, то существуют такие слова (1 и Я »(з в сифавитах А и Б соответственно, что Рл.!',»)с. 4. Пусть, в самом деле, [Р' О для некоторого слова Р Рз в алфавите АБ. Если в это слово не входят буквы алфавита Б, то Р есть слово в А и можно положить Я Х Р, ЯХЛ. Допустим, что в Р входят буквы алфавита Б. Пусть тогда (Е»БЧ»Б'О' — первое вхождение буквы алфавита Б в Р. !е есть тогда слово в А, т! — буква Б. Если бы Т»Б~»РУ было вхождением буквы $ алфавита А в Я, то мы имели бы Ечв Х(ЯТ~(7 и слово т!Т$, где $ — буква А, т! — буква Б, входило бы в Р вопреки тому, что [Р" О, Следовательно, никакая буква алфавита А не входит в 5 и 3 есть слово в Б. Остается положить )сйт~5, чтобы иметь Рй!Я, где !е — слово в А, )т †сло в Б.

3.7. Если Я вЂ сло в А, й †сло в Б, то [(тс А ~~ [ф~в~К,' Это очевидно из определения проекций. 3.8. Если [Р'. О, то РХ[РА[РБ, Это следует из двух предыдущих лемм. 3.9. Если [Р' О, то А»А, Б: 1' ~. В самом деле, если [Р' О, то никакие слова вида т)Я (3 †бук А, т! †бук Б), т. е. никакие левые части фор- 178 НОРМАЛЬНЫЕ АЛГОРИФМЫ [гл. мул подстановок алгорифма ВА Б, не входят в Р. Это слово тогда не поддается ВА, в.

3.10. Если [РвчьО, то существует такое слово (е, чта ВА,,': Р)-Е. Пусть, в самом деле, Р— слово в АБ и [Рв-е-О. Тогда в Р входит слово вида 111т9, где $ — буква А, и — буква Б. Пусть Е Ж ЧРтя Ж Т будет вхождением такого слова в Р.

В слово ЧЯ$ входит буква алфавита А, Пусть УЖЬЖ'ввпервое вхождение буквы алфавита А в Ч)ск. Тогда У)~А, так как ь Л'71. У есть слово в алфавите Б, Следовательно, У имеет вид Ф'д, где 7 — буква Б. Имеем поэтому Ьтт м БЩУТ и тхжт. Таким образом, в Р входит слово х~, где ь" — буква А, у — буква Б, т. е.

в Р входит левая часть одной из формул подстановок алгорифма ВА Б. так как все формулы подстановок этого алгорифма простые, алгорифм просто переводит Р в некоторое слово Я, что и требовалось доказать. 3,11. Если ВА, Б. .Р[ — Я, то Я'=[Р' — 1, [Я~Х[РА, [()Б ~ [РБ В самом деле, пусть ВА, в..

Р) — 1~. Тогда первый шаг применения алгорифма ВА, в к слову Р состоит в подстановке правой части св1 одной из формул подстановок алгорифма вместо первого вхождения ее левой части ц$ (9— буква А, 11 — буква Б). Пусть 1сЖтДЖŠ— первое вхождение зД в Р. Тогда Р тг 7(тДЕ, ~хЯЧЕ. Принимая во внимание, что по определению высоты [~Д'= 1, дч =о' и что [[Б„Аг [[е„вг [[„БАг [[„евг получаем, согласно 3.5, [Р -Р +1+[я+[[РБ +([Рзг Х [[9Аг)-+УАг, [е7в [Авв+[Ов+[[над 1 (Увел УАг)+УАг Огкуда [Яв=[Рв — 1. ':ввм АЛГОРИФМЫ ПОБУКВЕННОГО КОДИРОВАНИЯ Принимая далее во внимание, что [$11А 9г. [т)Р Х $, 179 получаем [РА Б [ОА1 [ОА ~[()А Аналогичным образом убеждаемся, что [РБХЯБ.

3.12. Алгорифм ЙА, Б применйм к любому слову в АБ. В самом деле, согласно 3.9 он применйм к любому .слову высоты нуль. Пусть теперь )е' — какое-либо натуральное число. Предположим, что 2А Б применим ко всякому слову 1е в АБ такому, что [ве'=А), и пусть Р— слово в АБ такое, что [Р'=)в"+1. Покажем, что ВА, Б применим к Р. Действительно, [РАФО, и, значит, существует такое слово Я, что ВА, Б. 'Р1 — (е [3.!0]. согласно 3.11 [Аг'=У, и потому алгорифм В», в применим к ~. Но тогда он применим и к Р [9 25.8.9]. Следовательно, ВА, Б применим к любому , слову в АБ, что и требовалось доказать. Покажем теперь, что (14) ВА, в (Р) Х[РА [РБ , для всякого слова Р в АБ. Пусть, в самом деле, Р— слово в АБ. Алгорифм ВА, Б , применим к Р [3.12].

Следовательно, существует 1~ в АБ , такое, что В~, Б(Р)Х(Е. Ясно, что (15) В.,,:;~Е~ н что в7 — слово высоты нуль [3.10]. Индукцией по шагам работы алгорифма ВА, Б с использованием 3.11 легко пока- зать, что (16) [РА — [()А (17) [РБ У [()Б Так как фв О, имеем (18) О~[ОА[ОБ Таким образом, ВА, в (Р) х (е' вА[1;1А [1е [(18)] Х [РА [РБ [(16), (17)]. Следовательно, ВА Б(Р)х~Р'[РБ, что и требовалось до. казать, 180 НОРМАЛЬНЫЕ ЛЛГОРНФМЫ [гл. Рн Формулируем здесь одно следствие, применяемое в дальнейшем. 3.12.

Если Я вЂ” слово в А, Я вЂ” слово в В, то (19) Вл, ь(У(е)~ (Ж. В самом деле, при этих условиях [щам я, [о()в тг р и потому (19) следует из (14). Соотношение (14) позволяет нам охарактеризовать Вл, ь как алгорифм двойного проектирования. 2 34. Некоторые арифметические алгорифмы 1. Построим теперь некоторые нормальные алгорифмы, работающие над натуральными числами и системами натуральных чисел. Отсюда до конца параграфа М, У, Я, )1, 3 означают переменные для натуральных чисел, представленных как слова в алфавите 1. Зададим нормальный алгорифм Ит в алфавите 1:«схемой «с Этот алгорифм перерабатывает пару натуральных чисел УФМ в абсолютную величину разности этих чисел, т.

е. (2) И, (У*М) х1У вЂ” М1 для любых натуральных чисел У и М. Действительно, из рассмотрения схемы (1) имеем 1.1. И,: М1Ф1У1 — МФУ. 1.2. И„: МФ)- М. 1.3. Й,: «М 1- М. 1.4. И~.' М 1. Кроме того, правой индукцией по У с использованием 1.1 и равенства У!Х! У могут быть доказаны следующие утверждения: ~1.6. И: муФу)=мж. 1.6. Ит: У:«УМ )= ж М. А теперь утверждение (2) доказывается следующим образом, зл1 нькотогыв лгнематнчьскиз ллгогифмы ~81 Если Уч.:;М, то УЖМхгУ:«У1У вЂ” М! и Й,: У4сУ1У вЂ” М1~=ж1У вЂ” М! [1.6] )- ! У М 1.] [1.3, 1.4]. Если же У) М, то УФМХ1У вЂ” М1М«М и Й,: ! У вЂ” М1М:«М)=1У вЂ” М1:«[1.5] ~=! У вЂ” М1 1 [1.2, 1.4].

, В обоих случаях, следовательно, Й, (У Ф М) лг1 У вЂ” М 1, : что и требовалось доказать. В частности, И,(М Ж У)я.Л тогда и только тогда, когда М лгУ, 2. Зададим далее нормальный алгорифм И, в алфавите ! ' схемой (1) 1П И!- Покажем, что он перерабатывает всякое натуральное число в остаток от деления этого числа на 5. В самом деле, из рассмотрения схемы (1) непосредственно усматривается справедливость следующих лемм: 2.1. И;. У+51- У. 2.2. Если У < 5, то И;.

У~. Из 2.1 вытекает 2.3. И;. 1с+ 5 х 9 ~= 11. Пусть теперь У вЂ” произвольное натуральное число. Представим его в виде У+5х Я, где У вЂ” остаток, Я— частноеотделения У на 5. Так как У У+бхай и У<5, алгорифм Й, в применении к слову У работает следующим образом: И;. У 1= Я 1 [2.3, 2.2], откуда Й,(У) хУ, что и требовалось доказать.

В частности, И,(У) ХЛ тогда и только тогда, когда У делится на 5. 3. Зададим теперь нормальный алгорифм Й, в алфавите ж схемой АППП!-1ж «с! 182 НОРМАЛ ЬНЫЕ АЛГОРИФМЫ [гл. п~ .; гзм НЕКОТОРЫЕ АРИФМЕТИЧЕСКИЕ АЛГОРИФМЫ 183 Покажем, что он перерабатывает всякое натуральное число У в неполное частное от деления У на 5, т. е. в ~ — ~ В самом деле, из рассмотрения схемы (1) легко усматривается справедливость следующих лемм: 3.1.

Й,: Ухч(М+5) ) — (У+1)КМ. 32. Если 0<М<5, то Й,: УжМ ) — УФ(М вЂ” 1). 3.3. Й,: Уж)- У. 3.4. Йз1 У 1- ФУ. Из 3.1 вытекает 3.5. Йз1 УФЯ+5З~Д) )==(У+(г)зКзч. Из 3.2 вытекает 3.6. Если У < 5, то й,: ржу~=дж. Пусть теперь У вЂ произвольн натуральное число. Представим его в виде Я+5хЯ, где Я вЂ” остаток, частное от деления У на 5. Так как У У+5Х Я и У < 5, алгорифм Й, в применении к слову У работает следующим образом: Й,: У) — чч(Р+бх ф [3,41 ~ЯФЯ [3.51 [3.61 )- Я.

[3.31 Таким образом, й,: У)= 1г, откуда й,(У)Х9, что и требовалось доказать. 4. Легко также построить нормальный алгорнфм в )Ф, перерабатывающий всякое натуральное число У в пару 1гФЯ, где Я вЂ” частное от деления У на 5, У вЂ” остаток от этого деления. Зададим, в самом деле, нормальный алго- рифм й, в [ж схемой *! ПП-!ж Ф- Ж вЂ” > яч, Этот алгорифм работает указанным только что образом, как читатель без труда докажет. ') Прямоугольные скобки прнменнютсн здесь длн обознзченни Велоя части.

Делитель 5 в трех предыдущих примерах взят только для определенности. Такие же нормальные алгорифмы можно, очевидно, построить для деления иа любое другое, отличное ,' от нуля натуральное число. Для этого надо только заменить пять черточек в левой части первой формулы каждой из трех только что рассмотренных схем соответствующим другим числом черточек. Если бы мы, однако, попытались построить 1- аналогичные алгорифмы для деления на нуль, совсем отбрасывая черточки в левой части первых формул этих схем, то, как 4 нетрудно видеть, мы получили бы алгорнфмы, не применимые ни к какому натуральному числу, что, разумеется, вполне соответствует сущности дела.

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

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

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

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