Слайд 1Автома
Автоматическая обработка информации.
Машина Поста
10 класс
Слайд 2Цели урока:
1) способствовать углублению знаний учащихся об алгоритмах обработки информации;
2)
ввести понятие алгоритмической машины, рассказать о моделях алгоритмических машин Тьюринга
и Поста;
3) способствовать формированию умения составлять программу на компьютерной модели машины Поста.
Слайд 3«Сами машины - это пустые перчатки,
Но их надевает человеческая рука,
Которая
может быть хорошей или плохой»
Р. Брэдбери.
Слайд 4Теория Алгоритмов
В 30-х годах XX века возникает
новая наука — теория алгоритмов. Вопрос, на который ищет ответ
эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения?
Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
Слайд 5 Английский ученый Алан Тьюринг предложил модель такого
исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина»
является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите.
МАШИНА ТЬЮРИНГА
Слайд 6Машина Тьюринга
Бесконечная лента
Каретка
Программа
Слайд 7МАШИНА ПОСТА
Практически одновременно с Тьюрингом (1936-1937
гг.) другую модель алгорит- мической машины описал Эмиль Пост. Машина
Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным случаем машины Тьюринга.
Слайд 8Машина Поста
Бесконечная лента
Программа
Каретка
Слайд 9
Алгоритм, по которому работает
машина Поста, будем называть программой.
Под словом «программа»
мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.
Машина Поста
Слайд 10 Опишем архитектуру машины Поста. Имеется
бесконечная информационная лента, разделенная на позиции — клетки. В каждой
клетке может либо стоять метка (некоторый знак), либо отсутствовать (пусто).
Вдоль ленты движется каретка — считывающее устройство. На рисунке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей.
Каретка является еще и процессором машины. С ее помощью машина может:
• распознать, пустая клетка или помеченная знаком;
• стереть знак в текущей клетке;
• записать знак в пустую текущую клетку.
Слайд 11Машина Поста
Существенное отличие каретки-процессора
машины Поста от процессора компьютера состоит в том, что в
компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Поста — только последовательно.
Слайд 12Машина Поста
Назначение машины Поста — производить
преобразования на информационной ленте.
Исходное
состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
Система команд машины Поста
Слайд 13Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 14Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 15Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 16Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 17Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 18Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 19Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 20Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 21Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 22Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 23Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 24Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения
задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
Слайд 25Машина Поста
В процессе выполнения приведенной
программы многократно повторяется выполнение команд с номерами 2 и 3.
Такая ситуация называется циклом.
Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.
Слайд 26Машина Поста
Назначение машины Поста — производить
преобразования на информационной ленте.
Исходное
состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?
1 → 2
2 ↕ 3
3 → 4
4? 5, 2
5 ← 6
6 V 7
7 !
Закрепление материала
Задание 1
Слайд 27Машина Поста
Назначение машины Поста — производить
преобразования на информационной ленте.
Исходное
состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
Закрепление материала
Задание 2
Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.
Начальное состояние:
Конечное состояние:
Слайд 28Машина Поста
Назначение машины Поста — производить
преобразования на информационной ленте.
Исходное
состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
Закрепление материала
Задание 3
Составить программу перевода информационной ленты из начального состояния в конечное:
Начальное состояние:
Конечное состояние: