Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. Помним про добавление англоязычных терминов в конспекты. == 1. Основные определения. Простые комбинаторные свойства слов ==# [[Основные определения, связанные со строками]]# '''!!!''' [[Период и бордер, их связь]]## Нормальное и правильное доказательство про НОД# [[Слово Фибоначчи]]# '''!!!''' [[Слово Туэ-Морса]]## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.## А ещё сделать ссылки на Википедию через интервики == 2. Поиск подстроки в строке ==# [[Наивный алгоритм поиска подстроки в строке]]## Добавить категории## Преимущества алгоритма (да, даже у наивного они есть)# '''!!!''' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]## Добавить категории## Пример плохой строки, на которой хеширование не работает# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]# [[Префикс-функция]]## Категории!# [[Алгоритм Кнута-Морриса-Пратта]]## И тут категории# [[Z-функция]]## Категории## Ссылки на википедию оформить как интервики# '''!!!''' [[Автомат для поиска образца в тексте]]## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)# '''!!!''' [[Бор]]## Можно добавить задачи с использованием бора, например, как он позволяет проверять текст на соответствие шаблону# '''!!!''' [[Алгоритм Ахо-Корасик]]## Написать асимптотику нормально## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать == 3. Суффиксное дерево ==# [[Суффиксный бор]]# [[Сжатое суффиксное дерево]]# '''!!!!!''' [[Алгоритм Укконена]]## Дописать нормальный псевдокод## Сделать понятное и нормальное описание == 4. Суффиксный массив ==# [[Суффиксный массив]]# [[Построение суффиксного массива с помощью стандартных методов сортировки]]# [[Цифровая сортировка]]# [[Алгоритм цифровой сортировки суффиксов циклической строки]]# [[Алгоритм Касаи и др.]]## Можно добавить псевдокод# [[Алгоритм Карккайнена-Сандерса]]# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]## Над этим конспектом ещё нужно помедитировать... == 5. Задача о наименьшем общем предке ==# [[Метод двоичного подъема]]# [[Сведение задачи LCA к задаче RMQ]]# перенаправление [[Решение RMQ с помощью разреженной таблицы]]# [[Алгоритм Фарака-Колтона и Бендера]] (решение +Участник:Shersh/-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>4ому терму]]
