Алгоритм поиска в ширину — 09.11.2026 — КСП, план урока, Информатика, 11 класс
Создайте свой план урока с ИИ
Создать бесплатно
Предпросмотр
Открыть материал
Краткосрочный план
| Раздел |
Алгоритмы и структуры данных: графы и их обход
|
| Тема урока |
Алгоритм поиска в ширину — 09.11.2026
|
| Класс |
11
|
| Цели обучения в соответствии с учебной программой |
11.2.2.1 реализовывать алгоритм поиска в ширину (BFS) на языке Python и применять его для пошагового обхода невзвешенного графа
|
| Цели урока |
Учащиеся знают принцип обхода графа в ширину: посещение вершин по уровням, начиная с заданной вершины.
Учащиеся знают роль очереди и множества посещённых вершин в алгоритме поиска в ширину.
Учащиеся знают основные шаги реализации поиска в ширину на языке Пайтон и умеют применять алгоритм для обхода невзвешенного графа.
|
| Ценности |
Ответственный подход к решению задач развивается через последовательную проверку посещённых вершин и корректное применение алгоритма. Сотрудничество и уважение к мнению других формируются при совместном разборе порядка обхода графа.
|
Ход урока
| Этап урока/ Время | Действия педагога | Действия ученика | Оценивание | Ресурсы |
|---|---|---|---|---|
| Организационный настрой 3 мин |
Организационный момент:
Приветствует класс, проверяет готовность к уроку и наличие тетрадей и устройств.
Кратко сообщает тему: «Алгоритм поиска в ширину» и связывает её с задачами обхода графов.
|
Учащиеся приветствуют учителя и готовят тетради и устройства. Учащиеся записывают тему урока. | Готовность к работе и наличие необходимых материалов — 1 балл. Максимум за этап — 1 балл. | доска, тетради, компьютеры |
| Постановка учебной задачи 5 мин |
Постановка проблемы:
Показывает невзвешенный граф и предлагает найти порядок посещения вершин, начиная с вершины А.
Спрашивает: «Как обойти граф так, чтобы сначала посетить ближайшие к начальной вершине вершины, а затем более удалённые?».
Ответы:
Ожидаемый ответ: переходить от начальной вершины к соседям, затем к соседям этих вершин.
Ожидаемый ответ: отмечать уже посещённые вершины, чтобы не обходить их повторно.
|
Учащиеся рассматривают граф и предлагают порядок обхода. Учащиеся объясняют, почему необходимо отмечать посещённые вершины; ожидаемый ответ — чтобы избежать повторного посещения и зацикливания. | Предлагает корректный принцип обхода по уровням — 1 балл. Объясняет необходимость учёта посещённых вершин — 1 балл. Максимум за этап — 2 балла. | схема невзвешенного графа, доска |
| Изучение алгоритма 10 мин |
Объяснение нового материала:
Объясняет, что поиск в ширину обходит граф по уровням расстояния от начальной вершины.
Разбирает роль очереди: сначала в неё помещается стартовая вершина; затем извлекается первая вершина и в очередь добавляются её ещё не посещённые соседи.
Показывает, как множество посещённых вершин предотвращает повторную обработку.
Представляет реализацию на языке Пайтон: список смежности, очередь, множество посещённых вершин и цикл обработки очереди.
Демонстрирует на примере графа порядок извлечения вершин и изменения очереди.
Слайд 1 — Алгоритм поиска в ширину
Слайд 2 — Представьте, что вы хотите узнать, сколько переходов отделяет вас от одноклассника в соци…
Слайд 3 — К концу занятия вы сможете…
Слайд 4 — Обход по уровням
Слайд 5 — Очередь и посещения
Слайд 6 — Почему вершину нужно отмечать посещённой уже при добавлении в очередь, а не после её извл…
Слайд 7 — Пример обхода
Слайд 8 — Реализация на Python
Слайд 9 — Главное
Слайд 10 — Проверьте себя
|
Учащиеся слушают объяснение и фиксируют ключевые понятия: уровень, очередь, список смежности, посещённая вершина. Учащиеся прослеживают пример и записывают порядок обхода. | Верно определяет назначение очереди — 1 балл. Объясняет роль множества посещённых вершин — 1 балл. Правильно прослеживает порядок обхода примера — 1 балл. Максимум за этап — 3 балла. | |
| Проверка понимания 5 мин |
Вопросы классу:
«Почему поиск в ширину использует очередь, а не стек?».
«В какой момент вершину следует отмечать как посещённую?».
«Какое свойство невзвешенного графа позволяет искать кратчайший путь по числу рёбер с помощью поиска в ширину?».
Ответы:
Ожидаемый ответ: очередь обеспечивает обработку вершин в порядке их добавления, поэтому обход идёт по уровням.
Ожидаемый ответ: при добавлении вершины в очередь, чтобы не добавить её повторно.
Ожидаемый ответ: рёбра имеют одинаковую стоимость, и поиск в ширину первым достигает вершины по пути с минимальным числом рёбер.
|
Учащиеся отвечают на вопросы. Учащиеся объясняют, что очередь задаёт обход по уровням, вершину отмечают при добавлении в очередь, а в невзвешенном графе первым находится путь с минимальным числом рёбер. | Объясняет выбор очереди — 1 балл. Называет правильный момент отметки вершины — 1 балл. Объясняет поиск пути с минимальным числом рёбер — 1 балл. Максимум за этап — 3 балла. | доска, тетради |
| Игровая практика 6 мин |
Инструктаж:
Организует игру «Эстафета очереди»: группы получают схему графа и стартовую вершину.
Предлагает по очереди назвать следующую вершину, которую нужно извлечь из очереди, и обновить очередь и множество посещённых вершин.
Просит группы проверить, совпадает ли полученный порядок обхода, и кратко обосновать расхождения.
|
Учащиеся в группах выполняют эстафету, по очереди обновляют очередь и множество посещённых вершин. Учащиеся сверяют порядок обхода и аргументируют ответы. | Правильно определяет следующую вершину — 1 балл. Корректно обновляет очередь и отметки посещения — 1 балл. Максимум за этап — 2 балла. | |
| Практическое задание 8 мин |
Практическое задание:
Выдаёт задание: представить заданный невзвешенный граф списком смежности и написать на языке Пайтон функцию обхода в ширину, принимающую граф и начальную вершину.
Просит вывести порядок обхода и проверить, что каждая достижимая вершина посещена не более одного раза.
Предлагает проверить работу функции на графе с циклом и на графе с вершинами, не связанными с начальной.
|
Учащиеся составляют список смежности и пишут функцию поиска в ширину на языке Пайтон. Учащиеся запускают проверку на примерах и записывают полученный порядок; ожидаемый результат — достижимые вершины выводятся по уровням, недостижимые не выводятся. | Корректно задаёт список смежности — 1 балл. Правильно использует очередь и множество посещённых вершин — 2 балла. Получает корректный порядок обхода — 1 балл. Максимум за этап — 4 балла. |
Здоровье и соблюдение техники безопасности
| Здоровье и соблюдение техники безопасности | При работе за компьютером соблюдайте правильную посадку, держите экран на комфортном расстоянии и делайте перерывы для глаз. Подключайте оборудование только сухими руками и не трогайте провода без разрешения учителя. |
О материале
- Тип материала
- План урока (КСП)
- Предмет
- Информатика
- Класс
- 11 класс
- Язык
- Русский
- Направление обучения
- Физмат
Создайте свой план урока с ИИ
- По вашей теме, предмету и классу
- Готово примерно за минуту
- Начать можно бесплатно
