Ученики на Учителя.com


Конспект урока "Уточнение понятия алгоритма. Машина Поста" 10 класс

1
Конспект урока
с применением проблемно-модульной технологии
по теме «Уточнение понятия алгоритма. Машина Поста»
Учитель: Гурова Алла Александровна
Класс: 10
Цели урока:
1. Образовательные:
• усвоение определений понятия «алгоритм»;
• формирование навыков работы с машиной Поста;
• формирование навыка использовать имитатор машины Поста для решения возникшей
проблемы.
2. Воспитательные:
• воспитание умения находить связь учебной науки с жизненными ситуациями;
• побуждение желания объяснить происходящее;
• воспитание у учащихся творчества.
3. Развивающие:
• развитие логического мышления;
• формирование умений наблюдать.
Задачи урока:
• ознакомление с формальным определением понятия «алгоритм»;
• ознакомление с возможностями и структурой машины Поста;
• ознакомление с системой команд для машины Поста;
• формирование первичных навыков работы с машиной Поста;
• формирование навыка использовать имитатор машины Поста для решения возникшей
проблемы.
Тип урока: изучение нового материала.
Методы и технологии: проблемно-модульная технология.
Формы: сочетание фронтальных и индивидуальных форм.
Виды деятельности: изложение нового материала учителем, коллективное обсуждение
результата выполнения программы для машины Поста, индивидуальная практическая работа с
программами для машины Поста с использованием имитатора машины Поста.
Приемы: наглядный, словесный и практический.
Технические средства:
- компьютеры;
- мультимедийный проектор.
2
План урока:
1. Организационный этап (2 мин).
2. Усвоение новых знаний (15 мин).
3. Закрепление нового материала (24 мин).
4. Информация о домашнем задании (2 мин).
5. Итог урока (2 мин).
Ход урока
1 этап Организационный
Учитель озвучивает цели и задачи урока.
2 этап Усвоение новых знаний
Машина Поста (проще машины Тьюринга) была предложена также в качестве уточнения
понятия алгоритма.
Определение по Посту (формальное).
Алгоритм – это программа для машины Поста, приводящая к решению
поставленной задачи.
Гипотеза Поста:
Всякий алгоритм представим в форме Машины Поста.
Машины Поста и Тьюринга эквивалентны по своим возможностям.
В машине Поста в ячейках бесконечной ленты можно записывать только два знака: 0 и 1.
Это ограничение не влияет на её универсальность, так как любой алфавит может быть
закодирован двумя знаками.
Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:
• умеет двигаться вперед, назад и стоять на месте;
• умеет читать содержимое, стирать и записывать 0 или 1;
• управляется программой.
Состоянию машины Поста соответствует одна из шести следующих команд:
1. Записать 1, перейти к i-ой строке программы.
2. Записать 0, перейти к i-ой строке программы.
3. Выполнить сдвиг влево, перейти к i-ой строке программы.
4. Выполнить сдвиг вправо, перейти к i-ой строке программы.
5. Останов.
6. Если 0, то перейти к i-ой строке программы, иначе перейти к j-ой строке
программы.
Состояние машины – это состояние ленты и положение каретки.
К аварийной остановке машины могут привести следующие (недопустимые)
действия:
• попытка записать 1 (метку) в заполненную ячейку;
• попытка стереть метку в пустой ячейке;
• уход каретки в бесконечность (зацикливание).
Команды машины будем обозначать следующим образом:
3
→ а - шаг вправо, перейти к строке с номером а;
← а - шаг влево, перейти к строке с номером а;
V a - записать метку, перейти к строке с номером а;
X a - стереть метку, перейти к строке с номером а;
? a; b - просмотреть ячейку; если в ячейке находится 0, то перейти к строке
с номером а, иначе – к строке с номером b;
! - останов.
Проводится обсуждение программы для машины Поста.
На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором
расстоянии слева от ячейки. Необходимо подвести каретку к ячейке, стереть метку и
оставить каретку слева от неё.
Решение:
Программа для машины Поста:
1. → 2
2. ? 1; 3
3. X 4
4. ← 5
5. !
3 этап Закрепление нового материала
Учащимся предлагается выполнить индивидуальную практическую работу с
программами для машины Поста с использованием имитатора машины Поста.
Каждый учащийся получает распечатку-задание и приступает к теоретическому
анализу предложенных программ. Получив результат, учащиеся проверяют практически
свои выводы на имитаторе машины Поста. При обнаружении проблем пытаются
самостоятельно решить их.
Задание 1. Выяснить, применимы ли программы к заданным состояниям машины Поста,
указать результат работы машины Поста для каждого состояния.
a) Начальное состояние ленты:
1) 1110011
2) 1110111
3) 1001011
1. ? 3; 2
2. 1
3. 4
4. ? 6; 5
5. 1
6. 7
7. ? 8; 9
8. !
9. 4
b) Начальное состояние ленты:
1) 111101
2) 111011
3) 111111
4
1. ? 4; 2
2. Х 3
3. 9
4. V 5
5. 6
6. ? 7; 6
7. V 8
8. 9
9. ? 11; 10
10. 1
11. !
c) Начальное состояние ленты:
1) 1011
2) 11001
3) 10101
1. ? 4; 2
2. Х 3
3. 6
4. V 5
5. 1
6. ? 4; 7
7. 8
8. ? 9; 11
9. V 10
10. 1
11. !
Ответы:
a) 1) 1110011000
2) зацикливание
3) 1001011000
b) 1) зацикливание
2) 010011
3) 01010110
c) 1) зацикливание (…111)
2) зацикливание (…1111001)
3) зацикливание (1010111…)
Задание 2. Определить состояние, в котором окажется машина Поста в результате
выполнения программы при заданном начальном состоянии ленты.
Пояснение: выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в
начальный момент времени.
a) Начальное состояние ленты:
1) 1111101
2) 111111
1. ? 2; 4
5
2. V 3
3. !
4. X 5
5. 6
6. ? 8; 7
7. 6
8. 1
b) Начальное состояние ленты:
1) 111111
2) 11101
3) 101111
1. ? 2; 3
2. !
3. 4
4. ? 7; 5
5. X 6
6. 9
7. V 8
8. 2
9. ? 12; 10
10. X 11
11. 1
12. V 13
13. 1
Решение. Выделенная цифра показывает, на какой ячейке остановится машина.
a) 1) 110000001
2) 11000001
b) 1) 1100101
2) 10001
3) 111111
4 этап Информация о домашнем задании
Домашнее задание: Составить программы для машины Поста.
1. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка
находится либо слева от массива, либо над одной из ячеек самого массива.
2. Даны два массива меток, которые находятся на некотором расстоянии друг от
друга. Требуется соединить их в один массив. Каретка находится над крайней
левой меткой первого массива.
5 этап Итог урока
Подведение итогов работы.
Скачать материал

Информатика - еще материалы к урокам: