Уточнение понятия алгоритма. Машина Тьюринга

Разделы: Информатика

Тип урока урок изучения и первичного закрепления новых знаний

Цель урока уточнение понятия алгоритма; знакомство с машиной Тьюринга как уточнением понятия алгоритма

Задачи урока

Образовательные:

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

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

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

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

  • развивать алгоритмическое, наглядно-образное мышление;
  • формировать культуру познавательной деятельности;
  • формировать культуру коллективной деятельности, воспитывать чувство ответственности за результаты своего труда, используемые другими людьми;
  • развивать навыки самостоятельной деятельности, упорство в достижении цели.

Знания, умения, навыки и качества, которые приобретут и закрепят ученики в ходе урока:

  • закрепят и расширят понятие алгоритма;
  • усвоят понятие алгоритмически неразрешимой задачи;
  • приобретут знания о составе машины Тьюринга, принципах её работы;
  • приобретут навыки построения машин Тьюринга для решения простейших задач.

Необходимое оборудование и материалы:

Ход и содержание урока

Интерактивная поддержка Действия участников урока
Слайд 1 - заставка Презентация используется на протяжении всего урока.
Слайд 2 - использование возможностей интерактивной доски (инструмент Перо):

1 учащийся от каждой группы (на усмотрение лидеров) записывает на доске выбранный алфавит и способ его двоичного кодирования

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

На предыдущем уроке класс разбивается на группы (3 группы по 4-5 человек). Группы работают под руководством лидеров. Каждой группе выдаётся Рабочий лист (формат А4), который по мере выполнения заданий заполняет лидер.

Задание: Докажите, что любой алфавит можно заменить двухбуквенным алфавитом. Приведите примеры.

Выслушивается отчёт лидеров групп по выполнению задания. Обсуждаются вопросы, возникшие при выполнении работы. Проводится взаимопроверка домашнего задания, итоги фиксируются в Рабочем листе.

Слайды 3-5 - постановка проблемной задачи, демонстрация материала II. Подготовка учащихся к усвоению нового материала: сообщение темы и целей урока, постановка проблемной задачи

1. Беседа с учащимися об известных им различных определениях алгоритма.

2. Постановка проблемы: возможно ли построение алгоритма, позволяющего сконструировать машину для перевода чисел из унарной системы счисления в десятичную? Какие средства для этого могут быть использованы?
Слайды 6-10 - демонстрация изучаемого нового материала III. Изучение нового материала

Сообщение нового материала
Слайд 11 - демонстрация примера построения машины Тьюринга

Используются анимационные возможности MS PowerPoint - демонстрируется заранее смоделированная реализация задачи

 IV. Первичная проверка усвоения знаний

Демонстрация примера построения машины Тьюринга
Слайды 12-13 - демонстрация задач на реализацию алгоритмов с помощью машин Тьюринга, моделирование решений с использованием возможностей интерактивной доски; демонстрация задач для самопроверки знаний учащихся (инструменты Перо, Умное перо, Указатель, Ластик) V. Первичное закрепление знаний

Предлагаются задачи на реализацию алгоритмов с помощью машин Тьюринга. После обсуждения задач в группах учащиеся предлагают свои решения задач. Решения моделируются с использованием возможностей интерактивной доски.

Схема решения задач на реализацию алгоритмов для машины Тьюринга средствами StarBoard может быть такой:

  • с помощью инструмента Перо вписать символы входного слова в ячейки ленты (ввод данных);
  • с помощью инструмента Умное перо изобразить рамку квадратной формы (по форме ячейки) яркого цвета, обрамляющую ту ячейку ленты, которую должен обозревать автомат на первом шаге алгоритма;
  • последовательно выполнять команды алгоритма:
  • переместить рамку с помощью инструмента Указатель влево или вправо, в зависимости от выполняемой команды (таким образом мы фактически моделируем перемещение каретки чтения/записи вдоль ленты машины Тьюринга);
  • с помощью инструмента Ластик удалить символ, записанный в обозреваемой ячейке (при этом объект, созданный с помощью инструмента Умное перо (рамка-автомат), остаётся неизменным);
  • если не требуется оставить обозреваемую ячейку ленты пустой, вписать в неё с помощью инструмента Перо нужный символ;
  • закончить выполнение алгоритма по достижении клетки останова.
Слайд 14 - демонстрация задач для самопроверки знаний учащихся

Слайд 15 - демонстрация решения проблемной задачи, поставленной в начале урока, с использованием возможностей интерактивной доски.

 VI. Контроль и самопроверка знаний

1. Работа в группах на время, фиксирование лидерами групп результатов в Рабочих листах (слайд 14). Поочередно заслушивается решение задач каждой группы, обсуждаются результаты. Подводятся итоги выполненной работы, заполненные рабочие листы передаются учителю.

2. Обсуждение проблемной задачи, поставленной в начале урока (слайд 15).
Слайд 16 - демонстрация итогов урока VII. Подведение итогов урока

1. Формулирование выводов о расширении понятия алгоритма, его формализации

2. Объявление результатов урока (слайд 16)

3. Домашнее задание: придумать задачу и написать для её решения машину Тьюринга

4. Рефлексия:

  • что понравилось на уроке, а что нет?
  • какие знания об алгоритмах вы применяли на уроке?
  • сколько составляющих содержит команда машины Тьюринга?
  • какие затруднения вы испытали при решении задач?

Возможно использование описанного дидактического ресурса и в случае отсутствия интерактивной доски. Презентация демонстрируется с помощью мультимедийного проектора на обычный экран; данные вносятся на слайды в режиме демонстрации манипулятором "мышь" с использованием инструмента Указатель MS Power Point (Ручка, Фломастер или Выделение).

Но в этой ситуации невозможно указать и изменять в процессе реализации алгоритма положение головки автомата, можно просто зачёркивать значение в ячейке ленты и вписывать новое.

Использованные источники и литература.

  1. Касаткин В.Н. Информация, алгоритмы, ЭВМ: Пособие для учителя. - М.: Просвещение, 1991.
  2. Андреева Е.В. Математические основы информатики. Элективный курс: Учебное пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина - 2-е изд., испр. - М.: БИНОМ. Лаборатория Знаний, 2007.
  3. Андреева Е.В. Математические основы информатики. Элективный курс: Методическое пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина -М.: БИНОМ. Лаборатория Знаний, 2007.
  4. Юнина Е.А. Современные образовательные технологии. М., 2006.
  5. Рабочая программа среднего (полного) общего образования по информатике и ИКТ. Профильный уровень. Авторы: Лопушанская Н.Д., Нарзяева И.Ю.
  6. Программная система моделирования работы машины Тьюринга http://www.loonies.narod.ru/tmr.htm