Дискретная математика и алгоритмы — различия между версиями

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

Текущая версия на 15:51, 10 марта 2012