Методическая разработка урока по теме Формализация понятия алгоритма. Машина Тьюринга по учебной дисциплине ОП.03 Теория алгоритмов по специальности СПО 09.02.07 Информационные системы и программирование

Автор: Шелковникова Ольга Евгеньевна

Организация: ГБПОУ Салаватский индустриальный колледж

Населенный пункт: Республика Башкортостан, г. Салават

Целью данной работы является оказание методической помощи преподавателям, при изучении формальных конструкций алгоритмов и предназначена для обучения студентов специальности СПО 09.02.07 Информационные системы и программирование

В данной работе представлен урок открытия нового знания в формате дистанционного обучения, длительностью 90 минут на базе платформы ZOOM.US, групповой чата приложения Whatsapp, электронных файлообменников

Методическая разработка содержит подробный конспект урока с иллюстрациями, технологическую карту урока, электронное сопровождение.

Данная разработка была успешно использована при проведении занятий в группах ГБПОУ Салаватский индустриальный колледж.

Для проведения урока по представленной разработке необходимо полное обеспечение обучающихся и преподавателя персональным компьютером (ноутбук, планшет, телефон) с выходом в сеть Интернет и следующим программным обеспечением: Браузер для работы в сети Интернет, ZOOM, MS Office, Программа-тренажер «Машина Тьюринга» К.Ю. Полякова

Содержание

 

Краткая характеристика темы
Структура урока
Дидактическое и материально-техническое оснащение урока
Конспект урока
Список использованных источников
Приложение А Технологическая карта урока
Приложение Б Электронное сопровождение. Презентация «Формализация понятия алгоритма.ppt»
Приложение В Электронное сопровождение. Программа-тренажер «Машина Тьюринга» К.Ю. Полякова

 

Краткая характеристика темы

 

Представленная тема занятия «Формализация понятия алгоритма. Машина Тьюринга» входит в состав Темы 1.1 «Теоретические основы алгоритмизации» раздела 1 «Основные понятия теории алгоритмов» и направлена на формирование первичных, базовых понятий алгоритмизации.

Под алгоритмом в математике понимают «точное предписание, задающее вычислительный процесс, ведущий от начальных данных, которые могут варьироваться, к искомому результату»

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

После того, как в 30-е годы прошлого века была доказана алгоритмическая неразрешимость некоторых задач в разных разделах математики, возникла совершенно новая ситуация. До тех пор, пока ученые верили в возможность построения алгоритмов для всех поставленных задач, не было повода уточнять интуитивное понятие алгоритма. Доказательство существования алгоритмически неразрешимых проблем означало, что существуют классы задач, для решения которых алгоритм не просто не найден, а его не будет найдено никогда. В отличие от конкретных алгоритмов, доказательство алгоритмической неразрешимости, т.е. доказательство невозможности, в котором содержалось бы высказывание обо всех мыслимых алгоритмах, потребовало формального уточнения понятия «алгоритм». Не имея формального определения, невозможно говорить обо всех мыслимых алгоритмах.

Основная задача изучения учебного материала данной темы – это не просто изучение базовых формальных конструкций алгоритма, а формирование у будущих специалистов теоретической базы практического применения теории алгоритмов при программировании.

В данной теме необходимо рассмотреть Алгоритмические машины, Функции вычислимые алгоритмом, Исчисления. На примере конкретного эмулятора показать принципы построения алгоритмов для Машины Тьюринга

Изложение материала требует предельной аккуратности в определении терминов, наглядности изложения.

Результатом освоения темы учебной дисциплины является формирование общих и профессиональных компетенций:

ОК 01. Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам.

ОК 02. Осуществлять поиск, анализ и интерпретацию информации, необходимой для выполнения задач профессиональной деятельности.

ОК 03. Планировать и реализовывать собственное профессиональное и личностное развитие.

ОК 04. Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.

ОК 05. Осуществлять устную и письменную коммуникацию на государственном языке с учетом особенностей социального и культурного контекста.

ОК 09. Использовать информационные технологии в профессиональной деятельности.

ОК 10. Планировать предпринимательскую деятельность в профессиональной сфере.

ПК 1.1. Формировать алгоритмы разработки программных модулей в соответствии с техническим заданием.

