Граф - дерево. Длина пути между ребрами графа.

Ход урока

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

   3 мин

   Учитель

   • Приветствие класса: 'Здравствуйте! Сегодня мы переходим к сложным структурам данных'.
   • Озвучивание темы: 'Запишите тему: Граф - дерево. Длина пути'.

   Ученики

   • Подготовка рабочих мест и проверка наличия тетрадей.
   • Запись даты и темы урока в тетрадь.

   Результат

   Учащиеся готовы к уроку, тема зафиксирована в тетрадях.

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

   5 мин

   Учитель

   • Вопрос классу: 'Что такое граф и как он задается в памяти компьютера?'
   • Вопрос классу: 'Чем взвешенный граф отличается от невзвешенного?'

   Ученики

   • Ответ ученика: 'Граф задается матрицей смежности или списком ребер'.
   • Ответ ученика: 'У взвешенного графа на ребрах указаны числа - веса или длины'.

   Результат

   Ученики вспомнили базовые понятия теории графов и способы их представления.

3. 3Изучение нового материала: Деревья

   10 мин

   Учитель

   • Объяснение: 'Дерево — это связный граф без циклов. У него есть корень и листья'.
   • Вопрос: 'Где в информатике мы уже встречали структуру дерева?'
   • Демонстрация файловой системы на доске с выделением узлов и ребер.

   Ученики

   • Ответ ученика: 'В файловой системе компьютера, папки и файлы'.
   • Зарисовка в тетрадь примера дерева с подписью корня, узлов и листьев.

   Результат

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

4. 4Изучение нового материала: Длина пути

   12 мин

   Учитель

   • Объяснение: 'Длина пути — это сумма весов пройденных ребер между вершинами'.
   • Показ алгоритма: 'Чтобы найти кратчайший путь, мы строим дерево всех возможных путей из стартовой вершины'.
   • Совместное построение дерева путей по матрице смежности на доске.

   Ученики

   • Выбор стартовой вершины и пошаговое добавление ветвей к соседним узлам.
   • Подсчет суммы весов на каждой ветви и выбор минимального значения.

   Результат

   Ученики освоили метод построения дерева путей для нахождения кратчайшего маршрута.

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

   10 мин

   Учитель

   • Выдача задания: 'Решите задачу повышенного уровня: найдите кратчайший путь между А и Е, обязательно проходящий через С'.
   • Контроль самостоятельной работы, индивидуальные подсказки.

   Ученики

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

   Результат

   Ученики безошибочно решают задачи на поиск длины пути с дополнительными условиями.

6. 6Рефлексия и подведение итогов

   3 мин

   Учитель

   • Вопрос: 'Какое главное свойство отличает дерево от обычного графа?'
   • Вопрос: 'Почему метод построения дерева путей надежнее, чем просто смотреть на матрицу?'

   Ученики

   • Ответ: 'В дереве нет циклов, нельзя ходить по кругу'.
   • Ответ: 'Дерево перебирает все варианты, мы точно не пропустим скрытый короткий маршрут'.

   Результат

   Ученики осознанно формулируют главные тезисы урока и преимущества изученного алгоритма.

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

   2 мин

   Учитель

   • Объяснение ДЗ: 'Прочитать параграф о деревьях, решить 3 задачи из карточки (формат №4 ОГЭ)'.
   • Прощание: 'Спасибо за урок, вы отлично справились с алгоритмами!'.

   Ученики

   • Запись домашнего задания в дневники.
   • Уточняющие вопросы по формату оформления графов в домашней работе.

   Результат

   Домашнее задание зафиксировано и полностью понятно ученикам.