3622
правки
Изменения
Новая страница: «== Основные определения. Простые комбинаторные свойства слов == * [[Основные определения, с...»
== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Цифровая сортировка]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Алгоритм Шибера-Вишкина]]
* [[Сведение задачи RMQ к задаче LCA]]
== Матроиды ==
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]
== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Цифровая сортировка]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Алгоритм Шибера-Вишкина]]
* [[Сведение задачи RMQ к задаче LCA]]
== Матроиды ==
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]
== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
