- •1. Поняття конструктивного об’єкту.
- •2. Загальна схема побудови алгоритмічної системи
- •3. Алфавітні алгоритми.
- •4. Означення нормального алгоритму.
- •Розв’язування. Застосувавши першу підстановку до слова х, одержимо слово
- •Операція входження має вигляд
- •Іі. Завдання до лабораторної роботи:
- •III. Завдання для самостійного виконання
- •Індивідуальне завдання №2
Розв’язування. Застосувавши першу підстановку до слова х, одержимо слово
Y=1321445,
а, застосувавши другу підстановку, одержимо слово
Y=132144.
Розглянуті підстановки називаються, звичайними підстановками. При побудові алгоритмів в алгоритмічних системах передбачено обов’язкова присутність операції закінчення алгоритму.
У теорії нормальних алгоритмів роль такої операції виконує заключна підстановка виду
А.В,
після застосування якої алгоритмічний процес зупиняється (при цьому символ “.” - не входить до алфавіту U).
Застосування операції підстановки не можливе без іншої операції - операції входження.
Операція входження має вигляд
АХ,
де символ “” не входить до алфавіту U. Це предикат, значенням якого може бути “хиба” - 0 або “істина” - 1. Операція входження визначає можливість застосування операції підстановки АВ до слова Х.
Означення 1. Нормальним алгоритмом називається скінченна послідовність операцій входження і відповідних їм операцій підстановок, виконання яких призводить до розв’язування поставленої задачі в деякому абстрактному алфавіті.
Необхідною умовою можливості побудови нормальних алгоритмів, які реалізують будь-який конструктивно заданий процес перетворення слів, є використання обох видів підстановок як звичайних, так і заключних, яких може бути кілька в одному алгоритмі.
Сконструювати нормальний алгоритм означає записати в певному порядку одну допустиму операцію за іншою.
Суть алгоритмічного процесу в системі Маркова полягає в тому, щоб застосувати нормальний алгоритм до заданого вхідного слова за таким правилом:
виконати першу підстановку алгоритму, яку можна застосувати до заданого вхідного слова;
процес застосування підстановок вести доти, поки може бути застосована до поточного слова хоча б одна із звичайних підстановок алгоритму або доти, поки буде застосована перший і єдиний раз заключна підстановка, при цьому щоразу перегляд підстановок відбувається з першої операції в алгоритмі.
Якщо на деякому етапі алгоритмічного процесу жодна підстановка алгоритму А незастосовна до поточного слова, то алгоритм завершує свою роботу і результатом вважається одержане на цей момент слово.
Кажуть, що алгоритм А застосовний до слова Х, якщо процес перетворення слова Х закінчується після скінченого числа етапів яким-небудь словом Y. В цьому випадку кажуть, що алгоритм А перетворює слово Х в слово Y:
A(X)=Y.
Якщо процес перетворення слова Х алгоритмом А ніколи не закінчується, то кажуть, що алгоритм А незастосовний до слова Х.
Зауважимо, що якщо жодна підстановка алгоритму А незастосовна до вхідного слова Х, то результатом роботи алгоритму вважається саме слово Х, тобто
А(Х)=Х.
Для скороченого запису нормальних алгоритмів використовуються так звані схеми нормальних алгоритмів, які містять лише операції підстановки, а відповідні їм операції входження опускаються. Для задання алгоритмічного процесу, який визначає заданий алгоритм зручно використовувати блок-схеми, граф-схеми або скорочені граф-схеми.
Нормальний алгоритм називається замкненим, якщо його схема містить хоча б одну підстановку виду А.В, тобто заключну підстановку. Будь-який нормальний алгоритм можна зробити замкненим, якщо на при кінці алгоритму добавити підстановку виду ..
Будемо позначати замкнений нормальний алгоритм . Очевидно, що незамкнений алгоритм А і замкнений алгоритм , одержаний додаванням підстановки . еквівалентні.
Приклад 2. Нехай задано алфавіт U={a,b} і схема нормального алгоритму:
Побудувати граф-схему, скорочену граф-схему і блок-схему даного алгоритму і застосувати його до заданих вхідних слів:
X=bbaba;
Х=babbbaa;
Х=а;
Х=bb.
Р озв’язування. Блок-схему, граф-схему і скорочену граф-схему алгоритму подано відповідно на рис. 1.
Рис. 1.
Застосувавши до вхідних слів алгоритм А1 одержимо:
а) Х1=bbbaa
Х2=bba
Х3=b
Х4=a – результат;
b) X1=bbabbaa
X2=bbbabaa
X3=bbbbaaa
X4=bbbaa
X5=bba
X6=b
X7=a – результат;
с) Х=а – результат;
d) Х1=bb
Х2=ab – результат.
Приклад 3. В алфавіті U={|} побудувати нормальний алгоритм для знаходження суми двох натуральних чисел.
Розв’язування. Нехай задано два числа n, m N. Подамо ці числа у вигляді конструктивних об’єктів за допомогою слів алфавіту U={|}. Наприклад,
||| = 3, ||||| = 5.
В цьому алфавіті числа кодуються словами із відповідної кількості букв “|”.
Для подання вхідних даних задачі розширимо алфавіт U символом “+”. Тоді вхідні дані виду n+m в алфавіті U=U{+}={|,+} будуть мати, наприклад, такий вигляд
4+3=||||+|||.
Легко бачити, що нормальним алгоритмом для розв’язання поставленої задачі буде мати таку схему
Приклад 4. В алфавіті U={|,-} побудувати нормальний алгоритм для знаходження різниці двох натуральних чисел.
Розв’язування. В алфавіті U={|,-} вхідні дані задачі виду n-m будуть мати, наприклад, такий вигляд:
4-2=||||-||.
При цьому число 0 будемо вважати порожнім словом.
При відніманні двох чисел слід розглянути два випадки:
а) n m;
б) n<m.
До алгоритму для випадку а), тобто коли n m, треба ввести таку підстановку, яка зменшує по одній букві в зменшуваному і від’ємнику одночасно, а саме:
|-| -
Знак “-“ треба залишати в слові, що перетворюється доти, поки від’ємник має ненульову довжину. Щоб дістати різницю після закінчення дії першої підстановки, треба ввести ще підстановку, яка знищує букву “-“. Тоді алгоритм віднімання двох натуральних чисел за умови, що n m, в алфавіті U={|,-} має вигляд:
Для випадку б), тобто коли n<m, алгоритм дещо ускладнюється, оскільки треба проаналізувати процес завершення у випадку, коли після дії підстановки |-| - поточне слово буде починатися з підслова -|. Тому що, якщо залишити алгоритм без зміни, то він обчислює величину . Для одержання результату у вигляді від’ємного числа треба в алгоритм ввести підстановку
- |.-|
перед підстановкою - .. Тоді схема нормального алгоритму матиме вигляд:
а його блок-схема буде такою (рис. 2):
Рис.2.