Дискретная математика, алгоритмы и структуры данных — различия между версиями
Shersh (обсуждение | вклад) (→Поисковые структуры данных) |
Shersh (обсуждение | вклад) (→Третий семестр) |
||
| Строка 298: | Строка 298: | ||
* [[Связь степени матрицы смежности и количества путей]] | * [[Связь степени матрицы смежности и количества путей]] | ||
* [[Матрица инцидентности графа]] | * [[Матрица инцидентности графа]] | ||
| − | * [[Циклическое пространство графа]] | + | * [[Циклическое пространство графа]]<tex>^\star</tex> |
| − | * [[Фундаментальные циклы графа]] | + | * [[Фундаментальные циклы графа]]<tex>^\star</tex> |
* [[Дерево, эквивалентные определения]] | * [[Дерево, эквивалентные определения]] | ||
| − | * [[Алгоритмы на деревьях]] | + | * [[Алгоритмы на деревьях]]<tex>^\star</tex> |
* [[Дополнительный, самодополнительный граф]] | * [[Дополнительный, самодополнительный граф]] | ||
| Строка 342: | Строка 342: | ||
* [[Гамильтоновы графы]] | * [[Гамильтоновы графы]] | ||
* [[Теорема Хватала]] | * [[Теорема Хватала]] | ||
| − | * [[Теорема Поша]] | + | * [[Теорема Поша]]<tex>^\star</tex> |
* [[Теорема Дирака]] | * [[Теорема Дирака]] | ||
* [[Теорема Оре]] | * [[Теорема Оре]] | ||
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] | * [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] | ||
| − | * [[Теорема Гринберга]] | + | * [[Теорема Гринберга]]<tex>^\star</tex> |
* [[Турниры]] | * [[Турниры]] | ||
* [[Теорема Редеи-Камиона]] | * [[Теорема Редеи-Камиона]] | ||
| Строка 359: | Строка 359: | ||
* [[Теорема Понтрягина-Куратовского]] | * [[Теорема Понтрягина-Куратовского]] | ||
* [[Двойственный граф планарного графа]] | * [[Двойственный граф планарного графа]] | ||
| − | * [[Теорема Фари]] | + | * [[Теорема Фари]]<tex>^\star</tex> |
== Раскраски графов == | == Раскраски графов == | ||
| Строка 368: | Строка 368: | ||
* [[Формула Уитни]] | * [[Формула Уитни]] | ||
* [[Теорема Брукса]] | * [[Теорема Брукса]] | ||
| − | * [[Верхние и нижние оценки хроматического числа]] | + | * [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex> |
* [[Хроматическое число планарного графа]] | * [[Хроматическое число планарного графа]] | ||
| − | * [[Многочлен Татта]] | + | * [[Многочлен Татта]]<tex>^\star</tex> |
| − | * [[Теория Рамсея]] | + | * [[Теория Рамсея]]<tex>^\star</tex> |
== Обход в глубину == | == Обход в глубину == | ||
| Строка 389: | Строка 389: | ||
* [[Алгоритм Форда-Беллмана]] | * [[Алгоритм Форда-Беллмана]] | ||
* [[Алгоритм Дейкстры]] | * [[Алгоритм Дейкстры]] | ||
| − | * [[Алгоритм Левита]] | + | * [[Алгоритм Левита]]<tex>^\star</tex> |
* [[Алгоритм Флойда]] | * [[Алгоритм Флойда]] | ||
| − | * [[Алгоритм A*]] | + | * [[Алгоритм A*]]<tex>^\star</tex> |
* [[Алгоритм Джонсона]] | * [[Алгоритм Джонсона]] | ||
| − | * [[Эвристики для поиска кратчайших путей]] | + | * [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex> |
| − | * [[Алгоритм D*]] | + | * [[Алгоритм D*]]<tex>^\star</tex> |
== Задача о паросочетании == | == Задача о паросочетании == | ||
| Строка 407: | Строка 407: | ||
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | * [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | ||
* [[Декомпозиция Эдмондса-Галлаи]] | * [[Декомпозиция Эдмондса-Галлаи]] | ||
| − | * [[Задача об устойчивом паросочетании]] | + | * [[Задача об устойчивом паросочетании]]<tex>^\star</tex> |
== Задача о максимальном потоке == | == Задача о максимальном потоке == | ||
| Строка 427: | Строка 427: | ||
* [[Теорема о декомпозиционном барьере]] | * [[Теорема о декомпозиционном барьере]] | ||
* [[Циркуляция потока]] | * [[Циркуляция потока]] | ||
| − | * [[Алгоритм Каргера для нахождения минимального разреза]] | + | * [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex> |
== Задача о потоке минимальной стоимости == | == Задача о потоке минимальной стоимости == | ||
Версия 15:56, 11 января 2015
Убедительная просьба читать правила оформления вики-конспектов.
Символом помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
Содержание
- 1 Первый семестр
- 2 Второй семестр
- 3 Третий семестр
- 4 Четвертый семестр
Первый семестр
Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Метод Лупанова синтеза схем
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Квантовые гейты
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Динамическое программирование
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Наибольшая общая возрастающая подпоследовательность
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю
- Динамика по поддеревьям
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула полной вероятности
- Формула Байеса
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
- Марковская цепь
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- Скрытые Марковские модели
- Алгоритм Витерби
- Алгоритм "Вперед-Назад"
- Алгоритм Баума-Велша
Второй семестр
Амортизационный анализ
- Амортизационный анализ
- Динамический массив
- Hashed Array Tree
- Список
- Стек
- Очередь
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- Мажорирующий элемент
- Счетчик Кнута
Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Фибоначчиева куча
- Левосторонняя куча
- Тонкая куча
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки
Система непересекающихся множеств
- Наивные реализации
- Списки с весовой эвристикой
- Реализация с помощью леса корневых деревьев
- СНМ с операцией удаления за О(1)
Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу
- Splay-дерево
- Tango-дерево
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- Список с пропусками
- Fusion tree
- Сверхбыстрый цифровой бор
- Rope
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование. Амортизационный анализ
- Фильтр Блума
- Универсальное семейство хеш-функций
Сортировка
Квадратичные сортировки
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Терпеливая сортировка
- Timsort
- Теорема о нижней оценке для сортировки сравнениями
Многопоточные сортировки
Другие сортировки
- Поиск k-ой порядковой статистики
- Поиск k-ой порядковой статистики за линейное время
- Сортировка подсчетом
- Сортировка подсчетом сложных объектов
- Цифровая сортировка
- Карманная сортировка
- Сортировка Хана
Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортировочные сети с особыми свойствами
- Сортирующие сети для квадратичных сортировок
- Сеть Бетчера
Алгоритмы поиска
- Целочисленный двоичный поиск
- Вещественный двоичный поиск
- Троичный поиск
- Поиск с помощью золотого сечения
- Интерполяционный поиск
Связь между структурами данных
Третий семестр
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Дополнительный, самодополнительный граф
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Поша
- Теорема Дирака
- Теорема Оре
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Гринберга
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Двойственный граф планарного графа
- Теорема Фари
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Левита
- Алгоритм Флойда
- Алгоритм A*
- Алгоритм Джонсона
- Эвристики для поиска кратчайших путей
- Алгоритм D*
Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
- Декомпозиция Эдмондса-Галлаи
- Задача об устойчивом паросочетании
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
Четвертый семестр
Основные определения. Простые комбинаторные свойства слов
- Основные определения, связанные со строками
- Период и бордер, их связь
- Слово Фибоначчи
- Слово Туэ-Морса
- Декомпозиция Линдона
- Алгоритм Ландау-Шмидта
- Алгоритм Крочемора
Поиск подстроки в строке
- Наивный алгоритм поиска подстроки в строке
- Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- Префикс-функция
- Алгоритм Кнута-Морриса-Пратта
- Алгоритм Бойера-Мура
- Алгоритм Колусси
- Z-функция
- Автомат для поиска образца в тексте
- Бор
- Алгоритм Ахо-Корасик
- Алгоритм Ландау-Вишкина (k несовпадений)
Суффиксное дерево
Суффиксный массив
- Суффиксный массив
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм цифровой сортировки суффиксов циклической строки
- Алгоритм Касаи и др.
- Алгоритм Карккайнена-Сандерса
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
Задача о наименьшем общем предке
- Метод двоичного подъема
- Сведение задачи LCA к задаче RMQ
- Решение RMQ с помощью разреженной таблицы
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Алгоритм Шибера-Вишкина
- Сведение задачи RMQ к задаче LCA
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
- Link-Cut Tree
Матроиды
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Лемма о паросочетании в графе замен
- Лемма о единственном паросочетании в графе замен
- Граф замен для двух матроидов
- Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
- Алгоритм построения базы в пересечении матроидов
- Теорема Эдмондса-Лоулера
Объединение матроидов
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
- Алгоритм построения базы в объединении матроидов
