Изменения

#[[Определение отношения]]# [[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]# [[Симметричное отношение]]# [[Антисимметричное отношение]]# [[Транзитивное отношение]]# [[Отношение порядка]]# [[Изоморфизмы упорядоченных множеств]]<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 Алгоритмы сжатия ==# [[Алгоритм Хаффмана]] 2#[[Оптимальное хранение словаря в алгоритме Хаффмана]]# Английские термины[[Алгоритм Хаффмана за O(n)]] 0.5

#[[Алгоритм Ху-Таккера]]<tex>^\star</tex># Свойства оформить красиво[[Неравенство Крафта]] 5-10## Свойства обратного отношенияДоказательство вообще не о том, требуется полностью переписать#[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.Неравенство Макмиллана]] 0,252-5## См. такжеДоказательство требует косметических правок#[[Симметричное отношениеКод Шеннона]]#[[Антисимметричное отношениеОптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>#[[Транзитивное отношениеАлгоритмы LZ77 и LZ78]] 02## Переменные и константы взять в Tex## Добавить примеры итоговых таблиц## Рассказать,25как декодировать## Правильно оформить источники информации## Получше расписать описание алгоритма## Таблицы сделать красивыми## См. такжеИнтервики#[[Отношение порядкаАлгоритм LZW]] 0,5## Английские термины25

#[[Изоморфизмы упорядоченных множествАлгоритм LZSS]]<tex>^\star</tex>#[[Отношение эквивалентностиАлгоритм LZMA]]<tex>^\star</tex># [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]# [[Преобразование MTF]]# [[Расстояние Хэмминга]]# [[Избыточное кодирование, код Хэмминга]] 0,25

#[[Транзитивное замыкание|Транзитивное замыкание отношенияГамма-, дельта- и омега-код Элиаса]] <tex>^\star</tex> 0,25

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

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

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