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