Инфоурок / Информатика / Конспекты / Машина Поста
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Педагогическая деятельность в соответствии с новым ФГОС требует от учителя наличия системы специальных знаний в области анатомии, физиологии, специальной психологии, дефектологии и социальной работы.

Только сейчас Вы можете пройти дистанционное обучение прямо на сайте "Инфоурок" со скидкой 40% по курсу повышения квалификации "Организация работы с обучающимися с ограниченными возможностями здоровья (ОВЗ) в соответствии с ФГОС" (72 часа). По окончании курса Вы получите печатное удостоверение о повышении квалификации установленного образца (доставка удостоверения бесплатна).

Автор курса: Логинова Наталья Геннадьевна, кандидат педагогических наук, учитель высшей категории. Начало обучения новой группы: 27 сентября.

Подать заявку на этот курс    Смотреть список всех 224 курсов со скидкой 40%

Машина Поста

библиотека
материалов

Конспект урока по информатике за 10 класс по теме: «Машина Поста»

Цели урока:

образовательные

  • ввести понятие машины Поста;

  • научиться описывать алгоритмы при помощи машины Поста;

развивающие

  • развивать умение анализировать, делать выводы, систематизировать полученную информацию;

  • развивать навыки логического мышления;

воспитательные

  • воспитывать внимательность и аккуратность;

  • воспитывать самостоятельность и устойчивый интерес к предмету.

Тип урока: урок изучения и первичного закрепления новых знаний.

Формы работы учащихся: фронтальный опрос.

Оборудование:

Литература: «Информатика и ИКТ 10-11», Семакин И. Г., Хеннер Е. К. (2013, 246с.)

План урока:

Организационный момент (2 минуты);

Проверка домашней работы (7 минут);

Актуализация знаний (5 минут);

Изучение нового материала (15 минут);

Первичное закрепление изученного материала (12 минуты);

Подведение итогов (2 минуты);

Домашнее задание (2 минуты).


Ход урока

Организационный момент (2 минуты).

Приветствие учеников. Объявление целей урока, постановка задач. Проверка готовности учащихся к уроку: проверка наличия тетрадей, учебников. Проверка отсутствующих на уроке.


Проверка домашней работы (7 минут).

Во время проверки домашней работы ученики зачитывают подготовленные ими конспекты. Учитель задает дополнительные вопросы по теме конспектов.


Актуализация знаний (5 минут).

Учитель. Что такое алгоритм?

Ученик. Алгоритм – это определенная последовательность каких-либо операций или действий.

Учитель. Приведите пример алгоритма.

Ученик. Примером алгоритма может являться какая-либо инструкция, рецепт и т.д.

Учитель. Что такое Исполнитель?

Ученик. Человек или автоматическое устройство, которому поручается исполнить алгоритм или программу называется исполнителем.

Учитель. Что такое система команд Исполнителя?

Ученик. Это все команды, которые исполнитель умеет выполнять.

Учитель. Что такое программа?

Ученик. Программа – описание алгоритма решения задачи, заданное на языке программирования.


Изучение нового материала (15 минут).

Учитель. Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”.

Запись в тетрадях. Тезис Поста: “Всякий алгоритм представим в форме машины Поста”.

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

Запись в тетрадях. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия.

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

http://inf.1september.ru/2007/01/04-00.gif

Рис. 1.

Ученики зарисовывают в тетради.

В каждый момент времени каретка указывает на одну из ячеек. В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает одну ячейку. За единицу времени каретка может совершить одно из трех действий: стереть метку, поставить метку, совершить движение на соседнюю ячейку. Состояние машины Поста складывается из состояния ленты и положения каретки.

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

  • попытка записать 1 (метку) в заполненную ячейку;

  • попытка стереть метку в пустой ячейке;

  • бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий — зацикливание — ничуть не лучше вышеперечисленного).

Машина Поста может производить различные вычисления, для чего надо задать начальное состояние каретки и программу, которая эти вычисления сделает. Условимся каждый шаг программы обозначать номером. Команды машины будем обозначать следующим образом:

http://inf.1september.ru/2007/01/04-01.gif

Ученики записывают в тетради.

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

Рассмотрим задачу для машины Поста и ее решение.

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

Решение. Сначала попробуем описать алгоритм обычным языком.