ПК 1.2. Разрабатывать программные модули в соответствии с техническим заданием.

Структура урока

 

Тип урока Урок открытия нового знания с применением технологий дистанционного обучения

 

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

• ознакомится с понятием «формальное определение алгоритма»;
• выделить основные типы формальных алгоритмов: алгоритмические машины, функции вычислимые алгоритмом, исчисления;
• рассмотреть алгоритмические машины на примере машины Тьюринга;

 

Деятельностная цель Формирование умений реализации новых способов действия:

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

 

Этапы урока

 

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

Провести перекличку в групповом чате приложения Whatsapp и пригласить по ссылке в онлайн конференцию на базе облачной платформы ZOOM.US для проведения онлайн занятия

1. Мотивирование к учебной деятельности

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

Цель этапа Выработка на личностно значимом уровне внутренней готовности выполнения нормативных требований учебной деятельности

 

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

Повторение изученного материала, необходимого для «открытия нового знания», каждого обучающегося. Для этого:

• рассмотреть интуитивное определение понятия «алгоритм»;
• определить алгоритм как отображение (функция)

Цель этапа Подготовка мышления обучающихся, организация осознания ими внутренней потребности к построению учебных действий

 

1. Открытие нового знания

Активизация знания учащихся, создание проблемной ситуации

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

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

Цель этапа Постановка целей учебной деятельности и на этой основе – выбор способа и средств их реализации

1. Физкультурная пауза

Для предупреждения и снятия умственного и зрительного утомления преподаватель предлагает выполнить комплекс упражнений

 

1. Открытие нового знания Открытие нового знания (продолжение)

• ознакомится с устройством Машины Тьюринга и алгоритмом работы;
• рассмотреть эмулятор Машины Тьюринга: Программу-тренажер «Машина Тьюринга» К.Ю. Полякова

Цель этапа Построение учащимися нового способа действий и формирование умений его применять как при решении задачи, вызвавшей затруднение, так и при решении задач такого класса или типа вообще

 

1. Первичное закрепление

Устанавливается осознанность ситуации, решение типового задания

• построить алгоритм для Машины Тьюренга по заданию

Цель этапа Усвоение обучающимися нового способа действия при решении типовых задач. Интериоризация нового способа действия и исполнительская рефлексия достижения цели пробного учебного действия, применение нового знания в типовых заданиях

 

1. Домашнее задание

Организуется деятельность по применению новых знаний

• предлагаются типовые задания разного уровня сложности

Цель этапа Выявление границы применимости нового знания и использование его в системе изученных ранее знаний, повторение учебного содержания, необходимого для обеспечения содержательной непрерывности, включение нового способа действий в систему знаний

 

1. Обратная связь от обучающегося

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

• обработав электронные письма с выполненным заданием, преподаватель к назначенному сроку отправляет в групповой чат приложения Whatsapp правильную таблицу состояний Машины Тьюринга и комментирует выполненные работы

Цель этапа отслеживание прогресса обучающихся относительно достижения результатов и личностного развития

 

1. Рефлексия деятельности

Организуется рефлексия. Осуществляется самопроверка собственной учебной деятельности

• сделать выводы о выполненном задании;
• сравнить полученные результаты по предоставленным ответам.

Цель этапа Самооценивание обучающимися результатов своей учебной деятельности, осознание метода построения и границ применения нового способа действия

 

Дидактическое и материально-техническое оснащение урока

 

Оборудование компьютер, глобальная сеть Internet, видеокамера, наушники, микрофон

Программное обеспечение Браузер для работы в сети Интернет, ZOOM, MS Office, Программа-тренажер «Машина Тьюринга» К.Ю. Полякова

Электронное обеспечение презентация «Формализация понятия алгоритма.ppt»

 

Конспект урока

 

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

Перед занятием преподаватель настраивает время проведения видеоконференции на базе платформы ZOOM.US и отправляет приглашение в групповой чат приложения Whatsapp

Начинает занятие преподаватель приветствием и просьбой отметить свое присутствие в чате по форме: «Фамилия+», приглашает перейти в ZOOM и начинает видеоконференцию онлайн.

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

 

1. Мотивирование к учебной деятельности

