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