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


Конспект урока "Машины Тьюринга" 10 класс

Разработала учитель информатики
МАОУ «Гимназия №37» г. Казани
Хуснутдинова Р. Р.
Тема урока: «Машины Тьюринга».
PS: Тема “Машина Тьюринга” изучается в 10-ом классе в рамках темы «Алгоритм. Исполнители
алгоритма».
Цели урока: Изучение понятия алгоритма в виде воображаемой машины
Тьюринга.
Задачи урока:
образовательные:
изучить устройство машины Тьюринга; знать принцип
работы МТ; уметь строить программу для МТ; знать тезис
Тьюринга;
развивающие:
развитие алгоритмического мышления,
способностей к формализации, элементов системного
мышления;
воспитательные:
воспитание чувства ответственности за результаты своего
труда.
Материалы и оборудование к уроку:
ПК; мультимедийный проектор с экраном; презентация «Машина
Тьюринга», маркерная доска; маркер; программа ALGOO2000.
Тип урока:
комбинированный.
Форма проведения урока:
беседа, практикум решения задач.
Метод обучения:
Частично-поисковый (организация активного поиска решения задач
под руководством педагога. Процесс мышления приобретает продуктивный
характер, но при этом поэтапно направляется и контролируется педагогом.)
План урока:
1. Организационный момент
2. Разминка
3. Основные определения. Примеры машин Тьюринга.
4. Решение задач
5. Домашнее задание.
6. Итог урока
Ход урока:
1. Организационный момент (2мин) (Слайд 1):
Приветствие учащихся. Учитель формулирует тему урока. Ставить перед
учащимися задачи, настраивает класс на рабочую атмосферу. Отмечает
отсутствующих. Кратко излагает об А.Тьюринге ( Слайд 3, Слайд 4)
2. Разминка (3-4мин) (Слайд 5)
Решение логической задачи с проверкой у доски. (цель: развитие
логического мышления учащихся и составления алгоритма рассуждений)
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 3
2. умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя
вторую, умножает его на 4. Запишите порядок команд в программе получения из
числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.
Ответ : 22111
3. Основные определения. Примеры машин Тьюринга.(7-8 мин.)
Производится устный опрос учащихся по пройденной теме "Алгоритм.
Исполнители алгоритмов"(цель: повторить пройденный теоретический
материал. Уметь анализировать этапы алгоритма для МТ ) (Слайд 6)
1. Что такое алгоритм и для кого он предназначен?
2. Кто может выступать в роли исполнителя алгоритма?
3. Свойства алгоритма.
4. Основные понятия МТ
5. Продемонстрировать основные свойства алгоритмов на примере МТ
Примеры машин Тьюринга. Решение задач
Теоретическая часть:
Описание Машины Тьюринга (Слайд 7, Слайд 8)
В каждой машине Тьюринга есть две части:
1) неограниченная в обе стороны лента, разделенная на ячейки;
2) автомат (головка для считывания/записи, управляемая программой).
Что умеет воображаемая машина? (Слайд 9, Слайд 10)
За один такт работы она может:
• изменить содержимое обозреваемой ячейки памяти, т.е. заменить
содержащуюся в ней букву алфавита другой;
• совершить сдвиг влево или вправо на одну ячейку или остаться на месте
• изменить свое внутреннее состояние.
4. Решение задач
Практическая часть.
Учитель: Сегодня мы попробуем с помощью машины Тьюринга с имитировать
такое устройство, как КАЛЬКУЛЯТОР. Рассмотрим следующие задачи.
Задача 1 (Слайд 11)
На ленте МТ находится десятичное число. Прибавить к числу 1. Автомат
обозревает некую цифру входного числа.
Решение: составить словесный алгоритм решения задачи и перевести его на
язык МТ.
Словесный алгоритм
Алгоритм МТ
Q0 – поиск последней цифры числа
Если последняя цифра 0, 1, 2, 3, 4, 5, 6, 7,
8, то увеличить последнюю цифру на 1 и
завершить алгоритм,
иначе (если цифра 9), заменить последнюю
цифру на 0, переместиться на следующий
разряд и выполнить аналогичные действия.
Q1 – увеличение цифры на 1
Реализуется задача в ALGO2000 (Слайд 12)
Задача 2 (Слайд 13)
На ленте МТ находится натуральное число N>1. Разработать алгоритм МТ,
которая уменьшала бы заданное число N на 1. Автомат обозревает правую цифру
числа.
Учащиеся аналогичным способом составляют словесный алгоритм и
алгоритм МТ. Реализовывают алгоритм в системе ALGO2000 (Слайд 14)
После решения задач необходимо подвести итог о применении машины Тьюринга
(Слайд 15).
5. Домашнее задание. (Слайд 16)
1. На ленте МТ находится натуральное число N. Разработать алгоритм
машины Тьюринга, который бы умножил заданное число на 2
2. Творческое задание: «Тест Тьюринга»
По завершению урока можно учащимся предложить пройти тест по теоретической
части машины Тьюринга (файл прилагается)
6. Подведение итогов урока + выставление оценок за урок. (Слайд 18).
Литература:
1. Чепкунова Е.Г. «Основы теории кодирования информации и теории
алгоритмов» - Казань – 2009, 60 с.
2. Имитатор машины Тьюринга ALGO 2000
http://www.fayloobmennik.net/1492236
3. Оболочка для создания тестов easyQuizzy
http://easyquizzy.ru/
Скачать материал

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