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