Машина Поста

Конспект урока по информатике за 10 класс по теме: «Машина Поста»
Цели урока:
образовательныеввести понятие машины Поста;
научиться описывать алгоритмы при помощи машины Поста;
развивающиеразвивать умение анализировать, делать выводы, систематизировать полученную информацию;
развивать навыки логического мышления;
воспитательныевоспитывать внимательность и аккуратность;
воспитывать самостоятельность и устойчивый интерес к предмету.
Тип урока: урок изучения и первичного закрепления новых знаний.
Формы работы учащихся: фронтальный опрос.
Оборудование: –
Литература: «Информатика и ИКТ 10-11», Семакин И. Г., Хеннер Е. К. (2013, 246с.)
План урока:
Организационный момент (2 минуты);
Проверка домашней работы (7 минут);
Актуализация знаний (5 минут);
Изучение нового материала (15 минут);
Первичное закрепление изученного материала (12 минуты);
Подведение итогов (2 минуты);
Домашнее задание (2 минуты).
Ход урока
Организационный момент (2 минуты).
Приветствие учеников. Объявление целей урока, постановка задач. Проверка готовности учащихся к уроку: проверка наличия тетрадей, учебников. Проверка отсутствующих на уроке.
Проверка домашней работы (7 минут).
Во время проверки домашней работы ученики зачитывают подготовленные ими конспекты. Учитель задает дополнительные вопросы по теме конспектов.
Актуализация знаний (5 минут).
Учитель. Что такое алгоритм?
Ученик. Алгоритм – это определенная последовательность каких-либо операций или действий.
Учитель. Приведите пример алгоритма.
Ученик. Примером алгоритма может являться какая-либо инструкция, рецепт и т.д.
Учитель. Что такое Исполнитель?
Ученик. Человек или автоматическое устройство, которому поручается исполнить алгоритм или программу называется исполнителем.
Учитель. Что такое система команд Исполнителя?
Ученик. Это все команды, которые исполнитель умеет выполнять.
Учитель. Что такое программа?
Ученик. Программа – описание алгоритма решения задачи, заданное на языке программирования.
Изучение нового материала (15 минут).
Учитель. Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.
Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”.
Запись в тетрадях. Тезис Поста: “Всякий алгоритм представим в форме машины Поста”.
Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.
Запись в тетрадях. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.
Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия.
Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

Рис. 1.
Ученики зарисовывают в тетради.
В каждый момент времени каретка указывает на одну из ячеек. В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.
Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает одну ячейку. За единицу времени каретка может совершить одно из трех действий: стереть метку, поставить метку, совершить движение на соседнюю ячейку. Состояние машины Поста складывается из состояния ленты и положения каретки.
Действия каретки подчинены программе, состоящей из перенумерованного набора команд (команды можно представлять как строки программы). Команды бывают шести типов:
1. записать 1 (метку), перейти к i-й строке программы;
2. записать 0 (стереть метку), перейти к i-й строке программы;
3. сдвиг влево, перейти к i-й строке программы;
4. сдвиг вправо, перейти к i-й строке программы;
5. останов;
6. если 0, то перейти к i, иначе перейти к j.
Приведем список недопустимых действий, ведущих к аварийной остановке машины:
попытка записать 1 (метку) в заполненную ячейку;
попытка стереть метку в пустой ячейке;
бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий — зацикливание — ничуть не лучше вышеперечисленного).
Машина Поста может производить различные вычисления, для чего надо задать начальное состояние каретки и программу, которая эти вычисления сделает. Условимся каждый шаг программы обозначать номером. Команды машины будем обозначать следующим образом:

Ученики записывают в тетради.
Будем говорить, что мы можем применить программу к текущему состоянию машины Поста, если выполнение программы не приведет к зацикливанию, т.е. рано или поздно мы выполним команду останов.
Рассмотрим задачу для машины Поста и ее решение.
Задача. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.
Решение. Сначала попробуем описать алгоритм обычным языком.
Ученик 1. Поскольку нам известно, что каретка стоит напротив пустой ячейки, но неизвестно, сколько шагов нужно совершить до пустой ячейки, мы можем сразу сделать шаг вправо.
Ученик 2. Проверить, заполнена ли ячейка.
Ученик 3. Если она пустая, то повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку.
Ученик 4. Как только мы ее найдем, мы выполним операцию стирания.
Ученик 5. После чего нужно будет лишь сместить каретку влево и остановить выполнение программы.
Учитель: А теперь попробуем записать данные команды с помощью команд машины Поста.
Ученик выходит к доске.
Запись на доске и в тетрадях.