Ученик 1. Поскольку нам известно, что каретка стоит напротив пустой ячейки, но неизвестно, сколько шагов нужно совершить до пустой ячейки, мы можем сразу сделать шаг вправо.

Ученик 2. Проверить, заполнена ли ячейка.

Ученик 3. Если она пустая, то повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку.

Ученик 4. Как только мы ее найдем, мы выполним операцию стирания.

Ученик 5. После чего нужно будет лишь сместить каретку влево и остановить выполнение программы.

Учитель: А теперь попробуем записать данные команды с помощью команд машины Поста.

Ученик выходит к доске.

Запись на доске и в тетрадях.

http://inf.1september.ru/2007/01/04-03.gif


Первичное закрепление изученного материала (12 минут).

Учитель. А теперь постараемся решить следующие задачи. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста. Начальное состояние имеет следующий вид.


V

V

V



V

V


Ученик выходит к доске. Другие ученики переносят состояние ленты в тетради.

Учитель. К алгоритму применимы следующие команды.

http://inf.1september.ru/2007/01/04-04.gif

Учитель. Какую команду мы должны выполнить, чтобы выяснить является ли ячейка пустой или нет?

Ученик. Мы должны посмотреть пуста ли ячейка – выполнить команду 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


Учитель. Для данной ленты применимы следующие команды.

http://inf.1september.ru/2007/01/04-06.gif

Ученик выходит к доске. Другие ученики переносят состояние ленты и команды в тетради. Задача решается по аналогии.

Ученик. Лента примет вид.


V

V







V


Учитель. Молодец, правильно.


Подведение итогов (2 минуты).

Учитель. Сегодня мы с вами познакомились с понятием «Машина Поста», узнали, что с помощью нее можно записать любой алгоритм, научились пользоваться ей на практике.


Домашнее задание (2 минуты).

Учитель. Дома вам необходимо решить следующие задания:

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


V

V

V


V

V

V


К алгоритму применимы следующие команды.

http://inf.1september.ru/2007/01/04-04.gif

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


V

V

V

V

V

V


Для данной ленты применимы следующие команды.

http://inf.1september.ru/2007/01/04-06.gif

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



Самые низкие цены на курсы переподготовки

Специально для учителей, воспитателей и других работников системы образования действуют 50% скидки при обучении на курсах профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца с присвоением квалификации (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок", но в дипломе форма обучения не указывается.

Начало обучения ближайшей группы: 27 сентября. Оплата возможна в беспроцентную рассрочку (10% в начале обучения и 90% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru

Краткое описание документа:

Ход урока Организационный момент (2 минуты). Приветствие учеников. Объявление целей урока, постановка задач. Проверка готовности учащихся к уроку: проверка наличия тетрадей, учебников. Проверка отсутствующих на уроке.   Проверка домашней работы (7 минут). Во время проверки домашней работы ученики зачитывают подготовленные ими конспекты. Учитель задает дополнительные вопросы по теме конспектов.   Актуализация знаний (5 минут). Учитель. Что такое алгоритм? Ученик. Алгоритм – это определенная последовательность каких-либо операций или действий. Учитель. Приведите пример алгоритма. Ученик. Примером алгоритма может являться какая-либо инструкция, рецепт и т.д. Учитель. Что такое Исполнитель? Ученик. Человек или автоматическое устройство, которому поручается исполнить алгоритм или программу называется исполнителем. Учитель. Что такое система команд Исполнителя? Ученик. Это все команды, которые исполнитель умеет выполнять. Учитель. Что такое программа? Ученик. Программа – описание алгоритма решения задачи, заданное на языке программирования.

Общая информация

Номер материала: 108765051927

Похожие материалы

2017 год объявлен годом экологии и особо охраняемых природных территорий в Российской Федерации. Министерство образования и науки рекомендует в 2017/2018 учебном году включать в программы воспитания и социализации образовательные события, приуроченные к году экологии.

Учителям 1-11 классов и воспитателям дошкольных ОУ вместе с ребятами рекомендуем принять участие в международном конкурсе «Законы экологии», приуроченном к году экологии. Участники конкурса проверят свои знания правил поведения на природе, узнают интересные факты о животных и растениях, занесённых в Красную книгу России. Все ученики будут награждены красочными наградными материалами, а учителя получат бесплатные свидетельства о подготовке участников и призёров международного конкурса.

Конкурс "Законы экологии"