Cheatsheet
Дискретная математика — all topics on one page
Множества и отношения
Теория множеств, бинарные отношения, порядок и эквивалентность
Язык математики → Операции над множествами → Мощность множеств → Декартово произведение → Аксиоматика: системы ZF и ZFC → Иерархия бесконечностей Кантора → Применения теории множеств в информатике → Мощность множества и теорема Кантора → Численный пример: диагональный аргумент Кантора
Formulas
Теория множеств — универсальный язык математики. Все математические объекты — числа, функции, структуры — можно определить через множества.
Джордж Кантор создал теорию множеств в 1870-х, несмотря на сопротивление консервативных математиков. Давид Гильберт назвал его теорию «раем, из которого нас никто не изгонит».
Объединение: A ∪ B = {x: x∈A или x∈B}. Пересечение: A ∩ B = {x: x∈A и x∈B}. Разность: A\B = {x: x∈A, x∉B}. Симметрическая разность: A △ B = (A\B) ∪ (B\A). Дополнение: Aᶜ = U\A (U — универсум).
Множества A и B равномощны, если существует биекция A → B. Конечные: |A| — число элементов. Бесконечные: сравниваем по биекции.
Определение → Отношения эквивалентности → Отношения порядка → Диаграммы Хассе → Свойства отношений порядка: минимумы и максимумы → Функции и их свойства → Применение теории отношений в информатике → Функции Эйлера и кольца вычетов → Решётки и приложения к криптографии → Численный пример: отношения эквивалентности и частичного порядка
- •Рефлексивность: aRa для всех a.
- •Антирефлексивность: не aRa ни для какого a.
- •Симметричность: aRb → bRa.
- •Антисимметричность: aRb и bRa → a=b.
- •Транзитивность: aRb и bRc → aRc.
Класс эквивалентности: [a] = {b: b~a}. Классы образуют разбиение A (попарно непересекающиеся, покрывают A).
Примеры: Равенство по модулю n: a ~ b ⟺ n | (a−b). Классы: {0, n, 2n,...}, {1, n+1, 2n+1,...}, ..., {n-1, 2n-1, ...}.
Частичный порядок (poset): рефлексивное, антисимметричное, транзитивное. Пример: делимость на ℕ.
Линейный порядок: дополнительно сравнимость: для любых a,b: aRb или bRa. Пример: обычное ≤ на ℝ.
Решётка → Булева алгебра → Булевы функции → Алгебра Хантингтона и решёточные тождества → Минимизация булевых функций: практика → Применения булевой алгебры в САПР и верификации → Конечные поля и коды Рида-Соломона → Булева сложность схем → BDD и символическое представление булевых функций → Численный пример: минимизация булевой функции
Definitions
- •sup{a,b} = a∨b (объединение, наименьшая верхняя грань)
- •inf{a,b} = a∧b (пересечение, наибольшая нижняя грань)
Частично упорядоченное множество L — решётка, если для любых двух элементов a, b существуют:
Примеры: (2^A, ⊆) — решётка подмножеств. (ℕ, |) — решётка по делимости: a∨b = НОК(a,b), a∧b = НОД(a,b). Подпространства векторного пространства.
Дистрибутивная дополненная решётка: выполняются дистрибутивные законы a∧(b∨c) = (a∧b)∨(a∧c) и дополнение aᶜ такое, что a∧aᶜ = 0, a∨aᶜ = 1.
Теорема Стоуна: Каждая конечная булева алгебра изоморфна алгебре подмножеств некоторого конечного множества. Размер — степень двойки.
Булевы функции и теорема Поста
Полнота систем булевых функций, замкнутые классы
СДНФ и СКНФ → Теорема Поста о полноте → Применения → Пять замкнутых классов Поста: подробнее → Сложность распознавания полноты → Полиномы Жегалкина → Теорема о полноте для многозначных логик → Квантовые логические вентили: обобщение булевых → Квантовая запутанность и её вычислительные следствия → Численный пример: нормальные формы и функциональная полнота
- •T₀: функции, сохраняющие 0 (f(0,...,0)=0)
- •T₁: функции, сохраняющие 1 (f(1,...,1)=1)
- •S: самодвойственные (f(¬x₁,...,¬xₙ) = ¬f(x₁,...,xₙ))
- •M: монотонные (xᵢ ≤ yᵢ → f(x) ≤ f(y))
- •L: линейные (над GF(2))
СДНФ (совершенная дизъюнктивная нормальная форма): дизъюнкция минтермов. Минтерм — конъюнкция всех переменных (с отрицаниями или без), соответствующая строке таблицы истинности с f=1.
СКНФ (совершенная конъюнктивная нормальная форма): конъюнкция макстермов (дизъюнкции для строк с f=0).
Замкнутый класс функций — множество F, замкнутое относительно суперпозиции (подстановки, отождествления переменных).
Теорема Поста: Система F функций полна тогда и только тогда, когда она не содержится ни в одном из пяти классов.
Основные принципы счёта → Принцип включений-исключений → Производящие функции → Принцип двойного счёта и тождества → Метод размещений с повторениями и мультисеты → Принцип включений-исключений: обобщение и применения → Экстремальная комбинаторика → Лемма Ловаса: метод алгебраической геометрии в комбинаторике → Коды с исправлением ошибок: конструкции → Экстремальная комбинаторика и гипергрупповые тесты
Definitions
Правило суммы: если A и B не пересекаются, |A∪B| = |A|+|B|. Правило произведения: последовательных выборов k₁, k₂, ...: k₁·k₂·...
Размещения A(n,k) = n!/(n−k)! (упорядоченный выбор k из n). Сочетания C(n,k) = n!/(k!(n−k)!) (неупорядоченный выбор).
Число дерangangements (перестановок без фиксированных точек): D(n) = n! Σₖ₌₀ⁿ (−1)ᵏ/k! ≈ n!/e.
Число разбиений n в слагаемые из множества S: коэффициент при xⁿ в ∏_{s∈S} 1/(1−xˢ).
Линейные рекуррентности → Общий метод → Мастер-теорема → Линейные рекуррентности с нечёткими корнями → Рекуррентности и комбинаторные интерпретации → Мастер-теорема: граничные случаи и обобщения → Решение линейных рекуррентностей: алгебраический взгляд → Рекуррентности в анализе алгоритмов: тонкости → Динамическое программирование: вероятностные расширения → Перечислительная комбинаторика: принцип включений-исключений
Последовательность определена рекуррентно: a(n) выражается через a(n−1), ..., a(n−k).
Характеристическое уравнение: x² = x + 1. Корни: φ = (1+√5)/2 (золотое сечение), ψ = (1−√5)/2.
1. Характеристическое уравнение: xᵏ = c₁xᵏ⁻¹ + ... + cₖ. 2. Если корни x₁,...,xₖ различны: a(n) = α₁x₁ⁿ + ... + αₖxₖⁿ. 3. Коэффициенты из начальных условий.
При кратных корнях xᵢ кратности mᵢ: слагаемое xᵢⁿ·(α₀ + α₁n + ... + α_{mᵢ-1}nᵐⁱ⁻¹).
Теория графов
Связность, деревья, планарность, раскраски
Определение и виды → Пути и связность → Деревья → Числа Кирхгофа → Спектральная теория графов → Алгоритмы на графах: практика → Теоретико-графовые задачи в Computer Science → Планарность: алгоритм Планара и формула Эйлера → Гипер-графы и их применения → Численный пример: алгоритм Дейкстры
Definitions
- •Любые две вершины соединены единственным путём
- •Связен и добавление любого ребра создаёт цикл
Ориентированный (орграф): рёбра направлены. Взвешенный: рёбра имеют веса.
Степень вершины deg(v) — число рёбер, инцидентных v. Лемма о рукопожатиях: Σ deg(v) = 2|E| (каждое ребро вносит 2 в сумму степеней). Следствие: число вершин нечётной степени чётно.
Маршрут: последовательность вершин v₀, v₁, ..., vₖ с рёбрами v_{i-1}v_i. Путь: маршрут без повторяющихся вершин.
Кратчайшие пути: алгоритм Дейкстры (неотрицательные веса) O((V+E)log V); Беллман–Форд (допускает отрицательные) O(VE); Флойд–Уоршелл (все пары) O(V³).
Планарные графы → Раскраска графов → Теорема Рамсея → Хроматический полином и алгебраические методы → Теорема Рамсея: точные значения → Двудольность и алгоритм двудольного паросочетания → Теорема о 5-красках: конструктивное доказательство → Ориентированные графы и задачи достижимости → Численный пример: компоненты сильной связности
Formulas
Граф планарный, если его можно нарисовать на плоскости без пересечений рёбер.
Формула Эйлера: для связного планарного графа V − E + F = 2, где F — число граней (включая внешнюю).
Теорема Куратовского: граф планарен тогда и только тогда, когда не содержит подграф, являющийся подразделением K₅ или K₃,₃.
Хроматическое число χ(G) — минимальное k, при котором можно раскрасить вершины в k цветов так, чтобы соседние вершины имели разные цвета.
Эйлеровы пути → Гамильтоновы пути → Потоки в сетях → Алгоритм Форда-Фалкерсона: детали и корректность → Эйлеровы цепи: алгоритм Флёри → Гамильтоновы пути и задача коммивояжёра → Раскраска рёбер (хроматический индекс) → Теория совершенных графов → Случайные графы: модель Эрдёша-Реньи → Экспандерные графы и их применения
Definitions
Теорема Эйлера (1736): Граф имеет эйлеров цикл тогда и только тогда, когда он связен и все вершины имеют чётную степень.
Задача Кёнигсбергских мостов: семь мостов через реку — можно ли пройти каждый ровно раз? Четыре острова, все нечётные степени → нет.
В отличие от Эйлерова: нет простого критерия! Задача нахождения гамильтонова цикла NP-полна.
Достаточное условие (теорема Дирака): Если каждая вершина имеет степень ≥ n/2 (n ≥ 3), то гамильтонов цикл существует.
Комбинаторика
Принцип включений-исключений, производящие функции
Задачи счёта → Разбиения чисел → Комбинаторное тождество Вандермонда → Лемма Бёрнсайда → Комбинаторика на словах и последовательностях → Метод производящих функций для сложных перечислений → Числа Белла и разбиения множеств → Теорема Пойа и перечисление с симметриями → Асимптотика разбиений и формула Харди-Рамануджана → Группы симметрий и применения в химии
Комбинаторика отвечает на вопрос: «Сколько?» — сколько различных объектов данного типа существует. Это фундаментально для теории алгоритмов, криптографии, статистики.
Число сюрьекций из n-элементного во m-элементное (m ≤ n): S(n,m) = Σₖ₌₀ᵐ (−1)ᵏ C(m,k)(m−k)ⁿ.
Числа Стирлинга второго рода S(n,k) — разбиение n-элементного множества на k непустых подмножеств. Рекуррентность: S(n,k) = k·S(n−1,k) + S(n−1,k−1).
Разбиение числа n — способ представить n как сумму натуральных чисел (без учёта порядка).
Обыкновенные производящие функции → Экспоненциальные производящие функции → Линейные рекуррентности и дроби → Аналитические методы → Генерирующие функции для задач анализа алгоритмов → Случайные структуры через производящие функции → Оценки для нетривиальных перечислительных задач → Блочные схемы и дизайн экспериментов → Кодирование в конечных полях → Комбинаторные доказательства тождеств
Число разбиений в нечётные части = число разбиений в различные части (замечательное тождество Эйлера).
Число перестановок без фиксированных точек: D_n = n! Σ (−1)ᵏ/k!. ЭПФ: e^{−x}/(1−x).
F(n) (Фибоначчи) → f(x) = x/(1−x−x²) = x/((1−φx)(1−ψx)). Разложение на простые дроби → формула Бине.
Метод седловой точки (Лапласа): для коэффициента [xⁿ]f(x) при больших n — асимптотика через седловую точку f.
Задачи об экстремуме → Принцип Дирихле (ящиков) → Теоремы Рамсея и Гельфанда → Теорема Грина-Тао и простые числа в АП → Ультраметрика и метрические результаты Рамсея → Полихроматические числа Рамсея → Комбинаторные игры и теорема Хекса → Теория игр и комбинаторные игры: числа Гранди → Алфавитные игры и коды → Детерминированные клеточные автоматы
Экстремальная комбинаторика: как велик или мал может быть объект с заданными свойствами?
Теорема Турана: Максимальное число рёбер в K_{r+1}-свободном графе на n вершинах: e ≤ (1 − 1/r)·n²/2. Достигается на полном r-дольном графе Турана T(n,r).
Задача Эрдёша о числе расстояний: n точек на плоскости определяют ≥ c√n различных расстояний.
Если n предметов разложить в m ящиков и n > m, то в каком-то ящике окажется ≥ 2 предметов.
Автоматы и формальные языки
Конечные автоматы, регулярные языки, теорема Клини
Детерминированный конечный автомат (ДКА) → Недетерминированные автоматы (НКА) → Регулярные языки и выражения → Минимальные автоматы и синтаксические моноиды → Детерминистические vs. недетерминистические автоматы → Регулярные языки и алгебра Буля → ω-автоматы и бесконечные языки → Формальные грамматики и естественные языки → Регулярные выражения и их вычислительная сложность → Автоматы и криптографические потоковые шифры
ДКА = (Q, Σ, δ, q₀, F): Q — множество состояний, Σ — алфавит, δ: Q×Σ → Q — функция переходов, q₀ — начальное состояние, F ⊆ Q — принимающие состояния.
Пример: ДКА для бинарных строк, делящихся на 3: состояния — остатки {0, 1, 2}. q₀ = F = {0}. δ(q, 0) = 2q mod 3, δ(q, 1) = (2q+1) mod 3.
Теорема (Рабин–Скотт): ДКА и НКА эквивалентны по распознаваемым языкам (конструкция подмножеств).
Теорема Клини: Язык регулярен ⟺ распознаётся ДКА ⟺ задаётся регулярным выражением.
КСГ и КСЯ → Автоматы с магазинной памятью → Иерархия Хомского → Алгоритмические задачи → Нормальные формы КСГ и алгоритм CYK → Иерархия Хомского → Детерминированные КСЯ и парсинг → Лемма о накачке для КСЯ → Атрибутные грамматики → Трансдьюсеры и транслирующие автоматы
- •Тип 3: ДКА / регулярные выражения.
- •Тип 2: МП-автоматы / КСГ (грамматики языков программирования).
- •Тип 1: Линейно ограниченные ТМ (LBA).
- •Тип 0: Произвольные ТМ.
Контекстно-свободная грамматика G = (V, Σ, R, S): V — нетерминалы, Σ — терминалы, R — правила вида A → α (A∈V, α∈(V∪Σ)*), S — стартовый нетерминал.
Нормальная форма Хомского: A → BC или A → a. Всякая КСГ эквивалентна грамматике в НФХ.
КСЯ замкнуты: объединение, конкатенация, звезда Клини. Не замкнуты: пересечение, дополнение (в общем случае).
Тип 0 (без ограничений) → рекурсивно перечислимые языки, машины Тьюринга. Тип 1 (контекстные) → ЛБА (линейно ограниченные автоматы). Тип 2 (контекстно-свободные) → МПА. Тип 3 (регулярные) → ДКА.
Машина Тьюринга → Классы сложности → Неразрешимые задачи → Машина Тьюринга: детали и варианты → Теорема Гёделя и неполнота → Сложность описания и алгоритмическая информация → Неразрешимость: проблема останова и её следствия → Сложность и доказуемость: теорема Гёделя → Квантовая вычислимость и сложность → Оракульные модели и иерархия классов сложности
Formulas
МТ = (Q, Σ, Γ, δ, q₀, q_accept, q_reject): Q — состояния, Σ — входной алфавит, Γ — ленточный алфавит (Σ ⊆ Γ), δ: Q×Γ → Q×Γ×{L,R} — функция переходов. Бесконечная лента, читающая/пишущая головка.
МТ — теоретическая модель компьютера. Тезис Чёрча–Тьюринга: всё, что можно вычислить интуитивно, вычисляет машина Тьюринга.
NP: задачи, решение которых проверяется за полиномиальное время. Эквивалентно: решаются недетерминированной МТ за полиномиальное время.
NP-полные задачи: любая задача из NP полиномиально сводится к ней. SAT (Кук, 1971), Клика, Раскраска, TSP,...