Патреева Я.Т. Методическая разработка урока по учебной дисциплине ЕН.02 «Дискретная математика с элементами математической логики» по теме «Применение теории графов в решении прикладных задач»
Библиографическое описание: Патреева Я.Т. Методическая разработка урока по учебной дисциплине ЕН.02 «Дискретная математика с элементами математической логики» по теме «Применение теории графов в решении прикладных задач» // Образовательный альманах. 2023. № 7 (69). Часть 2. URL: https://f.almanah.su/2023/69-2.pdf.
Тип урока: закрепление полученных знаний и навыков.
Технологии урока – игровая деятельность.
Форма организации – работа в группах.
Методы обучения – словесный, проблемный, проектный, наглядный.
Методы контроля – фронтальный групповой опрос, фронтальный индивидуальный опрос, самоконтроль.
Место урока в рабочей программе учебной дисциплины: урок по теме «Применение теории графов в решении прикладных задач» входит в систему уроков по теме «Элементы теории графов».
Продолжительность урока – 45 минут.
Цель урока – научиться применять элементы теории графов на практике
Задачи урока:
Образовательная – систематизировать знания и умения по теме «Элементы теории графов»: определение графа и его элементов, виды графов, свойства графов.
Развивающая – развивать творческую и мыслительную деятельность обучающихся.
Воспитательная – способствовать развитию интереса к учебной дисциплине «Дискретная математика с элементами математической логики», способствовать формированию нравственных качеств личности (уверенность в себе, терпимость к недостаткам других, коммуникабельности).
Формируемые умения:
· применять логические операции, формулы логики, законы алгебры логики;
· формулировать задачи логического характера и применять средства математической логики для их решения.
Формируемые знания:
· основные принципы математической логики, теории множеств и теории алгоритмов;
· основные принципы теории множеств.
Формируемые компетенции:
ОК1. Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам.
ОК2. Осуществлять поиск, анализ и интерпретацию информации, необходимой для выполнения задач профессиональной деятельности
ОК4. Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.
Ход урока:
1 этап. Организационный этап. Постановка цели и задач урока. Мотивация учебной деятельности учащихся.
Преподаватель приветствует обучающихся, объявляет тему урока и формулирует его цель. Делит группу на 2 команды с равным количеством участников.
2 этап. Первичное закрепление в знакомой ситуации (типовые), в изменённой ситуации (конструктивные).
Преподаватель проводит устный опрос обучающихся. Контрольные вопросы командам:
· Дайте определение графа, определение графа с кратными ребрами и петлями, определение орграфа.
· Назовите характеристики и элементы графов, способы задания графа (аналитический, рисунком, матрицей).
· Дайте определение Эйлерова графа, теорема Эйлера.
За каждый верный ответ команда получает 1 балл.
3 этап. Творческое применение и добывание знаний в новой ситуации.
Преподаватель представляет задачу №1 для команд:
«Перед вами 2 схемы авиасообщения между островами (рис.1. и рис.2), которые пилот должен облететь за некоторый промежуток времени. За каждый перелет он получает 10 очков, за повторный перелет по тому же пути снимается 5 очков. За непосещение каждого из островов взимается штраф 10 очков, а непосещение пути – 5 очков. Без необходимости пилот не может несколько раз прилетать на один и тот же остров. Но при возможности должен стараться пролететь по каждому из путей для проверки связи, если в этом есть необходимость. «Повторный» полет возможен не сразу. Если между островами существует два разных пути, каждый из них засчитывается как самостоятельный. Вылететь пилот может с любого острова. Может ли пилот выполнить задание без штрафов? Если без штрафов не обойтись, предложите оптимальный путь».
Контрольные вопросы командам:
· Каким графом обозначена схема перелета?
· Какое свойство графа отвечает за максимальный набор пилотом очков?
Решение. Задача сводится к определению эйлерова графа, ведь нам выгодно пройти по каждому из 7 ребер только 1 раз. По признаку степеней вершин схема №1 (рис.1) – эйлеров граф. Возможная эйлерова цепь: 1-2-3-4-2-4-5-2. Максимальное количество очков: 70. Схема № 2 (рис.2) – не эйлеров граф. Поэтому придется жертвовать штрафами. Самый оптимальный путь за вычетом штрафов 4-3-5-2-5-3-2-1-2 65 очков.
Рис.1. Схема № 1
Рис.2 Схема № 2
Команды решают задачу №1 и записывают ответы в табл.1. (приложение 1). Таблица с записанными ответами сдается преподавателю на проверку.
Команды обсуждают варианты решения задачи.
Преподаватель представляет задачу №2 для команд 1 и 2:
«На рисунке (рис.3, рис. 4): на рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. Двигаться можно только в направлении по стрелке. Сколько существует различных путей из города А в город К?»
Рис.3. Схема №3 Рис.4. Схема №4
Контрольные вопросы командам:
· Каким графом обозначена данная схема?
· Каковы свойства этого графа?
Решение: перед нами: ориентированный граф, его вершины – города, а ребра – дороги с учетом направления. Схема № 3: существуют 13 путей. Схема №4: 12 путей.
Каждая команда решает задачу №2 и записывают ответ в табл.1 (приложение 1). Таблица с записанными ответами сдается преподавателю на проверку.
Преподаватель представляет задачу №3 для команд:
«Пусть вес ребра – это стоимость в у.е. транспорта между пунктами-вершинами. Найти самый дешевый пусть из вершины 0 в вершину 8 на схеме №5 (рис.5) и из вершины 1 в вершину 8 на схеме №6 (рис.6).»
Рис. 5. Схема № 5
Рис. 6. Схема № 6
Контрольные вопросы командам: в чем отличие графов в задачах №2 и №3?
Решение: перед нами взвешенный ориентированный граф. Нужно из всех путей найти тот, который имеет наименьшую сумму весов ребер. Схема №5: 8. Схема №6: 8.
Каждая команда решает задачу №3 и записывают ответ в табл.1 (приложение 1). Таблица с записанными ответами сдается преподавателю на проверку.
4 этап. Рефлексия (подведение итогов занятия).
Преподаватель проверяет решенные задачи, выставляет командам баллы. Правильный ответ и обоснованное решение задачи – 3 баллы, правильный ответ с незначительными недостатками в теоретической части – 2 балла, ответ верный, но решение не обосновано - 1 балл; неправильный ответ – 0 баллов. За внеочередные ответы - штраф 0,5 балла.
Побеждает команда, набравшая большее количество баллов. При одинаковом количестве баллов объявляется ничья.
На этапе рефлексии каждый участник заполняет таблицу 2 (Приложение 2).