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## См. такжеДописать раздел про ранги суперпозиций#[[ДНФ]]
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
#[[КНФ]] 0,25## См. также#[[2-SAT]]#[[XOR-SAT]]<tex>^\star</tex>#[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]#[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 0,25## См. также #[[Полные системы функций. Теорема Поста о полной системе функций]] 0,25## См. также#[[Представление функции класса DM с помощью медианы]] 0.252-10 ## СмДобавить см. также## Правильно оформить источники информации## Исправить знаки неравенств## Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)#[[Пороговая функция]] 0.25## См. также
#[[Троичная логика]]<tex>^\star</tex>
== 3 Схемы из функциональных элементов ==
#[[Реализация булевой функции схемой из функциональных элементов]]5## Добавить информацию о методе построения схемы по функции ## Добавить алгоритм вычисления глубины схемы## Добавить картинки к доказательствам#[[Простейшие методы синтеза схем из функциональных элементов]] 0.5## Изменить знаки неравенств6## Ссылку Добавить примеры на каждый метод синтеза схем Шэннона сделать примечанием## Определение жирным## Оформить правильно См. также и Источники информации## Увеличить дроби#[[Метод Лупанова синтеза схем]] 0.5## Заменить литературу на Правильно оформить источники информации## Изменить знаки неравенств## Запятые криво стоят в определении функции g## Увеличить дроби
#[[Cумматор]]
#[[Каскадный сумматор]]
#[[Двоичный каскадный сумматор]]5## Сделать конспект более понятным
#[[Троичный сумматор]]<tex>^\star</tex>
#[[Реализация вычитания сумматором]]
#[[Дерево Уоллеса]]
#[[Контактная схема]] 1
## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов
#[[Триггеры]]<tex>^\star</tex>
#[[Квантовые гейты]]<tex>^\star</tex>
# [[Алгоритм Хаффмана]]
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
# [[Алгоритм Хаффмана за O(n)]] 10.5## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё окИсточники информации
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
# [[Неравенство Крафта]]5-10## Доказательство вообще не о том, требуется полностью переписать# [[Неравенство Макмиллана]]2-5## Доказательство требует косметических правок
# [[Код Шеннона]]
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
=== 3 Подсчёт числа объектов ===
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]1## в первой теореме в доказательстве по индукции получен результат не тот, что в условии# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] 0,5## Сделать через tex возведение в степень в заголовках## См. также# [[Производящая функция]] 0,25## См. также
# [[Лемма Бёрнсайда и Теорема Пойа]]
# [[Задача об ожерельях]]
# [[Числа Стирлинга первого рода]] 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 рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> 0,25## См. также# [[Числа Каталана]] 0,255
## См. также
# [[Конструирование комбинаторных объектов и их подсчет]]
=== 4 Свойства комбинаторных объектов ===
# [[Умножение перестановок, обратная перестановка, группа перестановок]] 5## Английские термины## Определения жирным## Тут вообще неправильно описано умножение перестановок (не путать с подстановками)## Отформатировать псевдокоды## Все переменные и константы взять в Tex## Оформить правильно источники информации## Добавить примеров из конспекта групп по теории чисел## Добавить реккурентную формулу числа инволюций c доказательством
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
# [[Таблица инверсий]] 0,25
# [[Теорема Кэли]]
# [[Матричное представление перестановок]]
# [[Задача о минимуме/максимуме скалярного произведения]] 0,25## Cм. также# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] 0.25## См. также
