RGR_6

Балтийский Федеральный Университет им.И.Канта

Факультет Высшей Школы Педагогики

Кафедра педагогики и образовательных технологий

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

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

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

Вариант №15

Выполнила: студентка 2 курса

направления «Педагогическое образование»

Скобликова Мария

Проверил: Колесников Александр Васильевич, профессор

Калиниград, 2014г

Содержание

1. Нормальные алгоритмы Маркова

   1. Определение понятия «Нормальный алгоритм Маркова»…………………..3

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

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

2.1 Математическая модель машины Тьюринга…………………………..........6

2. Решение задачи с помощью машины Тьюринга…………………..……...6-9

3. Анализ результатов и выводы…………………………………….………….10

4. Список используемой литературы……………...............................................11

1.Нормальные алгоритмы Маркова

1.1 Определение понятия «Нормальный алгоритм Маркова»

Понятие «нормальный алгоритм» было введено в 1947 г. Советским ученым А.А. Марковым в качестве одного из уточнений представления об алгоритме. Он предполагал, что нормальный алгоритм, являясь алгоритмом в некотором алфавите, порождает некоторый детерминированный процесс переработки только одного слова и только в одном алфавите.

Словами в алгоритме Маркова могут быть арифметические, алгебраические или логические выражения. Но это оказалось удобным средством алгоритмизации для слов не математической природы.

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

где α_i и β_i - слова в алфавите Vт.

Слово α_i часто называют левой, а β_i - правой частью правил.

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

k>=1

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

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

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

Дано:

A={a,b,c}.

Условие:

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

Решение:

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

*ba .ab

*ab .ba

*ac .ca

*ca .ac

*bc .cb

*cb .bc

** .

*

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

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

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

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

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

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

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

2.1 Математическая модель машины Тьюринга

Математическая модель машины Тьюринга имеет вид:

Т=<V_t; Q; D; ; ;  ,

где: VT = {ai; a2; ... an}	- символы внешней памяти;
Q = {qo, qi; q2; ... qm}	- символы внутренней памяти;
D = {П; Л; С}	- символы перемещения головки;
: Q  Vt => Vt	- функция выхода машины Тьюринга;
: Q  Vt => Q	- функция переходов машины Тьюринга.
: Q  Vt => D	- функция перемещения головки машины Тьюринга.

2.2 Решение задачи с помощью машины Тьюринга

Дано:

A={a,b}

Условие:

Удвоить слово P

Решение:

Для того, чтобы обозначить конец слова, введём в данный нам алфавит ещё один символ - c.

1) Построение таблицы

Теку щее состо яние	Символы
	a	b	c	#	Комментарий
q0	q0 аП	q0 bП	-	q1 cЛ	Установка символа «c» в конец слова
q1	q1 аЛ	q1 bЛ	-	q2 #П	Переход обратно к началу слова
q2	q3 #П	q4 #П	q7 #Л	-	Определяет букву, над которой находится головка
q3	q3 аП	q3 bП	q3 cП	q5 аЛ	Копирование буквы а
q4	q4 аП	q4 bП	q4 cП	q6 bЛ	Копирование буквы b
q5	q5 аЛ	q5 bЛ	q5 cЛ	q2 аП	Копирование буквы а
q6	q6 аЛ	q6 bЛ	q6 cЛ	q2 bП	Копирование буквы b
q7	q8 #П	q9 #П	-	q11#П	Перенос слова на ячейку вправо
q8	-	-	-	q10 аЛ	Перенос слова на ячейку вправо
q9	-	-	-	q10 bЛ	Перенос слова на ячейку вправо
q10	-	-	-	q7 #Л	Перенос слова на ячейку вправо
q11	qk aС	qk bС	-	q11 #П	Передвижение головки в начало слова

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

q₀ а q₀ аП

q₀ b q₀ bП

q₀ # q₁ cЛ

q₁ а q₁ аЛ

q₁ b q₁ bЛ

q₁ # q₂ #П

q₂ а q₃ #П

q₂ b q₄ #П

q₂ c q₇ #Л

q₃ а q₃ аП

q₃ b q₃ bП

q₃ c q₃ cП

q₃ # q₅ аЛ

q₄ а q₄ аП

q₄ b q₄ bП

q₄ c q₄ cП

q₄ # q₆ bЛ

q₅ а q₅ аЛ

q₅ b q₅ bЛ

q₅ c q₅ cЛ

q₅ # q₂ аП

q₆ а q₆ аЛ

q₆ b q₆ bЛ

q₆ c q₆ cЛ

q₆ # q₂ bП

q₇ а q₈ #П

q₇ b q₉ #П

q₇ # q₁₁ #П

q₈ # q₁₀ аЛ

q₉ # q₁₀ bЛ

q₁₀ # q₇ #Л

q₁₁a q_k a C

q₁₁b q_k b C

q₁₁ # q₁₁# П

3) Построение графа

Граф представлен на следующей странице

Пусть нам дана последовательность ab, тогда имеем следующий вычислительный процесс:

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

Для начала отмечу, что данный эмулятор Машины Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ — это конечное состояние: попав в него, автомат заканчивает работу ( именно поэтому в эмуляторе состояний (q) больше, чем в моих таблице, протоколе, графе).

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

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

3. Анализ результатов и выводы

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

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

Данные средства используются в информатике для уточнения понятия «алгоритм».

5. Список используемой литературы

1. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) - М.: МГУ, 2006. – 47 с.

2. Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.

3. Сайта К. Полякова «Преподавание, наука и жизнь» [Электронный ресурс]. – Режим доступа: http://kpolyakov.narod.ru/index.htm, свободный. – Загл. с экрана (дата обращения: 15.11.2014).