Дискретная математика

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

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

См. также: Логика, обзор Математическая основа IT.

Множества

Множество — совокупность различных элементов без порядка. x ∈ A, x ∉ A. В IT чаще всего работают с конечными множествами (ограниченная память).

Операции

Операция	Обозначение	Аналог в коде / SQL
Объединение	A ∪ B	UNION, объединение множеств
Пересечение	A ∩ B	INTERSECT, фильтр по двум критериям
Разность	A \ B	элементы A, не входящие в B
Дополнение	Ā относительно U	«все, кроме…»

Законы совпадают с булевой алгеброй (включая де Моргана для дополнений).

Мощность и булеан

|A| — число элементов. Булеан множества мощности n имеет 2^n подмножеств — отсюда экспоненциальный взрыв при полном переборе конфигураций, фич-комбинаций в тестах, подмножеств в оптимизации.

Дискретная математика

Отношения

Бинарное отношение на A — подмножество A × A (пары). Примеры: «меньше», «родственник», «наследует класс».

Свойство	Формула (идея)	Пример
Рефлексивность	каждый элемент связан с собой	«≤» на числах
Симметричность	(a,b) ⇒ (b,a)	«сосед в неориентированном графе»
Транзитивность	(a,b)∧(b,c) ⇒ (a,c)	«предок в иерархии»

• Эквивалентность (рефлексивно + симметрично + транзитивно) → классы эквивалентности (типы, остатки по модулю, ключи хеша).
• Частичный порядок (рефлексивно + антисимметрично + транзитивно) → включение множеств, иерархия классов, зависимости задач.
• Линейный порядок — любые два элемента сравнимы → сортировка, топологический порядок при отсутствии циклов.

Графы

Граф G = (V, E): вершины (узлы) и рёбра (связи). Моделируют сети, зависимости модулей, состояния, социальные связи, маршруты.

Понятие	Смысл
Путь	цепочка рёбер между вершинами
Цикл	путь, замыкающийся в ту же вершину
Связность	между любыми двумя вершинами есть путь
Степень	число инцидентных рёбер

Виды: неориентированные, ориентированные (орграфы), взвешенные (вес = расстояние, стоимость, задержка), деревья (связный ациклический граф), двудольные (matching, рекомендации).

Алгоритмы на графах

Алгоритм	Идея	Типичное применение
BFS	очередь, слой за слоем	кратчайший путь в невзвешенном графе, краулеры
DFS	стек / рекурсия	циклы, топосорт, связность
Дейкстра	жадный выбор с неотрицательными весами	маршрутизация
Флойд–Уоршелл	все пары вершин	транзитивное замыкание, компиляторы
MST (Прим, Краскал)	дерево минимального веса	проектирование сетей

Сложность чаще O(V + E) или O(E log V) — при проектировании систем важно, растёт ли граф вместе с нагрузкой.

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

Подсчёт и перечисление вариантов:

• Перестановки — все элементы, порядок важен: n!
• Размещения — k из n, порядок важен
• Сочетания — k из n, порядок не важен: C(n,k)

Формула включений-исключений — мощность объединения по пересечениям; парадокс дней рождения и оценка коллизий хешей.

Сложность перебора

Задача	Порядок роста
Все подмножества	O(2^n)
Все перестановки	O(n!)
Коммивояжёр (полный перебор)	O(n!)

На практике: эвристики, аппроксимация, backtracking с отсечением (судоку, SAT, генерация AST).

Прикладные оценки в IT

• Пароли и ключи: мощность пространства |алфавит|^длина; словарные атаки снижают эффективную энтропию.
• Pairwise-тестирование: покрытие пар параметров вместо полного декартова произведения.
• SQL: оптимизатор оценивает кардинальность join’ов; ошибка → плохой план (nested loops вместо hash join).
• ML: отбор признаков, перебор гиперпараметров — комбинаторные пространства с жадными и байесовскими сокращениями.

Дальше: Теория чисел и алгоритмы.

---