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