🗊Презентация Алгоритмы Маркова

Алгоритмы Маркова

Андрей Андреевич Марков Андрей Андреевич Марков (1903-1979), советский математик. Сын известного русского математика А.А.Маркова. Окончил Восьмую Петроградскую Гимназию в 1919 году. Окончил Ленинградский Университет в 1924 году. Окончил аспирантуру в Астрономическом Институте (Ленинград) в 1928 году.

Алгоритмы Маркова В 1954 году советский математик А.А.Марков предложил другую алгоритмическую схему, эквивалентную машине Тьюринга, в которой данные преобразуются на основе других принципов. В алгоритмической схеме Маркова нет понятия ленты и осуществляется непосредственный доступ к различным частям преобразуемого слова. Марков назвал эту алгоритмическую схему нормальным алгоритмом.

Схема алгоритма: Формат команды (строки) следующий Pi (∙) Qj, где Pi – последовательность символов, которая ищется в слове  - знак перехода к операции записи Qj - последовательность символов, которая записывается вместо найденной (•) - знак принудительного окончания алгоритма (необязательный параметр)

Нормальный алгоритм над А преобразует слова в алфавите А следующим образом. Работа данного нормального алгоритма над словом R состоит из отдельных шагов,в результате которых получаются слова R=R1 ,R2 ,R3 ,….,Ri ,Ri+1,… (1) Нормальный алгоритм над А преобразует слова в алфавите А следующим образом. Работа данного нормального алгоритма над словом R состоит из отдельных шагов,в результате которых получаются слова R=R1 ,R2 ,R3 ,….,Ri ,Ri+1,… (1) Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в "начало" работы алгоритма и вновь проверяется на возможность применения правил подстановки.

