|
|
| (не показано 155 промежуточных версий 45 участников) |
| Строка 1: |
Строка 1: |
| − | == Отношения ==
| + | #перенаправление [[Дискретная математика, алгоритмы и структуры данных]] |
| − | *Определение отношения
| + | [[Категория:Дискретная математика и алгоритмы]] |
| − | *Степень отношений
| |
| − | *[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
| |
| − | *[[Симметричное отношение]]
| |
| − | *[[Антисимметричное отношение]]
| |
| − | *[[Композиция отношений|Композиция отношений. Обратное отношение]]
| |
| − | *[[Транзитивное отношение]]
| |
| − | *[[Транзитивное замыкание|Транзитивное замыкание отношения]]
| |
| − | *[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
| |
| − | | |
| − | == Булевы функции ==
| |
| − | *[[Определение булевой функции]]
| |
| − | *[[Примеры булевых функций|Примеры булевых функций: все функции от нуля, одной и двух переменных]]
| |
| − | *Подстановка одной функции в другую, отождествление переменных
| |
| − | *Представление функции формулой, полные системы функций
| |
| − | *[[СДНФ]]
| |
| − | *[[СКНФ]]
| |
| − | *[[Полином Жегалкина]]
| |
| − | *[[Теорема Поста о полной системе функций]]
| |
| − | *[[Сокращенная и минимальная ДНФ]]
| |
| − | *[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
| |
| − | *[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
| |
| − | *[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
| |
| − | | |
| − | == Схемы из функциональных элементов ==
| |
| − | *[[Реализация булевой функции схемой из функциональных элементов]]
| |
| − | *[[Изменение размера оптимальной схемы при переходе к другому базису]]
| |
| − | *[[Cумматор]]
| |
| − | *[[Каскадный сумматор]]
| |
| − | *[[Двоичный каскадный сумматор]]
| |
| − | *[[Матричный умножитель]]
| |
| − | *[[Дерево Уоллеса]]
| |
| − | | |
| − | == Представление информации ==
| |
| − | *[[Кодирование информации]]
| |
| − | *[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
| |
| − | *[[Представление вещественных чисел]]
| |
| − | *[[Представление символов, таблицы кодировок]]
| |
| − | *[[Алгоритм Хаффмана]]
| |
| − | | |
| − | == Алгоритмы сжатия ==
| |
| − | *[[Алгоритм LZW]]
| |
| − | *[[Алгоритмы LZ77 и LZ78]]
| |
| − | *[[Преобразование Барроуза-Уиллера]]
| |
| − | *[[Преобразование MTF]]
| |
| − | *[[Расстояние Хэмминга]]
| |
| − | *[[Избыточное кодирование, код Хэмминга]]
| |
| − | | |
| − | == Комбинаторика ==
| |
| − | *[[Комбинаторные объекты]]
| |
| − | *[[Лексикографический порядок]]
| |
| − | *[[Формула включения-исключения]]
| |
| − | *[[Генерация комбинаторных объектов в лексикографическом порядке]]
| |
| − | *[[Получение номера об объекту и объекта по номеру]]
| |
| − | *[[Получение следующего объекта]]
| |
| − | *[[Коды Грея]]
| |
| − | *[[Коды Грея для перестановок]]
| |
| − | *[[Цепные коды]]
| |
| − | *[[Таблица инверсий]]
| |
| − | *[[Теорема Кэли]]
| |
| − | *[[Задача о минимуме/максимуме скалярного произведения]]
| |
| − | *[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
| |
| − | *[[Поиск наибольшей возрастающей подпоследовательности и т. д.]]
| |
| − | | |
| − | == Динамическое программирование ==
| |
| − | *[[Задача о расстановке знаков в выражении]]
| |
| − | *[[Задача о наибольшей общей подпоследовательности]]
| |
| − | *[[Задача о наибольшей возрастающей подпоследовательности]]
| |
| − | *[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
| |
| − | *[[Метод четырех русских для умножения матриц]]
| |
| − | *[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
| |
| − | *[[Задача коммивояжера, ДП по подмножествам]]
| |
| − | | |
| − | == Теория вероятности ==
| |
| − | *[[Формула Байеса]]
| |
| − | *[[Случайная величина]]
| |
