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

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

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

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

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

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

0. !!! добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как здесь

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

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

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

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

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

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

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

6. Матроиды

• Тут вообще все конспекты нужно править. Добавлять категории и по мелочи красоту наводить. Могут даваться в нагрузку, если выбранная тема будет маленькой

1. Определение матроида
2. Примеры матроидов
3. Прямая сумма матроидов
4. Теорема Радо-Эдмондса (жадный алгоритм)
5. !!! Жадный алгоритм поиска базы минимального веса
   1. Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна.
6. Теорема о базах
7. Аксиоматизация матроида базами
8. Теорема о циклах
9. Аксиоматизация матроида циклами
10. Ранговая функция, полумодулярность
11. !!! Двойственный матроид
    1. Можно добавить доказательство через ранговую функцию
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]