Пример1. Пример1. Тождественный нормальный алгоритм над А – это нормальный алгоритм над А, который применим к каждому слову в алфавите А и результатом работы которого является это же слово. Такой алгоритм может быть задан алфавитом В=А (не содержащим → и ∙ ) и нормальной схемой {→∙ Пример 2. Нормальный алгоритм над А «левого присоединения» слова Q(фиксированного) – это нормальный алгоритм над А, применимый к каждому слову R в алфавите А, и результатом работы которого над словом R является слово QR. Такой алгоритм может быть задан алфавитом В=А и нормальной схемой {→∙Q Заметим, что самое левое вхождение является пустым словом.

Пример 3. Пример 3. Нормальный алгоритм над алфавитом {a,b} «правого присоединения» слова aba – это нормальный алгоритм,применимый к каждому слову в алфавите {a,b} , и результатом работы которого над словом R будет слово Raba. Зададим его алфавитом В={a,b,c} и нормальной схемой ca → ac cb → bc c → ∙ aba → c

Пример 4. Пример 4. Рассмотрим алгоритм, который перерабатывает всякое слово Р в алфавите А,содержащее хотя бы одно вхождение буквы b ,в слово,которое получается вычеркиванием в Р самого левого вхождения буквы b. Пусть А есть алфавит {b,c}. Рассмотрим схему подстановки:

Пример 5. Пример 5. Нормальный алгоритм удвоения – это нормальный алгоритм над А, преобразующий каждое слово R в алфавите в слово RR. Пусть А={a,b}. Зададим нормальный алгоритм над {a,b} алфавитом {a,b,c,d} и нормальной схемой ca → adac cb → bdbc daa → ada dab → bda dba → adb dbb → bdb d →Λ c → ∙ Λ → c Здесь аналогично заводятся два рабочих символа с и d. с по последней формуле подстановки как бы навешивается на пустое слово. Пояснение: da – это дубликат символа a, db – дубликат символа b. Алгоритм сначала заводит дубликаты каждого символа исходного слова, а затем переставляя местами дубликаты символов и сами символы, собирает все дубликаты в конце слова. Заметим, что дубликаты не могут переставляться с дубликатами и символы не могут переставляться с символами.

Т.о с и d являются вспомогательными атрибутами,хранящими и обрабатывающими в процессе выполнения алгоритма промежуточные состояния возможных подслов,которые впоследствии удваивают каждый символ.Т.о каждому входному символу присваивается свой рабочий символ Т.о с и d являются вспомогательными атрибутами,хранящими и обрабатывающими в процессе выполнения алгоритма промежуточные состояния возможных подслов,которые впоследствии удваивают каждый символ.Т.о каждому входному символу присваивается свой рабочий символ Работа предыдущего нормального алгоритма над словом bab состоит из следующей последовательности слов : bab → cbab → bdbcab → bdbadacb → bdbadabdbc → badbdabdbc → badbbdadbc → babdbdadbc → babbdadbc → babbadbc → babbabc → babbab . (каждое подчеркнутое подслово заменяется определенным правилом подстановки)

Пример 6. Пример 6. Алгоритм, состоящий из одной строки, вида 0  * будучи примененным к слову в алфавите {0,1}, заменит все нули на звездочки. В свою очередь алгоритм 0  * • будучи примененным к слову в алфавите {0,1}, заменит на звездочку первый встреченный ноль. Пример 7. Довольно сложная для реализации на машинах Тьюринга задача сортировки слова по возрастанию, решается при помощи алгоритма Маркова намного быстрее и проще. Допустим в алфавите {0,1,2} : 20  02 10  01 21  12

Построим алгоритм для вычисления функции U(N)=N+1; Построим алгоритм для вычисления функции U(N)=N+1; S={0,1,2,3,4,5,6,7,8,9};   V={*,+}. Схема имеет вид; Перегоняем служебный символ * в конец слова n, чтобы  отметить последнюю цифру младших разрядов. Увеличиваем на единицу, начиная с цифр младших разрядов.    Сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна: (k+1)+(m+1), где k - количество цифр в N, m - количество 9, которые были увеличены на 1.

Вычисление числовой функции с помощью нормального алгоритма. Целое неотрицательное число m будем изображать словом из m+1 едениц. Набор чисел m1,m2…,mn будем обозначать словом 1m(1)+1 * 1m(2)+1 *…* 1m(n)+1. Пример 8. Построим нормальный алгоритм М ,вычисляющий числовую функцию f(x)=x+1. Нормальный алгоритм зададим алфавитом {1} и нормальной схемой {1→∙11. Он применим к каждому слову в алфавите {1},и его работа при вычислении f(m) для любого числа m состоит из двух слов 1m+1,1m+2 . (1m=11….1- m раз)

Пример 10. Пример 10. Дано произвольное двоичное слово. Надо убрать из него два первых знака. Рассмотрим алгоритм вида: 00  • 01  • 10  • 11  • Если даны слова например «001011» или «01011101» , то алгоритм действительно выполнит указанную задачу . Но в слове 1100101 выбросятся два нуля, которые вовсе не являются первыми символами слова. В этом случае существующий алфавит надо расширить вспомогательными буквами. Они вводятся с помощью формулы λ  α (α – вспомогательная буква) или, что более корректно, пары формул λ 0  α 0 λ 1  α 1 Применив такие продукции к слову λ 1100101 λ получим: λ α 1100101 λ α 0  β α 1  β λ β 100101 λ β 0  • β 1  • λ 00101 λ

Доказательство: Пусть функция f(x1,…,xn) вычислима по Тьюрингу и ее вычисляет машина Тьюринга Т с алфавитом А. Пусть С- расширение алфавита А. Покажем, что существует нормальный алгоритм ВТ,C над С, вполне эквивалентный относительно С машине Тьюринга Т. Это означает,что для любых натуральных чисел k1,…,kn найдутся такие слова R1 и R2 (возможно,пустые) в алфавите {S0} (S0 – изображение пустой ячейки ленты МТ),что BT,С (k1*…*kn)= R1 f(k1,…,kn)R2 .

Пусть С= А U {qk(0),…,qk(m)}, где qk0,…,qk(m)-внутренние состояния Т и qk0=q0.. Пусть С= А U {qk(0),…,qk(m)}, где qk0,…,qk(m)-внутренние состояния Т и qk0=q0.. Построим схему для искомого алгоритма BТ,С : 1) выпишем сначала для всех команд вида qiSi : SkН qr машины Тьюринга Т подстановки qiSi→qrSk. 2) Затем для каждой команды вида qiSi : Sk L qr выпишем все возможные подстановки вида SnqiSi→qrSnSk,, где Snє A, и формулу подстановки qiSi→qrS0Sk... 3) Далее для каждой команды qjSi: Sk R qr выпишем все возможные подстановки qjSiSn→SkqrSn ,где Sn єC, и формулу подстановки qjSi→SkqrS0.. 4) Далее выпишем всевозможные формулы подстановки qk(i)→Λ, где qk(i) єС и формулу подстановки Λ→q0. Полученная таким образом схема определяет некоторый нормальный алгоритм BТ,С над С, и легко показать ,что BТ,С(Р)≈Т(P) для любого слова Р ,т.е BТ,С – есть искомый алгоритм Маркова.

