Множества и операции

2 миллиарда строк в день - столько данных обрабатывает Uber. PageRank - это итерация по множеству страниц с весами рёбер. RSA-криптография без модульной арифметики и теории чисел физически невозможна. Алгоритм Bloom Filter, который стоит в каждом CDN-узле Cloudflare - это пересечение множеств со вероятностной ошибкой. Дискретная математика - не школьный курс ради галочки. Это язык, на котором написаны алгоритмы, которые прямо сейчас работают на десятках миллиардов устройств. Множества - первое слово этого языка.

• **Bloom Filter (Redis, Cassandra, CDN)**: вместо хранения всего множества - компактная битовая маска. Ложноположительные результаты есть, ложноотрицательных - нет. Пересечение множеств с контролируемой ошибкой за $O(k)$.
• **SQL UNION / INTERSECT / EXCEPT**: три операции прямо из теории - в каждом production-запросе, в каждой аналитике. PostgreSQL планировщик их оптимизирует, зная свойства из этого урока.
• **RBAC / ABAC (права доступа)**: разрешения пользователя - пересечение множества его ролей и множества ресурсов. Keycloak, AWS IAM, Kubernetes RBAC - всё это алгебра множеств.
• **Дедупликация в streaming-пайплайнах**: Kafka + Spark Streaming держат `HashSet` посещённых ID. Мощность множества = гарантия уникальности. При 100M событий/сутки это экономит терабайты.
• **Криптография**: RSA работает с множествами чисел, взаимно простых с $n = p \cdot q$. Группа $\mathbb{Z}_n^*$ - это множество с операцией умножения. Без теории множеств - нет ключей шифрования.

Что такое множество

`WHERE status IN ('active', 'pending')` - проверка принадлежности к множеству. `DISTINCT` в SQL - преобразование мультимножества в множество. `HashSet<String>` в Java - структура, которая форсирует уникальность за $O(1)$. Множество - не абстракция из учебника, а контракт: никаких дубликатов, никакого порядка, только принадлежность.

**Множество** - это неупорядоченная коллекция различных объектов. Обозначается фигурными скобками: `A = {1, 2, 3}`. Порядок не важен: `{1, 2, 3} = {3, 1, 2}`. Дубликаты игнорируются: `{1, 1, 2} = {1, 2}`.

Мощность $|A|$ - количество элементов. Для конечных множеств это просто счётчик. Но именно мощность определяет сложность алгоритмов: проверка принадлежности в `set` за $O(1)$, в `list` за $O(|A|)$. Разница между «быстро» и «зависает» в продакшне.

**Подмножество:** A ⊆ B означает «каждый элемент A есть и в B». Пример: `{1, 2} ⊆ {1, 2, 3}`. Пустое множество ∅ является подмножеством любого множества.

Объединение множеств (A ∪ B)

**Объединение** A ∪ B - всё из A плюс всё из B, без повторений. В SQL это `UNION`. В Python это `A | B`. В Elasticsearch - запрос `bool: should`. Один оператор - три интерфейса, одна математика.

**Формально:** A ∪ B = {x | x ∈ A **или** x ∈ B}. Слово «или» здесь - **включающее** (OR), то есть элемент может принадлежать и A, и B одновременно.

**|A ∪ B| = |A| + |B| - |A ∩ B|** - принцип включений-исключений. Вычитаем пересечение, чтобы не считать дважды. Это уже не просто формула: вся комбинаторика, от подсчёта PIN-кодов до вероятностных расчётов числа коллизий в хеш-таблице, стоит на этом принципе.

Пересечение множеств (A ∩ B)

`INNER JOIN` в SQL возвращает только строки, которые есть в обеих таблицах - это пересечение. Рекомендательная система Netflix: пересечение множества «пользователи, которым понравился X» и «пользователи похожего вкуса» - так работает коллаборативная фильтрация. **Пересечение** A ∩ B: только то, что есть в обоих.

**Формально:** A ∩ B = {x | x ∈ A **и** x ∈ B}. Здесь «и» - это конъюнкция (AND): элемент должен быть и в A, и в B.