Первичное закрепление изученного материала (12 минут).
Учитель. А теперь постараемся решить следующие задачи. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста. Начальное состояние имеет следующий вид.
V V V V V Ученик выходит к доске. Другие ученики переносят состояние ленты в тетради.
Учитель. К алгоритму применимы следующие команды.
Учитель. Какую команду мы должны выполнить, чтобы выяснить является ли ячейка пустой или нет?
Ученик. Мы должны посмотреть пуста ли ячейка – выполнить команду 1.
Учитель. Ячейка не пуста, значит к какой команде мы должны перейти?
Ученик. Так как ячейка пуста нужно перейти к команде 2.
Учитель. Что нужно сделать в команде 2?
Ученик. Нужно сдвинуться в право и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 2.
Учитель. Что нужно сделать в команде 2?
Ученик. Нужно сдвинуться в право и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 2.
Учитель. Что нужно сделать в команде 2?
Ученик. Нужно сдвинуться в право и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V _ V V Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 3.
Учитель. Что нужно сделать в команде 3?
Ученик. Нужно сдвинуться в право и перейти к команде 4.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V _ V V Учитель. Что нужно сделать в команде 4?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 6.
Учитель. Что нужно сделать в команде 6?
Ученик. Нужно сдвинуться в право и перейти к команде 7.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 7?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 9.
Учитель. Что нужно сделать в команде 9?
Ученик. Нужно сдвинуться в право и перейти к команде 4.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 4?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 5.
Учитель. Что нужно сделать в команде 5?
Ученик. Нужно сдвинуться в лево и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 2.
Учитель. Что нужно сделать в команде 2?
Ученик. Нужно сдвинуться в право и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка не пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 2.
Учитель. Что нужно сделать в команде 2?
Ученик. Нужно сдвинуться в право и перейти к команде 1.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V _ Учитель. Что нужно сделать в команде 1?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 3.
Учитель. Что нужно сделать в команде 3?
Ученик. Нужно сдвинуться в право и перейти к команде 4.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V _ Учитель. Что нужно сделать в команде 4?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 6.
Учитель. Что нужно сделать в команде 6?
Ученик. Нужно сдвинуться в право и перейти к команде 7.
Учитель. Какой вид примет лента после этого?
Ученик. Лента примет вид.
V V V V V _ Учитель. Что нужно сделать в команде 7?
Ученик. Нужно посмотреть пуста ли ячейка.
Учитель. Ячейка пуста, следовательно к какой команде нужно перейти?
Ученик. Нужно перейти к команде 8.
Учитель. Что нужно сделать в команде 8?
Ученик. Нужно остановит машину.
Учитель. Какой вид примет лента?
Ученик. Лента примет вид.
V V V V V _ Учитель. Молодец, правильно.
Ученики зарисовывают в тетради все этапы решения задачи с поэтапным применением команд.
Учитель. Следующее состояние имеет вид. Команды те же, что и в первой задаче.
V V V V Ученик выходит к доске. Другие ученики переносят состояние ленты в тетради. Задача решается по аналогии.
Ученик. Лента примет вид.
V V V V _ Учитель. Молодец, правильно.
Учитель. Что делает данный алгоритм?
Ученик. Данный алгоритм приписывает к ленте 3 пустых ячейки.
Учитель. Правильно. Следующее задание. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.
V V V V V V Учитель. Для данной ленты применимы следующие команды.

Ученик выходит к доске. Другие ученики переносят состояние ленты и команды в тетради. Задача решается по аналогии.
Ученик. Лента примет вид.
V V V Учитель. Молодец, правильно.
Подведение итогов (2 минуты).
Учитель. Сегодня мы с вами познакомились с понятием «Машина Поста», узнали, что с помощью нее можно записать любой алгоритм, научились пользоваться ей на практике.
Домашнее задание (2 минуты).
Учитель. Дома вам необходимо решить следующие задания:
1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста. Начальное состояние имеет следующий вид.
V V V V V V К алгоритму применимы следующие команды.

2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.
V V V V V V Для данной ленты применимы следующие команды.

Урок окончен, все свободны.