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

Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Отношения

• Определение отношения
• Композиция отношений, степень отношения, обратное отношение
• Рефлексивное отношение. Антирефлексивное отношение.
• Симметричное отношение
• Антисимметричное отношение
• Транзитивное отношение
• Отношение порядка
• Изоморфизмы упорядоченных множеств[math]^\star[/math]
• Отношение эквивалентности
• Транзитивное замыкание отношения
• Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
• Транзитивный остов

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

• Определение булевой функции
• Побитовые операции[math]^\star[/math]
• Суперпозиции
• ДНФ
• Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
• КНФ
• 2-SAT
• XOR-SAT[math]^\star[/math]
• Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
• Полином Жегалкина, преобразование Мёбиуса
• Полные системы функций. Теорема Поста о полной системе функций
• Представление функции класса DM с помощью медианы
• Пороговая функция
• Троичная логика[math]^\star[/math]

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

• Реализация булевой функции схемой из функциональных элементов
• Простейшие методы синтеза схем из функциональных элементов
• Метод Лупанова синтеза схем
• Cумматор
• Каскадный сумматор
• Двоичный каскадный сумматор
• Троичный сумматор[math]^\star[/math]
• Реализация вычитания сумматором
• Матричный умножитель
• Дерево Уоллеса
• Контактная схема
• Триггеры[math]^\star[/math]
• Квантовые гейты[math]^\star[/math]

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

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

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

• Алгоритм Хаффмана
• Оптимальное хранение словаря в алгоритме Хаффмана
• Алгоритм Хаффмана за O(n)
• Алгоритм Ху-Таккера[math]^\star[/math]
• Неравенство Крафта
• Неравенство Макмиллана
• Код Шеннона
• Оптимальный префиксный код с длиной кодового слова не более L бит[math]^\star[/math]
• Алгоритмы LZ77 и LZ78
• Алгоритм LZW
• Алгоритм LZSS[math]^\star[/math]
• Алгоритм LZMA[math]^\star[/math]
• Преобразование Барроуза-Уиллера и обратное ему
• Преобразование MTF
• Расстояние Хэмминга
• Избыточное кодирование, код Хэмминга
• Гамма-, дельта- и омега-код Элиаса[math]^\star[/math]

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

Комбинаторные объекты

• Комбинаторные объекты
• Лексикографический порядок
• Коды Грея
• Коды Грея для перестановок
• Коды антигрея
• Монотонный код Грея
• Цепные коды
• Правильные скобочные последовательности

Генерация комбинаторных объектов

• Генерация комбинаторных объектов в лексикографическом порядке
• Получение номера по объекту
• Получение объекта по номеру
• Получение следующего объекта
• Получение предыдущего объекта[math]^\star[/math]
• Метод генерации случайной перестановки, алгоритм Фишера-Йетса
• Методы генерации случайного сочетания[math]^\star[/math]

Подсчёт числа объектов

• Формула включения-исключения, подсчет числа беспорядков
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
• Производящая функция
• Лемма Бёрнсайда и Теорема Пойа
• Задача об ожерельях
• Числа Стирлинга первого рода
• Числа Стирлинга второго рода
• Числа Эйлера первого и второго рода. Подъемы в перестановках[math]^\star[/math]
• Числа Каталана

Свойства комбинаторных объектов

• Умножение перестановок, обратная перестановка, группа перестановок
• Действие перестановки на набор из элементов, представление в виде циклов
• Таблица инверсий
• Теорема Кэли
• Матричное представление перестановок
• Задача о минимуме/максимуме скалярного произведения
• Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

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

Классические задачи динамического программирования

• Кратчайший путь в ациклическом графе
• Задача о числе путей в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц
• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности
• Быстрый поиск наибольшей возрастающей подпоследовательности*
• Задача коммивояжера, ДП по подмножествам
• Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
• Задача о рюкзаке

Способы оптимизации методов динамического программирования

• Метод четырех русских для умножения матриц
• Применение метода четырех русских в задачах ДП на примере задачи о НОП[math]^\star[/math]
• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
• Meet-in-the-middle[math]^\star[/math]
• Convex hull trick

Другие задачи

• Задача о расстоянии Дамерау-Левенштейна[math]^\star[/math]
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Задача о наибольшей подпоследовательности-палиндроме
• Задача о наибольшей общей возрастающей последовательности[math]^\star[/math]
• Задача о наибольшей общей палиндромной подпоследовательности[math]^\star[/math]
• Динамическое программирование по профилю[math]^\star[/math]
• Динамика по поддеревьям