Дискретная математика и алгоритмы
Отношения
- Определение отношения
- Степень отношений
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Композиция отношений. Обратное отношение
- Транзитивное отношение
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
Булевы функции
- Определение булевой функции
- Примеры булевых функций: все функции от нуля, одной и двух переменных
- Подстановка одной функции в другую, отождествление переменных
- Представление функции формулой, полные системы функций
- СДНФ
- СКНФ
- Полином Жегалкина
- Теорема Поста о полной системе функций
- Сокращенная и минимальная ДНФ
- Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
- Представление функции класса DM с помощью медианы
- Пороговая функция
Схемы из функциональных элементов
Представление информации
Алгоритмы сжатия
Комбинаторика
- Комбинаторные объекты
- Лексикографический порядок
- Формула включения-исключения
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Коды Грея
- Коды Грея для перестановок
- Цепные коды
- Действие перестановки на набор из элементов, представление в виде циклов
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Таблица инверсий
- Умножение перестановок, обратная перестановка, группа перестановок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Поиск наибольшей возрастающей подпоследовательности и т. д.
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о наибольшей общей подпоследовательности
- Задача о перемножении матриц
- Задача о наибольшей возрастающей подпоследовательности
- Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача коммивояжера, ДП по подмножествам
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о редакционном расстоянии, алгоритм Левенштейна
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Теория вероятности
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула Байеса
- Формула полной вероятности
- Дискретная случайная величина
- Независимые случайные величины
- Линейность математического ожидания
- Ковариация случайных величин
- Дисперсия случайной величины
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
Марковские цепи
Амортизационный анализ
Приоритетные очереди
Система непересекающихся множеств
Деревья поиска
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
Хеширование
Сортировка
- Сортировка пузырьком
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Сортировка вставками
- Сортировка подсчетом
- Сортировка подсчетом сложных объектов
- Цифровая сортировка
- Поиск k-ой порядковой статистики
- Поиск k-й порядковой статистики за линейное время
- Теорема о нижней оценке для сортировки сравнениями
- Быстрая сортировка
