Ноу Інти, лекція, нормальні алгоритми маркова
Анотація: Визначення нормального алгоритму Маркова та його виконання. Можливості нормальних алгоритмів Маркова і теза Маркова. Методика розробки нормальних алгоритмів Маркова.
Визначення нормального алгоритму і його виконання
В середині минулого століття видатний український математик А.А. Марков ввів поняття нормального алгоритму (алгорифм) з метою уточнення поняття "алгоритм", що дозволяє вирішувати завдання по визначенню алгоритмічно нерозв'язних проблем. Пізніше це поняття отримало назву нормального алгоритму Маркова (НАМ). Мова НАМ. з одного боку, навмисно бідний, що необхідно для цілі введення поняття "алгоритм". Однак, з іншого боку, ідеї НАМ покладені в основу великої групи мов програмування, які отримали назву мови логічного програмування. які є темою даної допомоги.
Для визначення НАМ вводиться довільний алфавіт - кінцеве непорожня множина символів, за допомогою яких описується алгоритм і дані. В алфавіт також включається порожній символ. який ми будемо позначати грецькою буквою. Під словом розуміється будь-яка послідовність непустих символів алфавіту або порожній символ, який позначає пусте слово.
Всякий НАМ визначається кінцевим впорядкованим безліччю пар слів алфавіту, званих підстановками. У парі слів підстановки ліве (перше) слово непорожнє, а праве (друге) слово може бути порожнім символом. Для наочності ліве і праве слово поділяються стрілкою. наприклад,
Як дані алгоритму береться будь-яка непорожній рядок символів. Робота НАМ складається з послідовності абсолютно однотипних кроків. Крок роботи алгоритму може бути описаний таким чином:
- У впорядкованої послідовності підстановок шукаємо найпершу підстановку, ліве слово якої входить в рядок даних.
- У рядку даних шукаємо найперше (ліве) входження лівого слова знайденої підстановки.
- Це входження в рядку даних замінюємо на праве слово знайденої підстановки (перетворення даних).
Крок роботи алгоритму повторюється до тих пір, поки
- або не виникне ситуація, коли крок не зможе бути виконаний через те, що жодна підстановка не підходить (ліве слово будь-підстановки вже не входить в рядок даних) - правило зупинки;
- або не буде встановлено, що процес підстановок не може зупинитися.
У першому випадку рядок даних. вийшла при зупинці алгоритму, є вихідний (результатом) і алгоритм застосуємо до вхідних даних. а в другому випадку алгоритм застосуємо до вхідних даних.
Так, певний вище в прикладі нормальний алгоритм Маркова перетворює слово в слово такий спосіб (над стрілкою перетворення ми пишемо номер застосовуваної підстановки. А в преобразуемой рядку підкреслюємо ліве слово застосовується підстановки):
а при перетворенні слова abbc цей же алгоритм буде необмежено працювати, так як має місце циклічне повторення даних:
Таким чином, будь-яка нормальна алгоритм Маркова визначає функцію, яку ми назвемо нормальною (або обчислюваною по Маркову). яка може бути частковою і яка в області визначення вхідному слову ставить у відповідність вихідне слово.
Можливості нормальних алгоритмів і теза Маркова
Перш за все розглянемо можливості реалізації арифметичних операцій за допомогою нормальних алгоритмів Маркова. Спочатку звернемо увагу на одну обставину, пов'язане з роботою будь-якого НАМ. потрібно або вводити додаткове правило зупинки роботи нормального алгоритму (інакше в прикладі збільшення числа на 1 алгоритм продовжить роботу і знову буде збільшувати отриманий результат ще на 1 і т.д. необмежену кількість разів), або перед початком роботи нормального алгоритму додавати до вхідному рядку спеціальні символи. відмінні від інших символів рядка, які враховуються підстановками алгоритму на початку його роботи і які віддаляються в кінці роботи алгоритму. Ми будемо дотримуватися другого способу, як і одна з найбільш успішних реалізацій нормальних алгоритмів Маркова у вигляді мови програмування Рефал. Як додається символу візьмемо символ "@".
Приклад 1. Розглянемо найпростішу операцію збільшення десяткового числа на 1. В цьому випадку майже завжди необхідно збільшити останню цифру на 1, а остання цифра відрізняється тим, що після неї йде символ "@". Тому першими підстановками повинні бути підстановки типу
Але якщо це цифра 9, то її потрібно замінити 0 і збільшення на 1 перенести в попередній розряд. Цьому відповідає підстановка
Нарешті, якщо число починається з 9 і перед цією цифрою потрібно поставити 1, то цього буде відповідати підстановка
а якщо це не так, то в кінці роботи алгоритму символи @ треба стерти, що виконає підстановка
Таким чином, ми отримуємо наступний НАМ збільшення десяткового числа на 1:
Наведемо роботу побудованого алгоритму для чисел 79 і 99:
Аналогічним чином розробляється нормальний алгоритм Маркова для зменшення числа на 1 (див. Вправу 1.3.1).
Продемонструємо роботу алгоритму для числа 10:
Для побудови алгоритму складання двох чисел можна використовувати ідею зменшення одного числа на 1 з наступним збільшенням іншого числа на 1 і повторенням цього до тих пір, поки зменшуване число не зникне після того, як стане рівним 0. Але можна використовувати і більш складну ідею порозрядного додавання з перенесенням 1 в розряд зліва. Побудова цих алгоритмів, а також алгоритмів вирахування. множення і ділення виділено для самостійної роботи в вправах 2 - 9 (див. 1.3).
Наведені приклади показують також можливості апарату нормальних алгоритмів Маркова з організації розгалуження і циклічних процесів обчислення. Це показує, що всякий алгоритм може бути нормалізований т. Е. Задано нормальним алгоритмом Маркова. В цьому і полягає тезу Маркова. який слід розуміти як визначення алгоритму.
Разом з тим побудова алгоритму в останньому наведеному прикладі підказує наступну методику розробки НАМ:
- запам'ятовування копійованого розряду - розряд 1 запам'ятовується як символ "a", а розряд 0 - як символ "b";
- запам'ятовування місця копійованого розряду - позначка ще не скопійованого символу додатковим символом "!" з заміною його на символ "?" при пересуванні копійованого розряду і зворотного заміною після пересування.
вправи
- Визначте нормальний алгоритм. який зменшує число на одиницю.
- Визначте нормальний алгоритм складання двох двійкових чисел методом зменшення одного числа на 1 і збільшенням іншого числа на 1 до тих пір, поки зменшуване число не стане рівним 0.
- Визначте нормальний алгоритм логічного додавання двох двійкових чисел.
- Визначте нормальний алгоритм логічного множення двох двійкових чисел.
- Визначте нормальний алгоритм складання по модулю 2 двох двійкових чисел.
- Визначте нормальний алгоритм порозрядного додавання двох двійкових чисел.
- Визначте нормальний алгоритм віднімання двійкових чисел.
- Визначте нормальний алгоритм множення двох двійкових чисел стовпчиком.
- Визначте нормальний алгоритм розподілу двох двійкових чисел з визначенням приватного і залишку.
- Визначте нормальний алгоритм обчислення найбільшого загального дільника двох двійкових чисел.
- Визначте нормальний алгоритм обчислення найменшого спільного кратного двох двійкових чисел.