Дискретная математика и алгоритмы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Приоритетные очереди)
 
Строка 1: Строка 1:
 +
#перенаправление [[Дискретная математика, алгоритмы и структуры данных]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
<center>
 
{| class=wikitable
 
|-
 
| style="vertical-align: middle;line-height:1.3;padding: 0px; width:45%;text-align: left; background-color:White; border-color:Purple; font-size:130%;font-family: Verdana, sans-serif; border-width: 1px 1px 1px 10px; padding: 4px; margin: 1px auto;" | [[Файл:Nohate.jpg|64px|left|nothumb]] <b>НЯ!</b><br>Эта статья полна любви и обожания.<br>Возможно, стоит добавить [[Теория сложности|ещё больше]]?
 
|}
 
</center>
 
<br>
 
 
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]!
 
 
 
= Первый семестр =
 
 
== Отношения ==
 
*[[Определение отношения]]
 
*[[Степень отношений]]
 
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
*[[Симметричное отношение]]
 
*[[Антисимметричное отношение]]
 
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
 
*[[Транзитивное отношение]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Отношение порядка]]
 
*[[Отношение эквивалентности]]
 
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 
 
== Булевы функции ==
 
*[[Определение булевой функции]]
 
*[[Суперпозиции]]
 
*[[ДНФ]]
 
*[[КНФ]]
 
*[[Полином Жегалкина]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Сокращенная и минимальная ДНФ]]
 
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Пороговая функция]]
 
 
== Схемы из функциональных элементов ==
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Cумматор]]
 
*[[Каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 
*[[Реализация вычитания сумматором]]
 
*[[Матричный умножитель]]
 
*[[Дерево Уоллеса]]
 
 
== Представление информации ==
 
*[[Кодирование информации]]
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление вещественных чисел]]
 
*[[Представление символов, таблицы кодировок]]
 
 
== Алгоритмы сжатия ==
 
*[[Алгоритм Хаффмана]]
 
*[[Алгоритм LZW]]
 
*[[Алгоритмы LZ77 и LZ78]]
 
*[[Преобразование Барроуза-Уиллера]]
 
*[[Обратное преобразование Барроуза-Уиллера]]
 
*[[Преобразование MTF]]
 
*[[Расстояние Хэмминга]]
 
*[[Избыточное кодирование, код Хэмминга]]
 
*[[Неравенство Крафта]]
 
*[[Неравенство Макмиллана]]
 
 
== Комбинаторика ==
 
*[[Комбинаторные объекты]]
 
*[[Лексикографический порядок]]
 
*[[Формула включения-исключения]]
 
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
 
*[[Получение номера по объекту]]
 
*[[Получение объекта по номеру]]
 
*[[Получение следующего объекта]]
 
*[[Коды Грея]]
 
*[[Коды Грея для перестановок]]
 
*[[Цепные коды]]
 
*[[Правильные скобочные последовательности]]
 
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
 
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
*[[Таблица инверсий]]
 
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
 
*[[Теорема Кэли]]
 
*[[Матричное представление перестановок]]
 
*[[Задача о минимуме/максимуме скалярного произведения]]
 
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 
*[[Производящая функция]]
 
 
== [[Динамическое программирование]] ==
 
*[[Кратчайший путь в ациклическом графе]]
 
*[[Задача о расстановке знаков в выражении]]
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о порядке перемножения матриц]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
 
*[[Метод четырех русских для умножения матриц]]
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о расстоянии Дамерау-Левенштейна]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
 
== Теория вероятностей ==
 
*[[Вероятностное пространство, элементарный исход, событие]]
 
*[[Независимые события]]
 
*[[Условная вероятность]]
 
*[[Формула Байеса]]
 
*[[Формула полной вероятности]]
 
*[[Дискретная случайная величина]]
 
*[[Независимые случайные величины]]
 
*[[Математическое ожидание случайной величины]]
 
*[[Ковариация случайных величин]]
 
*[[Дисперсия случайной величины]]
 
*[[Энтропия случайного источника]]
 
*[[Симуляция одним распределением другого]]
 
*[[Арифметическое кодирование]]
 
*[[Задача о двух конвертах]]
 
 
== [[Марковская цепь|Марковские цепи]] ==
 
 
* [[Теорема о поглощении]]
 
* [[Фундаментальная матрица]]
 
* [[Математическое ожидание времени поглощения]]
 
* [[Расчет вероятности поглощения в состоянии]]
 
* [[Эргодическая марковская цепь]]
 
* [[Регулярная марковская цепь]]
 
 
= Второй семестр =
 
 
== Амортизационный анализ ==
 
* [[Амортизационный анализ]]
 
* [[Саморасширяющийся массив]]
 
* [[Массив с увеличением/уменьшением размера]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Список]]
 
 
== Приоритетные очереди ==
 
 
* [[Двоичная куча]]
 
* [[Биномиальная куча]]
 
* [[Фибоначчиева куча]]
 
 
== Система непересекающихся множеств ==
 
* [[СНМ(наивные реализации) | Наивные реализации]]
 
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
* [[Анализ реализации с ранговой эвристикой  | Анализ реализации с ранговой эвристикой]]
 
 
== Деревья поиска ==
 
* [[Упорядоченное множество]]
 
* [[Дерево поиска, наивная реализация]]
 
* [[АВЛ-дерево]]
 
* [[2-3 дерево]]
 
* [[B-дерево]]
 
* [[Красно-черное дерево]]
 
* [[Декартово дерево]]
 
* [[Splay-дерево]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Дерево ван Эмде Боаса]]
 
 
== Дерево отрезков ==
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков снизу]]
 
* [[Несогласованные поддеревья. Реализация массового обновления]]
 
* [[Многомерное дерево отрезков]]
 
* [[Сжатое многомерное дерево отрезков]]
 
 
== Дерево Фенвика ==
 
* [[Дерево Фенвика]]
 
* [[Встречное дерево Фенвика]]
 
* [[Дерево Фенвика для некоммутативных операций]]
 
* [[Многомерное дерево Фенвика]]
 
 
== Хеширование ==
 
* [[Хеширование]]
 
* [[Открытое и закрытое хеширование]]
 
* [[Поиск свободного места при закрытом хешировании]]
 
* [[Хеширование кукушки]]
 
* [[Двойное хеширование]]
 
* [[Перехеширование. Амортизационный анализ]]
 
* [[Фильтр Блума]]
 
* [[Универсальное семейство хеш-функций]]
 
 
== Сортировка ==
 
* [[Сортировка пузырьком]]
 
* [[Сортировка слиянием]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
* [[Сортировка вставками]]
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом сложных объектов]]
 
* [[Цифровая сортировка]]
 
* [[Поиск k-ой порядковой статистики]]
 
* [[Поиск k-й порядковой статистики за линейное время]]
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 
* [[Быстрая сортировка]]
 
 
== [[Сортирующие сети]] ==
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сеть Бетчера]]
 
 
== Алгоритмы поиска ==
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Вещественный двоичный поиск]]
 
 
= [[Связь между структурами данных|Картинка от Комарова]] =
 

Текущая версия на 15:51, 10 марта 2012