Ниже — подборка задач из дискретной математики (комбинаторика, теории графов, булевой алгебры), каждая — с кратким указанием, какую практическую задачу в информатике она иллюстрирует. После списка подробно разбираю одну задачу (корректность и оценка сложности алгоритма) и обосновываю выбор приёмов доказательства/анализа.

1) Комбинаторика

Задача A (структуры данных): Сколько различных бинарных деревьев поиска можно построить на n различных ключах? (Ответ: n-й каталановой число). Применение: оценка числа возможных структур, анализ среднего/худшего случая для алгоритмов, которые перебирают все деревья.Задача B (рандомизация, теория вероятностей): Проблема коллекционера купонов: сколько попыток в среднем нужно, чтобы заполнить таблицу хеширования из n разных бакетов (при равномерном распределении)? Применение: оценка времени заполнения/коллизий в хеш-таблицах, ожидания в алгоритмах с рандомизацией.Задача C (перестановки/комбинаторика): Сколько сравнениями можно сортировать n элементов при оптимальной стратегии (информационное нижнее ограничение: lg(n!) ~ n lg n)? Применение: оценка сложности сортировок и доказательство нижних границ.

2) Теория графов

Задача D (корректность алгоритма): Доказать корректность алгоритма Дейкстры (однократный источник кратчайших путей при неотрицательных весах). Применение: маршрутизация, планирование, оптимизация путей.Задача E (оценка сложности): Оценить время работы алгоритма Дейкстры при использовании разных структур данных (массив, бинарная куча, биномиальная / Фибоначчиева куча) в терминах V и E. Применение: выбор структуры данных при реализации.Задача F (NP-полнота + эвристики): Покраска графа в минимальное число цветов — NP-полная задача; предложить эвристики (жадные, локальный поиск) для распределения регистров в компиляторе. Применение: аллокейшн регистров, планирование задач.Задача G (связность/потоки): Найти минимальное число ребер, удаление которых разделит граф (min-cut), и связь с максимальным потоком (макс-флоу мин-кат). Применение: надежность сети, балансировка потоков.

3) Булева алгебра и логика

Задача H (упрощение схем): Даны логические выражения, упростить их с помощью тождеств булевой алгебры (и/или/не). Применение: оптимизация логических схем, уменьшение числа вентилей.Задача I (эквивалентность схем): Доказать, что две логические схемы эквивалентны (с помощью символьных тождеств или SAT/BDD). Применение: формальная проверка аппаратных/программных преобразований.Задача J (SAT): Свести задачу планирования/расписания к SAT и использовать SAT-солвер для поиска решения. Применение: верификация, поиск контрпримеров, автоматическое планирование.

Выбранная задача для развернутого разбора: Задача D + E — доказать корректность алгоритма Дейкстры и оценить его сложность в зависимости от используемой структуры данных.

Почему выбрал эту задачу

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

Условие (формулировка)
Дан ориентированный (или неориентированный) связный граф G = (V, E) с весами на рёбрах w(e) ≥ 0 и источник s ∈ V. Требуется найти для всех вершин v расстояние dist[v] = минимальная суммарная длина пути s → v.

Алгоритм (стандартный Дейкстра)

Инициализация: dist[s] = 0, dist[u] = ∞ для u ≠ s. Множество Settled (S) = ∅.Пока существуют вершины не в S:
Выбрать вершину u ∉ S с минимальным dist[u] (операция Extract-Min).Добавить u в S.Для каждого ребра (u, v) с весом w: если dist[v] > dist[u] + w, то обновить dist[v] := dist[u] + w (операция Relax).Возвращаем dist[·].

Доказательство корректности (методика и подробности)
Метод: доказательство инварианта множества "устойчиво вычисленных" расстояний и использование индукции / доказательства от противного.

Инвариант
После каждого шага (после добавления очередной вершины u в S) для всех вершин x ∈ S значение dist[x] равно истинному кратчайшему расстоянию δ(s, x). Для вершин вне S dist[] — это верхняя оценка (больше или равна истинному).

Доказательство инварианта (по индукции по количеству добавленных вершин)

База (перед началом): S = ∅, инвариант тривиален (нет вершин в S).Шаг индукции: Пусть инвариант верен для текущего S. Рассмотрим выбор следующей вершины u — вершины вне S с минимальным dist[u]. Нужно показать, что dist[u] = δ(s, u), т.е. выбранный dist[u] — настоящий кратчайший путь.

Доказательство корректности выбора (стандартная аргументация)
Предположим противное: существует путь P от s до u длины L = δ(s, u) < dist[u]. Рассмотрим первый ребро (x, y) на пути P такое, что x ∈ S, а y ∉ S (такой существует, потому что s ∈ S? В начале s не обязательно в S; уточним: при корректной инициализации s может быть первым выбран; более формально: либо все вершины пути вне S — тогда dist values contradict minimality — ниже рассуждение даёт классический вариант). Более аккуратно:

Пусть P = (s = v0, v1, ..., vk = u) — некоторый кратчайший путь. Так как s может быть в S или нет, но индукция гарантирует, что все вершины из S имеют верные dist. Рассмотрим первую позицию j такое, что vj ∉ S и все v0..v{j-1} ∈ S. Такая j существует, потому что если все вершины пути в S, то u ∈ S, противоречие. Тогда v{j-1} ∈ S и vj ∉ S. По индукционному предположению dist[v{j-1}] = δ(s, v_{j-1}).

Рассмотрим цену пути до vj через ребро (v{j-1}, v_j): δ(s, vj) = δ(s, v{j-1}) + w(v_{j-1}, vj) = dist[v{j-1}] + w(...). Когда мы ранее обрабатывали v_{j-1}, мы релаксировали все его исходящие рёбра и поэтому установили dist[vj] ≤ dist[v{j-1}] + w(...)=δ(s,v_j). Следовательно dist[v_j] ≤ δ(s, v_j). Но по определению δ(s, v_j) ≤ δ(s, u) (так как это первый вне S по пути к u), и δ(s, u) < dist[u] по предположению. Тогда dist[v_j] ≤ δ(s, v_j) ≤ δ(s,u) < dist[u]. Но тогда dist[v_j] < dist[u], что противоречит тому, что u выбран как вершина вне S с минимальным dist. Следовательно предположение неверно и dist[u] = δ(s, u). Таким образом, после включения u в S инвариант сохраняется.

Заключение: По индукции после извлечения всех вершин каждый dist[v] = δ(s, v). Таким образом алгоритм корректен при неотрицательных весах.

Замечание про неотрицательность весов
Ключевой момент — монтоность: когда вершина извлечена как минимальная, её значение dist окончательно. Это верно только если рёбра имеют неотрицательные веса; при отрицательных весах релаксация позже может уменьшить dist уже извлечённой вершины.

Оценка сложности (анализ в зависимости от структуры данных)
Пусть n = |V|, m = |E|.

Реализация на массиве (или линейном поиске минимума):

Каждый Extract-Min — O(n) (поиск минимума среди несетлет), всего n таких → O(n^2).Relax каждого ребра — O(1), всего m релаксаций → O(m).Итог: O(n^2 + m). Для плотных графов (m ~ n^2) — O(n^2). Для разреженных (m << n^2) — всё равно O(n^2).Практическая простота реализации; подходит, если n невелико или граф плотный.

Реализация с бинарной кучей (min-heap):

Инициализация O(n).Каждый Extract-Min — O(log n), всего n → O(n log n).Каждая релаксация, приводящая к уменьшению ключа (Decrease-Key), — O(log n). В худшем случае может быть до m таких → O(m log n).Итог: O((n + m) log n) = O(m log n) для m ≥ n.Применима для разреженных графов; хорошая практическая производительность.

Реализация с Фибоначчиевой кучей:

Extract-Min — O(log n) аморт., всего O(n log n).Decrease-Key — аморт. O(1), всего O(m).Итог: O(n log n + m). Теоретически лучше для графов, где m >> n.На практике сложнее и константы могут быть хуже; редко используется в продуктивных реализациях, но имеет важное теоретическое значение.

Реализация с использованием упорядоченной структуры (например, упорядоченное дерево, multiset) даст аналогичные оценки O((n + m) log n).

Выбор реализации в практических задачах

Если граф плотный (m ~ n^2), то O(n^2) на массиве — простая и часто лучшая реализация.Если граф разреженный (m ~ n), бинарная куча обычно оптимальна: O(m log n).Если m очень велика по сравнению с n и важна теоретическая оптимальность — Фиб. куча даёт O(n log n + m).

Пример (кратко)
Небольшой пример показать не буду полностью, но схема: для графа с 5 вершинами и весами все релаксации и извлечения следуют описанному инварианту; при каждой релаксации dist уменьшается или остаётся, и первый раз, когда у вершины становится минимальное dist, это её окончательное значение.

Дополнительные замечания

Для поиска кратчайших путей на всех парах вершин используйте Floyd–Warshall (матрица) или многократный запуск Дейкстры (с разными реализациями).Для графов с отрицательными рёбрами используйте алгоритм Беллмана–Форда (корректность доказывается через релаксации за ≤ n−1 проходов) либо алгоритмы на DAG (топологическая сортировка + релаксации).Корректность Дейкстры можно также доказать с помощью так называемой «свойства разреза» (cut property): если S — множество уже окончательно оценённых вершин, то ребро минимального веса от S к V\S ведёт к вершине с минимальным возможным dist.

Краткое резюме

Предложил несколько задач из трёх областей с применениями в информатике.Подробно разобрал Дейкстру: доказал корректность через инвариант и индукцию/аргумент от противного, показал зависимости сложности от используемой структуры данных и объяснил практические выборы.

Если хотите, могу:

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