Конспект урока по информатике для учащихся 10 класса по теме: «Автоматическая обработка информации. Машина Поста»

Конспект урока по информатике для учащихся 10 класса по теме:

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

Цель урока:

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

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

воспитательная: воспитание информационной культуры.

Тип урока: урок изучения нового материала

Методы обучения: дедуктивно – репродуктивный, индуктивно – репродуктивный

Оборудование: персональный компьютер (ПК) учителя, мультимедийный проектор, экран; презентация «Автоматическая обработка информации»

Литература:

1. И.Г. Семакин, Е.К. Хеннер., Т.Ю.Шейна Информатика. Базовый уровень. 10 класс.– М.: БИНОМ. Лаборатория знаний, 2015.

2. И.Г. Семакин, Е.К. Хеннер. Шеина Т.Ю. Практикум по информатике и ИКТ для 10-11 классов. Базовый уровень.– М.: БИНОМ. Лаборатория знаний, 2011.

3. Информатика. Задачник-практикум в 2 т. под ред. И.Г. Семакина, Е.К. Хеннера.– М.: БИНОМ. Лаборатория знаний, 2011.

4. Информатика и ИКТ. Базовый уровень. 10-11 класс: методическое пособие/ И.Г. Семакин, Е.К. Хеннер.–2-е изд. – М.: БИНОМ. Лаборатория знаний, 2011.

5. И.Н.Фалина, Е.Л.Радченко «Изучение машины Поста в школьном курсе информатики» (http://xn--80aawbkjgiswr.xn--1-btbl6aqcj8hc.xn--p1ai/articlef.php?ID=200700104)

План урока:

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

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

3. Практическая работа (15 мин).

4. Домашнее задание (2 мин).

5. Итог урока (2 мин).

Ход урока

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

Машина Поста

Теория Алгоритмов

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

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

МАШИНА ТЬЮРИНГА

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

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

МАШИНА ПОСТА

Машина Поста

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

Каретка

Программа

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

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

Машина Поста

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

v

v

v

v

v

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

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

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

• стереть знак в текущей клетке;

• записать знак в пустую текущую клетку.

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

Машина Поста

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

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

Система команд машины Поста

Команда

Действие

n ← m

Сдвиг каретки на шаг влево и переход к выполнению команды с номером m

n → m

n v m

Сдвиг каретки на шаг вправо и переход к выполнению команды с номером m

Запись метки в текущую пустую клетку и переход к выполнению команды с номером m

n ↕ m

Стирание метки в текущей клетке и переход к выполнению команды с номером m

n !

Остановка выполнения программы

n ? m,k

Переход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k

Машина Поста

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

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

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

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

Машина Поста

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

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

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

Машина Поста

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

Задание 1

• Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.
• Пояснение : выделенная цифра, например  1 , означает, что эту ячейку каретка обозревает в начальный момент времени.

Ответ: Выделенная цифра показывает, на какой ячейке остановится машина.

a) 1) 11000000 1

    2) 1100000 1

b) 1) 11001 0 1

     2) 100 0 1

РЕШЕНИЕ:

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

Задание 2

Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

ОТВЕТ:

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

Задание 3

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

ОТВЕТ:

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

§ 10, № 1, 2

№ 1: Останется 1 и последняя метка

ОТВЕТЫ: