Шпаргалка

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

Все темы на одной странице

5модулей

15статей

7определений

3формул

Множества и отношения

Теория множеств, бинарные отношения, порядок и эквивалентность

Теория множеств и операции

Язык математики → Операции над множествами → Мощность множеств → Декартово произведение → Аксиоматика: системы ZF и ZFC → Иерархия бесконечностей Кантора → Применения теории множеств в информатике → Мощность множества и теорема Кантора → Численный пример: диагональный аргумент Кантора

Формулы

Континуум-гипотеза: |ℝ| = 2^{|ℕ|}. Нет кардинала между |ℕ| и |ℝ|. Независима от аксиом ZFC (Гёдель 1940, Коэн 1963).

Теория множеств — универсальный язык математики. Все математические объекты — числа, функции, структуры — можно определить через множества.

Джордж Кантор создал теорию множеств в 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 и символическое представление булевых функций → Численный пример: минимизация булевой функции

Определения

Конечное поле GF(pⁿ): — поле из pⁿ элементов. GF(2ⁿ) используется в криптографии (AES работает в GF(2⁸)) и теории кодирования. Элементы GF(2⁸): полиномы степени ≤ 7 над GF(2), с умножением по модулю неприводимого полинома степени 8.

·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 функций полна тогда и только тогда, когда она не содержится ни в одном из пяти классов.

Комбинаторика: принцип включений-исключений

Основные принципы счёта → Принцип включений-исключений → Производящие функции → Принцип двойного счёта и тождества → Метод размещений с повторениями и мультисеты → Принцип включений-исключений: обобщение и применения → Экстремальная комбинаторика → Лемма Ловаса: метод алгебраической геометрии в комбинаторике → Коды с исправлением ошибок: конструкции → Экстремальная комбинаторика и гипергрупповые тесты

Определения

Мультисет: — коллекция с повторениями. Число k-элементных подмультисетов n-элементного множества: C(n+k−1, k) = «звёзды и палки» (stars and bars). Интерпретация: разместить k неразличимых шаров по n различимым ящикам. Пример: число решений x₁+x₂+x₃=10 в неотри...

Правило суммы: если 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 → Планарность: алгоритм Планара и формула Эйлера → Гипер-графы и их применения → Численный пример: алгоритм Дейкстры

Определения

Компоненты связности: — максимальные связные подграфы.
Дерево: — связный граф без циклов. Эквивалентные условия (для n вершин):

·Любые две вершины соединены единственным путём
·Связен и добавление любого ребра создаёт цикл

Ориентированный (орграф): рёбра направлены. Взвешенный: рёбра имеют веса.

Степень вершины 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-красках: конструктивное доказательство → Ориентированные графы и задачи достижимости → Численный пример: компоненты сильной связности

Формулы

Граф K₃,₃ (полный двудольный 3+3): E=9, 2V−4=8 (биpartite). Непланарен.

Граф планарный, если его можно нарисовать на плоскости без пересечений рёбер.

Формула Эйлера: для связного планарного графа V − E + F = 2, где F — число граней (включая внешнюю).

Теорема Куратовского: граф планарен тогда и только тогда, когда не содержит подграф, являющийся подразделением K₅ или K₃,₃.

Хроматическое число χ(G) — минимальное k, при котором можно раскрасить вершины в k цветов так, чтобы соседние вершины имели разные цвета.

Эйлеровы и гамильтоновы графы. Потоки в сетях

Эйлеровы пути → Гамильтоновы пути → Потоки в сетях → Алгоритм Форда-Фалкерсона: детали и корректность → Эйлеровы цепи: алгоритм Флёри → Гамильтоновы пути и задача коммивояжёра → Раскраска рёбер (хроматический индекс) → Теория совершенных графов → Случайные графы: модель Эрдёша-Реньи → Экспандерные графы и их применения

Определения

Эйлеров путь: — маршрут, проходящий по каждому ребру ровно по одному разу.
Гамильтонов путь: — путь, проходящий через каждую вершину ровно раз.
G(n,p): — случайный граф на n вершинах, каждое ребро независимо с вероятностью p. Теория пороговых значений: при p < (1−ε)ln(n)/n граф почти наверное не является связным, при p > (1+ε)ln(n)/n — почти наверное связен. Порог появления треугольников: p ~ n^{−1...

Теорема Эйлера (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 (регулярные) → ДКА.

Машины Тьюринга и сложность вычислений

Машина Тьюринга → Классы сложности → Неразрешимые задачи → Машина Тьюринга: детали и варианты → Теорема Гёделя и неполнота → Сложность описания и алгоритмическая информация → Неразрешимость: проблема останова и её следствия → Сложность и доказуемость: теорема Гёделя → Квантовая вычислимость и сложность → Оракульные модели и иерархия классов сложности

Формулы

P = NP? Главная открытая проблема Computer Science. Большинство математиков считают P ≠ NP, но доказательства нет.

МТ = (Q, Σ, Γ, δ, q₀, q_accept, q_reject): Q — состояния, Σ — входной алфавит, Γ — ленточный алфавит (Σ ⊆ Γ), δ: Q×Γ → Q×Γ×{L,R} — функция переходов. Бесконечная лента, читающая/пишущая головка.

МТ — теоретическая модель компьютера. Тезис Чёрча–Тьюринга: всё, что можно вычислить интуитивно, вычисляет машина Тьюринга.

NP: задачи, решение которых проверяется за полиномиальное время. Эквивалентно: решаются недетерминированной МТ за полиномиальное время.

NP-полные задачи: любая задача из NP полиномиально сводится к ней. SAT (Кук, 1971), Клика, Раскраска, TSP,...