Конспект урока по информатике по теме: "Машина Поста"

Тема: Машина Поста.

Цель урока: сформировать знания обучающихся об автоматической обработке информации на примере машины Поста.

Задачи урока:

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

Развивающие:  способствовать развитию логического мышления; способствовать развитию кругозора учащихся.

Воспитательные:  создавать условия для воспитания потребности в овладении специальными знаниями, умениями, навыками.

Ход урока

1.Организационный момент.

2. Постановка целей и задач урока

«Сами машины - это пустые перчатки,
но их надевает человеческая рука,
которая может быть хорошей или плохой»

Р.Брэдбери.

3. Актуализация опорных знаний

Давайте вспомним, что понимают под обработкой информации?

Обработка информации – это процесс изменения формы представления информации или её содержания.

Кто может быть исполнителем обработки информации?

Исполнителем обработки информации может быть человек или автомат (компьютер).

Какие варианты обработки информации Вам известны?

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

Что такое алгоритм?

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

Приведите примеры алгоритмов.

Примеры алгоритмов:

а) алгоритм нахождения корней квадратного уравнения с помощью теоремы Виета;

б) алгоритм Евклида.

Какими свойствами обладает алгоритм?

Свойства алгоритмов:

·          Дискретность (разделенность на части) и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.

·          Детерминированность (однозначная определенность). Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда дает один и тот же результат.

·          Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.

·          Результативность и конечность. Работа алгоритма должна завершаться за определенное число шагов, при этом задача должна быть решена.

·          Массовость. Определенный алгоритм должен быть применим ко всем однотипным задачам.

4. Объяснение нового материала

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

В 1936 году английский ученый Алан Тьюринг и английский математик и логик польского происхождения Эмиль Пост независимо друг от друга предложили модели таких исполнителей – алгоритмические машины.

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

Характеристика машины Поста:

Описание машины	абстрактная вычислительная машина
Состав машины	1. бесконечная лента, разделенная на одинаковые ячейки 2. читающая, пишущая и перемещающаяся головка
Алфавит	двузначный или трехзначный
Выполняемые действия	поставить метку, перейти к j-й строке программы. стереть метку, перейти к j-й строке программы. сдвинуться влево, перейти к j-й строке программы. сдвинуться вправо, перейти к j-й строке программы. если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.    ! – конец программы (стоп).
Запись программы для машины	состоит из пронумерованных строк

Машина Поста проще, чем машина Тьюринга.

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

Знакомство с машиной Поста (ALGO2000). Демонстрация интерфейса.

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

Указание: Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

								v
0	0	1	1	1	1	1	0	1	1	1	0	0	0
Р								Q

Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. Х       - стираем левый символ у Q

2. →

3. ? 4, 5

4. Stop    - стоп если затерли Q=0

5. ←                              

6. ? 5, 7  - цикл поиска P

7. Х       - стираем правый символ у P

8. →

9. ? 8, 1  - ищем Q

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P. Проверьте работу программы.

6. Подведение итогов урока

Какие действия выполняет машина Поста?

Какие трудности у Вас возникли при написании программы вычитания двух чисел на машине Поста?

Выставление оценок активным учащимся.

7. Постановка домашнего задания: §1.7.3.