Лекція 5 Нормальні алгоритми а. А. Маркова

Як ми вже домовилися, усякий загальний спосіб завдання алгоритмів називається алгоритмічною системою. Алгоритмічна система, заснована на відповідності між словами в абстрактному алфавіті, містить у собі об'єкти двоякої природи: елементарні оператори й елементарні розпізнавачі.

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

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

Для зазначення набору елементарних операторів і порядку їхнього проходження при завданні конкретного алгоритму зручно користуватися орієнтованими графами особливого ряду, називаними граф-схемами відповідних алгоритмів.

Граф-схема алгоритму являє собою скінченну множину з'єднаних між собою вершин (або геометричних фігур), називаних вузлами граф-схеми. Кожному вузлу, крім особливих вузлів, що називаються входом і виходом, зіставляється який-небудь елементарний оператор або розпізнавач. З кожного вузла, якому зіставлений оператор, а також із вхідного вузла виходить точно по одній дузі. З кожного вузла, якому зіставлений розпізнавач, виходить точно по дві дуги. З вихідного вузла не виходить ні однієї дуги. Число дуг, що входять у вузол графа-схеми, може бути будь-яким.

Розглянемо на прикладі загальний вид такої графа-схеми (стор. 46). У розглянутому випадку для вершини, що відповідає входу, маємо

+ -

Р або Р⁺(х) = 0, Р або Р^— (х) = 1; для вершин, що відповідають

+ -

елементарним операторам, P або Р⁺(х) = I, Р або Р^—{х) = 1; для вершин,

+ -

відповідних елементарним розпізнавачам, -р або Р⁺(х) = 2, Р(x) або Р^—(х) = 2; для вершини, відповідній

+ —

виходу, -р або Р⁺(х) = 1, Р або Р^-{х) = 0.

У загальному випадку число дуг, що входять у вершины- розпізнавачі, може бути будь-яким.

Алгоритм, визначений граф-схемою, працює в такий спосіб. Вхідне слово надходить на вхід і рухається по напрямках, зазначеним стрілками. При влученні слова в розпізнавальний вузол здійснюється перевірка умови, зіставленої цьому вузлу. При виконанні умови слово направляється в операторний вузол, при невиконанні - до наступного розпізнавачу (іноді ці стрілки відповідно позначають знаками «+» й «-»).

Якщо вхідне слово р, подане на вхід граф-схеми, проходячи через вузли схеми й перетворюючись, потрапляє через скінченне число кроків на вихід, то вважається, що алгоритм придатний до слова р (слово р входить в область визначень цього алгоритму). Результатом впливу на слово р буде те слово, що виявляється на виході схеми. Якщо після подачі слова р на вхід графа його перетворення й рух по граф-схемі триває нескінченно довго, не приводячи на вихід, уважається,, що алгоритм не придатний до слова р, тобто слово р не входить в область визначення алгоритму.

У нормальних алгоритмах як елементарний оператор використається оператор підстановки, а в якості елементарного розпізнавача - розпізнавач входження.

Розпізнавач входження перевіряє умову — чи має місце входження розглянутого слова р₁ у якості підслова деякого заданого слова q.

Оператор підстановки заміняє перше ліворуч входження слова p₁ у слово q на деяке задане слово p₂. Оператор підстановки задається звичайно у вигляді двох слів, з'єднаних стрілою p₁→p₂.

Наприклад, для слова аbсаbса застосування підстановки bс→сb через два кроки приводить до слова асbасbа.

аbсаbс→асbаbса→асbасbа.

Послідовність слів p₁, p₂, ..., p_n, одержуваних у процесі реалізації алгоритму, називається дедуктивним ланцюжком, що веде від слова р₁ до слова p_n.

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

+

відповідним операторам підстановки Р(х) = 1.

Розглянемо приклад узагальненого нормального алгоритму, заданого підстановками

bа→аb, bс→bа, bb→ас

