Графы: понятия, виды и алгоритмы
Цели и задачи
- Цель: к концу урока научиться распознавать основные виды графов, определять их свойства и выбирать алгоритм решения задачи по заданным условиям.
- Сформировать представление о вершинах, рёбрах, путях, степени вершины и записи графа $G=(V,E)$.
- Развивать умение анализировать граф, обосновывать выбор алгоритма и предлагать способ программной проверки результата.
- Воспитывать ответственное отношение к точности рассуждений и интерес к применению графовых моделей в будущей профессиональной деятельности.
Планируемые результаты
Личностные
- Осознавать практическую значимость графов для моделирования сетей, маршрутов и зависимостей.
- Проявлять самостоятельность при выборе способа решения и готовность аргументировать позицию.
Метапредметные
- Анализировать условие, выделять вершины, рёбра и свойства графа.
- Планировать решение, проверять результат и сотрудничать при исследовании графовой модели.
- Формулировать алгоритм и описывать способ его программной проверки.
Предметные
- Знать определения графа, вершины, ребра, пути, степени вершины.
- Различать ориентированные, неориентированные, взвешенные, полные, деревья и ациклические графы.
- Уметь выбирать поиск в ширину, алгоритм Дейкстры или динамический подсчёт путей в DAG.
Универсальные учебные действия (УУД)
Личностные УУД
- Самоопределение через связь темы с алгоритмами, программированием и задачами вузовского уровня.
- Смыслообразование: понимание графа как модели объектов и связей между ними.
Регулятивные УУД
- Ставить цель исследования, планировать последовательность действий.
- Осуществлять самопроверку, находить и корректировать ошибки в классификации и подсчётах.
Познавательные УУД
- Сравнивать виды графов, устанавливать признаки и ограничения алгоритмов.
- Моделировать задачу графом, выполнять топологическую сортировку и динамический подсчёт путей.
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Коммуникативные УУД
- Распределять роли в паре или группе, задавать уточняющие вопросы.
- Аргументированно представлять решение и учитывать обоснованные предложения одноклассников.
Ход урока
- Этап 1. Организационный момент и мотивация (3 мин). Кратко: учитель предлагает рассмотреть схему связей и формулирует проблемный вопрос о поиске кратчайшего пути; ученик определяет, какие объекты и связи можно представить графом.
- Этап 2. Актуализация знаний (5 мин). Кратко: учитель организует работу в парах по распознаванию объектов на схеме и фиксирует начальные представления; ученик называет вершины, рёбра и возможные пути.
- Этап 3. Постановка проблемы (4 мин). Кратко: учитель предлагает сравнить неориентированный, ориентированный и взвешенный варианты одной сети; ученик выявляет затруднение и формулирует цель исследования — выбрать способ анализа по свойствам графа.
- Этап 4. Открытие нового знания (13 мин). Кратко: учитель направляет исследование определений графа $G=(V,E)$, степени вершины, пути, полного графа, дерева, DAG и взвешенного графа; ученик в мини-группах составляет краткую классификацию и обосновывает признаки. Для поиска кратчайшего пути сопоставляются поиск в ширину для графа без весов и алгоритм Дейкстры при неотрицательных весах.
- Этап 5. Первичное закрепление (7 мин). Кратко: учитель предлагает разобрать ориентированный ациклический граф с рёбрами $A\to B$, $A\to C$, $B\to C$, $B\to D$, $C\to D$, $C\to E$, $D\to E$; ученик записывает топологическую сортировку и находит число путей из $A$ в $E$ динамическим подсчётом.
- Этап 6. Самостоятельная работа (9 мин). Кратко: учитель предлагает задания базового и повышенного уровня: классифицировать граф, определить степени вершин, выбрать алгоритм и объяснить выбор; ученик решает индивидуально, выполняет самопроверку по ключевым признакам и формулирует способ программной проверки.
- Этап 7. Рефлексия и домашнее задание (4 мин). Кратко: учитель проводит краткий билет на выход по вопросам о выборе алгоритма и свойствах DAG; ученик фиксирует освоенное, затруднение и вариант применения графов. Учитель сообщает домашнее задание.
Домашнее задание
- Минимум: составить словарь из пяти понятий темы и классифицировать три предложенные схемы как ориентированные или неориентированные.
- Базовый: для заданного DAG с вершинами $A$, $B$, $C$, $D$, $E$ записать одну топологическую сортировку и вычислить число путей из $A$ в $E$.
- Повышенный: разработать алгоритм или небольшую программу для подсчёта путей в DAG и описать, почему ацикличность гарантирует завершение вычислений.
