Нормальні алгоритми маркова - студопедія
Для формалізації поняття алгоритму український математик А.А.Марков запропонував використовувати асоціативні обчислення.
Розглянемо деякі поняття асоціативного обчислення. Нехай є алфавіт (кінцевий набір різних символів). Складові його символи будемо називати буквами. Будь-яка кінцева послідовність літер алфавіту (лінійний їх ряд) називається словом в цьому алфавіті.
Розглянемо два слова N і М в деякому алфавіті А. Якщо N є частиною М, то кажуть, що N входить в М.
Задамо в деякому алфавіті кінцеву систему підстановок N - М, S - Т. де N, М, S, Т. - слова в цьому алфавіті. Будь-яку підстановку N-M можна застосувати до деякого слову До в такий спосіб: якщо в До є одне або кілька входжень слова N, то будь-яка з них може бути замінено словом М, і, навпаки, якщо є входження М, то його можна замінити словом N.
Наприклад, в алфавіті А = є слова N = ab, М = bcb, К = abcbcbab, Замінивши в слові До слово N на М, отримаємо bcbcbcbab або abcbcbbcb, і, навпаки, замінивши М на N, отримаємо aabcbab або аbсаbаb.
Підстановка ab - bcb недопустима до слова bacb, так як не ab, ні bcb не входить в це слово. До отриманих за допомогою допустимих підстановок словами можна знову застосувати допустимі підстановки і т.д. Сукупність усіх слів в даному алфавіті разом з системою допустимих підстановок називають асоціативним обчисленням. Щоб задати асоціативне обчислення, досить задати алфавіт і систему підстановок.
Слова P1 і Р2 в деякому асоціативному обчисленні називаються суміжними, якщо одна з них може бути перетворено в інше одноразовим застосуванням допустимої підстановки.
Послідовність слів Р, P1. Р2. М називається дедуктивної ланцюжком, що веде від слова Р до слова М, якщо кожне з двох поруч стоять слів цього ланцюжка - суміжне.
Слова Р і М називають еквівалентними, якщо існує ланцюжок від Р до М і назад.
а, b, с, d, е> ас - Сa, abac - abace
Слова abcde і acbde - суміжні (підстановка bc - cb). Слова abcde - cadbe еквівалентні.
Може бути розглянутий спеціальний вид асоціативного обчислення, в якому підстановки є орієнтованими: N → М (стрілка означає, що підстановку дозволяється проводити лише зліва направо). Для кожного асоціативного обчислення існує завдання: для будь-яких двох слів визначити, чи є вони еквівалентними чи ні.
Будь-який процес виведення формул, математичні викладки і перетворення також є дедуктивним ланцюжками в деякому асоціативному обчисленні. Побудова асоціативних обчислень є універсальним методом детермінованою переробки інформації і дозволяє формалізувати поняття алгоритму.
Введемо поняття алгоритму на основі асоціативного обчислення: алгоритмом в алфавіті А називається зрозуміле точне розпорядження, що визначає процес над словами з А і допускає будь-яке слово в якості вихідного. Алгоритм в алфавіті А задається в вигляді системи допустимих підстановок, доповненої точним розпорядженням про те, в якому порядку потрібно застосовувати допустимі підстановки і коли настає зупинка.
Алфавіт: Система підстановок В:
Припис про застосування підстановок: в довільному слові Р треба зробити можливі підстановки, замінивши ліву частину підстановок на праву; повторити процес з знову отриманими словом.
Так, застосовуючи систему підстановок В з розглянутого прикладу до слів babaac і bсaсаbс отримуємо:
babaac → bbcaaac → зупинка
bcacabc → bcacbcac → bcacccac → bсасаbс → нескінченні процес (зупинки немає), так як ми отримали вихідне слово.
Запропонований А.А.Маркова спосіб уточнення поняття алгоритму заснований на понятті нормального алгоритму, який визначається наступним чином. Нехай заданий алфавіт А і система підстановок В. Для довільного слова Р підстановки з В підбираються в тому ж порядку, в якому вони слідують у В. .Якщо підходящої підстановки немає, то процес зупиняється. В іншому випадку береться перша з відповідних підстановок і проводиться заміна її правою частиною першого входження її лівій частині в Р. Потім всі дії повторюються для отриманого слова P1. Якщо застосовується остання підстановка з системи В, процес зупиняється.
Такий набір приписів разом з алфавітом А і набором підстановок В визначають нормальний алгоритм. Процес зупиняється тільки в двох випадках: 1) коли відповідна підстановка не знайдено; 2) коли застосована остання підстановка з їх набору. Різні нормальні алгоритми відрізняються один від одного алфавітами і системами підстановок.
Наведемо приклад нормального алгоритму, що описує складання -натуральна чисел (представлених наборами одиниць).
Алфавіт: Система підстановок В:
А = (+, 1) 1 + → + 1
Слово Р: 11 + 11 + 111
Послідовна переробка слова Р за допомогою нормального алгоритму Маркова проходить через наступні етапи:
Р = 11 + 11 + 111 Р5 = + 1 + 111111
Р1 = 1 + 111 + 111 Р6 = ++ 1111111
Р2 = + 1111 + 111 Р7 = + 1111111
Р3 = + 111 + 1111 Р8 = 1111111
Р4 = + 11 + 11111 Р9 = 1111111
Нормальний алгоритм Маркова можна розглядати як універсальну форму завдання будь-якого алгоритму. Універсальність нормальних алгоритмів декларується принципом нормалізації: для будь-якого алгоритму в довільному кінцевому алфавіті А можна побудувати еквівалентний йому нормальний алгоритм над алфавітом А,
Роз'яснимо останнє твердження. У деяких випадках не вдається побудувати нормальний алгоритм, еквівалентний даному в алфавіті А, якщо використовувати в підстановках алгоритму тільки букви цього алфавіту. Однак, можна побудувати необхідний нормальний алгоритм, виробляючи розширення алфавіту А (додаючи до нього деяке число нових букв). У цьому випадку говорять, що побудований алгоритм є алгоритмом над алфавітом А, хоча він буде застосовуватися лише до слів у вихідному алфавіті A.
Якщо алгоритм N заданий в деякому розширенні алфавіту А, то говорять, що N є нормальний алгоритм над алфавітом А.
Домовимося називати той чи інший алгоритм нормалізуемих, якщо можна побудувати еквівалентний йому нормальний алгоритм, і ненормалізуемим в іншому випадку. Принцип нормалізації тепер може бути висловлений у видозміненій формі: все алгоритми нормалізуемих.
| Даний принцип не може бути строго доведений, оскільки поняття довільного алгоритму не є строго визначеним і грунтується на тому, що все Відомі в даний час алгоритми є нормалізуемих, а способи ромпозіціі алгоритмів, що дозволяють будувати нові алгоритми з уже відомих, не виводять за межі класу нормалізуемих алгоритмів. Нижче перераховані способи композиції нормальних алгоритмів.
I. Суперпозиція алгоритмів. При суперпозиції двох алгоритмів А і В вихідна слово першого алгоритму розглядається як вхідний слово другого алгоритму В. Результат суперпозиції З може бути представлений у вигляді С (р) = В (А (р)),
II. Об'єднання алгоритмів. Об'єднанням алгоритмів А і В в одному і тому ж алфавіті називається алгоритм З в тому ж алфавіті, що перетворює будь-яке слово р, що міститься в перетині областей визначення алгоритмів А і В, в записані поруч слова А (р) і В (р).
III. Розгалуження алгоритмів. Розгалуження алгоритмів є композицією D трьох алгоритмів А, В і С, причому область визначення алгоритму D є перетином областей визначення всіх трьох алгоритмів А, В і С, а для будь-якого слова р з цього перетину D (p) = А (р), якщо С (р) = е, D (p) = B (p), якщо С (р) = е, де е - порожній рядок.
IV. Ітерація алгоритмів. Ітерація (повторення) являє собою таку композицію З двох алгоритмів А і В, що для будь-якого вхідного слова р відповідне слово С (р) виходить в результаті послідовного багаторазового застосування алгоритму А до тих пір, поки не вийде слово, що перетворюється алгоритмом В.
Нормальні алгоритми Маркова є не тільки засобом теоретичних побудов, а й основою спеціалізованої мови програмування, що застосовується як мову символьних перетворень при розробці систем штучного інтелекту. Це один з небагатьох мов, розроблених вУкаіни і здобули популярність у всьому світі.
Існує строгий доказ того, що за можливостями перетворення нормальні алгоритми Маркова еквівалентні машинам Тьюринга.