Пусть G1-нормальный алгоритм над {1,*,S0},стирающий все вхождения S0 перед первым вхождением 1 или * во всяком слове в алфавите {1,*,S0}.Такой алгоритм задается схемой1 Пусть G1-нормальный алгоритм над {1,*,S0},стирающий все вхождения S0 перед первым вхождением 1 или * во всяком слове в алфавите {1,*,S0}.Такой алгоритм задается схемой1 Пусть также G2-нормальный алгоритм над {1,*,S0},который стирает все вхождения S0 после последнего вхождения 1 или * во всяком слове в алфавите {1,*,S0}.G2 можно задать схемой2:

Положим теперь G = G2◦ G1◦ BТ,С. Положим теперь G = G2◦ G1◦ BТ,С. Для любых натуральных k1,…,kn имеем ВT,C (k1*…*kn )≈ R1f(k1,…,kn)R2 где R1 и R2- некоторые слова в {S0}. Поэтому G1(R1f(k1,…,kn)R2 )≈ f(k1,…,kn)R2 и G2(f(k1,…,kn)R2 )≈ f(k1,…,kn). Получаем ,что f есть вычислимая по Маркову функция, которую вычисляет нормальный алгоритм G.

Теорема 2: Всякая вычислимая по Маркову функция вычислима по Тьюрингу. Доказательство: Пусть В – нормальный алгоритм в алфавите А, не содержащем S0 и σ.Тогда существует МТ М(АU{S(0),σ}) в алфавите АU{S0,σ} , такая что для всякого слова W в А машина М применима к W тогда и только тогда, когда к W применим алгоритм В, и при этом М(W) имеет следующий вид

Пусть A={S1,S2…Sk}. Пусть A={S1,S2…Sk}. Пусть P→(∙)Q – произвольная формула подстановки. Построим систему команд МТ, действие которой состоит в замещении самого левого вхождения слова Р в произвольное слово W (если такие вхождения вообще имеются) словом Q. Если Р≠Λ,то пусть Р=b0…br

Рассмотрим следующую систему команд q0 Si R q0 (SiєA,Si≠b0) q0 b0 σ q0 q0 σ R q2 q2 b1 R q3 q2 Si Si qr+2 (Siє АU{S0} , Si≠b1) q3 b2 R q4 q3 Si Si qr+2 (Siє АU{S0} , Si≠b2) …............. qr br-1 R qr+1 qr Si Si qr+2 (Siє АU{S0} , Si≠br-1) qr+1 br R qr+4 qr+1 Si Si qr+2 (Siє АU{S0} , Si≠br) qr+2 Si L qr+2 (Siє АU{S0} ) qr+2 σ b0 qr+3 qr+3 b0 R q0 q0 S0 L qr+5 qr+5 Si L qr+5 (SiєA) qr+5 σ b0 qr+5 qr+5 S0 R qy где индекс Y- некоторое целое число,большее любого из индексов,которые еще будут употреблены.

