Головна |
Для формалізації поняття алгоритму російський математик А. а. марков запропонував використовувати асоціативні обчислення.
Розглянемо деякі поняття асоціативного обчислення. Нехай є алфавіт (кінцевий набір різних символів). Складові його символи будемо називати буквами. Будь-яка кінцева послідовність літер алфавіту (лінійний їх ряд) називається словом в цьому алфавіті.
Розглянемо два слова N и М в деякому алфавіті А. якщо N є частиною М, то кажуть, що N входить в М.
Задамо в деякому алфавіті кінцеву систему підстановок N - М, S - Т, ..., де N, М, S, Т, ... - слова в цьому алфавіті. будь-яку підстановку N-M можна застосувати до деякого слову К в такий спосіб: якщо в К є одне або кілька входжень слова N, то будь-яка з них може бути замінено словом М, і, навпаки, якщо є входження М, то його можна замінити словом N.
Наприклад, в алфавіті А = {а, b, с} є слова 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
ad - da; eca - ae
bc - cb; eda - be
bd - db; edb - be
слова abcde и acbde - Суміжні (підстановка bc - cb). слова abcde - cadbe еквівалентні.
Може бути розглянутий спеціальний вид асоціативного обчислення, в якому підстановки є орієнтованими: N > М (стрілка означає, що підстановку дозволяється проводити лише зліва направо). Для кожного асоціативного обчислення існує завдання: для будь-яких двох слів визначити, чи є вони еквівалентними чи ні.
Будь-який процес виведення формул, математичні викладки і перетворення також є дедуктивним ланцюжками в деякому асоціативному обчисленні. Побудова асоціативних обчислень є універсальним методом детермінованою переробки інформації і дозволяє формалізувати поняття алгоритму.
Введемо поняття алгоритму на основі асоціативного обчислення: алгоритмом в алфавіті А називається зрозуміле точне розпорядження, що визначає процес над словами з А і допускає будь-яке слово в якості вихідного. Алгоритм в алфавіті А задається в вигляді системи допустимих підстановок, доповненої точним розпорядженням про те, в якому порядку потрібно застосовувати допустимі підстановки і коли настає зупинка.
приклад
Алфавіт: Система підстановок В:
А = {а, b, з} cb - cc
сса - аb
ab - bса
Припис про застосування підстановок: в довільному слові Р треба зробити можливі підстановки, замінивши ліву частину підстановок на праву; повторити процес з знову отриманими словом.
Так, застосовуючи систему підстановок В з розглянутого прикладу до слів babaac и bсaсаbс отримуємо:
babaac > bbcaaac > зупинка
bcacabc > bcacbcac > bcacccac > bсасаbс > нескінченні процес (зупинки немає), так як ми отримали вихідне слово.
Запропонований А. а. Марковим спосіб уточнення поняття алгоритму заснований на понятті нормального алгоритму, який визначається наступним чином. Нехай заданий алфавіт А і система підстановок В. Для довільного слова Р підстановки з В підбираються в тому ж порядку, в якому вони слідують у В. . якщо підходящої підстановки немає, то процес зупиняється. В іншому випадку береться перша з відповідних підстановок і проводиться заміна її правою частиною першого входження її лівій частині в Р. Потім всі дії повторюються для отриманого слова P1. Якщо застосовується остання підстановка з системи В, процес зупиняється.
Такий набір приписів разом з алфавітом А і набором підстановок В визначають нормальний алгоритм. Процес зупиняється тільки в двох випадках: 1) коли відповідна підстановка не знайдено; 2) коли застосована остання підстановка з їх набору. Різні нормальні алгоритми відрізняються один від одного алфавітами і системами підстановок.
Наведемо приклад нормального алгоритму, що описує складання -натуральна чисел (представлених наборами одиниць).
приклад
Алфавіт: Система підстановок В:
А = (+, 1) 1 + > + 1
+ 1 > 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. Ітерація алгоритмів. Ітерація (повторення) являє собою таку композицію З двох алгоритмів А и В, що для будь-якого вхідного слова р відповідне слово с (р) виходить в результаті послідовного багаторазового застосування алгоритму А до тих пір, поки не вийде слово, що перетворюється алгоритмом В.
Нормальні алгоритми Маркова є не тільки засобом теоретичних побудов, а й основою спеціалізованого мови програмування, що застосовується як мову символьних перетворень при розробці систем штучного інтелекту. Це один з небагатьох мов, розроблених в Росії і здобули популярність у всьому світі.
Існує строгий доказ того, що за можливостями перетворення нормальні алгоритми Маркова еквівалентні машинам Тьюринга.
МІЖНАРОДНІ СИСТЕМИ байтовими КОДУВАННЯ | ОСНОВНІ ПОНЯТТЯ | ПОДАННЯ гРАФІВ | АЛГОРИТМ І ЙОГО ВЛАСТИВОСТІ | ПОНЯТТЯ ВИКОНАВЦЯ АЛГОРИТМА | ГРАФІЧНЕ ПОДАННЯ АЛГОРИТМІВ | властивості алгоритмів | ПОНЯТТЯ алгоритмічні мови | ПОСТАНОВКА ПРОБЛЕМИ | МАШИНА ПОСТУ |