Участник:Shersh/Тикеты по конспектам year2012
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
Помним про добавление англоязычных терминов в конспекты.
Содержание
1. Основные определения. Простые комбинаторные свойства слов
- взяли Основные определения, связанные со строками
- Англоязычные термины
- Исправить tex
- Убрать определения бордера и периода из следующего конспекта и перенести их в этот, а там сделать ссылками
- Добавить определение периода, как возможность представить строку в виде конкатенации каких-то строк
- Помёржить с похожим конспектом теории формальных языков
- fixed Период и бордер, их связь
- Избавиться от br и подобных тегов. Всё сделать через tex
- Добавить больше ссылок
- Поправить доказательства местами
- Нормальное доказтельство про НОД
- !!! Слово Фибоначчи
- Написать, почему строка Фибоначчи будет (2, 4) исключением
- Можно написать про исключения отдельный конспект даже, если там много информации наберётся
- !!! Слово Туэ-Морса
- Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
- А ещё сделать ссылки на Википедию через интервики
2. Поиск подстроки в строке
- 0. added добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как здесь
- fixed Наивный алгоритм поиска подстроки в строке
- Добавить категории
- Преимущества алгоритма (да, даже у наивного они есть)
- Поправить tex в конспекте и псевдокод
- fixed Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Добавить категории
- Пример плохой строки, на которой хеширование не работает
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- fixed Префикс-функция
- Добавить неформальное определение
- Отформатировать псевдокод — сейчас не совсем по-человечески выглядит
- Поменять заголовки "Алгоритм" и "Оптимизация" на "Наивный алгоритм" и "Эффективный алгоритм"
- Ужасная картинка! Перерисовать
- Сделать описание эффективного алгоритма более понятным и адекватным
- Категории!
- Англоязычные термины
- fixed Алгоритм Кнута-Морриса-Пратта
- И тут категории
- Оформить нормально источники
- Поправить tex в описании, сделать описание более понятным. Например, сказать, что значение префикс функции в данной позиции равно длине бордера строки, а в данном случае это и будет ответом
- Англоязычные термины
- Индекс в картинке слишком маленький относительно букв — поправить
- взяли Z-функция
- Категории
- Ссылки на википедию оформить как интервики
- Поправить ужасный псевдокод
- 'взяли Автомат для поиска образца в тексте
- Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)
- !!! Бор
- Больше ссылок
- Кое-где надо подправить tex
- Нарисовать нормальные картинки
- Построение оформить эстетично по шагам
- Добавить ссылки на суффиксный бор, провести связь с суффиксным деревом
- Добавить информацию про использование дерева для хранения переходов
- Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
- !!! Алгоритм Ахо-Корасик
- Написать асимптотику нормально
- Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать
3. Суффиксное дерево
- Суффиксный бор
- Сжатое суффиксное дерево
- взяли Алгоритм Укконена
- Дописать нормальный псевдокод
- Сделать понятное и нормальное описание
- Подстроку переписать как
- Константы и переменные взять в tex
- Пробелы перед скобками в тексте
- Интервики на леммы
- В Cм. также добавить два других алгоритма построения суффиксных деревьев
- Добавить ссылок в источники, оформить нормально
4. Суффиксный массив
- Суффиксный массив
- Построение суффиксного массива с помощью стандартных методов сортировки
- !!! Алгоритм цифровой сортировки суффиксов циклической строки
- Добавить ссылку на цифровую сортировку куда-нибудь в конспект
- Заменить картинку таблицы на теховскую таблицу
- Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
- Возможно придётся чуточку переписать описание алгоритма
- взяли Алгоритм Касаи и др.
- Добавить псевдокод
- Заменить Источники на Источники информации
- Исправить знаки неравенств
- Переход в последней теореме оформить на отдельной строке, чтобы пояснение не путалось в формуле
- Алгоритм Карккайнена-Сандерса
- !!! Алгоритм поиска подстроки в строке с помощью суффиксного массива
- Отформатировать псевдокоды
- Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
5. Задача о наименьшем общем предке
- fixed Метод двоичного подъема
- Поправить ужасный псевдокод
- Сведение задачи LCA к задаче RMQ
- Решение RMQ с помощью разреженной таблицы
- !!! Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Добавить оптимизацию по памяти
- Написать псевдокод
- Добавить сведение задачи RMQ к задаче +/-1 RMQ
- Алгоритм Шибера-Вишкина
- Сведение задачи RMQ к задаче LCA
6. Матроиды
- fixed Определение матроида
- Англоязычные термины
- Поправить источники информации
- Заменить тире на Шаблон:---
- взяли Примеры матроидов
- Англоязычные термины
- Добавить ссылок, см. также
- Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)
- Длинные слова взять в \mathrm
- Добавить интервики
- Добавить примеры матроидов из дз как определения
- Добавить примеры матроидов отсюда (ещё про бинарные) с доказательствами (может набраться на баллов в итоге, если всё сделать очень хорошо)
- !!! Прямая сумма матроидов
- Добавить в определение слова "прямая сумма"
- Добавить ссылки, см. также, интервики
- Пример разложения в прямую сумму (можно из дз)
- !!! Теорема Радо-Эдмондса (жадный алгоритм)
- Объединить со следующим конспектом
- Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна
- Ссылки, tex
- Жадный алгоритм поиска базы минимального веса
- Добавить разных ссылок
- !!! Теорема о базах
- Англоязычные термины
- Добавить ссылок, см. также
- Поправить tex
- Обернуть семейство в \mathcal
- Добавить сильную теорему баз (base exchange) — см. Chandra Chekuri
- Аксиоматизация матроида базами
- Больше ссылок
- fixed Теорема о циклах
- Поправить tex
- Заменить Ccl на \mathfrak{C}
- Добавить ссылок
- Англоязычные термины
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- tex
- Ссылки
- Англоязычные термины
- fixed Двойственный матроид
- Множество через фигурные скобки написать в определении
- Англоязычные термины к определениям
- Маркированный и нумерованный списки смотрятся ужасно вместе
- Тире заменить на шаблон
- Добавить ссылок и интервики
- Расписать неочевидный переход про единственность цикла в расширенной базе
- fixed Оператор замыкания для матроидов
- Тире
- Больше ссылок
7.Пересечение матроидов
- !!! Пересечение матроидов, определение, примеры
- Ссылки
- tex
- Ещё примеров
- Больше общих описаний
- Пример, когда пересечение матроидов не является матроидом
- Доказательство матроидности уже приведённых примеров
- !!! Лемма о паросочетании в графе замен
- Док-во по индукции оформить красиво
- Исправить док-во: неверный переход
- Заменить xor на треугольник
- fixed Лемма о единственном паросочетании в графе замен
- Константы в tex
- Убрать сокращения
- Добавить интервики
- !!! Граф замен для двух матроидов
- Нарисовать нормальную картинку
- Добавить информацию про граф замен для одного матроида
- Исправить ссылки в соответствующих конспектах
- Создать новый конспект, в него сделать перенаправление из текущего
- Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
- Картинки плывут — разместить нормально
- Заменить обозначение графа замен на принятое
- Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
- !!! Алгоритм построения базы в пересечении матроидов
- Матроиды записать через угловые скобки
- Заменить тире на шаблон
- Добавить категории
- Отформатировать псевдокод
- Мелкие правки в tex
- Перерисовать картинку
- Помёрджить со следующим конспектом
- Теорема Эдмондса-Лоулера
- Добавить категории
- Заменить знак симметрической разности, а так же другие мелкие правки в tex
- Картинки кривовато расположены — поправить
8. Объединение матроидов
- !!! Объединение матроидов, проверка множества на независимость
- Добавить формальное определение
- Структурировать конспект, а не оставлять просто набором тезисов
- Добавить категории
- Добавить ссылок
- Избавиться от сокращений
- Добавить содержательный примеры
- Заменить тире на Шаблон:---
- Помёрджить со следующим конспектом
- Объединение матроидов, доказательство того, что объединение является матроидом
- Добавить категории
- Добавить интервики
- !!! Алгоритм построения базы в объединении матроидов
- В определение само определение выделить жирным
- Тире заменить на Шаблон:---
- Добавить категории
- Добавить псевдокод
- Написать более подробное описание алгоритма поиска базы в объединении