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