Презентация по информатике _Машина поста_ (10-11 классы).pptx

Автоматическая обработка информации.
Машина Поста
11 класс

1) способствовать углублению знаний учащихся об алгоритмах обработки информации;

2) ввести понятие алгоритмической машины, рассказать о моделях алгоритмических машин Тьюринга и Поста;

3) способствовать формированию умения составлять программу на компьютерной модели машины Поста.

В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения?
Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в лю­бом алфавите.

Бесконечная лента

Каретка

Программа

Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгорит- мической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным слу­чаем машины Тьюринга.

Бесконечная лента

Программа

Каретка

Ал­горитм, по которому работает машина Поста, будем на­зывать программой.
Под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто).

Вдоль ленты движется каретка — считывающее устройство. На рисун­ке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей.
Каретка является еще и процессором машины. С ее помощью машина может:
• распознать, пустая клетка или помеченная знаком;
• стереть знак в текущей клетке;
• записать знак в пустую текущую клетку.

Существенное отличие каретки-процессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Поста — только последовательно.

Назначение машины Поста — производить преобразования на инфор­мационной ленте.
Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

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

В процессе выполнения приведенной программы многократно повторя­ется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом.
Напомним, что цикл относится к числу основных алгоритмичес­ких структур вместе со следованием и ветвлением.

Назначение машины Поста — производить преобразования на инфор­мационной ленте.
Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?
1 → 2
2 ↕ 3
3 → 4
4? 5, 2
5 ← 6
6 V 7
7 !

Закрепление материала

Назначение машины Поста — производить преобразования на инфор­мационной ленте.
Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

Закрепление материала

На ленте поставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

Назначение машины Поста — производить преобразования на инфор­мационной ленте.
Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

Закрепление материала

Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.
Начальное состояние:


Конечное состояние:

Назначение машины Поста — производить преобразования на инфор­мационной ленте.
Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

Закрепление материала

Составить программу перевода информационной ленты из начального состояния в конечное:

Начальное состояние:


Конечное состояние:

Домашнее задание:

§ 45, отвечать на вопросы, задачи № 1-8
2. Подготовьте сообщение:
«Какие бывают машины Тьюринга?»
«Эзотерические языки программирования»
«Рекурсивные функции»