Дискретная математика, алгоритмы и структуры данных — различия между версиями
(→Амортизационный анализ) |
Yurik (обсуждение | вклад) |
||
| Строка 186: | Строка 186: | ||
== Сортировка == | == Сортировка == | ||
| + | * [[Теорема об энтропийном барьере|Теорема об энтропийном барьере (время работы сортировок)]] | ||
* [[Сортировка пузырьком]] | * [[Сортировка пузырьком]] | ||
* [[Сортировка слиянием]] | * [[Сортировка слиянием]] | ||
Версия 23:03, 1 марта 2012
Убедительная просьба читать правила оформления вики-конспектов!
Содержание
- 1 Первый семестр
- 2 Второй семестр
- 3 Третий семестр
- 3.1 Основные определения теории графов
- 3.2 Связность в графах
- 3.3 Остовные деревья
- 3.4 Обходы графов
- 3.5 Укладки графов
- 3.6 Раскраски графов
- 3.7 Обход в глубину
- 3.8 Кратчайшие пути в графах
- 3.9 Остовные деревья
- 3.10 Задача о паросочетании
- 3.11 Задача о максимальном потоке
- 3.12 Задача о потоке минимальной стоимости
- 4 Четвертый семестр
Первый семестр
Отношения
- Определение отношения
- Степень отношений
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Композиция отношений. Обратное отношение
- Транзитивное отношение
- Транзитивное замыкание отношения
- Отношение порядка
- Отношение эквивалентности
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
Булевы функции
- Определение булевой функции
- Суперпозиции
- ДНФ
- КНФ
- Полином Жегалкина
- Полные системы функций. Теорема Поста о полной системе функций
- Сокращенная и минимальная ДНФ
- Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
- Представление функции класса DM с помощью медианы
- Пороговая функция
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Алгоритм LZW
- Алгоритмы LZ77 и LZ78
- Преобразование Барроуза-Уиллера
- Обратное преобразование Барроуза-Уиллера
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Неравенство Крафта
- Неравенство Макмиллана
Комбинаторика
- Комбинаторные объекты
- Лексикографический порядок
- Формула включения-исключения
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Коды Грея
- Коды Грея для перестановок
- Цепные коды
- Правильные скобочные последовательности
- Действие перестановки на набор из элементов, представление в виде циклов
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Таблица инверсий
- Умножение перестановок, обратная перестановка, группа перестановок
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о наибольшей общей подпоследовательности
- Задача о порядке перемножения матриц
- Задача о наибольшей возрастающей подпоследовательности
- Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача коммивояжера, ДП по подмножествам
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о расстоянии Дамерау-Левенштейна
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула Байеса
- Формула полной вероятности
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Ковариация случайных величин
- Дисперсия случайной величины
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Задача о двух конвертах
Марковские цепи
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
Второй семестр
Амортизационный анализ
- Амортизационный анализ
- Саморасширяющийся массив
- Массив с увеличением/уменьшением размера
- Стек
- Очередь
- Список
- Персистентный стек
Приоритетные очереди
Система непересекающихся множеств
- Наивные реализации
- Списки с весовой эвристикой
- Реализация с помощью леса корневых деревьев
- Анализ реализации с ранговой эвристикой
Деревья поиска
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Splay-дерево
- Декартово дерево по неявному ключу
- Дерево ван Эмде Боаса
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
Хеширование
- Хеширование
- Открытое и закрытое хеширование
- Поиск свободного места при закрытом хешировании
- Хеширование кукушки
- Двойное хеширование
- Перехеширование. Амортизационный анализ
- Фильтр Блума
- Универсальное семейство хеш-функций
Сортировка
- Теорема об энтропийном барьере (время работы сортировок)
- Сортировка пузырьком
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Сортировка вставками
- Сортировка подсчетом
- Сортировка подсчетом сложных объектов
- Цифровая сортировка
- Поиск k-ой порядковой статистики
- Поиск k-й порядковой статистики за линейное время
- Теорема о нижней оценке для сортировки сравнениями
- Быстрая сортировка
Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сеть Бетчера
Алгоритмы поиска
Третий семестр
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Гамильтоновы графы
- Теорема Хватала
- Следствия теоремы Хватала:
- Теорема Оре
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Двойственный граф планарного графа
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм A*
- Алгоритм Джонсона
Остовные деревья
- Лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Блокирующий поток
- Схема алгоритма Диница
- Циркуляция потока
- Алгоритм поиска блокирующего потока в ациклической сети
- Алгоритм масштабирования потока
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
Четвертый семестр
Поиск подстроки в строке
- Наивный алгоритм поиска подстроки в строке
- Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- Префикс-функция
- Алгоритм Кнута-Морриса-Пратта
- Z-функция
- Автомат для поиска образца в тексте
- Бор
- Алгоритм Ахо-Корасик
Словарные структуры данных
Задача о наименьшем общем предке
- Метод двоичного подъема
- Сведение задачи LCA к задаче RMQ
- Решение RMQ с помощью разреженной таблицы
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четверых русских)
- Сведение задачи RMQ к задаче LCA
Суффиксный массив
- Суффиксный массив
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм цифровой сортировки
- Алгоритм цифровой сортировки суффиксов циклической строки
- Алгоритм Касаи и др.
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
Матроиды
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Жадный алгоритм поиска базы минимального веса
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Двойственный матроид
- Оператор замыкания для матроидов
- Пересечение матроидов, определение, примеры
- Лемма о паросочетании в графе замен
- Лемма о единственном паросочетании в графе замен
- Граф замен для двух матроидов
- Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
- Алгоритм построения базы в пересечении матроидов
- Теорема Эдмондса-Лоулера
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
- Алгоритм построения базы в объединении матроидов
