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

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

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

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

1. !!! Основные определения, связанные со строками
   1. Англоязычные термины
   2. Исправить tex [math] \leq [/math]
   3. Убрать определения бордера и периода из следующего конспекта и перенести их в этот, а там сделать ссылками
   4. Добавить определение периода, как возможность представить строку в виде конкатенации каких-то строк
2. fixed Период и бордер, их связь
   1. Избавиться от br и подобных тегов. Всё сделать через tex
   2. Добавить больше ссылок
   3. Поправить доказательства местами
   4. Нормальное доказтельство про НОД
3. !!! Слово Фибоначчи
   1. Написать, почему строка Фибоначчи будет (2, 4) исключением
   2. Можно написать про исключения отдельный конспект даже, если там много информации наберётся
4. !!! Слово Туэ-Морса
   1. Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
   2. А ещё сделать ссылки на Википедию через интервики

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

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

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

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

1. Суффиксный бор
2. Сжатое суффиксное дерево
3. взяли Алгоритм Укконена
   1. Дописать нормальный псевдокод
   2. Сделать понятное и нормальное описание
   3. Подстроку переписать как [math] s[i..j] [/math]
   4. Константы и переменные взять в tex
   5. Пробелы перед скобками в тексте
   6. Интервики на леммы
   7. В Cм. также добавить два других алгоритма построения суффиксных деревьев
   8. Добавить ссылок в источники, оформить нормально

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

1. Суффиксный массив
2. Построение суффиксного массива с помощью стандартных методов сортировки
3. !!! Алгоритм цифровой сортировки суффиксов циклической строки
   1. Добавить ссылку на цифровую сортировку куда-нибудь в конспект
   2. Заменить картинку таблицы на теховскую таблицу
   3. Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
   4. Возможно придётся чуточку переписать описание алгоритма
4. Алгоритм Касаи и др.
   1. Можно добавить псевдокод
5. Алгоритм Карккайнена-Сандерса
6. !!! Алгоритм поиска подстроки в строке с помощью суффиксного массива
   1. Отформатировать псевдокоды
   2. Разобраться в алгоритмах и написать нормальное описание: там встречаются баги

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

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

6. Матроиды

1. fixed Определение матроида
   1. Англоязычные термины
   2. Поправить источники информации
   3. Заменить тире на Шаблон:---
2. !!! Примеры матроидов
   1. Англоязычные термины
   2. Добавить ссылок, см. также
   3. Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)
   4. Длинные слова взять в \mathrm
   5. Добавить интервики
   6. Добавить примеры матроидов из дз как определения
   7. Добавить примеры матроидов отсюда (ещё про бинарные) с доказательствами (может набраться на [math] 10 [/math] баллов в итоге, если всё сделать очень хорошо)
3. !!! Прямая сумма матроидов
   1. Добавить в определение слова "прямая сумма"
   2. Добавить ссылки, см. также, интервики
   3. Пример разложения в прямую сумму (можно из дз)
4. !!! Теорема Радо-Эдмондса (жадный алгоритм)
   1. Объединить со следующим конспектом
   2. Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна
   3. Ссылки, tex
5. Жадный алгоритм поиска базы минимального веса
   1. Добавить разных ссылок
6. !!! Теорема о базах
   1. Англоязычные термины
   2. Добавить ссылок, см. также
   3. Поправить tex
   4. Обернуть семейство в \mathcal
   5. Добавить сильную теорему баз (base exchange) — см. Chandra Chekuri
7. Аксиоматизация матроида базами
   1. Больше ссылок
8. Теорема о циклах
   1. Поправить tex
   2. Заменить Ccl на \mathfrak{C}
   3. Добавить ссылок
   4. Англоязычные термины
9. Аксиоматизация матроида циклами
10. Ранговая функция, полумодулярность
    1. tex
    2. Ссылки
    3. Англоязычные термины
11. Двойственный матроид
    1. Множество через фигурные скобки написать в определении
    2. Англоязычные термины к определениям
    3. Маркированный и нумерованный списки смотрятся ужасно вместе
    4. Тире заменить на шаблон
    5. Добавить ссылок и интервики
12. Оператор замыкания для матроидов
    1. Тире
    2. Больше ссылок

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

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

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

1. !!! Объединение матроидов, проверка множества на независимость
   1. Добавить формальное определение
   2. Структурировать конспект, а не оставлять просто набором тезисов
   3. Добавить категории
   4. Добавить ссылок
   5. Избавиться от сокращений
   6. Добавить содержательный примеры
   7. Заменить тире на Шаблон:---
2. Объединение матроидов, доказательство того, что объединение является матроидом
   1. Добавить категории
   2. Добавить интервики
3. Алгоритм построения базы в объединении матроидов
   1. В определение само определение выделить жирным
   2. Тире заменить на Шаблон:---
   3. Добавить категории
   4. Добавить псевдокод

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]