Головна

НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА

  1.  алгоритми
  2.  Алгоритми виконання Завдання 2
  3.  Алгоритми виконання Завдання 2
  4.  Алгоритми виконання Завдання 3
  5.  Алгоритми генерації ISN.
  6.  АЛГОРИТМИ ГЕНЕРАЦІЇ ВИПАДКОВИХ ЧИСЕЛ
  7.  Алгоритми заміщення сторінок

Для формалізації поняття алгоритму російський математик А. а. марков запропонував використовувати асоціативні обчислення.

Розглянемо деякі поняття асоціативного обчислення. Нехай є алфавіт (кінцевий набір різних символів). Складові його символи будемо називати буквами. Будь-яка кінцева послідовність літер алфавіту (лінійний їх ряд) називається словом в цьому алфавіті.

Розглянемо два слова 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. Ітерація алгоритмів. Ітерація (повторення) являє собою таку композицію З двох алгоритмів А и В, що для будь-якого вхідного слова р відповідне слово с (р) виходить в результаті послідовного багаторазового застосування алгоритму А до тих пір, поки не вийде слово, що перетворюється алгоритмом В.

Нормальні алгоритми Маркова є не тільки засобом теоретичних побудов, а й основою спеціалізованого мови програмування, що застосовується як мову символьних перетворень при розробці систем штучного інтелекту. Це один з небагатьох мов, розроблених в Росії і здобули популярність у всьому світі.

Існує строгий доказ того, що за можливостями перетворення нормальні алгоритми Маркова еквівалентні машинам Тьюринга.




 МІЖНАРОДНІ СИСТЕМИ байтовими КОДУВАННЯ |  ОСНОВНІ ПОНЯТТЯ |  ПОДАННЯ гРАФІВ |  АЛГОРИТМ І ЙОГО ВЛАСТИВОСТІ |  ПОНЯТТЯ ВИКОНАВЦЯ АЛГОРИТМА |  ГРАФІЧНЕ ПОДАННЯ АЛГОРИТМІВ |  властивості алгоритмів |  ПОНЯТТЯ алгоритмічні мови |  ПОСТАНОВКА ПРОБЛЕМИ |  МАШИНА ПОСТУ |

© 2016-2022  um.co.ua - учбові матеріали та реферати