Тема: «Нормальные алгоритмы Маркова и машины Тьюринга»
Вариант №15
Выполнила: студентка 2 курса
направления «Педагогическое образование»
Скобликова Мария
Проверил: Колесников Александр Васильевич, профессор
Калиниград, 2014г
Содержание
Нормальные алгоритмы Маркова
1.1 Определение понятия «Нормальный алгоритм Маркова»…………………..3
1.2 Решение задачи с помощью нормальных алгоритмов Маркова………….3-5
Машина Тьюринга
2.1 Математическая модель машины Тьюринга…………………………..........6
2.2 Решение задачи с помощью машины Тьюринга…………………..……...6-9
3. Анализ результатов и выводы…………………………………….………….10
4. Список используемой литературы……………...............................................11
Нормальные алгоритмы Маркова
Определение понятия «Нормальный алгоритм Маркова»
Понятие «нормальный алгоритм» было введено в 1947 г. Советским ученым А.А. Марковым в качестве одного из уточнений представления об алгоритме. Он предполагал, что нормальный алгоритм, являясь алгоритмом в некотором алфавите, порождает некоторый детерминированный процесс переработки только одного слова и только в одном алфавите.
Словами в алгоритме Маркова могут быть арифметические, алгебраические или логические выражения. Но это оказалось удобным средством алгоритмизации для слов не математической природы.
Нормальный алгоритм Маркова – указание использовать упорядоченный список правил подстановки:
где αi и βi - слова в алфавите Vт.
Слово αi часто называют левой, а βi - правой частью правил.
Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:
k>=1
В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.
Записать алгоритм в виде НАМ – значит предъявить такой набор формул.
Решение задачи с помощью нормальных алгоритмов Маркова
Дано:
A={a,b,c}.
Условие:
Если в слове P не менее двух символов, то переставить два первых символа.
Решение:
1) Построение протокола
*ba .ab
*ab .ba
*ac .ca
*ca .ac
*bc .cb
*cb .bc
** .
*
Работника нам нужно обязательно ввести, для того, чтобы обозначить начало слова. Иначе машина Маркова будет работать некорректно, так как станет переставлять последовательности букв, не находящихся в начале слова
** могут появиться в случае, если слово содержит одну букву, или же первые две буквы одинаковые.
2) Графическое представление алгоритма
3) Результаты отладки на эмуляторе
Пусть нам дано входное слова abc, тогда имеем:
Результаты отладки на эмуляторе машины Маркова показываю, что вычислительный процесс преобразования исходного слова в заключительное выполняется верно.