Перейти к содержанию

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

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

1. Математическая логика 🧠

Логика — это язык, на котором формулируются утверждения и доказательства в CS.

Булева алгебра

Основана на двух значениях: Истина (1/True) и Ложь (0/False).

Базовые операции:

┌──────────────────────┬─────────────────────────────┬────────────────────────────────┬───────────────────────────────────────┐
│ Операция             │ Обозначение                 │ Описание                       │ Таблица истинности (A, B → Результат) │
├──────────────────────┼─────────────────────────────┼────────────────────────────────┼───────────────────────────────────────┤
│ **НЕ** (Отрицание)   │ `¬A`, `!A`, `NOT A`         │ Инвертирует значение           │ 0→1, 1→0                              │
│ **И** (Конъюнкция)   │ `A ∧ B`, `A & B`, `A AND B` │ Истина, если оба истинны       │ 0,0→0; 0,1→0; 1,0→0; **1,1→1**        │
│ **ИЛИ** (Дизъюнкция) │ `A ∨ B`, `A \               │ B`, `A OR B`                   │ Истина, если хотя бы один истинен     │
│ **Исключающее ИЛИ**  │ `A ⊕ B`, `A XOR B`          │ Истина, если значения различны │ 0,0→0; **0,1→1**; **1,0→1**; 1,1→0    │
└──────────────────────┴─────────────────────────────┴────────────────────────────────┴───────────────────────────────────────┘

Законы булевой алгебры: - Коммутативность: A ∧ B = B ∧ A, A ∨ B = B ∨ A - Ассоциативность: (A ∧ B) ∧ C = A ∧ (B ∧ C) - Дистрибутивность: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) - Законы де Моргана: - ¬(A ∧ B) = ¬A ∨ ¬B - ¬(A ∨ B) = ¬A ∧ ¬B

Применение: Упрощение условий в коде, оптимизация запросов, проектирование логических схем.

Предикаты и кванторы

  • Предикат — функция, возвращающая True/False в зависимости от аргумента: P(x) = "x > 5".
  • Квантор всеобщности (∀): "Для всех x верно P(x)".
  • Квантор существования (∃): "Существует x, для которого верно P(x)".

2. Теория множеств 📦

Множество — неупорядоченная коллекция уникальных элементов. Основа реляционных баз данных (SQL) и теории типов.

Базовые понятия

  • Обозначение: A = {1, 2, 3}, B = {2, 4, 6}
  • Принадлежность: 2 ∈ A (2 принадлежит A), 5 ∉ A (5 не принадлежит)
  • Мощность множества: |A| = 3 (количество элементов)
  • Пустое множество: ∅ или {}

Операции над множествами

┌─────────────────────────────┬─────────────┬───────────────────────────────────────────────────┬──────────────────────────────────────────────┐
│ Операция                    │ Обозначение │ Описание                                          │ Пример (A={1,2,3}, B={2,4})                  │
├─────────────────────────────┼─────────────┼───────────────────────────────────────────────────┼──────────────────────────────────────────────┤
│ **Объединение**             │ `A ∪ B`     │ Все элементы из A и B                             │ `{1, 2, 3, 4}`                               │
│ **Пересечение**             │ `A ∩ B`     │ Только общие элементы                             │ `{2}`                                        │
│ **Разность**                │ `A \ B`     │ Элементы A, которых нет в B                       │ `{1, 3}`                                     │
│ **Симметрическая разность** │ `A △ B`     │ Элементы, которые есть только в одном из множеств │ `{1, 3, 4}`                                  │
│ **Декартово произведение**  │ `A × B`     │ Все возможные пары (a, b)                         │ `{(1,2), (1,4), (2,2), (2,4), (3,2), (3,4)}` │
└─────────────────────────────┴─────────────┴───────────────────────────────────────────────────┴──────────────────────────────────────────────┘

