Нормальні алгоритми

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Нормальні алгоритми (нормальні алгоритми) — вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритму введене радянським математиком А. А. Марковим.

Нормальний алгоритм Маркова — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.

Визначення нормального алгоритму

Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні pq (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записують у вигляді списку. Цей список називається схемою алгоритму.

Принцип дії

Застосування нормального алгоритму до слова s полягає в такому.

  • В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s1.
  • З отриманим словом s1 повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова s.

Приклад роботи

Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер |*abc[1]:

При застосуванні алгоритму з наведеною вище схемою до слова будуть отримуватись слова:

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. .

Результатом застосування буде слово .

Можливості нормальних алгоритмів

Доведено, що відносно виконуваних перетворень, нормальні алгоритми збігаються з іншими класами алгоритмів, введених для уточнення інтуїтивного поняття алгоритму, наприклад, з машинами Тюринга.

Аналог тези Чорча для нормальних алгорифмів є такий принцип нормалізації А. А. Маркова: будь-який алгорифм в алфавіті A достатньо еквівалентний відносно A деякому нормальному алгорифма над A.

Визначення алгоритмів у нормальному вигляді дуже схоже на числення, і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі математики або кібернетики широко застосовують, як, приміром, в математичній логіці або в математичній лінгвістиці.

Використовуючи поняття нормального алгоритма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.

Джерела інформації

Посилання

  1. Нормальный алгоритм (рос.), Википедия, 26 січня 2007.

Див. також

Література

  • Марков А. А. Теория алгорифмов. «Труды математического ин-та им. В. А. Стеклова АН СССР», 1954, т. 42. (рос.)
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. — М.: Наука, 1984. — 432 с. (рос.)



Нормальний алгоритм Маркова — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті. У 1956 році математиком А. А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше було названо його ім'ям.

Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів

В запропонованому марковим уточненні виділені 7 параметрів були визначені таким чином:

  • Сукупність початкових даних — слова в алфавіті S;
  • Сукупність можливих результатів — слова в алфавіті W;
  • Сукупність можливих проміжних результатів — слова в алфавіті
  • Р = SWV, де V — алфавіт службових допоміжних символів.

P * — безліч слів над алфавітом Р, n називається правилом підстановки. Сенс цього правила полягає в тому, що оброблюване слово w є видимим зліва направо і шукається входження в нього слова a. Слово a називається входженням в слово w, якщо існують такі слова b і n над тим же алфавітом, що і a і w, для яких вірно: w = ban. Якщо входження a в w знайдено, то слово a замінюється на слово g. Всі правила постановки упорядковуються. Спочатку шукається входження для першого правила підстановки. Якщо воно знайдено, то відбувається підстановка і перетворюване слово знову проглядається зліва направо у пошуках входження. Якщо входження для першого правила не знайдено, то шукається входження для другого правила і т. д. Якщо входження знайдено для n-го правила підстановки, то відбувається підстановка, і перегляд правил починається з першого, а слово проглядається спочатку і зліва направо. Вся сукупність правил підстановки називається схемою алгоритму.

Визначення нормального алгоритму

Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні pq (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записують у вигляді списку. Цей список називається схемою алгоритму.

Принцип дії

Застосування нормального алгоритму до слова s полягає в наступному.

  • В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s1.
  • З отриманим словом s1 повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова s.

Приклад роботи

Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер |*abc[1]:

При застосуванні алгоритму з наведеною вище схемою до слова будуть отримуватись слова:

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. .

Результатом застосування буде слово .

Теореми та приклади

  • Правило початку — проглядання правил завжди починається з першого.
  • Правило закінчення — виконання алгоритму закінчується, якщо:
  1. було застосовано правило підстановки виду aag,
  2. не застосовно жодне правило підстановки зі схеми алгоритму.
  • Правило розміщення результату — слово, отримане після закінчення виконання алгоритму.

Побудувати алгоритм для обчислення.

U (n) = n +1;

S = {0,1,2,3,4,5,6,7,8,9}; S = W; V = {*, +}.

Переганяти службовий символ * в кінець слова n, щоб відзначити останню цифру молодших розрядів. Збільшуємо на одиницю, починаючи з цифр молодших розрядів. Вводимо службовий символ * в слово, щоб їм відзначити останню цифру в слові. Схема НАМ для обчислення U 1 (n) = n +1. Неважко зміркувати, що складність цього алгоритму, виражена в кількості виконаних правил підстановки, буде дорівнює: (k +1) + (l +1), де k — кількість цифр в n, l — кількість 9, які були збільшені на 1. Але в будь-якому випадку складність НАМ для U 1 (n) більше складності Машини Тюрінга для цієї ж функції, яка дорівнювала k +1. Зверніть увагу, що у НАМ порядок слідування правил підстановки в схемі алгоритму істотно впливає на результат, в той час як для МТ він не суттєво.

Побудувати алгоритм для обчислення.

U 2 ((n) 1) = (n-1) 1

Отже, S = {|}; W = S; V = Г†, тобто порожньо. Складність цього алгоритму рівна 1, у той час як складність алгоритму для Машини Тюрінга дорівнювала n.

Побудувати алгоритм для обчислення.

U 3 ((n) 1) = (n) 10

S = {|}; W = {0,1,2,3,4,5,6,7,8,9}; V = Г

Складність цього НАМ буде n + [log 10 n], що істотно менше складності для Машини Тюрінга, обчислює цю функцію, яка дорівнювала n 2 + [log 10 n (log 10 n +1)]. Реалізацію функції U 4 порівняння двох цілих чисел залишаємо читачу як вправи. Зауваження: початкове слово треба задати в формі *. Для нормальних алгоритмів Маркова справедлива теза, аналогічний тези Тьюринга. Теза Маркова: Для будь інтуїтивно обчислюваною функції існує алгоритм, її обчислює. Побудова алгоритмів з алгоритмів. Дотепер, будуючи ту чи іншу МТ, або НАМ ми кожного разу всі робили наново. Природно поставити запитання, а чи не можна при побудові, наприклад, нової МТ користуватися вже побудованою раніше МТ. МТ 3 з прикладу. U 3 ((n) 1) = (n) 10 по суті є належним чином об'єднані МТ для U 1 (n) = n +1 і U 2 ((n) 1) = (n-1) 1 . Аналогічне питання можна сформулювати для НАМ. Іншими словами чи можна акумулювати знання у формі алгоритмів так, щоб з них можна було будувати інші алгоритми. Ми розглянемо цю проблему стосовно до МТ. Однак всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалент уточнень поняття алгоритму ми розглянемо пізніше. Будемо говорити, що МТ 1 можна ефективно побудувати з МТ 2 і МТ 3 якщо існує алгоритм, який дозволяє, маючи програму для МТ 2 і МТ 3 , побудувати програму для МТ 3. Послідовною композицією МТ А і В називається така МТ З, що область застосовності МТ А і С збігаються; C (a) = B (A (a)). Іншими словами, застосування З до слова a дає такий же результат, як послідовне застосування до цього ж слова спочатку А, а потім до результату застосування А — В. Послідовну композицію МТ А і МТ В будемо позначати АoВ.

Теорема.

Нехай дано МТ А і В, такі, що В застосовна до результатів роботи А і Q A Q B = Г. Тоді можна ефективно побудувати МТ З таку, що С = АoВ.

Доказ.

Як алфавіт даних і множину станів для МТ З візьмемо об'єднання алфавітів даних і множин станів для А і В, тобто D C = D A D В, Q C = Q A Q B. У програмі початковий стан для В. Це забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, тому Q A Q B = Г.

Теорема.

Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С = А | | В.

Обґрунтування.

Ми не будемо давати тут строго доказу з причини його технічної складності. Покажемо лише обґрунтування правильності затвердження теореми. Позначимо D C = D A D B ; Q C = Q A Q B.

Див. також

Примітки

  1. Нормальный алгоритм (рос.), Википедия, 26 січня 2007.

Література

  • Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень. — М., 2002. — С528.
  • Марков А. А. Теория алгорифмов. «Труды математического ин-та им. В. А. Стеклова АН СССР», 1954, т. 42.
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984. — 432 с.