Дискретная математика и алгоритмы

Первый семестр

Отношения

• Определение отношения
• Степень отношений
• Рефлексивное отношение. Антирефлексивное отношение.
• Симметричное отношение
• Антисимметричное отношение
• Композиция отношений. Обратное отношение
• Транзитивное отношение
• Транзитивное замыкание отношения
• Отношение порядка
• Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения

Булевы функции

• Определение булевой функции
• Суперпозиции
• СДНФ
• СКНФ
• Полином Жегалкина
• Полные системы функций. Теорема Поста о полной системе функций
• Сокращенная и минимальная ДНФ
• Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
• Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
• Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
• Представление функции класса DM с помощью медианы
• Пороговая функция

Схемы из функциональных элементов

• Реализация булевой функции схемой из функциональных элементов
• Изменение размера оптимальной схемы при переходе к другому базису
• Cумматор
• Каскадный сумматор
• Двоичный каскадный сумматор
• Матричный умножитель
• Дерево Уоллеса

Представление информации

• Кодирование информации
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код
• Представление вещественных чисел
• Представление символов, таблицы кодировок

Алгоритмы сжатия

• Алгоритм Хаффмана
• Алгоритм LZW
• Алгоритмы LZ77 и LZ78
• Преобразование Барроуза-Уиллера
• Обратное преобразование Барроуза-Уиллера
• Преобразование MTF
• Расстояние Хэмминга
• Избыточное кодирование, код Хэмминга
• Неравенство Крафта
• Неравенство Макмиллана

Комбинаторика

• Комбинаторные объекты
• Лексикографический порядок
• Формула включения-исключения
• Генерация комбинаторных объектов в лексикографическом порядке
• Получение номера по объекту
• Получение объекта по номеру
• Получение следующего объекта
• Коды Грея
• Коды Грея для перестановок
• Цепные коды
• Действие перестановки на набор из элементов, представление в виде циклов
• Метод генерации случайной перестановки, алгоритм Фишера-Йетса
• Таблица инверсий
• Умножение перестановок, обратная перестановка, группа перестановок
• Теорема Кэли
• Матричное представление перестановок
• Задача о минимуме/максимуме скалярного произведения
• Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера

Динамическое программирование

• Кратчайший путь в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о наибольшей общей подпоследовательности
• Задача о перемножении матриц
• Задача о наибольшей возрастающей подпоследовательности
• Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
• Метод четырех русских для умножения матриц
• Применение метода четырех русских в задачах ДП на примере задачи о НОП
• Задача коммивояжера, ДП по подмножествам
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Задача о редакционном расстоянии, алгоритм Левенштейна
• Задача о расстоянии Дамерау-Левенштейна
• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

Теория вероятности

• Вероятностное пространство, элементарный исход, событие
• Независимые события
• Условная вероятность
• Формула Байеса
• Формула полной вероятности
• Дискретная случайная величина
• Независимые случайные величины
• Линейность математического ожидания
• Ковариация случайных величин
• Дисперсия случайной величины
• Энтропия случайного источника
• Симуляция одним распределением другого
• Арифметическое кодирование

Марковские цепи

• Теорема о поглощении
• Фундаментальная матрица
• Математическое ожидание времени поглощения
• Расчет вероятности поглощения в состоянии
• Эргодическая марковская цепь
• Регулярная марковская цепь

Второй семестр

Амортизационный анализ

• Амортизационный анализ. Метод предоплаты
• Саморасширяющийся массив
• Массив с увеличением/уменьшением размера
• Стек
• Очередь
• Список

Приоритетные очереди

• Двоичная куча
• Биномиальная куча
• Фибоначчиевы кучи

Система непересекающихся множеств

• Наивные реализации
• Списки с весовой эвристикой
• Реализация с помощью леса корневых деревьев
• Анализ реализации с ранговой эвристикой

Деревья поиска

• Упорядоченное множество
• Дерево поиска, наивная реализация
• АВЛ-дерево
• 2-3 дерево
• B-дерево
• Красно-черное дерево
• Декартово дерево
• Splay-дерево
• Декартово дерево по неявному ключу
• Дерево ван Эмде Боаса

Дерево отрезков

• Статистики на отрезках. Корневая эвристика
• Дерево отрезков. Построение
• Реализация запроса в дереве отрезков сверху
• Реализация запроса в дереве отрезков снизу
• Несогласованные поддеревья. Реализация массового обновления
• Многомерное дерево отрезков
• Сжатое многомерное дерево отрезков

Дерево Фенвика

• Дерево Фенвика
• Встречное дерево Фенвика
• Дерево Фенвика для некоммутативных операций
• Многомерное дерево Фенвика

Хеширование

• Хеширование
• Открытое и закрытое хеширование
• Поиск свободного места при закрытом хешировании
• Хеширование кукушки
• Двойное хеширование
• Перехеширование. Амортизационный анализ
• Фильтр Блума
• Универсальное семейство хеш-функций

Сортировка

• Сортировка пузырьком
• Сортировка слиянием
• Cортировка слиянием с использованием O(1) дополнительной памяти
• Сортировка вставками
• Сортировка подсчетом
• Сортировка подсчетом сложных объектов
• Цифровая сортировка
• Поиск k-ой порядковой статистики
• Поиск k-й порядковой статистики за линейное время
• Теорема о нижней оценке для сортировки сравнениями
• Быстрая сортировка

Сортирующие сети

• Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
• Сортирующие сети для квадратичных сортировок
• Сеть Бетчера

Алгоритмы поиска

• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск
• Вещественный двоичный поиск