|
|
| (не показано 90 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | == Основные определения. Простые комбинаторные свойства слов ==
| + | #перенаправление [[Участник:Shersh/Тикеты к 4ому терму]] |
| − | * [[Основные определения, связанные со строками]]
| |
| − | * [[Период и бордер, их связь]]
| |
| − | * [[Слово Фибоначчи]]
| |
| − | * [[Слово Туэ-Морса]]
| |
| − | | |
| − | == Поиск подстроки в строке ==
| |
| − | * [[Наивный алгоритм поиска подстроки в строке]]
| |
| − | * [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
| |
| − | * [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
| |
| − | * [[Префикс-функция]]
| |
| − | * [[Алгоритм Кнута-Морриса-Пратта]]
| |
| − | * [[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>]]
| |
