Материал из База знаний подготовки ЕГЭ и ОГЭ
ЕГЭ по информатике: графы и оптимизация[править | править код]
- Представление графов: списки, матрицы, таблицы смежности.
- Обходы в глубину и ширину, поиск кратчайших путей.
- Задачи на максимальный/минимальный вес, распределение ресурсов.
- Алгоритмы для задач ЕГЭ: Дейкстра, Флойд, поиск в ширину, жадные схемы.
Таблица «Тип задачи → подсказка → алгоритм»[править | править код]
| Задача |
Что анализировать |
Алгоритм/приём
|
| Найти количество путей |
Вершины, ограничения, условие повторов |
Динамика по графу, обход в глубину с мемоизацией
|
| Минимальный путь |
Веса рёбер, возможные отрицательные веса |
BFS (без весов) или Дейкстра (с положительными весами)
|
| Оптимизация маршрута |
Стоимость переходов, условия посещения |
Жадный выбор + проверка обратных ходов
|
| Сеть дорог с ограничениями |
Запрещённые вершины, промежуточные условия |
Модифицированный BFS с состояниями
|
| Расстояние между вершинами |
Матрица смежности, степень вершины |
Поиск в ширину, построение слоёв
|
- **День 1:** теория графов — типы, представления, подсчёт степеней.
- **День 2:** обходы и поиск путей, таблицы трассировки, визуализация.
- **День 3:** задачи на минимальный путь и стоимость (Дейкстра, BFS).
- **День 4:** комбинированные задачи с условиями (запреты, множители, логические условия).
- **День 5:** мини-пробник: 4 задачи ЕГЭ (№23, №26) + разбор ошибок.
- Различаю ориентированные и неориентированные графы.
- Умею строить и читать матрицу смежности и таблицу переходов.
- Могу вручную выполнить алгоритм Дейкстры для небольшого графа.
- Знаю, как добавить ограничения (запрещённые вершины) в обход.
- Позвольте ученику объяснить алгоритм на доске, шаг за шагом.
- Используйте цветные маркеры или стикеры для выделения уровней графа.
- Сравнивайте решения: «жадный» vs. «полный перебор», обсуждайте эффективность.
