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

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. Помним про добавление англоязычных терминов в конспекты.

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

1. Основные определения, связанные со строками
2. Период и бордер, их связь
3. Слово Фибоначчи
4. Слово Туэ-Морса

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

1. Наивный алгоритм поиска подстроки в строке
2. Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
3. Поиск наибольшей общей подстроки двух строк с использованием хеширования
4. Префикс-функция
5. Алгоритм Кнута-Морриса-Пратта
6. Z-функция
7. Автомат для поиска образца в тексте
8. Бор
9. Алгоритм Ахо-Корасик

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

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

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]