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

[править] Отношения

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

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

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

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

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

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

[править] Классические задачи динамического программирования
Кратчайший путь в ациклическом графе
Задача о числе путей в ациклическом графе
Задача о расстановке знаков в выражении
Задача о порядке перемножения матриц
Задача о наибольшей общей подпоследовательности
Задача о наибольшей возрастающей подпоследовательности
Задача коммивояжера, ДП по подмножествам
Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
Задача о рюкзаке
[править] Способы оптимизации методов динамического программирования
Метод четырех русских для умножения матриц^\star
Применение метода четырех русских в задачах ДП на примере задачи о НОП^\star
Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Meet-in-the-middle^\star
[править] Другие задачи
Задача о расстоянии Дамерау-Левенштейна^\star
Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
Задача о наибольшей подпоследовательности-палиндроме
Наибольшая общая возрастающая подпоследовательность^\star
Задача о наибольшей общей палиндромной подпоследовательности^\star
Динамическое программирование по профилю^\star
Динамика по поддеревьям
[править] Теория вероятностей

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

Марковская цепь
Теорема о поглощении
Фундаментальная матрица
Математическое ожидание времени поглощения
Расчет вероятности поглощения в состоянии
Эргодическая марковская цепь
Регулярная марковская цепь
Примеры использования Марковских цепей
Скрытые Марковские модели^\star
Алгоритм Витерби^\star
Алгоритм "Вперед-Назад"^\star
Алгоритм Баума-Велша^\star