Изменения

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

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

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

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

== Алгоритмы сжатия 4 Представление информации ==* # [[Алгоритм ХаффманаКодирование информации]]* # [[Оптимальное хранение словаря в алгоритме Хаффмана]]* [[Алгоритм Хаффмана за O(n)]]* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>* [[Неравенство Крафта]]* [[Неравенство Макмиллана]]* [[Код Шеннона]]* [[Оптимальный префиксный Представление целых чисел: прямой код, код со сдвигом, дополнительный код с длиной кодового слова не более L бит]]<tex>^\star</tex>* [[Алгоритмы LZ77 и LZ78]]* [[Алгоритм LZW]]* [[Алгоритм LZSS]]<tex>^\star</tex>* [[Алгоритм LZMA]]<tex>^\star</tex>* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]* [[Преобразование MTF]]* # [[Расстояние ХэммингаПредставление вещественных чисел]]* # [[Избыточное кодированиеПредставление символов, код Хэмминга]]* [[Гамма-, дельта- и омега-код Элиасатаблицы кодировок]]<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 Комбинаторные объекты ===* # [[Комбинаторные объекты]]# [[Генерация комбинаторных объектов в лексикографическом порядкеЛексикографический порядок]]* # [[Получение номера по объектуКоды Грея]]* # [[Получение объекта по номеруКоды Грея для перестановок]]* # [[Получение следующего объектаКоды антигрея]]* # [[Получение предыдущего объектаМонотонный код Грея]]<tex>^\star</tex> * # [[Метод генерации случайной перестановки, алгоритм Фишера-ЙетсаЦепные коды]]* # [[Методы генерации случайного сочетанияПравильные скобочные последовательности]]<tex>^\star</tex>

=== Подсчёт числа 2 Генерация комбинаторных объектов ===* # [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядковГенерация комбинаторных объектов в лексикографическом порядке]]0.5* [[Нахождение количества разбиений числа ## Заменить скобки "больше-меньше" на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]угловые## Нормальную красивую картинку нарисовать* # [[Производящая функцияПолучение номера по объекту]]* # [[Лемма Бёрнсайда и Теорема ПойаПолучение объекта по номеру]]* # [[Задача об ожерельяхПолучение следующего объекта]]* # [[Числа Стирлинга первого родаПолучение предыдущего объекта]]<tex>^\star</tex> * # [[Числа Стирлинга второго родаМетод генерации случайной перестановки, алгоритм Фишера-Йетса]]* # [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановкахМетоды генерации случайного сочетания]]<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 в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]заголовок*# [[Meet-in-the-middleТеорема Кэли]]<tex>^\star</tex>*# [[Convex hull trickМатричное представление перестановок]] === Другие задачи ===*# [[Задача о расстоянии Дамерау-Левенштейнаминимуме/максимуме скалярного произведения]]<tex>^\star</tex>*# [[Задача о выводе в контекстно-свободной грамматикемонотонных подпоследовательностях, алгоритм Кока-Янгера-Касами]]*[[Задача теорема о наибольшей подпоследовательности-палиндроме]]*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>*[[Динамическое программирование по профилю]]<tex>^\star</tex>*[[Динамика по поддеревьямсвязи длины НВП и НУП]]