ДС18о03-алгорифмы-Маркова (1238918)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonАлгоритмыМарковаАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 3, 21 сентября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Нормальные алгорифмы Маркова1946 г.2ОбозначенияПусть s, s’, a, b, b’, g - некоторые, возможнопустые, строки в алфавите Vпричемs = abg и s’ = ab’gТогда s’ есть результат подстановкиb’ в строку s на место строки b.Такая подстановка может быть задана функциейf(s,a,b,b’)Пример: s=aaaaa, b=aa, b’=b,3Нормальная подстановкаФункция f(s,b,b’) задаёт нормальнуюподстановку, заменяя самое левое вхождениестроки b в строку s на строку b’.Пусть V={a,b,…} – основной алфавит,V’={A, B, …} – вспомогательный, причем VÇV’=Æи b, b’Î(VÈV’)*Тогда b " b’ – это простое правило,а b * b’ – конечное правило подстановки.4Нормальный алгоритм МарковаУпорядоченное множество подстановок видовb " b’ и b * b’Исполнитель, просматривая слово s слева направо,пытается последовательно применить к нему правилаиз множества подстановок.1.

Если удается применить правило вида b " b’, топроцесс повторяется со словом s’;2. Если – вида b * b’ – происходит результативныйостанов.3. Если не удается применить ни одно из правил –останов не результативный (аварийный).5Пример 1: сложение унарных чисел |+ " +|2 +| " |ƒ |* |||||+||+||||||+|||+|||…+||||||+|||…++|||||||||2+|||||||||||||||||||||||||||2ƒ6Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол. Пустое слово не менять.a*b*®**a **b *bbbabab -> bbbbabbbbabab ® *bbbabab ® **bbbabab…7Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол.

Пустое слово не менять.®**a **b *bbbabab ® *bbbabab ® **bbbabab…*a **b *®*bbbabab ® *bbbabab ® bbabab8Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол. Пустое слово не менять.*a **b *®*® * ® **…*a **b ***®*bbbabab ® *bbbabab ® bbabab®*®9Композиция алгоритмов Марковаo Пусть заданы два алгоритма R и S.o Задача: построить алгоритм,который будет выполнять S(R(s)).o Проблема: как заблокировать подстановки Rпосле того, как завершён R и заработал S10Композиция алгоритмов Маркова1.2.3.4.xa®axax®axxh®xhxb®bxn правилn правилn2 правилn правил5.6.7.8.9.bx®bxxh®xhab *SbRan правилn2 правил11Композиция алгоритмов Маркова1.Удвоим алфавит, добавив для каждогосимвола алфавита x его близнеца x2.Добавим еще два символа a и b,которые не входили в исходный алфавит.3.Преобразуем R в Ra заменойправил вида … * z на …®azПреобразуем S в Sb заменой4.1.2.x на xправил вида … * z на …®zb12Пример композиции101+11R: переводдвоичного0|01+1100||1+11в унарное |0 ® 0|| 00||0|+1100|0|||+112 1® 0|000|||||+11ƒ 0®000|||||+0|1*000|||||+0|0|S: суммирование 000|||||+00|||… |||||+|||„ +®||||||||*…22222ƒ„…13Формальная схема|a+aa|a+|+||+|++|bb|||ab®®®®®®®®a|a+a|a+|+||+|++® b|® b|® ||*a11+1|||+|+ ®0|1+1a|||+|a®ab0|0|+1 a|||+|00|||+1 a|||+||0 ® 0|| 00|||+0| a|||+|1 ® 0|0|||+0| a|||+|0 ®|||+0| a||||l ® a|||+|ab||||ab||||ab||||ab||||Вместоab||||l ® b||||14u b1 ® 1bv b0 ® 0bw b *Перевод в унарнуюПеревод в двоичнуюa|| ® |a5|0 ® 0|| 1a| ® 16® 0| 21a® 07®30Сложение® a|8|®4+® b}|®|U15Пример101+111 20|01+111 1|||||+||||||| 400||1+111 2|||||||||||| U…U00||0|+111 1|||||||||||| 800|0|||+111 1000|||||+111 2000|||||+0|11 2000|||||+0|0|1 1000|||||+00|||1 2000|||||+00|||0| 2000|||||+00||0||| 2000|||||+00|0||||| 2000||||| + 000||||||| 3…316Примерa|||||||||||| 5|a|||||||||| 5||a|||||||| 5|||a|||||| 5||||a|||| 5|||||a|| 5||||||a 7||||||0 8a||||||0 5|a||||0 5||a||0 5|||a0 7|||00 8a|||00 5|a|00 6|100 8a|100 61100 }b1100 u1b100 u11b00 v110b0 v1100b w110017Проблема самоприменимостиНевозможно построить НАМ, которыйдля любого другого НАМ выносил бырешение о том, произойдет или нетостанов этого НАМ при его работе надданными, представляющимиописание этого НАМ.18Проблема самоприменимостиСамоприменимый1 a*bпосколькуa*b1b*bНесамоприменимый1 a ® abпосколькуa ® ab 1ab ® ab 1abb ® ab 1…19.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций