Изменения
Новая страница: «Категория:Дискретная математика и алгоритмы Убедительная просьба читать [[Обсуждени...»
[[Категория:Дискретная математика и алгоритмы]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]!
= Первый семестр =
== Отношения ==
*[[Определение отношения]]
*[[Степень отношений]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[КНФ]]
*[[Полином Жегалкина]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]
== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Обратное преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]
*[[Неравенство Крафта]]
*[[Неравенство Макмиллана]]
== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
*[[Получение объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]
== [[Динамическое программирование]] ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о расстоянии Дамерау-Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула Байеса]]
*[[Формула полной вероятности]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Ковариация случайных величин]]
*[[Дисперсия случайной величины]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Задача о двух конвертах]]
== [[Марковская цепь|Марковские цепи]] ==
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
= Второй семестр =
== Амортизационный анализ ==
* [[Амортизационный анализ. Метод предоплаты]]
* [[Саморасширяющийся массив]]
* [[Массив с увеличением/уменьшением размера]]
* [[Стек]]
* [[Очередь]]
* [[Список]]
== Приоритетные очереди ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиевы кучи]]
== Система непересекающихся множеств ==
* [[СНМ(наивные реализации) | Наивные реализации]]
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[Анализ реализации с ранговой эвристикой | Анализ реализации с ранговой эвристикой]]
== Деревья поиска ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Splay-дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Дерево ван Эмде Боаса]]
== Дерево отрезков ==
* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]
== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]
== Хеширование ==
* [[Хеширование]]
* [[Открытое и закрытое хеширование]]
* [[Поиск свободного места при закрытом хешировании]]
* [[Хеширование кукушки]]
* [[Двойное хеширование]]
* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Универсальное семейство хеш-функций]]
== Сортировка ==
* [[Сортировка пузырьком]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Сортировка вставками]]
* [[Сортировка подсчетом]]
* [[Сортировка подсчетом сложных объектов]]
* [[Цифровая сортировка]]
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-й порядковой статистики за линейное время]]
* [[Теорема о нижней оценке для сортировки сравнениями]]
* [[Быстрая сортировка]]
== [[Сортирующие сети]] ==
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сеть Бетчера]]
== Алгоритмы поиска ==
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Вещественный двоичный поиск]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]!
= Первый семестр =
== Отношения ==
*[[Определение отношения]]
*[[Степень отношений]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[КНФ]]
*[[Полином Жегалкина]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]
== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Обратное преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]
*[[Неравенство Крафта]]
*[[Неравенство Макмиллана]]
== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
*[[Получение объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]
== [[Динамическое программирование]] ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о расстоянии Дамерау-Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула Байеса]]
*[[Формула полной вероятности]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Ковариация случайных величин]]
*[[Дисперсия случайной величины]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Задача о двух конвертах]]
== [[Марковская цепь|Марковские цепи]] ==
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
= Второй семестр =
== Амортизационный анализ ==
* [[Амортизационный анализ. Метод предоплаты]]
* [[Саморасширяющийся массив]]
* [[Массив с увеличением/уменьшением размера]]
* [[Стек]]
* [[Очередь]]
* [[Список]]
== Приоритетные очереди ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиевы кучи]]
== Система непересекающихся множеств ==
* [[СНМ(наивные реализации) | Наивные реализации]]
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[Анализ реализации с ранговой эвристикой | Анализ реализации с ранговой эвристикой]]
== Деревья поиска ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Splay-дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Дерево ван Эмде Боаса]]
== Дерево отрезков ==
* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]
== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]
== Хеширование ==
* [[Хеширование]]
* [[Открытое и закрытое хеширование]]
* [[Поиск свободного места при закрытом хешировании]]
* [[Хеширование кукушки]]
* [[Двойное хеширование]]
* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Универсальное семейство хеш-функций]]
== Сортировка ==
* [[Сортировка пузырьком]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Сортировка вставками]]
* [[Сортировка подсчетом]]
* [[Сортировка подсчетом сложных объектов]]
* [[Цифровая сортировка]]
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-й порядковой статистики за линейное время]]
* [[Теорема о нижней оценке для сортировки сравнениями]]
* [[Быстрая сортировка]]
== [[Сортирующие сети]] ==
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сеть Бетчера]]
== Алгоритмы поиска ==
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Вещественный двоичный поиск]]
