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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Категория:Дискретная математика и алгоритмы Убедительная просьба читать [[Обсуждени...»)
 
Строка 1: Строка 1:
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы и структуры данных]]
  
 
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]!
 
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]!
−
+
 
  
 
= Первый семестр =
 
= Первый семестр =
Строка 206: Строка 207:
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
 
* [[Вещественный двоичный поиск]]
 
* [[Вещественный двоичный поиск]]
 +
 +
= Третий семестр =
 +
 +
== Основные определения теории графов ==
 +
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 +
* [[Лемма о рукопожатиях]]
 +
* [[Теорема о существовании простого пути в случае существования пути]]
 +
* [[Теорема о существовании простого цикла в случае существования цикла]]
 +
* [[Матрица смежности графа]]
 +
* [[Связь степени матрицы смежности и количества путей]]
 +
* [[Матрица инцидентности графа]]
 +
* [[Циклическое пространство графа]]
 +
* [[Фундаментальные циклы графа]]
 +
* [[Дерево, эквивалентные определения]]
 +
 +
== Связность в графах ==
 +
* [[Отношение связности, компоненты связности]]
 +
* [[Отношение реберной двусвязности]]
 +
* [[Отношение вершинной двусвязности]]
 +
* [[Граф компонент реберной двусвязности]]
 +
* [[Граф блоков-точек сочленения]]
 +
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Мост, эквивалентные определения]]
 +
* [[k-связность]]
 +
* [[Теорема Менгера]]
 +
* [[Теорема Менгера, альтернативное доказательство]]
 +
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
 +
== Остовные деревья ==
 +
* [[Матрица Кирхгофа]]
 +
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
 +
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 +
* [[Количество помеченных деревьев]]
 +
* [[Коды Прюфера]]
 +
 +
== Обходы графов ==
 +
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 +
* [[Покрытие ребер графа путями]]
 +
* [[Алгоритм построения Эйлерова цикла]]
 +
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Гамильтоновы графы]]
 +
* [[Теорема Хватала]]
 +
* Следствия теоремы Хватала:
 +
** [[Теорема Дирака]]
 +
* [[Теорема Оре]]
 +
* [[Турниры]]
 +
* [[Теорема Редеи-Камиона]]
 +
 +
== Укладки графов ==
 +
* [[Укладка графа на плоскости]]
 +
* [[Формула Эйлера]]
 +
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
 +
* [[Укладка дерева]]
 +
* [[Укладка графа с планарными компонентами реберной двусвязности]]
 +
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 +
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Двойственный граф планарного графа]]
 +
 +
== Раскраски графов ==
 +
* [[Раскраска графа]]
 +
* [[Двудольные графы и раскраска в 2 цвета]]
 +
* [[Хроматический многочлен]]
 +
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
 +
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
 +
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
 +
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
 +
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
 +
* [[Формула Зыкова]]
 +
* [[Формула Уитни]]
 +
 +
== Обход в глубину ==
 +
* [[Обход в глубину, цвета вершин]]
 +
* [[Лемма о белых путях]]
 +
* [[Использование обхода в глубину для проверки связности]]
 +
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 +
* [[Использование обхода в глубину для топологической сортировки]]
 +
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 +
* [[Использование обхода в глубину для поиска точек сочленения]]
 +
* [[Построение компонент вершинной двусвязности]]
 +
* [[Использование обхода в глубину для поиска мостов]]
 +
* [[Построение компонент реберной двусвязности]]
 +
 +
== Кратчайшие пути в графах ==
 +
* [[Обход в ширину]]
 +
* [[Алгоритм Форда-Беллмана]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Флойда]]
 +
* [[Алгоритм A*]]
 +
* [[Алгоритм Джонсона]]
 +
 +
== Остовные деревья ==
 +
* [[Лемма о безопасном ребре]]
 +
* [[Алгоритм Прима]]
 +
* [[Алгоритм Краскала]]
 +
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 +
* [[Алгоритм двух китайцев]]
 +
 +
== Задача о паросочетании ==
 +
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
 +
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 +
* [[Алгоритм Куна для поиска максимального паросочетания]]
 +
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 +
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 +
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 +
 +
== Задача о максимальном потоке ==
 +
