Просмотр исходного текста страницы Дискретная математика:Тикеты

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)

== 1. Отношения ==
# [[Определение отношения]]
# [[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
# [[Симметричное отношение]]
# [[Антисимметричное отношение]]
# [[Транзитивное отношение]]
# [[Отношение порядка]]
# [[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
# [[Отношение эквивалентности]] 
# [[Транзитивное замыкание|Транзитивное замыкание отношения]] 
# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
# [[Транзитивный остов]]

== 2 Булевы функции ==
# [[Определение булевой функции]] 0,5
## исправить знаки неравенств
# [[Побитовые операции]]<tex>^\star</tex>
# [[Суперпозиции]] 2
## Дописать раздел про ранги суперпозиций
# [[ДНФ]] 
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
# [[КНФ]] 
# [[2-SAT]]
# [[XOR-SAT]]<tex>^\star</tex>
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 
# [[Полные системы функций. Теорема Поста о полной системе функций]] 
# [[Представление функции класса DM с помощью медианы]] 2-10 
## Добавить см. также
## Правильно оформить источники информации
## Исправить знаки неравенств
## Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
# [[Пороговая функция]] 
#[[Троичная логика]]<tex>^\star</tex>

== 3 Схемы из функциональных элементов ==
#[[Реализация булевой функции схемой из функциональных элементов]] 5
## Добавить информацию о методе построения схемы по функции 
## Добавить алгоритм вычисления глубины схемы
## Добавить картинки к доказательствам
# [[Простейшие методы синтеза схем из функциональных элементов]] 6
## Добавить примеры на каждый метод
# [[Метод Лупанова синтеза схем]] 0.5
## Правильно оформить источники информации
#[[Cумматор]]
#[[Каскадный сумматор]]
#[[Двоичный каскадный сумматор]] 5
## Сделать конспект более понятным
#[[Троичный сумматор]]<tex>^\star</tex>
#[[Реализация вычитания сумматором]]
#[[Матричный умножитель]]
#[[Дерево Уоллеса]]
#[[Контактная схема]] 1
## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов 
#[[Триггеры]]<tex>^\star</tex>
#[[Квантовые гейты]]<tex>^\star</tex>

== 4 Представление информации ==
# [[Кодирование информации]]
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
# [[Представление вещественных чисел]]
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== 5 Алгоритмы сжатия ==
# [[Алгоритм Хаффмана]]
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
# [[Алгоритм Хаффмана за O(n)]] 0.5
## Источники информации
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
# [[Неравенство Крафта]] 5-10
## Доказательство вообще не о том, требуется полностью переписать
# [[Неравенство Макмиллана]] 2-5
## Доказательство требует косметических правок
# [[Код Шеннона]]
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
# [[Алгоритмы LZ77 и LZ78]] 2
## Переменные и константы взять в Tex
## Добавить примеры итоговых таблиц
## Рассказать, как декодировать
## Правильно оформить источники информации
## Получше расписать описание алгоритма
## Таблицы сделать красивыми
## Интервики
# [[Алгоритм LZW]] 0,25
## См. также
# [[Алгоритм LZSS]]<tex>^\star</tex>
# [[Алгоритм LZMA]]<tex>^\star</tex>
# [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
# [[Преобразование MTF]]
# [[Расстояние Хэмминга]]
# [[Избыточное кодирование, код Хэмминга]] 0,25
## См. также
# [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
## См. также

== 6 Комбинаторика ==
=== 1 Комбинаторные объекты ===
# [[Комбинаторные объекты]]
# [[Лексикографический порядок]]
# [[Коды Грея]]
# [[Коды Грея для перестановок]]
# [[Коды антигрея]]
# [[Монотонный код Грея]]
# [[Цепные коды]]
# [[Правильные скобочные последовательности]]

=== 2 Генерация комбинаторных объектов ===
# [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5
## Заменить скобки "больше-меньше" на угловые
## Нормальную красивую картинку нарисовать
# [[Получение номера по объекту]]
# [[Получение объекта по номеру]]
# [[Получение следующего объекта]]
# [[Получение предыдущего объекта]]<tex>^\star</tex>  
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
# [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== 3 Подсчёт числа объектов ===
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] 1
## в первой теореме в доказательстве по индукции получен результат не тот, что в условии
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] 
# [[Лемма Бёрнсайда и Теорема Пойа]]
# [[Задача об ожерельях]]
# [[Числа Стирлинга первого рода]] 5
## <tex>\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex> то есть результат не зависит от <tex>m</tex>?
## Поправить тех
## доказательства дополнительных тождеств
# [[Числа Стирлинга второго рода]]
# [[Символ Похгаммера]]
# [[Числа Белла]]
# [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]
# [[Числа Каталана]] 0,5
## См. также
# [[Конструирование комбинаторных объектов и их подсчет]]

=== 4 Свойства комбинаторных объектов ===
# [[Умножение перестановок, обратная перестановка, группа перестановок]] 
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
# [[Таблица инверсий]] 0,25
## tex в заголовок
# [[Теорема Кэли]]
# [[Матричное представление перестановок]]
# [[Задача о минимуме/максимуме скалярного произведения]] 
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]