Alterna · Глава 19 — Дискретные игры

Дискретные игры — задачи, где два игрока делают ходы по правилам, пока кто-то не выиграет. На ЕГЭ это №19, 20, 21 (стратегии). Главный приём: анализ с конца — помечаем проигрышные позиции (L) и выигрышные (W). Также в главе — алгоритм Дейкстры для кратчайшего пути (ЕГЭ №1).

ФГОС · 11 класс ФОП · базовый ЕГЭ №1, 19, 20, 21

Страницы главы

5 страниц с теорией, интерактивами и банком заданий.

19.1

Выигрышные позиции

Анализ с конца, L/W-разметка. Игра с ИИ «Камешки +1 или ×2». Мини-тест 5/50.

19.2

Дерево игры

Алгоритм минимакс с альфа-бета отсечением. Визуализатор для деревьев глубины 3.

20.3

Кратчайший путь

Алгоритмы Дейкстры и A*. Визуализатор пошагово на 6-вершинном графе.

19.4

Практикум

Банк 50+ заданий: ОГЭ + ЕГЭ №1,19-21,23 с разборами.

19.5

Экзамен-полигон

Квест 800 XP + тест 10 мин + 2 развёрнутых задачи (игра + дерево).

🔗

Связи с другими главами

Глава 17 (Графы) — ДАГ и поиск путей. Дейкстра работает на взвешенных графах. Подсчёт путей в ДАГ использует динамическое программирование — как и анализ игр с конца.

Глава 24

ДАГ, топсорт, подсчёт путей. Дейкстра — расширение поиска кратчайшего пути на взвешенные графы. Формула dp[v] = Σdp[u] похожа на анализ с конца.

Глава 18

Алгебра логики. Минимакс использует логические операции AND/OR при выборе хода. L-позиция = FALSE (проигрыш), W-позиция = TRUE (выигрыш).

Глава 25

Деревья, BST. Дерево игры — такое же бинарное дерево, как BST. Листья = терминальные позиции. Обход inorder = вычисление минимакса.

ОГЭ/ЕГЭ связи

ОГЭ №4 — схемы, графы, пути
ЕГЭ №1 — Дейкстра (кратчайший путь)
ЕГЭ №3 — графы, поиск пути
ЕГЭ №19-21 — теория игр, анализ с конца
ЕГЭ №23 — системы логических уравнений (минимакс на деревьях)