Тема 4. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА

Нормальные алгоритмы были предложены в 1951 г. советским ученым А.А. Марковым. Как и машины Тьюринга, нормальные алгоритмы оперируют со словами в некотором алфавите. Главное же их отличие от МТ состоит в том, что нормальный алгоритм представляет собой не устройство, а некоторый упорядоченный набор элементарных операций над словами. Операндами этих операций в общем случае являются последовательности букв, что зачастую упрощает построение нормального алгоритма по сравнению с МТ.

Для изучения данной темы необходимо повторить понятия и определения символьных конструкций и операций над ними.

В литературе алгоритмы Маркова коротко описаны в работах [1,2,5].

Задание на самостоятельную работу

Контрольные вопросы :

- как функционирует нормальный алгоритм ?

- чем отличается нормальный алгоритм в алфавите А от алгоритма над А ?

- является ли любой нормальный алгоритм в А в то же время и алгоритмом над А ? Справедливо ли обратное ?

- в каких случаях нормальный алгоритм останавливается ?

- приведите пример нормального алгоритма, работающего бесконечно;

- почему нельзя доказать принцип нормализации ?

1. Составьте следующие нормальные алгоритмы Маркова над алфавитом А.

а) замена в слове a в алфавите каждого символа a на символ с;

б) нормальный алгоритм над любым алфавитом, который ничего не делает;

в) перестановка в слове a в алфавите букв таким образом, чтобы сначала стояли все нули, а потом все единицы;

г) сложение двух чисел X и Y в унарном коде. Исходное слово имеет вид ;

д) вычисление функции в унарном коде. Исходное слово имеет вид : ;

е) вычисление функции в унарном коде.

ж) вычисление функции в унарном коде. Исходное слово имеет вид ;

з) последователь в десятичной системе счисления;

и) алгоритм над алфавитом , исключающий в слове последнюю звездочку;

к) алгоритм над алфавитом , меняющий местами первую и последнюю буквы слова;

л) алгоритм над алфавитом , переставляющий буквы слова в обратном порядке;

м) алгоритм над алфавитом , меняющий местами первый 0 и последнюю единицу в слове;

н) алгоритм над алфавитом , выдающий в качестве результата 0, если исходное слово представляет собой четное двоичное число, и 1, если число нечетное;

о) алгоритм над алфавитом , который выдает 1, если исходное слово содержит комбинацию baccd, и 0 - в противном случае.

п) алгоритм над алфавитом ,который выдает 1, если в исходном слове содержатся только парные нули, и 0 - в противном случае;

р) алгоритм над алфавитом , который выдает «да», если в исходном слове четное количество y-ков, и «нет» в противном случае;

с) алгоритм над алфавитом , выдающий в результате столько единиц, сколько нулей в исходном слове;

т) алгоритм над алфавитом , выделяющий часть слова, расположенную между первой парой звездочек.

2. На конкретных примерах исходных слов продемонстрируйте работу составленных алгоритмов.

ЛИТЕРАТУРА

1. Алферова З.В. Теория алгоритмов. -М.:Статистика,1973.-164с.

2. Криницкий Н.А. Алгоритмы вокруг нас. -М : Наука, 1977.-126с.

3. Криницкий Н.А. Миронов Г.А., Фролов Г.Д. Программирование и алгоритмические языки. -М.Наука, 1979.-496с.

4. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.: Энергия, 1980.-344с.

5. Мальцев А.И. Алгоритмы и рекурсивные функции. -М.Наука, 1965.-392с.

6. Петер Р. Рекурсивные функции. -М.ИЛ, 1954.-366с.

7. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. -М.: Советское радио, 1974.-200с.

8. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. -М.:Наука, 1980.-400с.

9. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.-М.:Наука, 1977.-368с.

10. Лавров И.А. , Максимов Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1975.-240с.