Участник:Shersh/Тикеты по конспектам year2012

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

Помним про добавление англоязычных терминов в конспекты.

1. Основные определения. Простые комбинаторные свойства слов

1. Основные определения, связанные со строками
2. !!! Период и бордер, их связь
   1. Нормальное и правильное доказательство про НОД
3. Слово Фибоначчи
4. !!! Слово Туэ-Морса
   1. Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
   2. А ещё сделать ссылки на Википедию через интервики

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

1. Наивный алгоритм поиска подстроки в строке
   1. Добавить категории
   2. Преимущества алгоритма (да, даже у наивного они есть)
2. !!! Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
   1. Добавить категории
   2. Пример плохой строки, на которой хеширование не работает
3. Поиск наибольшей общей подстроки двух строк с использованием хеширования
4. Префикс-функция
   1. Категории!
5. Алгоритм Кнута-Морриса-Пратта
   1. И тут категории
6. Z-функция
   1. Категории
   2. Ссылки на википедию оформить как интервики
7. !!! Автомат для поиска образца в тексте
   1. Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)
8. !!! Бор
   1. Можно добавить задачи с использованием бора, например, как он позволяет проверять текст на соответствие шаблону
9. !!! Алгоритм Ахо-Корасик
   1. Написать асимптотику нормально
   2. Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать

3. Суффиксное дерево

1. Суффиксный бор
2. Сжатое суффиксное дерево
3. !!!!! Алгоритм Укконена
   1. Дописать нормальный псевдокод
   2. Сделать понятное и нормальное описание

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

1. Суффиксный массив
2. Построение суффиксного массива с помощью стандартных методов сортировки
3. Цифровая сортировка
4. Алгоритм цифровой сортировки суффиксов циклической строки
5. Алгоритм Касаи и др.
6. Алгоритм Карккайнена-Сандерса
7. Алгоритм поиска подстроки в строке с помощью суффиксного массива

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

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

6. Матроиды

1. Определение матроида
2. Примеры матроидов
3. Прямая сумма матроидов
4. Теорема Радо-Эдмондса (жадный алгоритм)
5. Жадный алгоритм поиска базы минимального веса
6. Теорема о базах
7. Аксиоматизация матроида базами
8. Теорема о циклах
9. Аксиоматизация матроида циклами
10. Ранговая функция, полумодулярность
11. Двойственный матроид
12. Оператор замыкания для матроидов

7.Пересечение матроидов

1. Пересечение матроидов, определение, примеры
2. Лемма о паросочетании в графе замен
3. Лемма о единственном паросочетании в графе замен
4. Граф замен для двух матроидов
5. Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
6. Алгоритм построения базы в пересечении матроидов
7. Теорема Эдмондса-Лоулера

8. Объединение матроидов

1. Объединение матроидов, проверка множества на независимость
2. Объединение матроидов, доказательство того, что объединение является матроидом
3. Алгоритм построения базы в объединении матроидов

9. Теория расписаний

1. Классификация задач
2. Методы решения задач теории расписаний
3. Правило Лаулера
4. Flow shop
5. [math]1 \mid \mid \sum U_{i}[/math]
6. [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math]
7. [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math]
8. [math]1 \mid outtree \mid \sum w_i C_i[/math]
9. [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math]
10. [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math]
11. [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]
12. [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math]
13. [math]P \mid pmtn, r_i \mid L_{max}[/math]
14. [math]Q \mid pmtn \mid C_{max}[/math]
15. [math]Q \mid pmtn, r_{i} \mid L_{max}[/math]
16. [math]Q\mid\mid\sum{C_i}[/math]
17. [math]R2 \mid \mid C_{max}[/math]
18. [math]F2 \mid \mid C_{max}[/math]
19. [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math]
20. [math]O2 \mid \mid C_{max}[/math]
21. [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
22. [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math]
23. [math]J2\mid p_{ij} = 1\mid L_{max}[/math]