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