Автор работы: Пользователь скрыл имя, 06 Мая 2012 в 19:29, контрольная работа
Одним из центральных понятий информатики является понятие алгоритма. Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Леон Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат.
ВВЕДЕНИЕ 3
1. 1. Машина Поста. Основные понятия и операции 4
1.2. Способ задания проблемы и формулировка 1 6
2. Машина Тьюринга 8
3.Решение Задач 11
ЗАКЛЮЧЕНИЕ 13
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14
3. Решение задач
Задача 4.Машина Поста
Правила игры Баше: на ленте имеется последовательность из 21 метки. В начале игры головка расположена над крайней левой меткой. Игроки (машина Поста и вы) поочередно сдвигают головку вправо на 1, 2, 3 или 4 ячейки. Первый ход у вас. Проигрывает тот, кто первым достигает конца последовательности. Напишите программу для МП, по которой она будет выигрывать.
Решение:
Начинать с крайней левой
Для каждого хода запускать заново!
1 С 2 2 → 3 3 → (4, 2) 4 ← 5 5 → (49, 6) 6 ← 7 7 → (50, 8) 8 ← 9 9 → (51, 10) 10 ← 11
|
11 → (51, 12) 12 ← 13 13 → (44, 14) 14 ← 15 15 → (49, 16) 16 ← 17 17 → (50,18) 18 ← 19 19 → (51, 20) 20 ← 21
|
21 → (44, 22) 22 ← 23 23 → (49, 24) 24 ← 25 25 → (50, 26) 26 ← 27 27 → (51, 28) 28 ← 29 29 → (44, 30) 30 ← 31 |
31 → (49, 32) 32 ← 33 33 → (50, 34) 34 ← 35 35 → (51, 36) 36 ← 37 37 → (44, 38) 38 ← 39 39 → (49, 40) 40 ← 41 |
41 → (50, 42) 42 ← 43 43 → (51, 44) 44 M 45 45 → 46 46 → 47 47 → 48 48 → 52 49 M 46 50 M 47 51 M 48 52 СТОП 52 |
Задача 4. Машина Тьюринга
На ленте машины Тьюринга задана последовательность из символов двоичного алфавита. Необходимо переместить все нули в начало строки, а единицы – в конец.
Решение:
Начальное положение головки– над крайней левой меткой
A\Q |
Q0 |
Q1 |
Q2 |
Q3 |
1 |
1>0 |
0>2 |
||
0 |
0<1 |
0>3 |
1<0 |
0<0 |
Пробел |
_!0 |
_>3 |
ЗАКЛЮЧЕНИЕ
Машина Поста — это абстрактная
(т.е. не существующая в арсенале действующей
техники), но очень простая вычислительная
машина. Она способна выполнять лишь
самые элементарные действия, и потому
ее описание и составление простейших
программ может быть доступно ученикам
начальной школы. Тем не менее
на машине Поста можно запрограммировать
— в известном смысле — любые
алгоритмы. Изучение машины Поста можно
рассматривать как начальный
этап обучения теории алгоритмов и
программированию. Разработка программ
для машин Поста — достаточно
эффективный этап в обучении алгоритмизации,
т.к. в процессе написания этих программ
учащиеся учатся разбивать интуитивно
понятные вычислительные процедуры
на элементарные действия. Изучение машины
Поста полезно как школьникам,
интересующимся информатикой и математикой,
так и студентам младших
Машина Поста менее популярна, хотя она значительно проще машины Тьюринга. С ее помощью можно вести обучение первым навыкам составления программ для ЭВМ.
Машина Тьюринга - также очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы.
В 1947 г. Алан Тьюринг расширил определение,
описав "универсальную машину Тьюринга".
Позже для решения определенных классов
задач была введена ее разновидность,
которая позволяла выполнять не одну задачу,
а несколько.
СПИСОК ЛИТЕРАТУРЫ
1. Авдеев Р.Ф. Философия информационной цивилизации [Текст] / Р.Ф. Авдеев. – М.: ВЛАДОС, 2008.
2. Булгаков И.С. Счетные машины [Текст] / И.С. Булгаков. – М.: Машгиз, 2010.
3. Ершов Ю.Л. Математическая логика [Текст] / Ю.Л. Ершов, Е.А. Палютин. – М.: Наука, 2008.
4. Клини С. Введение в метаматематику [Текст] / С. Клини. – М.: Изд-во иностр. лит., 2008.
5. Клини С. Машины Тьюринга и рекурсивные функции [Текст] / С. Клини. – М., 2010.
6. Колин, К.К. Фундаментальные основы информатики: социальная информатика [Текст]: учеб. пособие для вузов / К.К. Колин. – М.: Академический Проект; Екатеринбург: Деловая книга, 2008.
7. Поликарпов В.С. История науки и техники [Текст]: учеб. пособие / В.С. Поликарпов. – Ростов Н/Д: Феникс, 2008.
8. Успенский В.А. Машина Поста [Текст] / В.А. Успенский. – М.: Наука, 2010. – 96 с.
9. Успенский В.А. Теория алгоритмов: основные открытия и приложения [Текст] / В.А. Успенский, А.Л. Семенов. – М.: Наука, 2010. – 288 с.