RGR_6
.docxБалтийский Федеральный Университет им.И.Канта
Факультет Высшей Школы Педагогики
Кафедра педагогики и образовательных технологий
Расчетно-графическая работа №6
по дисциплине: «Теоретические основы информатики»
Тема: «Нормальные алгоритмы Маркова и машины Тьюринга»
Вариант №15
Выполнила: студентка 2 курса
направления «Педагогическое образование»
Скобликова Мария
Проверил: Колесников Александр Васильевич, профессор
Калиниград, 2014г
Содержание
-
Нормальные алгоритмы Маркова
-
Определение понятия «Нормальный алгоритм Маркова»…………………..3
-
Решение задачи с помощью нормальных алгоритмов Маркова………….3-5
-
-
Машина Тьюринга
2.1 Математическая модель машины Тьюринга…………………………..........6
-
Решение задачи с помощью машины Тьюринга…………………..……...6-9
-
Анализ результатов и выводы…………………………………….………….10
-
Список используемой литературы……………...............................................11
1.Нормальные алгоритмы Маркова
1.1 Определение понятия «Нормальный алгоритм Маркова»
Понятие «нормальный алгоритм» было введено в 1947 г. Советским ученым А.А. Марковым в качестве одного из уточнений представления об алгоритме. Он предполагал, что нормальный алгоритм, являясь алгоритмом в некотором алфавите, порождает некоторый детерминированный процесс переработки только одного слова и только в одном алфавите.
Словами в алгоритме Маркова могут быть арифметические, алгебраические или логические выражения. Но это оказалось удобным средством алгоритмизации для слов не математической природы.
Нормальный алгоритм Маркова – указание использовать упорядоченный список правил подстановки:
где αi и βi - слова в алфавите Vт.
Слово αi часто называют левой, а βi - правой частью правил.
Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:
k>=1
В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.
Записать алгоритм в виде НАМ – значит предъявить такой набор формул.
1.2 Решение задачи с помощью нормальных алгоритмов Маркова
Дано:
A={a,b,c}.
Условие:
Если в слове P не менее двух символов, то переставить два первых символа.
Решение:
-
Построение протокола
*ba .ab
*ab .ba
*ac .ca
*ca .ac
*bc .cb
*cb .bc
** .
*
Работника нам нужно обязательно ввести, для того, чтобы обозначить начало слова. Иначе машина Маркова будет работать некорректно, так как станет переставлять последовательности букв, не находящихся в начале слова
** могут появиться в случае, если слово содержит одну букву, или же первые две буквы одинаковые.
-
Графическое представление алгоритма
-
Результаты отладки на эмуляторе
Пусть нам дано входное слова abc, тогда имеем:
Результаты отладки на эмуляторе машины Маркова показываю, что вычислительный процесс преобразования исходного слова в заключительное выполняется верно.
2. Машина Тьюринга
2.1 Математическая модель машины Тьюринга
Математическая модель машины Тьюринга имеет вид:
Т=<Vt; 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) Построение протокола
q0 а q0 аП
q0 b q0 bП
q0 # q1 cЛ
q1 а q1 аЛ
q1 b q1 bЛ
q1 # q2 #П
q2 а q3 #П
q2 b q4 #П
q2 c q7 #Л
q3 а q3 аП
q3 b q3 bП
q3 c q3 cП
q3 # q5 аЛ
q4 а q4 аП
q4 b q4 bП
q4 c q4 cП
q4 # q6 bЛ
q5 а q5 аЛ
q5 b q5 bЛ
q5 c q5 cЛ
q5 # q2 аП
q6 а q6 аЛ
q6 b q6 bЛ
q6 c q6 cЛ
q6 # q2 bП
q7 а q8 #П
q7 b q9 #П
q7 # q11 #П
q8 # q10 аЛ
q9 # q10 bЛ
q10 # q7 #Л
q11a qk a C
q11b qk b C
q11 # q11# П
3) Построение графа
Граф представлен на следующей странице
Пусть нам дана последовательность ab, тогда имеем следующий вычислительный процесс:
-
Результаты отладки на эмуляторе
Для начала отмечу, что данный эмулятор Машины Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние: попав в него, автомат заканчивает работу ( именно поэтому в эмуляторе состояний (q) больше, чем в моих таблице, протоколе, графе).
Пусть нам дано входное слово abba, тогда имеем:
Результаты отладки на эмуляторе машины Тьюринга показываю, что вычислительный процесс преобразования исходного слова в заключительное выполняется верно.
3. Анализ результатов и выводы
В ходе проделанной работы я разработала протокол и граф-схему нормального алгоритма Маркова, в соответствии с данным условием задачи. При этом результат был проверен на эмуляторе машины Маркова, что позволило сделать вывод о том, что алгоритм составлен верно.
Также, на основании условий задания, мной были разработаны протокол, таблица переходов и граф состояний машины Тьюринга. Как и в предыдущем случае, полученные результаты отлажены на эмуляторе машины Тьюринга и доказывают правильность найденного алгоритма.
Данные средства используются в информатике для уточнения понятия «алгоритм».
-
Список используемой литературы
-
Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) - М.: МГУ, 2006. – 47 с.
-
Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.
-
Сайта К. Полякова «Преподавание, наука и жизнь» [Электронный ресурс]. – Режим доступа: http://kpolyakov.narod.ru/index.htm, свободный. – Загл. с экрана (дата обращения: 15.11.2014).