Дискретная математика — различия между версиями
(→Производящая функция) |
SchrodZzz (обсуждение | вклад) (→Алгоритмы сжатия: - добавлена ссылка на статью Контекстное моделирование) |
||
| (не показано 7 промежуточных версий 5 участников) | |||
| Строка 31: | Строка 31: | ||
*[[Полные системы функций. Теорема Поста о полной системе функций]] | *[[Полные системы функций. Теорема Поста о полной системе функций]] | ||
*[[Представление функции класса DM с помощью медианы]] | *[[Представление функции класса DM с помощью медианы]] | ||
| + | *[[Выражение функции XOR через медианы]] | ||
*[[Пороговая функция]] | *[[Пороговая функция]] | ||
*[[Троичная логика]]<tex>^\star</tex> | *[[Троичная логика]]<tex>^\star</tex> | ||
| Строка 37: | Строка 38: | ||
*[[Реализация булевой функции схемой из функциональных элементов]] | *[[Реализация булевой функции схемой из функциональных элементов]] | ||
*[[Простейшие методы синтеза схем из функциональных элементов]] | *[[Простейшие методы синтеза схем из функциональных элементов]] | ||
| + | *[[Шифратор и дешифратор]] | ||
| + | *[[Мультиплексор и демультиплексор]] | ||
*[[Метод Лупанова синтеза схем]] | *[[Метод Лупанова синтеза схем]] | ||
*[[Cумматор]] | *[[Cумматор]] | ||
| Строка 48: | Строка 51: | ||
*[[Триггеры]]<tex>^\star</tex> | *[[Триггеры]]<tex>^\star</tex> | ||
*[[Квантовые гейты]]<tex>^\star</tex> | *[[Квантовые гейты]]<tex>^\star</tex> | ||
| + | *[[Квантовые алгоритмы]]<tex>^\star</tex> | ||
== Представление информации == | == Представление информации == | ||
| Строка 73: | Строка 77: | ||
* [[Избыточное кодирование, код Хэмминга]] | * [[Избыточное кодирование, код Хэмминга]] | ||
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> | * [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> | ||
| + | * [[Арифметическое кодирование]] | ||
| + | * [[Контекстное моделирование]] | ||
== Комбинаторика == | == Комбинаторика == | ||
| Строка 93: | Строка 99: | ||
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] | * [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] | ||
* [[Методы генерации случайного сочетания]]<tex>^\star</tex> | * [[Методы генерации случайного сочетания]]<tex>^\star</tex> | ||
| + | * [[Методы получения случайных комбинаторных объектов]] | ||
=== Подсчёт числа объектов === | === Подсчёт числа объектов === | ||
Версия 14:50, 7 января 2019
Убедительная просьба читать правила оформления вики-конспектов.
Символом помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
Содержание
Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Выражение функции XOR через медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Шифратор и дешифратор
- Мультиплексор и демультиплексор
- Метод Лупанова синтеза схем
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
- Квантовые алгоритмы
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
- Арифметическое кодирование
- Контекстное моделирование
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
- Методы получения случайных комбинаторных объектов
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Символ Похгаммера
- Числа Белла
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
- Конструирование комбинаторных объектов и их подсчет
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Производящая функция
- Арифметические действия с формальными степенными рядами
- Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
- Использование производящих функций для доказательства тождеств
- Производящие функции нескольких переменных
- Разложение рациональной функции в ряд
- Представление производящей функций в виде непрерывных дробей
- Задача о счастливых билетах
- Произведение Адамара
- Интегрирование/дифференцирование производящих функций
- Производящая функция Дирихле
- Решение рекуррентных соотношений
- Язык Дика
- Уравнение Лагранжа и теорема Лагранжа
- Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа
