Участник:Dgerasimov/Тикеты по конспектам year2013 — различия между версиями
(→1. Отношения) |
(→Алгоритмы сжатия) |
||
| Строка 85: | Строка 85: | ||
## сюда неплохо было бы добавить пример на python с созданием ''юникодной'' строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length | ## сюда неплохо было бы добавить пример на python с созданием ''юникодной'' строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length | ||
| − | == Алгоритмы сжатия == | + | == 5. Алгоритмы сжатия == |
| − | *[[Алгоритм Хаффмана]] | + | * [[Алгоритм Хаффмана]] |
| − | *[[Алгоритм LZW]] | + | * [[Алгоритм LZW]] |
| − | *[[Алгоритмы LZ77 и LZ78]] | + | * [[Алгоритмы LZ77 и LZ78]] |
| − | *[[Преобразование Барроуза-Уиллера]] | + | * [[Преобразование Барроуза-Уиллера]] |
| − | *[[Обратное преобразование Барроуза-Уиллера]] | + | * [[Обратное преобразование Барроуза-Уиллера]] |
| − | *[[Преобразование MTF]] | + | * [[Преобразование MTF]] |
| − | *[[Расстояние Хэмминга]] | + | * [[Расстояние Хэмминга]] |
| − | *[[Избыточное кодирование, код Хэмминга]] | + | * [[Избыточное кодирование, код Хэмминга]] |
| − | *[[Неравенство Крафта]] | + | * [[Неравенство Крафта]] |
| − | *[[Неравенство Макмиллана]] | + | * [[Неравенство Макмиллана]] |
| − | *[[Алгоритм Ху-Таккера]] | + | * [[Алгоритм Ху-Таккера]] |
== Комбинаторика == | == Комбинаторика == | ||
Версия 22:43, 5 ноября 2013
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела
Содержание
1. Отношения
- взяли Определение отношения
- Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
- На виды и примеры отношений дать внутренние ссылки
- англоязычные термины
- пункт "Определение" не нужен, см. правила форматирования конспектов
- Композиция отношений, степерь отношения, обратное отношение
- см. пункт 1.1
- англоязычные термины
- Рефлексивное отношение. Антирефлексивное отношение.
- англоязычные термины
- добавить внутренних ссылок на эквивдентность, порядки и т.д.
- Симметричное отношение
- англоязычные термины
- Антисимметричное отношение
- англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
- Транзитивное отношение
- англоязычные термины
- Отношение порядка
- англоязычные термины
- Отношение эквивалентности
- пункт "определение" не нужен
- англоязычные термины
- Транзитивное замыкание отношения
- англоязычные термины
- взяли Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- пункт "Задача" не нужен
- интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
- !!! Транзитивный остов
- возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
- если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
- аналогично предыдущему, придумать обобщение на случай бесконечных отношений
!!! 2. Булевы функции
- Определение булевой функции
- англоязычных терминов
- Суперпозиции
- англоязычных терминов
- ДНФ
- англоязычных терминов
- писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- англоязычных терминов
- КНФ
- англоязычных терминов
- писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- англоязычных терминов
- написать, почему факт того, что существует полиномиальный алгоритм, интересен
- Полином Жегалкина, преобразование Мёбиуса
- англоязычных терминов
- "Предпосылки" — странное название, переименовать в "Полнота", например
- Полные системы функций. Теорема Поста о полной системе функций
- англоязычных терминов
- Представление функции класса DM с помощью медианы
- Пороговая функция
!!! 3. Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- англоязычных терминов (на схемную сложность, глубину схемы)
- Теорема о нижней границе для количества элементов в схеме
- Cумматор
- англоязычных терминов
- Каскадный сумматор
- англоязычных терминов
- Двоичный каскадный сумматор
- англоязычных терминов
- из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
- Реализация вычитания сумматором
- Матричный умножитель
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
- Дерево Уоллеса
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
!!! 4. Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
- сюда неплохо было бы добавить пример на python с созданием юникодной строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length
5. Алгоритмы сжатия
- Алгоритм Хаффмана
- Алгоритм LZW
- Алгоритмы LZ77 и LZ78
- Преобразование Барроуза-Уиллера
- Обратное преобразование Барроуза-Уиллера
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Неравенство Крафта
- Неравенство Макмиллана
- Алгоритм Ху-Таккера
Комбинаторика
- Комбинаторные объекты
- Лексикографический порядок
- Формула включения-исключения
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Цепные коды
- Правильные скобочные последовательности
- Действие перестановки на набор из элементов, представление в виде циклов
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
- Таблица инверсий
- Умножение перестановок, обратная перестановка, группа перестановок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о наибольшей общей подпоследовательности
- Задача о порядке перемножения матриц
- Задача о наибольшей возрастающей подпоследовательности
- Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача коммивояжера, ДП по подмножествам
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о расстоянии Дамерау-Левенштейна
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Задача о наибольшей подпоследовательности-палиндроме
- Meet-in-the-middle
- Динамическое программирование по профилю
- Задача о рюкзаке
- Динамика по поддеревьям
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула Байеса
- Формула полной вероятности
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
- Марковская цепь
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- Скрытые Марковские модели
- Алгоритм Витерби
- Алгоритм "Вперед-Назад"
