Дискретная математика:Тикеты — различия между версиями
(→Отношения) |
(→Булевы функции) |
||
| Строка 28: | Строка 28: | ||
== Булевы функции == | == Булевы функции == | ||
| − | + | #[[Определение булевой функции]] 0,5 | |
| − | + | ## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]]) | |
| − | + | #[[Побитовые операции]]<tex>^\star</tex> | |
| − | + | #[[Суперпозиции]] 0,25 | |
| − | + | ## См. также | |
| − | + | #[[ДНФ]] | |
| − | + | #[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] | |
| − | + | #[[КНФ]] 0,25 | |
| − | + | ## См. также | |
| − | + | #[[2-SAT]] | |
| − | + | #[[XOR-SAT]]<tex>^\star</tex> | |
| − | + | #[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] | |
| − | + | #[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 0,25 | |
| − | + | ## См. также | |
| + | #[[Полные системы функций. Теорема Поста о полной системе функций]] 0,25 | ||
| + | ## См. также | ||
| + | #[[Представление функции класса DM с помощью медианы]] | ||
| + | ## См. также | ||
| + | #[[Пороговая функция]] | ||
| + | ## См. также | ||
| + | #[[Троичная логика]]<tex>^\star</tex> 0,25 | ||
| + | ## Английский термин | ||
== Схемы из функциональных элементов == | == Схемы из функциональных элементов == | ||
Версия 23:35, 28 февраля 2017
Содержание
1. Отношения
- Определение отношения 0.5
- Дефисы заменить на тире
- Оформить красиво источники информации
- Английские термины к видам отношений
- Композиция отношений, степень отношения, обратное отношение 2
- Английские термины
- Источники информации
- Свойства оформить красиво
- Свойства обратного отношения
- Рефлексивное отношение. Антирефлексивное отношение. 0,25
- См. также
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение 0,25
- См. также
- Отношение порядка 0,5
- Английские термины
- См. также
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности 0,25
- См. также
- Транзитивное замыкание отношения 0,25
- См. также
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов 0,25
- Английские термины
Булевы функции
- Определение булевой функции 0,5
- Добавить интервики на термины монотонности, линейности, сохранения и , самодвойственности для булевой функции. (все определения здесь)
- Побитовые операции
- Суперпозиции 0,25
- См. также
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ 0,25
- См. также
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса 0,25
- См. также
- Полные системы функций. Теорема Поста о полной системе функций 0,25
- См. также
- Представление функции класса DM с помощью медианы
- См. также
- Пороговая функция
- См. также
- Троичная логика 0,25
- Английский термин
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Метод Лупанова синтеза схем
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Динамическое программирование
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Быстрый поиск наибольшей возрастающей подпоследовательности*
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
- Convex hull trick
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Задача о наибольшей общей возрастающей последовательности
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю
- Динамика по поддеревьям
