§ 10. Автоматическая обработка информации

В качестве примера автомата, выполняющего обработку информации, рассмотрим машину Э. Поста (1897-1954). Алгоритм, по которому работает машина Поста, будем называть программой.

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

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

Рис. 2.3. Модель машины Поста

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

Каретка является еще и процессором машины. С ее помощью машина может:

• распознать, пустая клетка или помеченная знаком;
• стереть знак в текущей клетке;
• записать знак в пустую текущую клетку.

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

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

Теперь рассмотрим систему команд машины Поста (табл. 2.1). Запись всякой команды начинается с ее порядкового номера в программе — n. Затем следует код операции и после него — номер следующей выполняемой команды программы — m.

Таблица 2.1. Система команд машины Поста

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

Таблица 2.2. Программа для машины Поста

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

А теперь научим машину Поста играть в интеллектуальную игру, которая называется «Игра Баше»: Опишем правила игры.

Играют двое. Перед ними 21 (или 16, или 11 и т. д.) фишка. Игроки берут фишки по очереди. За один ход можно взять от 1 до 4 фишек. Проигрывает тот, кто забирает последнюю фишку.

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

Роль фишек на информационной ленте машины Поста будут выполнять метки (знаки). Машина играет с человеком. Человеку предоставляется возможность стирать метки (брать фишки) первым. Машина будет вступать в игру второй. Исходная обстановка: на ленте массив из 21 клетки содержит метки. Каретка установлена на крайней слева клетке этого массива. Стирать метки можно только подряд. Выигрышным результатом должна быть одна оставшаяся метка перед очередным ходом человека.

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

Программа управления машиной Поста в игре Баше против человека приведена в табл. 2.3.

Таблица 2.3. Программа игры Баше

Действуя по данной программе и начиная стирать метки второй после человека, машина всегда будет выигрывать, если правильно задано начальное число меток, которое должно быть равно 5n + 1, где n — любое натуральное число. В противном случае машина может проиграть.

Подведем итог. Автоматическая обработка информации возможна, если:

1. информация представлена в формализованном виде — в конечном алфавите некоторой знаковой системы;
2. реализован исполнитель, обладающий конечной системой команд, достаточной для построения алгоритмов решения определенного класса задач обработки информации;
3. реализовано программное управление работой исполнителя. Машина Поста — пример автоматического исполнителя обработки информации с ограниченными возможностями. Компьютер удовлетворяет всем вышеперечисленным свойствам. Он является универсальным автоматическим исполнителем обработки информации.

Система основных понятий

Вопросы и задания

На информационной ленте машины Поста расположен массив из N меток. Каретка находится под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?

7 !

На информационной ленте на некотором расстоянии справа от каретки, стоящей под пустой клеткой, находится непрерывный массив меток. Требуется присоединить к правому концу массива одну метку.

На ленте расположен массив из 2п — 1 меток. Составить программу отыскания средней метки и стирания ее.

На ленте расположен массив из 2п меток. Составить программу, по которой машина раздвинет на расстояние в одну клетку две половины данного массива.

Тема: Автоматическая обработка информации. Машина Поста. 10 класс
учебно-методический материал по информатике и икт на тему

Презентация и подборка задач с решениями.

Скачать:

Вложение	Размер
urok_12_mashina_posta.pptx	212.52 КБ
urok_13_zadachi_mashina_posta.docx	37.18 КБ

Предварительный просмотр:

Подписи к слайдам:

Автоматическая обработка информации Информатика 10 класс

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

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

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

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

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

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

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

Система команд машины Поста Команда Действие n ← m Сдвиг каретки на шаг влево и переход к выполнению команды с номером m n → m Сдвиг каретки на шаг вправо и переход к выполнению команды с номером m n v m Запись метки в текущую пустую клетку и переход к выполнению команды с номером m n ↕ m Стирание метки в текущей клетке и переход к выполнению команды с номером m n ! Остановка выполнения программы n ? m,k Переход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m , если непустая – команда с номером k

П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины

П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины V V V V

П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины

П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины

П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины v П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

v v v v v Команда Действие 1 ↕ 2 Стирание метки; переход к следующей команде 2 → 3 Сдвиг вправо на один шаг 3 ? 2 , 4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6 Запись метки в пустую клетку 6 ! Остановка машины П ример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

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