Эта система команд следующим образом действует на слово W: Эта система команд следующим образом действует на слово W: если W не содержит вхождений слова Р, то действие этой системы команд заканчивается конфигурацией qYW. Если же W содержат вхождения слова Р и W=W1P W2, где W1 и W2 определяются самым левым вхождением слова Р в W,то работа системы команд закончится конфигурацией W1P qr+4 W2. Приведенную систему команд следует расширить дополнительными командами,с помощью которых выделенное вхождение слова Р заменялось бы на Q. Пусть Q=c0…cs. Возможны три случая:

1) s=r, т.е Р и Q – слова одной длины. В этом случае добавим команды: 1) s=r, т.е Р и Q – слова одной длины. В этом случае добавим команды: qr+4 Si L qr+7 (Siє АU{S0} ) qr+7 br cr qr+8 qr+8 cr L qr+9 qr+9 br-1 cr-1 qr+10 qr+10 cr-1 L qr+11 ………… q3r+7 b0 c0 q3r+8 q3r+8 Si L q3r+8 (SiєA) q3r+9 S0 R qu Применяя эти команды к W1 P qr+4 W2 мы получим quW1Q W2. Где

2) s<r , т.е. Q короче Р 2) s<r , т.е. Q короче Р Добавим команды: qr+4 Si L qr+7 qr+7 br cs qr+8 qr+8 cs L qr+8 ….. qr+7+2s+2 br-s-1 S0 qr+7+2s+2 qr+7+2s+2 S0 L qr+7+2s+3 qr+7+2s+3 br-s-2 S0 qr+7+2s+3 qr+7+2s+3 S0 L qr+7+2s+4 ……. q2r+s+8 b0 S0 q2r+s+8 Применение этих команды к W1P qr+4 W2 приводит к конфигурации W1q2r+s+8S0r-s Q W2 . Теперь предусмотрим команды,с помощью которых можно было бы слово W1 подвинуть на ленте на r-s квадратов вправо,чтобы получить слово W1QW2..Пусть М –целое число,больше всех встречающихся выше индексов при qi и Si,,,например М=3r+9

Добавляем команды: Добавляем команды: Начиная с конфигурации W1q2r+s+8S0r-sQW2 ,с помощью этих команд приходим при некотором положительном p к конфигурации (S0)pquW1QW2 3) s>r, т.е слово Q длиннее слова Р. Этот случай рассматривается аналогично.

Пусть теперь задан произвольный нормальный алгоритм G в алфавите А={S1,..Sk}, не содержащий S0 и σ, и схема алгоритма G есть Пусть теперь задан произвольный нормальный алгоритм G в алфавите А={S1,..Sk}, не содержащий S0 и σ, и схема алгоритма G есть P1→(∙)Q1,.., Ph →(∙)Qh. Определим машину Тьюринга М следующим образом. 1). Воспроизведем всю предыдущую конструкцию для P1→(∙)Q1. 2). Перейдем ко второй подстановке. Построим список команд по образцу, который изложен выше. Эти полученные команды будут начинать действие после того, как слово, полученное первой группой команд, окажется лишенным вхождения слова Р1 .

С помощью этих новых команд находящееся на ленте слово будет испытываться на наличие в нем вхождений слова Р2. При этом имеются 2 возможности: С помощью этих новых команд находящееся на ленте слово будет испытываться на наличие в нем вхождений слова Р2. При этом имеются 2 возможности: А) Самое левое из них будет замещено на Q2 и машина перейдет в состояние q1, если P2→(∙)Q2 заключительная подстановка, либо в состояние q0 ,если – простая формула подстановки. Б) Вхождений P2 нет. Машина работающая по командам P2→(∙)Q2 в конечном итоге оставляет без изменения находившееся на ленте слово. Теперь начинают действовать команды P3→(∙)Q3, которые строятся аналогично. 3). Т.о достраиваем всю систему команд машины Тьюринга М, которая имитирует работу нормального алгоритма В в том смысле, что для любого слова W в А машина М применима к W тогда и только тогда, когда к W применим В и М(W) имеет вид (S0)mВ(W)(S0)n, где m и n-целые неотрицательные числа.