* [[Определение сети, потока]]
 +
* [[Разрез, лемма о потоке через разрез]]
 +
* [[Дополняющая сеть, дополняющий путь]]
 +
* [[Лемма о сложении потоков]]
 +
* [[Теорема Форда-Фалкерсона]]
 +
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 +
* [[Алоритм Эдмондса-Карпа]]
 +
* [[Теорема о декомпозиции]]
 +
* [[Теорема о декомпозиционном барьере]]
 +
* [[Блокирующий поток]]
 +
* [[Схема алгоритма Диница]]
 +
* [[Циркуляция потока]]
 +
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 +
* [[Алгоритм масштабирования потока]]
 +
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
 +
== Задача о потоке минимальной стоимости ==
 +
* [[Поток минимальной стоимости]]
 +
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
 +
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
 +
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
 +
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
 +
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 +
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
 +
= Четвертый семестр =
 +
 +
== Поиск подстроки в строке ==
 +
* [[Наивный алгоритм поиска подстроки в строке]]
 +
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 +
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 +
* [[Префикс-функция]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
* [[Z-функция]]
 +
* [[Автомат для поиска образца в тексте]]
 +
* [[Бор]]
 +
* [[Алгоритм Ахо-Корасик]]
 +
 +
== Словарные структуры данных ==
 +
* [[Суффиксный бор]]
 +
* [[Сжатое суффиксное дерево]]
 +
* [[Алгоритм Укконена]]
 +
 +
== Задача о наименьшем общем предке ==
 +
* [[Метод двоичного подъема]]
 +
* [[Сведение задачи LCA к задаче RMQ]]
 +
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
 +
* [[Сведение задачи RMQ к задаче LCA]]
 +
 +
== Суффиксный массив ==
 +
* [[Суффиксный массив]]
 +
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 +
* [[Алгоритм цифровой сортировки]]
 +
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 +
* [[Алгоритм Касаи и др.]]
 +
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
 +
== Матроиды ==
 +
* [[Определение матроида]]
 +
* [[Примеры матроидов]]
 +
* [[Прямая сумма матроидов]]
 +
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 +
* [[Жадный алгоритм поиска базы минимального веса]]
 +
* [[Теорема о базах]]
 +
* [[Аксиоматизация матроида базами]]
 +
* [[Теорема о циклах]]
 +
* [[Аксиоматизация матроида циклами]]
 +
* [[Ранговая функция, полумодулярность]]
 +
* [[Двойственный матроид]]
 +
* [[Оператор замыкания для матроидов]]
 +
* [[Пересечение матроидов, определение, примеры]]
 +
* [[Лемма о паросочетании в графе замен]]
 +
* [[Лемма о единственном паросочетании в графе замен]]
 +
* [[Граф замен для двух матроидов]]
 +
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 +
* [[Алгоритм построения базы в пересечении матроидов]]
 +
* [[Теорема Эдмондса-Лоулера]]
 +
* [[Объединение матроидов, проверка множества на независимость]]
 +
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
 +
* [[Алгоритм построения базы в объединении матроидов]]

Версия 17:04, 22 февраля 2012


Убедительная просьба читать правила оформления вики-конспектов!


Содержание

Первый семестр

Отношения

Булевы функции

Схемы из функциональных элементов

Представление информации

Алгоритмы сжатия

Комбинаторика

Динамическое программирование

Теория вероятностей

Марковские цепи

Второй семестр

Амортизационный анализ

Приоритетные очереди

Система непересекающихся множеств

Деревья поиска

Дерево отрезков

Дерево Фенвика

Хеширование

Сортировка

Сортирующие сети

Алгоритмы поиска

Третий семестр

Основные определения теории графов

Связность в графах

Остовные деревья

Обходы графов

Укладки графов

Раскраски графов

Обход в глубину

Кратчайшие пути в графах

Остовные деревья

Задача о паросочетании

Задача о максимальном потоке

Задача о потоке минимальной стоимости

Четвертый семестр

Поиск подстроки в строке

Словарные структуры данных

Задача о наименьшем общем предке

Суффиксный массив

Матроиды

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика,_алгоритмы_и_структуры_данных&oldid=18207»