Решение задачи с помощью нормальных алгоритмов Маркова

Расчетно-графическая работа №6

по дисциплине: «Теоретические основы информатики»

Тема: «Нормальные алгоритмы Маркова и машины Тьюринга»

Вариант №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 - правой частью правил.

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

Решение задачи с помощью нормальных алгоритмов Маркова

Дано:

A={a,b,c}.

Условие:

Если в слове P не менее двух символов, то переставить два первых символа.

Решение:

1) Построение протокола

*ba .ab

*ab .ba

*ac .ca

*ca .ac

*bc .cb

*cb .bc

** .

*

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

** могут появиться в случае, если слово содержит одну букву, или же первые две буквы одинаковые.

2) Графическое представление алгоритма

3) Результаты отладки на эмуляторе

Пусть нам дано входное слова abc, тогда имеем:

Результаты отладки на эмуляторе машины Маркова показываю, что вычислительный процесс преобразования исходного слова в заключительное выполняется верно.

Машина Тьюринга

Поиск по сайту: