Изменения

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

== 2 Булевы функции ==#[[Определение булевой функции]] 0,5## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])исправить знаки неравенств#[[Побитовые операции]]<tex>^\star</tex>#[[Суперпозиции]] 0,252## См. такжеДописать раздел про ранги суперпозиций#[[ДНФ]]

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

== 3 Схемы из функциональных элементов ==#[[Реализация булевой функции схемой из функциональных элементов]]5## Добавить информацию о методе построения схемы по функции ## Добавить алгоритм вычисления глубины схемы## Добавить картинки к доказательствам#[[Простейшие методы синтеза схем из функциональных элементов]]6## Добавить примеры на каждый метод#[[Метод Лупанова синтеза схем]]0.5## Правильно оформить источники информации

#[[Двоичный каскадный сумматор]]5## Сделать конспект более понятным

#[[Контактная схема]]1## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов

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

=== Другие задачи 4 Свойства комбинаторных объектов ===*# [[Задача о расстоянии Дамерау-ЛевенштейнаУмножение перестановок, обратная перестановка, группа перестановок]]<tex>^\star</tex>*# [[Задача о выводе Действие перестановки на набор из элементов, представление в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касамивиде циклов]]*# [[Задача о наибольшей подпоследовательности-палиндромеТаблица инверсий]]0,25*## tex в заголовок# [[Задача о наибольшей общей возрастающей последовательностиТеорема Кэли]]<tex>^\star</tex>*# [[Задача о наибольшей общей палиндромной подпоследовательностиМатричное представление перестановок]]<tex>^\star</tex>*# [[Динамическое программирование по профилюЗадача о минимуме/максимуме скалярного произведения]]<tex>^\star</tex>*# [[Динамика по поддеревьямЗадача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]