Роботу алгоритму, заданого таким графом, розглянемо для вхідного слова bсbааb.

bсbааb→bсаbаb→bсааbb→bаааbb→bаааас

Розглянувши узагальнені нормальні алгоритми, перейдемо до характеристики власне нормальних алгоритмів.

Нормальними алгоритмами називаються такі узагальнені нормальні алгоритми, граф-схеми яких задовольняють наступним умовам:

1. Всі вузли, що відповідають розпізнавачам, упорядковуються за допомогою їхньої нумерації від 1 до п.

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

3. Вхідний вузол приєднується дугою до першого розпізнавача.

Нормальні алгоритми прийнято задавати впорядкованою множиною підстановок всіх операторів даного алгоритму, називаним схемою алгоритму. При цьому звичайні підстановки записуються, як й в узагальнених алгоритмах, у вигляді двох слів, з'єднаних стрілкою (р₁→р₂), а заключні підстановки позначаються стрілкою із крапкою (p₁→^.p₂). Процес виконання підстановок закінчується лише тоді, коли жодна з підстановок схеми не застосовна до отриманого слова або коли виконана (перший раз) яка-небудь заключна підстановка.

Граф-схема нормального алгоритму в загальному виді може бути представлена на стор. 48.

Як приклад розглянемо роботу нормального алгоритму А. А. Маркова, заданого алфавітом A ={ + , 1} і системою підстановок

'1 + 1'→'11', '1'→'1'.

Нехай на вході заданий рядок '11+11+1'. Вона переробляється алгоритмом у рядок '11+11+1'→'1111+1'→'11111'→'11111'. Алгоритм реалізує додавання одиниць.

Наявність у нормальних алгоритмах підстановок двох видів — заключної й звичайної — необхідна умова універсальності нормальних алгоритмів, тобто можливості побудови нормального алгоритму, еквівалентного кожному наперед заданому алгоритму. Універсальність нормальних алгоритмів формулюється наступним принципом нормалізації. Для будь-якого алгоритму (конструктивно заданого алфавітного відображення) у довільному скінченному алфавіті А можна побудувати еквівалентний йому нормальний алгоритм над алфавітом А.

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

Якщо алгоритм N заданий у деякому розширенні алфавіту A, то говорять, що N є нормальний алгоритм над алфавітом A.

Одномісна часткова словникова функція F(р), задана в алфавіті А, називається нормально обчислюваної, якщо існує нормальний алгоритм N над алфавітом A такий, що для кожного слова p в алфавіті А виконана рівність F(р) = N(р).

Як приклад розглянемо словникову функцію в алфавіті {0, 1}, задану формулою F(р) =ра. Нехай N — нормальний алгоритм у більше широкому алфавіті {0, 1, 2}, що має схему:

20→02, 21→12, 2→^.а, Λ →2.

Візьмемо яке-небудь слово в алфавіті {0, 1}, наприклад слово 0110 = р. Після першого кроку ми одержимо слово 20110. Кожен наступний крок переробки буде зрушувати символ 2 на одне місце вправо, і після п'ятого кроку ми будемо мати слово 01102, що після використання заключної формули дасть слово 0110а = ра. Таким чином, алгоритм над алфавітом {0,1} із зазначеною схемою обчислює функцію ра, задану в алфавіті {0,1}.

Зокрема, алгоритм зі схемою Λ→^.Λ обчислює функцію F(р) = p, а алгоритм зі схемою Λ→Λ обчислює ніде не певну функцію.

Математично довести принцип нормалізації неможливо, оскільки поняття довільного алгоритму не є строго певним математичним поняттям.

Умовимося називати той або інший алгоритм нормалізуемим, якщо можна побудувати еквівалентний йому нормальний алгоритм, і ненормалізуемим - у іншому випадку. Принцип нормалізації тепер може бути висловлений у наступній видозміненій формі: всі алгоритми нормалізуемі.

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

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

I. При суперпозиції двох алгоритмів А и В вихідне слово першого алгоритму А розглядається як вхідне слово другого алгоритму В. Результат суперпозиції алгоритмів A й B можна представити у вигляді C(р) =В(A (p)). Суперпозиція може виконуватися для будь-якого скінченного числа алгоритмів.

Суперпозицію узагальнених нормальних алгоритмів можна розглядати як узагальнений нормальний алгоритм (стор. 50).

II. Об'єднанням алгоритмів A і В у тому самому алфавіті X називається алгоритм С у тім же алфавіті, що перетворюе будь-яке слово p, що міститься в перетинанні областей визначення алгоритмів A і В у записані поруч слова А(р) і В(р), на всіх інших вхідних словах цей алгоритм уважається невизначеним.

Задані X = {a, b}, А = {ab→bа), В = {ba→ab} і слово з області їхнього перетину аbа, тоді A (aba) = baa, В (aba) = aab, З(aba) = baaaab.

I II. Розгалуження алгоритмів являє собою композицію трьох алгоритмів А, B и С. Позначаючи результат цієї композиції буквою Д, будемо вважати, що область визначення алгоритму Д збігається з перетином областей визначення всіх трьох алгоритмів А, B и С, а для будь-якого слова р із цього перетину Д(р) = = А(р), якщо C(р) = е, Д(р) =В(р) і З(р) ≠е, де е - порожній рядок.

IV. Повторення (ітерація) являє собою композицію двох алгоритмів А и В. Позначаючи результат цієї композиції через С, визначимо, що для будь-якого вхідного слова р відповідне йому вихідне слово С(р) утворюється у результаті послідовного багаторазового застосування алгоритму А доти, доки не вийде слово, що переробляється алгоритмом B в деяке фіксоване слово.

Наприклад, задані Х={а, b}, А = {аb→bа), В = {bbbаа→аb). Тоді С(аbаbb) = аb, тому що аbаbb→уbааbb→bаbаb→bbааb→bbаbа→bbbаа→аb. Всі розглянуті композиції нормальних алгоритмів приводять до нормалізуемих алгоритмів.

Дуже важливе значення для нормальних алгоритмів, як і для всякої універсальної алгоритмічної системи, має задача побудови універсального алгоритму, що повинен виконувати роботу будь-якого нормального алгоритму, якщо задано його схему (система підстановок).

Для завдання універсального нормального алгоритму U може бути застосована, наприклад, наступна схема. Фіксується деякий стандартний алфавіт С(допустимо двійковий). Для всіх інших можливих алфавітів задається деякий спосіб їхнього кодування в алфавіті С. Для символів, уживаних у схемах нормальних алгоритмів (уведення, вивід, знак підстановки, роздільник операторів підстановки), приділяються окремі коди.

Тоді, якщо задано деякий алгоритм N, його кодують одним словом N^U, називаним зображенням алгоритму N, у стандартному алфавіті. Вхідне слово р кодують у слові р, називане зображенням слова.

Наприклад, заданий алгоритм N{xy→х, в→в} і задане вхідне слово р = ххух. Зображення цього алгоритму в стандартному алфавіті, що складається з десяткових цифр при кодуванні: Гх = 010, Гу = 020, Г = 030, Г <знак розділу>= 040. Г <уведення, висновок>= 50 буде наступним: N^U = 050 010 020 030 010 040 020 030 020 050; p = 010 010 020 010.

Справедлива наступна теорема Маркова про універсальний, нормальний алгоритм. Існує такий універсальний нормальний алгоритм U, що для будь-якого нормального алгоритму N і будь-якого вхідного слова р з області визначення алгоритму N переводить слово NUp, отримане приписуванням зображення слова р(рU) до зображення алгоритму N(N^U), у слово R^U, що є зображенням відповідного вхідного слова R = N(p), у яке алгоритм N переробляє слово р. Якщо ж слово р вибирається так, що алгоритм N до нього не придатний, то й універсальний алгоритм U не придатний до слова NUpU.

