Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів.
У 1956 році вітчизняним математиком А.А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше було названо його ім'ям.
У цьому уточненні виділені нами 7 параметрів були визначені таким чином:
Сукупність початкових даних - слова в алфавіті S;
Сукупність можливих результатів - слова в алфавіті W;
Сукупність можливих проміжних результатів - слова в алфавіті
Р = SWV, де V - алфавіт службових допоміжних символів.
Дії:
Дії мають вигляд або a В® g, або a a g, де a, g ГЋP * , де
P * - безліч слів над алфавітом Р, і називається правилом підстановки. Сенс цього правила полягає в тому, що оброблюваний слово w є видимим зліва направо і шукається входження в нього слова a.
Определеніе.3.1. Слово a називається входженням в слово w, якщо існують такі слова b і n над тим же алфавітом, що і a і w, для яких вірно: w = ban.
Якщо входження a в w знайдено, то слово a замінюється на слово g.
Всі правила постановки упорядковуються. Спочатку шукається входження для першого правила підстановки. Якщо воно знайдено, то відбувається підстановка і преобразуемое слово знову проглядається зліва направо у пошуках входження. Якщо входження для першого правила не знайдено, то шукається входження для другого правила і т.д. Якщо входження знайдено для i-го правила підстановки, то відбувається підстановка, і перегляд правил починається з першого, а слово проглядається спочатку і зліва направо.
Вся сукупність правил підстановки називається схемою алгоритму.
Правило початку - проглядання правил завжди починається з першого.
Правило закінчення - виконання алгоритму закінчується, якщо:
було застосовано правило підстановки виду aag,
не застосовно жодне правило підстановки зі схеми алгоритму.
7. Правило розміщення результату - слово, отримане після закінчення виконання алгоритму.
Розглянемо приклад 1 з лекції 2:
побудувати алгоритм для обчислення
U (n) = n +1;
S = {0,1,2,3,4,5,6,7,8,9}; S = W; V = {*, +}.
Cхема цього НАМ показана на малюнку 3.1.
переганяти службовий символ * в кінець слова n, щоб відзначити останню цифру молодших розрядів.
Збільшуємо на одиницю, починаючи з цифр молодших розрядів.
Вводимо службовий символ * в слово, щоб їм відзначити останню цифру в слові.
Рис.3.1. Схема НАМ для обчислення U 1 (n) = n +1
Неважко зміркувати, що складність цього алгоритму, виражена в кількості виконаних правил підстановки, буде дорівнює:
(k +1) + (l +1),
де k - кількість цифр в n, l - кількість 9, які були збільшені на 1.
Але в будь-якому випадку складність НАМ для U 1 (n) більше складності Машини Тюрінга для цієї ж функції, яка дорівнювала k +1.
Зверніть увагу, що у НАМ порядок слідування правил підстановки в схемі алгоритму істотно впливає на результат, в той час як для МТ він не суттєво.
Побудуємо НАМ для прикладу 2 з лекції 2:
побудувати алгоритм для обчислення
U 2 ((n) 1 ) = (n-1) 1
Отже, S = {|}; W = S; V = Г†, тобто порожньо.
| a
Складність цього алгоритму рівна 1, у той час як складність алгоритму для Машини Тюрінга дорівнювала n.
Тепер побудуємо НАМ для прикладу 3 з лекції 2:
побудувати алгоритм для обчислення
U 3 ((n) 1 ) = (n) 10
S = {|}; W = {0,1,2,3,4,5,6,7,8,9}; V = Г†
Схема цього алгоритму приведена на малюнку 3.2.
1 | В® 2
2 | В® 3
3 | В® 4
4 | В® 5
5 | В® 6
6 | В® 7
7 | В® 8
8 | В® 9
9 | В® | 0
| 0 В® 10
0 | В® 1
| В® 0 |
Рис. 3.2. Схема НАМ для обчислення U 3 ((n) 1 ) = (n) 10.
Складність цього НАМ буде n + [log 10 n], що істотно менше складності для Машини Тюрінга, обчислює цю функцію, яка дорівнювала n 2 + [log 10 n (log 10 n +1)].
Реалізацію функції U 4 порівняння двох цілих чисел залишаємо читачу як вправи.
Зауваження: початкове слово треба задати в формі *
Для нормальних алгоритмів Маркова справедлива теза, аналогічний тези Тьюринга.
Теза Маркова: Для будь інтуїтивно обчислюваною функції існує алгоритм, її обчислює.
Побудова алгоритмів з алгоритмів.
Дотепер, будуючи ту чи іншу МТ, або НАМ ми кожного разу всі робили наново. Природно поставити запитання, а чи не можна при побудові, наприклад, нової МТ користуватися вже побудованою раніше МТ.
Наприклад, МТ 3 з прикладу 3
U 3 ((n) 1 ) = (n) 10
по суті є належним чином об'єднані МТ для U 1 (n) = n +1 і U 2 ((n) 1 ) = (n-1) 1 .
Аналогічне питання можна сформулювати для НАМ. Іншими словами чи можна акумулювати знання у формі алгоритмів так, щоб з них можна було будувати інші алгоритми.
Ми розглянемо цю проблему стосовно до МТ. Однак всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалент уточнень поняття алгоритму ми розглянемо пізніше.
Определеніе.3.2. Будемо говорити, що МТ 1 можна ефективно побудувати з МТ 2 і МТ 3 якщо існує алгоритм, який дозволяє, маючи програму для МТ 2 і МТ 3 , побудувати програму для МТ 3 .
Определение.3.3.Последовательной композицією МТ А і В називається така МТ З, що
область застосовності МТ А і С збігаються;
C (a) = B (A (a)).
Іншими словами, застосування З до слова a дає такий же результат, як послідовне застосування до цього ж слова спочатку А, а потім до результату застосування А - В.
Послідовну композицію МТ А і МТ В будемо позначати АoВ.
Теорема 3.1. Нехай дано МТ А і В, такі, що В застосовна до результатів роботи А і Q A Q B = Г†.
Тоді можна ефективно побудувати МТ З таку, що С = АoВ.
Доказ.
В якості алфавіту даних і безлічі станів для МТ З візьмемо об'єднання алфавітів даних і множин станів для А і В, тобто
D C = D A D В , Q C = Q A Q B
У програмі для А всі правила ap В® b! w, де a, bГЋD A *, wГЋ {Л, П, Н} замінимо на ap В® bq o B w, де q o B ГЋ Q B - початковий стан для В. Це забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, тому Q A Q B = Г†.
Що і т.д.
Таблична запис програми для З показана на малюнку 3.3.
Рис 3.3 Структура табличній записи програм для Машини З.
Определеніе3.4. Паралельної композицією Машин Тюрінга А і В назвемо таку Машину С, для якої:
D C = D A D B
Q C = Q A Q B
C (a | | b) = A (a | | b) В° B = B (a | | b) В° A = A (a) | | B (b).
З цього визначення видно, що порядок застосування МТ А і ...
