Дискретная математика:Тикеты — различия между версиями
(→3 Схемы из функциональных элементов) |
(→2 Генерация комбинаторных объектов) |
||
Строка 109: | Строка 109: | ||
=== 2 Генерация комбинаторных объектов === | === 2 Генерация комбинаторных объектов === | ||
− | # [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5 | + | # взяли [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5 |
## Заменить скобки "больше-меньше" на угловые | ## Заменить скобки "больше-меньше" на угловые | ||
## Нормальную красивую картинку нарисовать | ## Нормальную красивую картинку нарисовать |
Версия 09:26, 5 декабря 2018
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)
Содержание
1. Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
2 Булевы функции
- Определение булевой функции 0,5
- исправить знаки неравенств
- Побитовые операции
- Суперпозиции 2
- Дописать раздел про ранги суперпозиций
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы 2-10
- Добавить см. также
- Правильно оформить источники информации
- Исправить знаки неравенств
- Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
- Пороговая функция
- Троичная логика
3 Схемы из функциональных элементов
- взяли Реализация булевой функции схемой из функциональных элементов 5
- Добавить информацию о методе построения схемы по функции
- Добавить алгоритм вычисления глубины схемы
- Добавить картинки к доказательствам
- взяли Простейшие методы синтеза схем из функциональных элементов 6
- Добавить примеры на каждый метод
- взяли Метод Лупанова синтеза схем 0.5
- Правильно оформить источники информации
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор 5
- Сделать конспект более понятным
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема 1
- взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов
- Триггеры
- Квантовые гейты
4 Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
5 Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n) 0.5
- Источники информации
- Алгоритм Ху-Таккера
- Неравенство Крафта 5-10
- Доказательство вообще не о том, требуется полностью переписать
- Неравенство Макмиллана 2-5
- Доказательство требует косметических правок
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78 2
- Переменные и константы взять в Tex
- Добавить примеры итоговых таблиц
- Рассказать, как декодировать
- Правильно оформить источники информации
- Получше расписать описание алгоритма
- Таблицы сделать красивыми
- Интервики
- Алгоритм LZW 0,25
- См. также
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга 0,25
- См. также
- Гамма-, дельта- и омега-код Элиаса 0,25
- См. также
6 Комбинаторика
1 Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
2 Генерация комбинаторных объектов
- взяли Генерация комбинаторных объектов в лексикографическом порядке 0.5
- Заменить скобки "больше-меньше" на угловые
- Нормальную красивую картинку нарисовать
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
3 Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков 1
- в первой теореме в доказательстве по индукции получен результат не тот, что в условии
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода 5
- то есть результат не зависит от ?
- Поправить тех
- доказательства дополнительных тождеств
- Числа Стирлинга второго рода
- Символ Похгаммера
- Числа Белла
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана 0,5
- См. также
- Конструирование комбинаторных объектов и их подсчет
4 Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий 0,25
- tex в заголовок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП