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