Урок по теме: Составление алгоритмов решения задач для управления машиной Поста

Практическая работа «Составление алгоритмов решения задач для управления машиной Поста» -

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

Цели:

Обучающие:

• повторить пройденный материал по теме: "Автоматическая обработка информации";

• научить работать с имитатором машины Поста

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

Развивающие:

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

• развивать умение выделять главное, находить ошибку;

• развивать способности сравнивать, сопоставлять.

Воспитательные:

• воспитывать бережное отношение к компьютеру;

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

• способствовать развитию умения оценивать свои возможности.

Вид занятий (тип урока): практическое занятие.

Методы обучения: выполнение практического задания.

Средства обучения: персональные компьютеры, имитатор машины Поста.

Ход урока:

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

- Здравствуйте! Все готовы к уроку?

- Садитесь. Кто сегодня дежурный? Кто отсутствует на уроке?

2. Актуализация знаний.

Проверка домашнего задания.

3. Сообщение темы и цели урока.

- Сегодня мы с вами поработаем за компьютерами. Прошу занять свои места. И открыть имитатор машины Поста. Сегодня будем разбирать задачи.

4. Практическая работа.

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

Команда

Действие

n ← m

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

n → m

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

n v m

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

n ↕ m

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

n !

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

n ? m, k

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

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

- А сейчас давайте, рассмотрим один пример вместе. Рассмотрим программу:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две - единицу, и т.д. Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:

На доске вместе с учениками разбирается пример.

1 → 2

2 ? 1;3

3 ←4

4 V 5

5 !

- Исходное состояние:

v

v

v

v

↑

- Результат:

v

v

v

v

v

↑

- Всем понятно решение этого примера?

Задачи для самостоятельной работы:

1. Пусть задано исходное состояние головки и требуется на пустой ленте написать две метки: одну в секцию под головкой, вторую справа от нее.

2. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

Решение №1:

1. 1 v 2

2. 2 → 3

3. 3 v 4

4. 4 !

↑

v

↑

v

↑

v

v

↑

Решение № 2:

1. → 2

2. ? 3, 1

3. → 4

4. ? 5, 6

5. !

6. ← 7

7. v 1

Пример программы, которая не применима ни к одному состоянию машины Поста:

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

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

Программа для машины Поста:

Пояснения к условиям задач

1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.

2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длиныn.

3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: nподряд идущих меток будем обозначать 1n, а m пустых ячеек - 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.

К примеру, запись "12012" будет соответствовать записи "11011" на ленте.

4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.

1. Применимость программ. Определение результата выполнения программ

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

Ответы:

a) 1) 1110011000

2) зацикливание

3) 1001011000

b) 1) зацикливание

2) 010011

3) 01010110

c) 1) зацикливание (…111)

2) зацикливание (…1111001)

3) зацикливание (1010111…)