Дискретная математика
Дискретная математика изучает конечные и счётные структуры — множества, графы, логические формулы, комбинации. Вычислительные системы по природе дискретны (биты, конечная память, конечные автоматы), поэтому эта дисциплина — естественный язык информатики.
См. также: Логика, формальный слой множеств, реляционная алгебра и таблицы, графы — углубление, рекуррентные соотношения, обзор Математическая основа IT.
пользователи_с_подпиской := {Аня, Борис, Вера}
пользователи_с_пробным := {Борис, Глеб}
все_с_доступом := пользователи_с_подпиской ∪ пользователи_с_пробным
// {Аня, Борис, Вера, Глеб}
и_подписка_и_пробный := пользователи_с_подпиской ∩ пользователи_с_пробным
// {Борис} — только те, кто в обоих списках
только_подписка := пользователи_с_подпиской \ пользователи_с_пробным
// {Аня, Вера}
изменились_статусы := пользователи_с_подпиской △ пользователи_с_пробным
// {Аня, Вера, Глеб} — кто только в одном из списков
Множества
Множество — совокупность различных элементов без порядка. x ∈ A, x ∉ A. В IT чаще всего работают с конечными множествами (ограниченная память).
Задать множество можно перечислением M = {a, b, c} или свойством: {x | P(x)} — все x, для которых выполняется условие P (в SQL то же читается как WHERE).
Кортеж (x₁, x₂, …, xₙ) — упорядоченная n-ка: порядок координат важен. Пары (1, 2) и (2, 1) различны, хотя множества {1, 2} и {2, 1} совпадают. Строка таблицы БД, координата (x, y), ключ (user_id, role_id) — кортежи; множество уникальных id без порядка — множество.
Операции
| Операция | Обозначение | Аналог в коде / SQL |
|---|---|---|
| Объединение | A ∪ B | UNION, объединение множеств |
| Пересечение | A ∩ B | INTERSECT, фильтр по двум критериям |
| Разность | A \ B | элементы A, не входящие в B |
| Симметрическая разность | A △ B | symmetric_difference, «только в одном» |
| Дополнение | Ā относительно U | "все, кроме…" |
A △ B = (A \ B) ∪ (B \ A) — элементы, которые лежат ровно в одном из множеств. Для двух списков id это «добавились или удалились» при сравнении снимков; для битовых масок — XOR.
Законы совпадают с булевой алгеброй (включая де Моргана для дополнений). На диаграммах Венна △ — области, принадлежащие ровно одному кругу.
Битовые представления
Множество на фиксированном универсуме U = {1,…,n} можно кодировать характеристическим вектором (битовой строкой) длины n: бит i равен 1, если i ∈ A, иначе 0.
| Операция над множествами | Побитовая операция |
|---|---|
A ∩ B | AND |
A ∪ B | OR |
A △ B | XOR |
дополнение Ā | NOT по позициям |
Тот же приём лежит в основе bitmap-индексов в аналитических СУБД и битовых карт в Redis: сложный фильтр по нескольким категориям сводится к быстрым AND/OR на CPU.
Мощность и булеан
|A| — число элементов. Булеан множества мощности n имеет 2^n подмножеств — отсюда экспоненциальный взрыв при полном переборе конфигураций, фич-комбинаций в тестах, подмножеств в оптимизации.
Play ITЗагрузка интерактивного демо…
Отношения
Бинарное отношение на A — подмножество A × A (пары). Примеры — "меньше", "родственник", "наследует класс".
| Свойство | Формула (идея) | Пример |
|---|---|---|
| Рефлексивность | каждый элемент связан с собой | "≤" на числах |
| Симметричность | (a,b) ⇒ (b,a) | "сосед в неориентированном графе" |
| Транзитивность | (a,b)∧(b,c) ⇒ (a,c) | "предок в иерархии" |
- Эквивалентность (рефлексивно + симметрично + транзитивно) → классы эквивалентности (типы, остатки по модулю, ключи хеша).
- Частичный порядок (рефлексивно + антисимметрично + транзитивно) → включение множеств, иерархия классов, зависимости задач.
- Линейный порядок — любые два элемента сравнимы → сортировка, топологический порядок при отсутствии циклов.
Матрица отношения
На конечных множествах A = {a₁,…,aₘ}, B = {b₁,…,bₙ} бинарное отношение P ⊆ A × B кодируют матрицей 0/1 — pᵢⱼ = 1, если (aᵢ, bⱼ) ∈ P. Так хранят графы смежности, матрицы доступа ролей, таблицы совместимости в тестах.
Для отношения эквивалентности на A матрицу можно привести к блочно-диагональному виду перестановкой строк и столбцов: каждый блок — один класс эквивалентности. В коде тот же смысл у группировки по ключу: GROUP BY status выделяет классы строк с одинаковым статусом.
Фактор-множество и разбиения
Отношение эквивалентности E разбивает множество A на непересекающиеся классы A/E. Фактор-множество — множество таких классов; элемент фактор-множества — целый класс, а не отдельный объект.
| Пример | Классы | Зачем в IT |
|---|---|---|
x ≡ y (mod n) | остатки по модулю n | хеш по hash % buckets |
одинаковый status | группы заказов | агрегаты, отчёты |
| эквивалентность по URL без query | канонический ключ | дедупликация |
Графы
Граф G = (V, E): вершины (узлы) и рёбра (связи). Моделируют сети, зависимости модулей, состояния, социальные связи, маршруты.
| Понятие | Смысл |
|---|---|
| Путь | цепочка рёбер между вершинами |
| Цикл | путь, замыкающийся в ту же вершину |
| Связность | между любыми двумя вершинами есть путь |
| Степень | число инцидентных рёбер |
Виды: неориентированные, ориентированные (орграфы), взвешенные (вес = расстояние, стоимость, задержка), деревья (связный ациклический граф), двудольные (matching, рекомендации).
Эксцентриситет вершины — максимальное расстояние до остальных; радиус графа — минимум эксцентриситетов; центр — вершины с этим минимумом. В сети дорог центр — кандидат на склад или узел CDN: минимизируется худшее время до любого клиента (в идеальной модели без прочих ограничений).
В связном неориентированном мультиграфе есть эйлеров цикл (проход по каждому ребру ровно один раз) тогда и только тогда, когда степень каждой вершины чётна.
Классическая задача о семи мостах Кёнигсберга не имеет такого маршрута — у всех вершин нечётная степень. Проверка "можно ли обойти все рёбра" встречается при планировании обхода кабеля или маршрута инспекции.
Гамильтонов цикл проходит через каждую вершину один раз. Задача коммивояжёра — найти гамильтонов цикл минимального веса во взвешенном графе.
Полный перебор даёт порядок O(n!) — на практике используют эвристики и приближения (см. анализ сложности).
Остов связного графа — подмножество рёбер, связывающее все вершины без циклов (минимальное "скелетное" дерево на графе). Разрез — множество рёбер, удаление которых разрывает связность. Остовы и разрезы важны при проектировании сетей без избыточных циклов и при оценке уязвимости топологии.
Алгоритмы на графах
| Алгоритм | Идея | Типичное применение |
|---|---|---|
| BFS | очередь, слой за слоем | кратчайший путь в невзвешенном графе, краулеры |
| DFS | стек / рекурсия | циклы, топосорт, связность |
| Дейкстра | жадный выбор с неотрицательными весами | маршрутизация |
| Уоршелл | булево OR–AND на матрице смежности | достижимость в орграфе, транзитивное замыкание |
| Флойд–Уоршелл | минимум сумм весов | кратчайшие пути между всеми парами |
| MST (Прим, Краскал) | дерево минимального веса | проектирование сетей |
Сложность чаще O(V + E) или O(E log V) — при проектировании систем важно, растёт ли граф вместе с нагрузкой.
Комбинаторика
Подсчёт и перечисление вариантов опирается на два базовых правила:
- Правило суммы — варианты из непересекающихся классов складываются:
|A ∪ B| = |A| + |B|, еслиA ∩ B = ∅. - Правило произведения — независимые выборы перемножаются:
|A × B| = |A| · |B|; дляkшагов — произведение числа вариантов на каждом.
| Тип выборки | Порядок | Повторения | Формула (идея) |
|---|---|---|---|
| Перестановки | важен | нет | n! |
| Размещения | важен | нет | n!/(n−k)! |
| Сочетания | не важен | нет | C(n,k) = n!/(k!(n−k)!) |
| Размещения с повторениями | важен | да | n^k (пароль из k символов алфавита n) |
| Сочетания с повторениями | не важен | да | C(n+k−1, k) (распределить k одинаковых по n ящикам) |
Перестановки с повторениями: если среди n символов есть группы одинаковых (например, буквы слова), число различных строк делится на факториалы кратностей: n!/(n₁!·n₂!·…).
Формула включений-исключений для двух множеств: |A ∪ B| = |A| + |B| − |A ∩ B|. Для трёх:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
Прикладные следствия: парадокс дней рождения (коллизия дат при ~23 человеках в комнате), оценка коллизий хеш-таблицы при m корзинах и n ключах.
Принцип Дирихле
Если n объектов раскладывают по m «ящикам» и n > m, то хотя бы в одном ящике окажется больше одного объекта. Обобщение: при n > k·m найдётся ящик с не менее k+1 объектами.
| Ситуация | «Ящики» | Следствие |
|---|---|---|
Хеш по m корзинам, n ключей | корзины | при n > m коллизия неизбежна |
| 13 месяцев, 12 знаков зодиака | знаки | два человека с одним знаком |
Больше 256 разных IPv4 в подсети /24 | последний октет | повтор адреса в одной /24 |
Это нижняя оценка «надо ли вообще думать о коллизиях», а не вероятностная модель.
Сложность перебора
| Задача | Порядок роста |
|---|---|
| Все подмножества | O(2^n) |
| Все перестановки | O(n!) |
| Коммивояжёр (полный перебор) | O(n!) |
На практике — эвристики, аппроксимация, backtracking с отсечением (судоку, SAT, генерация AST).
Прикладные оценки в IT
- Пароли и ключи: мощность пространства
|алфавит|^длина; словарные атаки снижают эффективную энтропию. - Pairwise-тестирование: покрытие пар параметров вместо полного декартова произведения.
- SQL: оптимизатор оценивает кардинальность join’ов; ошибка → плохой план (nested loops вместо hash join).
- ML: отбор признаков, перебор гиперпараметров — комбинаторные пространства с жадными и байесовскими сокращениями.
Дальше: Рекуррентные соотношения → Теория чисел и алгоритмы.