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

1. Отношения

1. Определение отношения
   1. Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
   2. На виды и примеры отношений дать внутренние ссылки
   3. англоязычные термины
   4. пункт "Определение" не нужен, см. правила форматирования конспектов
2. Композиция отношений, степерь отношения, обратное отношение
   1. см. пункт 1.1
   2. англоязычные термины
3. Рефлексивное отношение. Антирефлексивное отношение.
   1. англоязычные термины
   2. добавить внутренних ссылок на эквивдентность, порядки и т.д.
4. Симметричное отношение
   1. англоязычные термины
5. Антисимметричное отношение
   1. англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
6. Транзитивное отношение
   1. англоязычные термины
7. Отношение порядка
   1. англоязычные термины
8. Отношение эквивалентности
   1. пункт "определение" не нужен
   2. англоязычные термины
9. Транзитивное замыкание отношения
   1. англоязычные термины
10. Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
    1. пункт "Задача" не нужен
    2. интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
11. Транзитивный остов
    1. возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
    2. если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
    3. аналогично предыдущему, придумать обобщение на случай бесконечных отношений

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

1. Определение булевой функции
2. Суперпозиции
3. ДНФ
4. КНФ
5. Полином Жегалкина
6. Полные системы функций. Теорема Поста о полной системе функций
7. Сокращенная и минимальная ДНФ
8. Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
9. Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
10. Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
11. Представление функции класса DM с помощью медианы
12. Пороговая функция

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

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

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

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

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

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

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

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

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

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

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

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

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

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