**Дизъюнктные множества:** Если A ∩ B = ∅, множества называются **дизъюнктными** (не имеют общих элементов). Пример: {1, 2} ∩ {3, 4} = ∅. Чётные и нечётные числа - дизъюнктные множества.

Дополнение и законы де Моргана

**Дополнение** Ā - всё из U, чего нет в A. В security-контексте: U - все HTTP-запросы, A - разрешённые IP-адреса, Ā - список для блокировки. Firewall-правило `DENY ALL EXCEPT whitelist` - это буквально дополнение множества.

**Формально:** Ā = U \ A = {x ∈ U | x ∉ A}. Здесь U - **универсальное множество** (Universal set), которое содержит все рассматриваемые объекты. Без определения U дополнение не имеет смысла.

**Законы де Моргана** - одни из самых полезных тождеств в математике и программировании: **(A ∪ B)' = A' ∩ B'** - дополнение объединения = пересечение дополнений **(A ∩ B)' = A' ∪ B'** - дополнение пересечения = объединение дополнений Программисты используют их каждый день: `!(a || b)` эквивалентно `!a && !b`.

**Разность множеств** A \ B = {x | x ∈ A и x ∉ B} - элементы A, не входящие в B. Это более общая операция, чем дополнение: Ā = U \ A - частный случай разности, где первое множество - универсальное.

Булеан: множество всех подмножеств

Множество, элементами которого служат другие множества. Причём не любые - все возможные подмножества данного. Это **булеан** (power set). Именно он определяет вычислительную сложность задач полного перебора - и объясняет, почему NP-трудные задачи не решаются за разумное время.

**Булеан** P(A) - множество всех подмножеств множества A, включая пустое множество ∅ и само A. Мощность булеана: **|P(A)| = 2^n**, где n = |A|.

Почему $2^n$? Для каждого из $n$ элементов ровно два выбора: включить или нет. $n$ независимых бинарных решений = $2^n$ комбинаций. Задача о рюкзаке, optimal feature selection в ML, поиск минимального покрытия - все они перебирают подмножества. При $n = 40$ это $2^{40} \approx 10^{12}$ вариантов. Никакой суперкомпьютер не спасёт.

**Экспоненциальный рост!** Для множества из 10 элементов булеан содержит 2^10 = 1024 подмножества. Для 20 элементов - уже больше миллиона. Для 64 элементов - больше, чем атомов в теле человека. Это делает полный перебор подмножеств непрактичным для больших множеств.

**Где это нужно?** Булеан используется в комбинаторике, теории вероятностей (пространство событий), базах данных (подмножества атрибутов), и даже в задачах оптимизации (задача о рюкзаке - перебор подмножеств предметов).

Ключевые идеи

• **Множество** - неупорядоченная коллекция уникальных элементов. Хеш-таблица под капотом Python `set` даёт проверку принадлежности за $O(1)$ вместо $O(n)$ у списка
• **Объединение A ∪ B** - «хотя бы в одном», SQL UNION. **Пересечение A ∩ B** - «в обоих», SQL INTERSECT / INNER JOIN
• **Законы де Моргана**: $(A \cup B)' = A' \cap B'$ - не просто тождество, а инструмент оптимизации запросов и рефакторинга условий в коде
• **Булеан $|P(A)| = 2^n$** - экспоненциальный взрыв, который делает задачу о рюкзаке NP-трудной и ограничивает полный перебор уже при $n = 30$
• **Пустое множество ∅** - подмножество любого множества. Это не аксиома по вкусу - это следствие определения через vacuously true

Связанные темы

Множества - фундамент для логики, комбинаторики и теории графов:

• Логика высказываний — Операции ∪, ∩, ' соответствуют логическим OR, AND, NOT
• Комбинаторика — Подсчёт подмножеств, формула включений-исключений
• Отношения и функции — Определяются через декартово произведение множеств

Вопросы для размышления

• В каких ситуациях в вашем коде вы неявно работаете с множествами? Можно ли заменить списки на set для ускорения?
• Почему проверка `x in set` работает за O(1), а `x in list` - за O(n)? Как это связано с хеш-таблицами?
• Как бы вы применили закон де Моргана к сложному условию `if not (a > 5 or b < 3)` для его упрощения?

Связанные уроки

• plt-02-type-systems