Изменения

== 1. Основные определения. Простые комбинаторные свойства слов ==* # [[Основные определения, связанные со строками]]* # [[Период и бордер, их связь]]* # [[Слово Фибоначчи]]* # [[Слово Туэ-Морса]]

== 2. Поиск подстроки в строке ==* # [[Наивный алгоритм поиска подстроки в строке]]* # [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]* # [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]* # [[Префикс-функция]]* # [[Алгоритм Кнута-Морриса-Пратта]]* # [[Z-функция]]* # [[Автомат для поиска образца в тексте]]* # [[Бор]]* # [[Алгоритм Ахо-Корасик]]

== 3. Суффиксное дерево ==* # [[Суффиксный бор]]* # [[Сжатое суффиксное дерево]]* # [[Алгоритм Укконена]]

== 4. Суффиксный массив ==* # [[Суффиксный массив]]* # [[Построение суффиксного массива с помощью стандартных методов сортировки]]* # [[Цифровая сортировка]]* # [[Алгоритм цифровой сортировки суффиксов циклической строки]]* # [[Алгоритм Касаи и др.]]* # [[Алгоритм Карккайнена-Сандерса]]* # [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== 5. Задача о наименьшем общем предке ==* # [[Метод двоичного подъема]]* # [[Сведение задачи LCA к задаче RMQ]]* # [[Решение RMQ с помощью разреженной таблицы]]* # [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)* # [[Алгоритм Шибера-Вишкина]]* # [[Сведение задачи RMQ к задаче LCA]]

== 6. Матроиды ==* # [[Определение матроида]]* # [[Примеры матроидов]]* # [[Прямая сумма матроидов]]* # [[Теорема Радо-Эдмондса (жадный алгоритм)]]* # [[Жадный алгоритм поиска базы минимального веса]]* # [[Теорема о базах]]* # [[Аксиоматизация матроида базами]]* # [[Теорема о циклах]]* # [[Аксиоматизация матроида циклами]]* # [[Ранговая функция, полумодулярность]]* # [[Двойственный матроид]]* # [[Оператор замыкания для матроидов]]=== Пересечение матроидов ===* [[Пересечение матроидов, определение, примеры]]* [[Лемма о паросочетании в графе замен]]* [[Лемма о единственном паросочетании в графе замен]]* [[Граф замен для двух матроидов]]* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]* [[Алгоритм построения базы в пересечении матроидов]]* [[Теорема Эдмондса-Лоулера]]=== Объединение матроидов ===* [[Объединение матроидов, проверка множества на независимость]]* [[Объединение матроидов, доказательство того, что объединение является матроидом]]* [[Алгоритм построения базы в объединении матроидов]]

== 7.Пересечение матроидов ==# [[Пересечение матроидов, определение, примеры]]# [[Лемма о паросочетании в графе замен]]# [[Лемма о единственном паросочетании в графе замен]]# [[Граф замен для двух матроидов]]# [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]# [[Алгоритм построения базы в пересечении матроидов]]# [[Теорема Эдмондса-Лоулера]]== 8. Объединение матроидов ==# [[Объединение матроидов, проверка множества на независимость]]# [[Объединение матроидов, доказательство того, что объединение является матроидом]]# [[Алгоритм построения базы в объединении матроидов]] == 9. Теория расписаний ==* # [[Классификация задач]]* # [[Методы решения задач теории расписаний]]* # [[Правило Лаулера]]* # [[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>]]