Ця теорема має велике значення, тому що з її випливає можливість побудови машини, що може виконувати роботу будь-якого нормального алгоритму, а виходить, у силу принципу нормалізації— роботу довільного алгоритму. Програмою машини в цьому випадку повинне бути слово N^U (зображення даного алгоритму), а вихідними даними — слово р.

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

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

Має місце наступна теорема Детловса (2). Клас нормально обчислюваних часткових функцій, заданих у довільному алфавіті А, збігається із класом всіх одномісних частково рекурсивних словникових функцій в алфавіті А.

Для доказу досить зрівняти визначення нормального алгоритму з визначенням алгоритму Т'юрінга за допомогою програми підстановок. Справді, нехай F(p) -довільна, частково рекурсивна словникова функція, задана в алфавіті А.

Відповідно до теореми Т'юрінга, існує машина Т'юрінга Т, що має зовнішній алфавіт а₀, А (а₀ — новий, що не входить в А символ), і функція, що обчислює, F (р).

Нехай q₀, q₁, ..., q_n — внутрішні стани Т и П — програма підстановок для машини Т. Заміняючи вхідні в П формули виду q_ia_j→q₀a_k формулами q_ia_j→^.q₀a_k, одержимо схему деякого нормального алгоритму N в алфавіті {а₀, А, q₀, q₁, ..., q_n}. Порівнюючи опису роботи машини Т и операцій, приписаних алгоритмом N, безпосередньо бачимо, що для кожного слова р в алфавіті А П(р) =N(p).

Таким чином, кожна частково рекурсивна словесна функція нормально обчислювана.

Вправи:

1. Побудувати граф реалізації алгоритму в алфавіті А = { + ,ٮ, ?, Q}, заданого підстановками ? ٮ' →'ٮ', '+ٮ'→'?', '?Q'>' + ':

а) визначити, до якого виду нормальних алгоритмів він належить;

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

2. Задати нормальний алгоритм Маркова, що реалізує віднімання А — В, де значеннями А и В є натуральні числа, представлені рядками, що складаються із символів 1 (наприклад, для А = 4, B = 3, А — В = 1 слово '1111—111' повинне бути перероблене алгоритмом у слово '1').

Перевірити роботу алгоритму для випадків:

а) А = 6, В = 2;

б) А = 3, В = 5.

3. Нормальний алгоритм Маркова, що реалізує операцію множення, заданий алфавітом А = {1, * , Т, Ф} і послідовністю підставок:

*11>Т*1;*1>Т; 1Т>Т1Ф; ФТ>ТФ;

Ф1→1Ф; Т1→Т; ТФ→Ф; Ф→1; 1→^.1.

Побудувати дедуктивний ланцюжок від слова '111*1111' до слова '111111111111'.

4. Задати нормальний алгоритм Маркова, що реалізує операцію множення чисел, представлених у вигляді послідовності одиниць (алгоритм повинен бути відмінний від алгоритму п. 3). Побудувати дедуктивний ланцюжок для одного із вхідних слів.

5. Задати нормальний алгоритм, що реалізує операцію порівняння призначної частини двох чисел, заданих у вигляді:

а) V VV 111* VVV 111 або VV 11 * VVVV 1111

б)VVV*111? VV*111 або VV? 111*VVV ?11;

в) 111?11*11?1111.

У пунктах а й б призначна частина числа представлена символами V, а в пункті в вона представлена в тих же символах, що й саме число, тобто одиницями.

Побудувати відповідні дедуктивні ланцюжки по кожному алгоритмі.

6. Виконати суперпозицію нормальних алгоритмів, отриманих у пп. 3 й 4.

Побудувати дедуктивний ланцюжок для одного довільного приклада.