Начальную мотивацию учебной деятельности преподаватель осуществляет, открыв рисунок 1 в режиме демонстрации экрана в Zoom и отравив его в чат, обращаясь к студентам со словами:

Перед вами иерархическая структура создания базовых языков программирования. Что объединяет все эти языки программирования? Что в первую очередь надо знать чтобы писать программы на этих языках программирования?

Основой всех языков программирования является алгоритмический язык – это формальный язык, используемый для записи, реализации и изучения алгоритмов

Исторически термин «алгоритм» произошел от фамилии узбекского математика IX века Мухаммада ибн Муса ал-Хорезми, который впервые сформулировал правила четырех основных арифметических действий. Поначалу именно эти правила назывались алгоритмами, но затем термин получил дальнейшее развитие в первую очередь в математике - алгоритмом стал называться любой способ вычислений, единый для некоторого класса исходных данных, например, нахождение производной функции. Термин «алгоритм» стал общеупотребимым и получил интуитивное определение.

Алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса.

Однако появились задачи, для которых невозможно было построить алгоритм. Но и нельзя было доказать невозможность алгоритмического решения задачи. Следовательно, возникла проблема: построить формальное определение алгоритма.

Запишем тему занятия

Рисунок 1 – Иерархическая структура базовых языков программирования

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

Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D в R, рисунок 2

 

Рисунок 2 – Алгоритм как отображение (функция)

 

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

Определение. Алгоритм называется частичным алгоритмом, если получен результат только для некоторых d Є D, и полным алгоритмом, если алгоритм получает правильный результат для всех d Є D

В теории алгоритмов были введены различные формальные определения алгоритма и все они эквивалентны в смысле их равномощности

Алгоритм – некоторый точно определенный инструмент, при помощи которого можно конструировать любые интуитивно понятные порождающие (вычисляющие) и распознающие (разрешающие) процедуры.

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

Алгоритм – это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи.

Алгоритм – это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя.

Алгоритм – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность» (Д. Кнут)

Алгоритм – это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (А. Колмогоров)

Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату (А. Марков)

Алгоритм – точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа (Философский словарь / Под ред. Розенталя)

Рассказывая о понятии алгоритма преподаватель открывает рисунок 2, демонстрирующий теоретико-множественный подход, а затем выводит на экран последовательно представленные выше определения, предлагая их зачитать вслух используя связь ВКС ZOOM. Для удобства представления на экране и организации анимации преподаватель запускает презентацию «Формализация понятия алгоритма.ppt», приложение Б (слайды 2,3).

 

1. Открытие нового знания

За 30–40 годы ХХ столетия интенсивного поиска универсального уточнения алгоритма было предложено примерно двадцать формальных конструкций алгоритмов, которые условно можно разбить на три типа:

1. • Алгоритмические машины (АМ).
   • Функции вычислимые алгоритмом
   • Исчисления.

Далее преподаватель отправляет теоретическую часть в групповой чат, открывает информацию в ZOOM и кратко комментирует.

Рассмотрим более подробно формальные конструкции алгоритмов.

Алгоритмические машины имеют один процессор, выполняющий небольшой набор очень примитивных действий, простую структуру данных (структуру памяти) в виде бесконечной ленты, простую логику (правила) управления процессором. В этом случае алгоритм представляется набором правил команд процессора, последовательность выполнения которых управляет состоянием памяти – программой. Основные алгоритмические машины, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов: Машина Тьюринга (1937 г), Машина Поста (1937 г), Нормальный алгоритм (алгорифм) Маркова (НАМ) (1953 г), рисунок 3

 

Рисунок 3 – Алгоритмические машины

 

Функции вычислимые алгоритмом – это рекурсивные функции, где алгоритм рассматривается как целочисленная функция при целочисленных значениях аргументов. Курт Гедель определил алгоритм как последовательность правил построения сложных математических функций из более простых. Более общая формулировка была дана Стивеном Клини, согласно которой все частичные (то есть не обязательно определённые для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными

Рекурсией называется способ задания функции, при котором значение функции при определенном значении аргументов выражается через уже заданные значения функции при других значениях аргументов, рисунок 4.

Полный текст статьи см. в приложении.
 

1. file0.doc.. 518,0 КБ
2. file1.ppt.zip.. 326,0 КБ

Опубликовано: 15.02.2021