Дискретная математика:Тикеты — различия между версиями
м (→2 Булевы функции) |
(→2 Генерация комбинаторных объектов) |
||
(не показаны 34 промежуточные версии 3 участников) | |||
Строка 2: | Строка 2: | ||
== 1. Отношения == | == 1. Отношения == | ||
− | #[[Определение отношения]] | + | # [[Определение отношения]] |
− | + | # [[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] | |
− | + | # [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | |
− | #[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] | + | # [[Симметричное отношение]] |
− | + | # [[Антисимметричное отношение]] | |
− | + | # [[Транзитивное отношение]] | |
− | + | # [[Отношение порядка]] | |
− | + | # [[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex> | |
− | + | # [[Отношение эквивалентности]] | |
− | #[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | + | # [[Транзитивное замыкание|Транзитивное замыкание отношения]] |
− | + | # [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | |
− | #[[Симметричное отношение]] | + | # [[Транзитивный остов]] |
− | #[[Антисимметричное отношение]] | ||
− | #[[Транзитивное отношение]] | ||
− | |||
− | #[[Отношение порядка]] | ||
− | |||
− | |||
− | |||
− | #[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex> | ||
− | #[[Отношение эквивалентности]] | ||
− | |||
− | #[[Транзитивное замыкание|Транзитивное замыкание отношения]] | ||
− | |||
− | |||
− | #[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | ||
− | #[[Транзитивный остов]] | ||
− | |||
== 2 Булевы функции == | == 2 Булевы функции == | ||
− | # | + | # [[Определение булевой функции]] 0,5 |
− | ## | + | ## исправить знаки неравенств |
− | + | # [[Побитовые операции]]<tex>^\star</tex> | |
− | # | + | # [[Суперпозиции]] 2 |
− | + | ## Дописать раздел про ранги суперпозиций | |
− | #[[Суперпозиции]] | + | # [[ДНФ]] |
− | ## | ||
− | |||
− | # | ||
− | |||
− | |||
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] | #[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] | ||
− | # | + | # [[КНФ]] |
− | + | # [[2-SAT]] | |
− | + | # [[XOR-SAT]]<tex>^\star</tex> | |
− | + | # [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] | |
− | #[[2-SAT]] | + | # [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] |
− | #[[XOR-SAT]]<tex>^\star</tex> | + | # [[Полные системы функций. Теорема Поста о полной системе функций]] |
− | #[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] | + | # [[Представление функции класса DM с помощью медианы]] 2-10 |
− | #[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] | ||
− | |||
− | |||
− | |||
− | #[[Полные системы функций. Теорема Поста о полной системе функций]] | ||
− | |||
− | #[[Представление функции класса DM с помощью медианы]] | ||
## Добавить см. также | ## Добавить см. также | ||
## Правильно оформить источники информации | ## Правильно оформить источники информации | ||
− | ## | + | ## Исправить знаки неравенств |
− | #[[Пороговая функция]] | + | ## Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов) |
− | + | # [[Пороговая функция]] | |
− | |||
#[[Троичная логика]]<tex>^\star</tex> | #[[Троичная логика]]<tex>^\star</tex> | ||
== 3 Схемы из функциональных элементов == | == 3 Схемы из функциональных элементов == | ||
− | #[[Реализация булевой функции схемой из функциональных элементов]] | + | #[[Реализация булевой функции схемой из функциональных элементов]] 5 |
− | #[[Простейшие методы синтеза схем из функциональных элементов]] | + | ## Добавить информацию о методе построения схемы по функции |
− | + | ## Добавить алгоритм вычисления глубины схемы | |
− | ## | + | ## Добавить картинки к доказательствам |
− | + | # [[Простейшие методы синтеза схем из функциональных элементов]] 6 | |
− | + | ## Добавить примеры на каждый метод | |
− | + | # [[Метод Лупанова синтеза схем]] 0.5 | |
− | #[[Метод Лупанова синтеза схем]] 0.5 | + | ## Правильно оформить источники информации |
− | ## | ||
− | |||
− | |||
− | |||
#[[Cумматор]] | #[[Cумматор]] | ||
#[[Каскадный сумматор]] | #[[Каскадный сумматор]] | ||
− | #[[Двоичный каскадный сумматор]] | + | #[[Двоичный каскадный сумматор]] 5 |
+ | ## Сделать конспект более понятным | ||
#[[Троичный сумматор]]<tex>^\star</tex> | #[[Троичный сумматор]]<tex>^\star</tex> | ||
#[[Реализация вычитания сумматором]] | #[[Реализация вычитания сумматором]] | ||
Строка 87: | Строка 55: | ||
#[[Дерево Уоллеса]] | #[[Дерево Уоллеса]] | ||
#[[Контактная схема]] 1 | #[[Контактная схема]] 1 | ||
− | ## Перерисовать картинки с построением контактных схем и дерево конъюнктов | + | ## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов |
#[[Триггеры]]<tex>^\star</tex> | #[[Триггеры]]<tex>^\star</tex> | ||
#[[Квантовые гейты]]<tex>^\star</tex> | #[[Квантовые гейты]]<tex>^\star</tex> | ||
Строка 100: | Строка 68: | ||
# [[Алгоритм Хаффмана]] | # [[Алгоритм Хаффмана]] | ||
# [[Оптимальное хранение словаря в алгоритме Хаффмана]] | # [[Оптимальное хранение словаря в алгоритме Хаффмана]] | ||
− | # [[Алгоритм Хаффмана за O(n)]] | + | # [[Алгоритм Хаффмана за O(n)]] 0.5 |
− | ## | + | ## Источники информации |
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex> | # [[Алгоритм Ху-Таккера]]<tex>^\star</tex> | ||
− | # [[Неравенство Крафта]] | + | # [[Неравенство Крафта]] 5-10 |
− | # [[Неравенство Макмиллана]] | + | ## Доказательство вообще не о том, требуется полностью переписать |
+ | # [[Неравенство Макмиллана]] 2-5 | ||
+ | ## Доказательство требует косметических правок | ||
# [[Код Шеннона]] | # [[Код Шеннона]] | ||
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex> | # [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex> | ||
Строка 150: | Строка 120: | ||
=== 3 Подсчёт числа объектов === | === 3 Подсчёт числа объектов === | ||
− | # [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] | + | # [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] 1 |
− | # [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] | + | ## в первой теореме в доказательстве по индукции получен результат не тот, что в условии |
− | + | # [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] | |
− | |||
# [[Лемма Бёрнсайда и Теорема Пойа]] | # [[Лемма Бёрнсайда и Теорема Пойа]] | ||
# [[Задача об ожерельях]] | # [[Задача об ожерельях]] | ||
# [[Числа Стирлинга первого рода]] 5 | # [[Числа Стирлинга первого рода]] 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>? | ## <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, | + | # [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]] |
+ | # [[Числа Каталана]] 0,5 | ||
## См. также | ## См. также | ||
+ | # [[Конструирование комбинаторных объектов и их подсчет]] | ||
=== 4 Свойства комбинаторных объектов === | === 4 Свойства комбинаторных объектов === | ||
− | # [[Умножение перестановок, обратная перестановка, группа перестановок]] | + | # [[Умножение перестановок, обратная перестановка, группа перестановок]] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
# [[Действие перестановки на набор из элементов, представление в виде циклов]] | # [[Действие перестановки на набор из элементов, представление в виде циклов]] | ||
# [[Таблица инверсий]] 0,25 | # [[Таблица инверсий]] 0,25 | ||
Строка 180: | Строка 144: | ||
# [[Теорема Кэли]] | # [[Теорема Кэли]] | ||
# [[Матричное представление перестановок]] | # [[Матричное представление перестановок]] | ||
− | # [[Задача о минимуме/максимуме скалярного произведения]] | + | # [[Задача о минимуме/максимуме скалярного произведения]] |
− | + | # [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | |
− | # [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | ||
− |
Текущая версия на 23:03, 13 декабря 2018
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)
1. Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
2 Булевы функции
- Определение булевой функции 0,5
- исправить знаки неравенств
- Побитовые операции
- Суперпозиции 2
- Дописать раздел про ранги суперпозиций
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы 2-10
- Добавить см. также
- Правильно оформить источники информации
- Исправить знаки неравенств
- Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
- Пороговая функция
- Троичная логика
3 Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов 5
- Добавить информацию о методе построения схемы по функции
- Добавить алгоритм вычисления глубины схемы
- Добавить картинки к доказательствам
- Простейшие методы синтеза схем из функциональных элементов 6
- Добавить примеры на каждый метод
- Метод Лупанова синтеза схем 0.5
- Правильно оформить источники информации
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор 5
- Сделать конспект более понятным
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема 1
- взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов
- Триггеры
- Квантовые гейты
4 Представление информации
5 Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n) 0.5
- Источники информации
- Алгоритм Ху-Таккера
- Неравенство Крафта 5-10
- Доказательство вообще не о том, требуется полностью переписать
- Неравенство Макмиллана 2-5
- Доказательство требует косметических правок
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78 2
- Переменные и константы взять в Tex
- Добавить примеры итоговых таблиц
- Рассказать, как декодировать
- Правильно оформить источники информации
- Получше расписать описание алгоритма
- Таблицы сделать красивыми
- Интервики
- Алгоритм LZW 0,25
- См. также
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга 0,25
- См. также
- Гамма-, дельта- и омега-код Элиаса 0,25
- См. также
6 Комбинаторика
1 Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
2 Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке 0.5
- Заменить скобки "больше-меньше" на угловые
- Нормальную красивую картинку нарисовать
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
3 Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков 1
- в первой теореме в доказательстве по индукции получен результат не тот, что в условии
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода 5
- то есть результат не зависит от ?
- Поправить тех
- доказательства дополнительных тождеств
- Числа Стирлинга второго рода
- Символ Похгаммера
- Числа Белла
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана 0,5
- См. также
- Конструирование комбинаторных объектов и их подсчет
4 Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий 0,25
- tex в заголовок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП