Конспект урока по информатике для 11 класса Социальные сети как модель графа

Конспект урока по информатике для 11 класса

Тема: «Социальные сети как модель графа. Алгоритмы на графах: поиск в ширину (BFS)».

Цель урока: сформировать представление о графах как математической модели; рассмотреть социальные сети как пример графа; изучить алгоритм поиска в ширину (BFS) и его применение для определения «теории шести рукопожатий».

Оборудование: доска, презентация, рабочие листы.

Ход урока

1.     Организационный момент (2 мин).Приветствие, проверка готовности к уроку.

2.     Актуализация знаний и мотивация (5 мин).

o    Вопрос классу: знакомы ли вы с понятием «теория шести рукопожатий»? o Обсуждение: утверждение, что любые два человека на Земле разделены не более чем пятью уровнями общих знакомых.

o    Вывод: эту задачу можно представить в виде графа, где люди — это вершины, а их знакомства — рёбра. Поиск кратчайшей цепочки знакомств — это задача на графах.

3.     Изучение нового материала (15 мин).

o    Графы: определение. Вершины (узлы) и рёбра (связи).

o    Социальная сеть как граф: пользователи — вершины, дружба/подписка — рёбра. Это неориентированный (дружба) или ориентированный (подписка) граф.

o    Алгоритмы на графах: методы для решения задач на таких моделях.

o    Поиск в ширину (Breadth-First Search, BFS):

▪  Идея: алгоритм исследует граф «слоями». Сначала посещаются все вершины, находящиеся на расстоянии 1 от начальной, затем на расстоянии 2, и так далее.

▪  Применение: идеально подходит для поиска кратчайшего пути в невзвешенном графе (например, цепочки знакомств).

▪  Визуализация: как волна, расходящаяся от центра.

4.     Практическая работа / Решение задачи (20 мин).Учащиеся выполняют задания на рабочих листах, вручную выполняя алгоритм BFS на предложенной модели социальной сети для поиска кратчайшего пути между двумя людьми.

5.     Подведение итогов (5 мин).

o    Обсуждение результатов выполнения алгоритма.

o    Ответы на вопросы: почему BFS находит именно кратчайший путь? В чём отличие BFS от поиска в глубину (DFS)?

6.     Домашнее задание (3 мин).Изучить информацию о том, как алгоритмы на графах используются в работе рекомендательных систем (например, «предложить друзей» или «рекомендованные товары»).

Рабочий лист к уроку

Фамилия, имя: ______________________ Класс: 11 ___

Тема: Социальная сеть как граф. Поиск в ширину (BFS)

Задание 1. Теоретическая разминка.Заполните пропуски:

1.     Граф — это математическая модель, состоящая из вершин (узлов) и рёбер (связей), которые их соединяют.

2.     В социальной сети пользователи являются вершинами, а их отношения дружбы — рёбрами графа.

3.     Алгоритм поиска в ширину (BFS) используется для нахождения кратчайшего пути в невзвешенном графе.

4.     Основная идея BFS — это обход графа «слоями» от начальной вершины.

Задание 2. Анализ модели.Представьте небольшую социальную сеть из 6 человек: Анна (А), Борис (Б), Виктор (В), Галина (Г), Дмитрий (Д), Елена (Е).Знакомства между ними:

•       А дружит с Б и В.

•       Б дружит с А и Г.

•       В дружит с А и Д.

•       Г дружит с Б и Е.

•       Д дружит с В.

•       Е дружит с Г.

Нарисуйте этот граф (можно схематично) и ответьте на вопрос: кто является «другом друга» для Анны (то есть находится на расстоянии 2)?

Ответ: Галина (Г) и Дмитрий (Д).

Задание 3. Практическая работа «Шесть рукопожатий».Используя модель из Задания 2, найдите кратчайший путь (цепочку знакомств) от Анны (А) до Елены (Е) с помощью алгоритма BFS.Инструкция: Выполняйте шаги алгоритма, записывая «волны» посещения вершин.

1.     Волна 0 (начало): {А}

2.     Волна 1 (друзья А): {Б, В}

3.     Волна 2 (друзья Б и В, не считая А): {Г, Д}

4.     Волна 3 (друзья Г и Д, не считая уже посещённых): {Е}

Результат: Мы достигли цели на шаге 3. Кратчайший путь: А -> Б -> Г -> Е. Количество «рукопожатий» — 3.

Задание 4. Задача на логику.Почему алгоритм поиска в глубину (DFS) не подходит для решения задачи о «шести рукопожатиях», если наша цель — найти кратчайший путь?

Ответ:Алгоритм DFS («поиск в глубину») идёт по одному пути до самого конца, пока не упрётся в «тупик», и только потом возвращается назад, чтобы попробовать другой путь. Он может найти путь от Анны до Елены, но этот путь не обязательно будет самым коротким. Он может быть очень длинным и извилистым. BFS, напротив, проверяет все возможные короткие пути одновременно, поэтому он гарантированно находит кратчайший.

Задание 5. Найдите ошибку.Ученик утверждает: «Кратчайший путь в графе можно найти с помощью простого перебора всех возможных путей».В чём ошибка ученика? Почему для больших сетей (как ВКонтакте или Facebook) его метод не сработает?

Ответ:Ошибка ученика заключается в непонимании понятия

«вычислительная сложность». Количество возможных путей в графе растёт экспоненциально с увеличением числа вершин. Для сети из миллионов пользователей простой перебор всех путей займёт миллионы лет даже на самом мощном суперкомпьютере. Эффективные алгоритмы, такие как BFS, решают эту задачу за разумное время, так как им не нужно проверять все возможные пути.