Участник:Dgerasimov/Тикеты по конспектам year2013
< Участник:Dgerasimov
Версия от 23:40, 16 октября 2013; Dgerasimov (обсуждение | вклад) (Новая страница: «= Первый семестр = == Отношения == *Определение отношения *[[Композиция отношений|Компози...»)
Первый семестр
Отношения
- Определение отношения
- Композиция отношений, степерь отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Суперпозиции
- ДНФ
- КНФ
- Полином Жегалкина
- Полные системы функций. Теорема Поста о полной системе функций
- Сокращенная и минимальная ДНФ
- Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
- Представление функции класса DM с помощью медианы
- Пороговая функция
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Теорема о нижней границе для количества элементов в схеме
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Алгоритм LZW
- Алгоритмы LZ77 и LZ78
- Преобразование Барроуза-Уиллера
- Обратное преобразование Барроуза-Уиллера
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Неравенство Крафта
- Неравенство Макмиллана
- Алгоритм Ху-Таккера
Комбинаторика
- Комбинаторные объекты
- Лексикографический порядок
- Формула включения-исключения
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Цепные коды
- Правильные скобочные последовательности
- Действие перестановки на набор из элементов, представление в виде циклов
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
- Таблица инверсий
- Умножение перестановок, обратная перестановка, группа перестановок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о наибольшей общей подпоследовательности
- Задача о порядке перемножения матриц
- Задача о наибольшей возрастающей подпоследовательности
- Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача коммивояжера, ДП по подмножествам
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о расстоянии Дамерау-Левенштейна
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Задача о наибольшей подпоследовательности-палиндроме
- Meet-in-the-middle
- Динамическое программирование по профилю
- Задача о рюкзаке
- Динамика по поддеревьям
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула Байеса
- Формула полной вероятности
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
- Марковская цепь
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- Скрытые Марковские модели
- Алгоритм Витерби
- Алгоритм "Вперед-Назад"