Участник:Dgerasimov/Тикеты по конспектам year2013

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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