3622
правки
Изменения
Новая страница: «Категория:Дискретная математика и алгоритмы Убедительная просьба читать [[Обсуждение...»
[[Категория:Дискретная математика и алгоритмы]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]
*[[XOR-SAT]]<tex>^\star</tex>
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>
== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Алгоритм LZMA]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Монотонный код Грея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]
=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]
=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]
=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>
*[[Convex hull trick]]
=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]
*[[XOR-SAT]]<tex>^\star</tex>
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>
== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Алгоритм LZMA]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Монотонный код Грея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]
=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]
=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]
=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>
*[[Convex hull trick]]
=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]