Подмножества

  • Подмножество (⊆): A ⊆ B, если каждый элемент A содержится в B.
  • Собственное подмножество (⊂): A ⊂ B, если A ⊆ B и A ≠ B.
  • Булеан (множество всех подмножеств): P(A). Если |A| = n, то |P(A)| = 2^n.

Применение в IT: SQL (JOIN, UNION, INTERSECT), проверка прав доступа (роли как множества), теория типов в языках программирования.

3. Комбинаторика 🔢

Наука о подсчете количества вариантов. Критична для анализа сложности алгоритмов и криптографии.

Основные правила

  1. Правило суммы: Если объект A можно выбрать m способами, а объект B — n способами, и выборы не пересекаются, то выбор "A или B" возможен m + n способами.
  2. Правило произведения: Если объект A можно выбрать m способами, и после каждого такого выбора объект B можно выбрать n способами, то пару (A, B) можно выбрать m × n способами.

Формулы

┌───────────────────────────────────┬──────────────────────────────┬───────────────────────────────────────────────────┬─────────────────────────────────────────────────────┐
│ Концепция                         │ Формула                      │ Описание                                          │ Пример                                              │
├───────────────────────────────────┼──────────────────────────────┼───────────────────────────────────────────────────┼─────────────────────────────────────────────────────┤
│ **Перестановки** (без повторений) │ `P_n = n!`                   │ Сколькими способами можно упорядочить n элементов │ 3 книги на полке: `3! = 6` способов                 │
│ **Перестановки с повторениями**   │ `P = n! / (n₁! × n₂! × ...)` │ Если есть одинаковые элементы                     │ Слово "ООК": `3! / 2! = 3` способа (ООК, ООО, КОО)  │
│ **Размещения** (порядок важен)    │ `A_n^k = n! / (n-k)!`        │ Выбор k элементов из n с учетом порядка           │ 3 призовых места из 10 участников: `10! / 7! = 720` │
│ **Сочетания** (порядок НЕ важен)  │ `C_n^k = n! / (k! × (n-k)!)` │ Выбор k элементов из n без учета порядка          │ Выбор 3 дежурных из 10: `C_10^3 = 120`              │
└───────────────────────────────────┴──────────────────────────────┴───────────────────────────────────────────────────┴─────────────────────────────────────────────────────┘

Биномиальные коэффициенты: Формула бинома Ньютона: (a + b)^n = Σ C_n^k × a^(n-k) × b^k

Применение: Подсчет вариантов паролей, анализ worst-case сценариев алгоритмов, вероятность коллизий в хэш-таблицах.

4. Теория графов 🕸️

Граф — структура из вершин (узлов) и соединяющих их ребер. Моделирует сети, социальные связи, маршруты, зависимости.

Основные понятия

  • Вершина (узел): Объект графа.
  • Ребро (дуга): Связь между вершинами.
  • Неориентированный граф: Ребра двусторонние (A-B).
  • Ориентированный граф (Digraph): Ребра имеют направление (A→B).
  • Степень вершины: Количество инцидентных ей ребер.
  • Путь: Последовательность вершин, соединенных ребрами.
  • Цикл: Путь, начинающийся и заканчивающийся в одной вершине.

Виды графов

┌────────────────┬─────────────────────────────────────────────────────────┬────────────────────────────────────────┐
│ Тип            │ Описание                                                │ Пример применения                      │
├────────────────┼─────────────────────────────────────────────────────────┼────────────────────────────────────────┤
│ **Связный**    │ Между любыми двумя вершинами есть путь                  │ Социальная сеть (все друзья связаны)   │
│ **Полный**     │ Каждая вершина соединена со всеми остальными            │ Турнирная таблица (каждый с каждым)    │
│ **Дерево**     │ Связный граф без циклов                                 │ Файловая система, DOM дерева           │
│ **Взвешенный** │ Ребрам присвоены числа (вес)                            │ Карта дорог (расстояние/время)         │
│ **Двудольный** │ Вершины делятся на 2 множества, ребра только между ними │ Задачи соответствия (работники-задачи) │
└────────────────┴─────────────────────────────────────────────────────────┴────────────────────────────────────────┘

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

  • Поиск в ширину (BFS): Кратчайший путь в невзвешенном графе. O(V+E).
  • Поиск в глубину (DFS): Обход, поиск циклов, топологическая сортировка. O(V+E).
  • Алгоритм Дейкстры: Кратчайший путь во взвешенном графе (без отрицательных весов). O((V+E)logV).
  • Алгоритм Флойда-Уоршелла: Кратчайшие пути между всеми парами вершин. O(V³).

Применение: Маршрутизация в интернете (OSPF, BGP), рекомендации друзей, поиск зависимостей в пакетных менеджерах (npm, pip), GPS-навигация.

5. Отношения и функции 🔗

Отношения

Отношение R между множествами A и B — подмножество их декартова произведения A × B.

Свойства отношений на одном множестве: - Рефлексивность: ∀x: xRx (каждый элемент связан сам с собой). Пример: ≤. - Симметричность: Если xRy, то yRx. Пример: "быть братом". - Транзитивность: Если xRy и yRz, то xRz. Пример: <, =, ≤. - Антисимметричность: Если xRy и yRx, то x=y. Пример: ≤.

Важные типы отношений: - Отношение эквивалентности: Рефлексивно, симметрично, транзитивно. Разбивает множество на классы эквивалентности. Пример: "иметь одинаковый остаток от деления на 5". - Отношение порядка: Рефлексивно, антисимметрично, транзитивно. Пример: ≤ на числах.

Функции

Функция f: A → B ставит в соответствие каждому элементу A ровно один элемент B.

Свойства функций: 

┌───────────────────────────┬──────────────────────────────────────────────────────────────────────────┬───────────────────────────────────┐
│ Свойство                  │ Определение                                                              │ Пример                            │
├───────────────────────────┼──────────────────────────────────────────────────────────────────────────┼───────────────────────────────────┤
│ **Инъективность** (1-к-1) │ Разным элементам A соответствуют разные элементы B                       │ `f(x) = 2x` на натуральных числах │
│ **Сюръективность** (onto) │ Каждый элемент B имеет прообраз в A                                      │ `f(x) = x mod 3` на Z→{0,1,2}     │
│ **Биективность**          │ Одновременно инъективна и сюръективна (взаимно однозначное соответствие) │ `f(x) = x + 1` на Z→Z             │
└───────────────────────────┴──────────────────────────────────────────────────────────────────────────┴───────────────────────────────────┘

Применение: Хэш-функции (должны минимизировать коллизии → стремиться к инъективности), шифрование (биективные преобразования), нормализация БД.

📝 Шпаргалка: Формулы для запоминания

Факториал:          n! = 1 × 2 × ... × n
Перестановки:       P_n = n!
Размещения:         A_n^k = n! / (n-k)!
Сочетания:          C_n^k = n! / (k! × (n-k)!)
Сумма степеней 2:   Σ(2^i, i=0..n) = 2^(n+1) - 1
Число подмножеств:  |P(A)| = 2^|A|
Число ребер в полном графе: E = n(n-1)/2

🎯 Практическое применение в разработке

  1. Базы данных: Реляционная алгебра основана на теории множеств. JOIN — это декартово произведение с фильтрацией.
  2. Поисковые системы: Булева логика для запросов ("коты И собаки НЕ птицы").
  3. Сети: Графы для моделирования топологии, маршрутизации.
  4. Криптография: Теория чисел (раздел дискретной математики) для RSA, эллиптических кривых.
  5. Машинное обучение: Теория вероятностей (базируется на мере и множествах) для байесовских моделей.
  6. Компиляторы: Графы зависимостей для оптимизации кода, конечные автоматы (раздел теории графов) для лексического анализа.

Запомните: Без понимания дискретной математики вы будете просто копировать код из StackOverflow. С её пониманием — вы сможете создавать новые алгоритмы и решать задачи, которых ещё не было в интернете.