Дискретная математика:Тикеты

1. Отношения

1. Определение отношения 0.5
   1. Дефисы заменить на тире
   2. Оформить красиво источники информации
   3. Английские термины к видам отношений
2. Композиция отношений, степень отношения, обратное отношение 2
   1. Английские термины
   2. Источники информации
   3. Свойства оформить красиво
   4. Свойства обратного отношения
3. Рефлексивное отношение. Антирефлексивное отношение. 0,25
   1. См. также
4. Симметричное отношение
5. Антисимметричное отношение
6. Транзитивное отношение 0,25
   1. См. также
7. Отношение порядка 0,5
   1. Английские термины
   2. См. также
8. Изоморфизмы упорядоченных множеств[math]^\star[/math]
9. Отношение эквивалентности 0,25
   1. См. также
10. Транзитивное замыкание отношения 0,25
    1. См. также
11. Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
12. Транзитивный остов 0,25
    1. Английские термины

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

• Определение булевой функции
• Побитовые операции[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]
• Динамика по поддеревьям