Дискретная математика — различия между версиями
(→Производящая функция) |
м (rollbackEdits.php mass rollback) |
||
| (не показана 41 промежуточная версия 22 участников) | |||
| Строка 3: | Строка 3: | ||
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса. | Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса. | ||
| + | |||
| + | [https://youtube.com/andrewzta видеолекции Андрея Станкевича] | ||
== Отношения == | == Отношения == | ||
| + | *[[Множества]] | ||
*[[Определение отношения]] | *[[Определение отношения]] | ||
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] | *[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] | ||
| Строка 31: | Строка 34: | ||
*[[Полные системы функций. Теорема Поста о полной системе функций]] | *[[Полные системы функций. Теорема Поста о полной системе функций]] | ||
*[[Представление функции класса DM с помощью медианы]] | *[[Представление функции класса DM с помощью медианы]] | ||
| + | *[[Выражение функции XOR через медианы]] | ||
*[[Пороговая функция]] | *[[Пороговая функция]] | ||
*[[Троичная логика]]<tex>^\star</tex> | *[[Троичная логика]]<tex>^\star</tex> | ||
| Строка 37: | Строка 41: | ||
*[[Реализация булевой функции схемой из функциональных элементов]] | *[[Реализация булевой функции схемой из функциональных элементов]] | ||
*[[Простейшие методы синтеза схем из функциональных элементов]] | *[[Простейшие методы синтеза схем из функциональных элементов]] | ||
| + | *[[Шифратор и дешифратор]] | ||
| + | *[[Мультиплексор и демультиплексор]] | ||
*[[Метод Лупанова синтеза схем]] | *[[Метод Лупанова синтеза схем]] | ||
| + | *[[Представление булевых функций линейными программами]] | ||
| + | *[[Нижняя оценка размера схем из функциональных элементов]] | ||
*[[Cумматор]] | *[[Cумматор]] | ||
*[[Каскадный сумматор]] | *[[Каскадный сумматор]] | ||
| Строка 48: | Строка 56: | ||
*[[Триггеры]]<tex>^\star</tex> | *[[Триггеры]]<tex>^\star</tex> | ||
*[[Квантовые гейты]]<tex>^\star</tex> | *[[Квантовые гейты]]<tex>^\star</tex> | ||
| + | *[[Квантовые алгоритмы]]<tex>^\star</tex> | ||
== Представление информации == | == Представление информации == | ||
| Строка 57: | Строка 66: | ||
== Алгоритмы сжатия == | == Алгоритмы сжатия == | ||
* [[Алгоритм Хаффмана]] | * [[Алгоритм Хаффмана]] | ||
| − | |||
* [[Алгоритм Хаффмана за O(n)]] | * [[Алгоритм Хаффмана за O(n)]] | ||
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex> | * [[Алгоритм Ху-Таккера]]<tex>^\star</tex> | ||
| Строка 72: | Строка 80: | ||
* [[Расстояние Хэмминга]] | * [[Расстояние Хэмминга]] | ||
* [[Избыточное кодирование, код Хэмминга]] | * [[Избыточное кодирование, код Хэмминга]] | ||
| + | * [[Обнаружение и исправление ошибок кодирования]] | ||
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> | * [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> | ||
| + | * [[Арифметическое кодирование]] | ||
| + | * [[Контекстное моделирование]] | ||
== Комбинаторика == | == Комбинаторика == | ||
| Строка 93: | Строка 104: | ||
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] | * [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] | ||
* [[Методы генерации случайного сочетания]]<tex>^\star</tex> | * [[Методы генерации случайного сочетания]]<tex>^\star</tex> | ||
| + | * [[Методы получения случайных комбинаторных объектов]] | ||
=== Подсчёт числа объектов === | === Подсчёт числа объектов === | ||
| Строка 101: | Строка 113: | ||
* [[Числа Стирлинга первого рода]] | * [[Числа Стирлинга первого рода]] | ||
* [[Числа Стирлинга второго рода]] | * [[Числа Стирлинга второго рода]] | ||
| + | * [[Символ Похгаммера]] | ||
| + | * [[Числа Белла]] | ||
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> | * [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> | ||
* [[Числа Каталана]] | * [[Числа Каталана]] | ||
| + | * [[Конструирование комбинаторных объектов и их подсчет]] | ||
| + | * [[Подсчет деревьев]] | ||
| + | * [[Метод производящих функций]] | ||
=== Свойства комбинаторных объектов === | === Свойства комбинаторных объектов === | ||
| Строка 113: | Строка 130: | ||
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | * [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | ||
| − | == [[Производящая функция]] | + | === Производящие функции === |
| + | * [[Производящая функция]] | ||
* [[Арифметические действия с формальными степенными рядами]] | * [[Арифметические действия с формальными степенными рядами]] | ||
| + | * [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] | ||
| + | * [[Асимптотическое поведение последовательности, заданной рекуррентным соотношением]] | ||
| + | * [[Использование производящих функций для доказательства тождеств]] | ||
* [[Производящие функции нескольких переменных]] | * [[Производящие функции нескольких переменных]] | ||
* [[Разложение рациональной функции в ряд]] | * [[Разложение рациональной функции в ряд]] | ||
| − | + | * [[Представление производящей функций в виде непрерывных дробей]] | |
| − | + | * [[Задача о счастливых билетах]] | |
| − | + | * [[Произведение Адамара рациональных производящих функций|Произведение Адамара]] | |
| − | *[[ | + | * [[Интегрирование/дифференцирование производящих функций]] |
| − | *[[Задача о | + | * [[Производящая функция Дирихле]] |
| − | *[[ | + | * [[Решение рекуррентных соотношений]] |
| − | *[[ | + | * [[Язык Дика]] |
| − | + | * [[Уравнение Лагранжа и теорема Лагранжа]] | |
| − | + | *[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]] | |
| − | + | * [[Обращение Лагранжа]] | |
| − | + | * [[Автокорреляционный многочлен]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | *[[ | ||
| − | *[[ | ||
| − | *[[ | ||
| − | *[[ | ||
| − | *[[ | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | *[[ | ||
| − | *[[ | ||
| − | |||
| − | |||
| − | |||
Текущая версия на 19:40, 4 сентября 2022
Убедительная просьба читать правила оформления вики-конспектов.
Символом помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
Содержание
Отношения
- Множества
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Выражение функции XOR через медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Шифратор и дешифратор
- Мультиплексор и демультиплексор
- Метод Лупанова синтеза схем
- Представление булевых функций линейными программами
- Нижняя оценка размера схем из функциональных элементов
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
- Квантовые алгоритмы
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Обнаружение и исправление ошибок кодирования
- Гамма-, дельта- и омега-код Элиаса
- Арифметическое кодирование
- Контекстное моделирование
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
- Методы получения случайных комбинаторных объектов
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Символ Похгаммера
- Числа Белла
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
- Конструирование комбинаторных объектов и их подсчет
- Подсчет деревьев
- Метод производящих функций
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Производящие функции
- Производящая функция
- Арифметические действия с формальными степенными рядами
- Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
- Асимптотическое поведение последовательности, заданной рекуррентным соотношением
- Использование производящих функций для доказательства тождеств
- Производящие функции нескольких переменных
- Разложение рациональной функции в ряд
- Представление производящей функций в виде непрерывных дробей
- Задача о счастливых билетах
- Произведение Адамара
- Интегрирование/дифференцирование производящих функций
- Производящая функция Дирихле
- Решение рекуррентных соотношений
- Язык Дика
- Уравнение Лагранжа и теорема Лагранжа
- Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа
- Обращение Лагранжа
- Автокорреляционный многочлен
