748
правок
Изменения
→2 Генерация комбинаторных объектов
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)
== 1. Отношения ==
#[[Определение отношения]] 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## См. такжеДописать раздел про ранги суперпозиций#[[ДНФ]]
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
#[[КНФ]] # [[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
## См. также
#[[2-SATАлгоритм LZSS]]<tex>^\star</tex>#[[XOR-SATАлгоритм LZMA]]<tex>^\star</tex>#[[Специальные формы КНФПреобразование Барроуза-Уиллера |Специальные формы КНФ: КНФ в форме Хорна Преобразование Барроуза-Уиллера и КНФ в форме Кромаобратное ему]]#[[Полином Жегалкина | Полином Жегалкина, преобразование МёбиусаПреобразование MTF]] 0,25## См. также [[Расстояние Хэмминга]]#[[Полные системы функций. Теорема Поста о полной системе функцийИзбыточное кодирование, код Хэмминга]] 0,25
## См. также
#[[Представление функции класса DM с помощью медианыГамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
## См. также
== Схемы из функциональных элементов 6 Комбинаторика ==*[[Реализация булевой функции схемой из функциональных элементов]]*[[Простейшие методы синтеза схем из функциональных элементов]]*[[Метод Лупанова синтеза схем]]*[[Cумматор]]*[[Каскадный сумматор]]=== 1 Комбинаторные объекты ===*# [[Двоичный каскадный сумматорКомбинаторные объекты]]*# [[Троичный сумматорЛексикографический порядок]]<tex>^\star</tex>*# [[Реализация вычитания сумматоромКоды Грея]]*# [[Матричный умножительКоды Грея для перестановок]]*# [[Дерево УоллесаКоды антигрея]]*# [[Контактная схемаМонотонный код Грея]]*# [[ТриггерыЦепные коды]]<tex>^\star</tex>*# [[Квантовые гейтыПравильные скобочные последовательности]]<tex>^\star</tex>
== Представление информации = 2 Генерация комбинаторных объектов ===*# [[Кодирование информацииГенерация комбинаторных объектов в лексикографическом порядке]]0.5## Заменить скобки "больше-меньше" на угловые## Нормальную красивую картинку нарисовать*# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный кодПолучение номера по объекту]]# [[Получение объекта по номеру]]# [[Получение следующего объекта]]*# [[Представление вещественных чиселПолучение предыдущего объекта]]<tex>^\star</tex> *# [[Представление символовМетод генерации случайной перестановки, таблицы кодировокалгоритм Фишера-Йетса]]# [[Методы генерации случайного сочетания]]<tex>^\star</tex>
=== Другие задачи 4 Свойства комбинаторных объектов ===*# [[Задача о расстоянии Дамерау-ЛевенштейнаУмножение перестановок, обратная перестановка, группа перестановок]]<tex>^\star</tex>*# [[Задача о выводе Действие перестановки на набор из элементов, представление в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касамивиде циклов]]*# [[Задача о наибольшей подпоследовательности-палиндромеТаблица инверсий]]0,25*## tex в заголовок# [[Задача о наибольшей общей возрастающей последовательностиТеорема Кэли]]<tex>^\star</tex>*# [[Задача о наибольшей общей палиндромной подпоследовательностиМатричное представление перестановок]]<tex>^\star</tex>*# [[Динамическое программирование по профилюЗадача о минимуме/максимуме скалярного произведения]]<tex>^\star</tex>*# [[Динамика по поддеревьямЗадача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]