Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. Помним про добавление англоязычных терминов в конспекты. == 1. Основные определения. Простые комбинаторные свойства слов ==# '''fixed''' [[Основные определения, связанные со строками]]## Англоязычные термины## Исправить tex <tex> \leq </tex>## Убрать определения бордера и периода из следующего конспекта и перенести их в этот, а там сделать ссылками## Добавить определение периода, как возможность представить строку в виде конкатенации каких-то строк## Помёржить с похожим конспектом теории формальных языков# '''fixed''' [[Период и бордер, их связь]]## Избавиться от br и подобных тегов. Всё сделать через tex## Добавить больше ссылок## Поправить доказательства местами## Нормальное доказтельство про НОД# '''!!!''' перенаправление [[Слово Фибоначчи]]## Написать, почему строка Фибоначчи будет (2, 4) исключением## Можно написать про исключения отдельный конспект даже, если там много информации наберётся# '''!!!''' [[Слово Туэ-Морса]]## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.## А ещё сделать ссылки на Википедию через интервики == 2. Поиск подстроки в строке ==Участник: 0. '''added''' добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как [[ Сортировка | здесь]]# '''fixed''' [[Наивный алгоритм поиска подстроки в строке]]## Добавить категории## Преимущества алгоритма (да, даже у наивного они есть)## Поправить tex в конспекте и псевдокод# ''fixed'' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]## Добавить категории## Пример плохой строки, на которой хеширование не работает# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]# '''fixed''' [[Префикс-функция]]## Добавить неформальное определение## Отформатировать псевдокод {{---}} сейчас не совсем по-человечески выглядит## Поменять заголовки "Алгоритм" и "Оптимизация" на "Наивный алгоритм" и "Эффективный алгоритм"## Ужасная картинка! Перерисовать## Сделать описание эффективного алгоритма более понятным и адекватным## Категории!## Англоязычные термины# '''fixed''' [[Алгоритм Кнута-Морриса-Пратта]]## И тут категории## Оформить нормально источники## Поправить tex в описании, сделать описание более понятным. Например, сказать, что значение префикс функции в данной позиции равно длине бордера строки, а в данном случае это и будет ответом## Англоязычные термины## Индекс <tex> i <Shersh/tex> в картинке слишком маленький относительно букв {{---}} поправить# ''fixed'' [[Z-функция]]## Категории## Ссылки на википедию оформить как интервики## Поправить ужасный псевдокод# '''взяли'' [[Автомат для поиска образца в тексте]]## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)# '''!!!''' [[Бор]]## Больше ссылок## Кое-где надо подправить tex## Нарисовать нормальные картинки## Построение оформить эстетично по шагам## Добавить ссылки на суффиксный бор, провести связь с суффиксным деревом## Добавить информацию про использование дерева для хранения переходов## Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах# '''!!!''' [[Алгоритм Ахо-Корасик]]## Написать асимптотику нормально## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать == 3. Суффиксное дерево ==# [[Суффиксный бор]]# [[Сжатое суффиксное дерево]]# '''взяли''' [[Алгоритм Укконена]]## Дописать нормальный псевдокод## Сделать понятное и нормальное описание## Подстроку переписать как <tex> s[i..j] </tex>## Константы и переменные взять в tex## Пробелы перед скобками в тексте## Интервики на леммы## В Cм. также добавить два других алгоритма построения суффиксных деревьев## Добавить ссылок в источники, оформить нормально == 4. Суффиксный массив ==# [[Суффиксный массив]]# [[Построение суффиксного массива с помощью стандартных методов сортировки]]# '''!!!''' [[Алгоритм цифровой сортировки суффиксов циклической строки]]## Добавить ссылку на цифровую сортировку куда-нибудь в конспект## Заменить картинку таблицы на теховскую таблицу## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать## Возможно придётся чуточку переписать описание алгоритма# ''взяли'' [[Алгоритм Касаи и др.]]## Добавить псевдокод## Заменить Источники на Источники информации## Исправить знаки неравенств## Переход в последней теореме оформить на отдельной строке, чтобы пояснение не путалось в формуле # [[Алгоритм Карккайнена-Сандерса]]# '''!!!''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]## Отформатировать псевдокоды## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги == 5. Задача о наименьшем общем предке ==# ''fixed'' [[Метод двоичного подъема]]## Поправить ужасный псевдокод# [[Сведение задачи LCA к задаче RMQ]]# [[Решение RMQ с помощью разреженной таблицы]]# '''!!!''' [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)## Добавить оптимизацию по памяти## Написать псевдокод## Добавить сведение задачи RMQ к задаче +/-1 RMQ# [[Алгоритм Шибера-Вишкина]]# [[Сведение задачи RMQ к задаче LCA]] == 6. Матроиды ==# ''fixed'' [[Определение матроида]]## Англоязычные термины## Поправить источники информации## Заменить тире на [[Шаблон:---]]# '''fixed''' [[Примеры матроидов]]## Англоязычные термины## Добавить ссылок, см. также## Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)## Длинные слова взять в \mathrm## Добавить интервики## Добавить примеры матроидов из дз как определения## Добавить примеры матроидов [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf отсюда] (ещё про бинарные) с доказательствами (может набраться на <tex> 10 </tex> баллов в итоге, если всё сделать очень хорошо)# '''fixed''' [[Прямая сумма матроидов]]## Добавить в определение слова "прямая сумма"## Добавить ссылки, см. также, интервики## Пример разложения в прямую сумму (можно из дз)# '''fixed''' [[Теорема Радо-Эдмондса (жадный алгоритм)]]## Объединить со следующим конспектом## Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна## Ссылки, tex# ''взяли'' [[Жадный алгоритм поиска базы минимального веса]]## Добавить разных ссылок## Мутное описание алгоритма## Криво написана асимптотика## Больше интервики# '''!!!''' [[Теорема о базах]]## Англоязычные термины## Добавить ссылок, см. также## Поправить tex## Обернуть семейство в \mathcal## Добавить сильную теорему баз (base exchange) {{---}} см. Chandra Chekuri# [[Аксиоматизация матроида базами]]## Больше ссылок# ''fixed'' [[Теорема о циклах]]## Поправить tex## Заменить Ccl на \mathfrak{C}## Добавить ссылок## Англоязычные термины# [[Аксиоматизация матроида циклами]]# [[Ранговая функция, полумодулярность]]## tex## Ссылки## Англоязычные термины# ''fixed'' [[Двойственный матроид]]## Множество через фигурные скобки написать в определении## Англоязычные термины Тикеты к определениям## Маркированный и нумерованный списки смотрятся ужасно вместе## Тире заменить на шаблон## Добавить ссылок и интервики## Расписать неочевидный переход про единственность цикла в расширенной базе# ''fixed'' [[Оператор замыкания для матроидов]]## Тире## Больше ссылок == 7.Пересечение матроидов ==# '''!!!''' [[Пересечение матроидов, определение, примеры]]## Ссылки## tex## Ещё примеров## Больше общих описаний## Пример, когда пересечение матроидов не является матроидом## Доказательство матроидности уже приведённых примеров# '''!!!''' [[Лемма о паросочетании в графе замен]]## Док-во по индукции оформить красиво## Исправить док-во: неверный переход## Заменить xor на треугольник# ''fixed'' [[Лемма о единственном паросочетании в графе замен]]## Константы в tex## Убрать сокращения## Добавить интервики# '''!!!''' [[Граф замен для двух матроидов]]## Нарисовать нормальную картинку## Добавить информацию про граф замен для одного матроида## Исправить ссылки в соответствующих конспектах## Создать новый конспект, в него сделать перенаправление из текущего# [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]## Картинки плывут {{---}} разместить нормально## Заменить обозначение графа замен на принятое## Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)# '''!!!''' [[Алгоритм построения базы в пересечении матроидов]]## Матроиды записать через угловые скобки## Заменить тире на шаблон## Добавить категории## Отформатировать псевдокод## Мелкие правки в tex## Перерисовать картинку## Помёрджить со следующим конспектом# [[Теорема Эдмондса-Лоулера]]## Добавить категории## Заменить знак симметрической разности, а так же другие мелкие правки в tex## Картинки кривовато расположены {{---}} поправить## Исправить ошибки в док-ве == 8. Объединение матроидов ==# '''!!!''' [[Объединение матроидов, проверка множества на независимость]]## Добавить формальное определение## Структурировать конспект, а не оставлять просто набором тезисов## Добавить категории## Добавить ссылок## Избавиться от сокращений## Добавить содержательный примеры## Заменить тире на [[Шаблон:---]]## Помёрджить со следующим конспектом# [[Объединение матроидов, доказательство того, что объединение является матроидом]]## Добавить категории## Добавить интервики# '''!!!''' [[Алгоритм построения базы в объединении матроидов]]## В определение само определение выделить жирным## Тире заменить на [[Шаблон:---]]## Добавить категории## Добавить псевдокод## Написать более подробное описание алгоритма поиска базы в объединении == 9. Теория расписаний ==# [[Классификация задач]]# [[Методы решения задач теории расписаний]]# [[Правило Лаулера]]# [[Flow shop]]# [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]# [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]# [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]# [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]# [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]# [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]# [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]# [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]# [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]# [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]# [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]# [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]# [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]# [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]# [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]# [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]# [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]# [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]# [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>4ому терму]]
