|
|
| (не показана 41 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| − | Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
| + | #перенаправление [[Участник:Shersh/Тикеты к 4ому терму]] |
| − | | |
| − | Помним про добавление англоязычных терминов в конспекты.
| |
| − | | |
| − | == 1. Основные определения. Простые комбинаторные свойства слов ==
| |
| − | # '''!!!''' [[Основные определения, связанные со строками]]
| |
| − | ## Англоязычные термины
| |
| − | ## Исправить tex <tex> \leq </tex>
| |
| − | ## Убрать определения бордера и периода из следующего конспекта и перенести их в этот, а там сделать ссылками
| |
| − | ## Добавить определение периода, как возможность представить строку в виде конкатенации каких-то строк
| |
| − | # '''взяли''' [[Период и бордер, их связь]]
| |
| − | ## Избавиться от br и подобных тегов. Всё сделать через tex
| |
| − | ## Добавить больше ссылок
| |
| − | ## Поправить доказательства местами
| |
| − | ## Нормальное доказтельство про НОД
| |
| − | # '''!!!''' [[Слово Фибоначчи]]
| |
| − | ## Написать, почему строка Фибоначчи будет (2, 4) исключением
| |
| − | ## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
| |
| − | # '''!!!''' [[Слово Туэ-Морса]] | |
| − | ## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
| |
| − | ## А ещё сделать ссылки на Википедию через интервики
| |
| − | | |
| − | == 2. Поиск подстроки в строке ==
| |
| − | : 0. '''!!!''' добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как [[ Сортировка | здесь]] | |
| − | # '''fixed''' [[Наивный алгоритм поиска подстроки в строке]]
| |
| − | ## Добавить категории
| |
| − | ## Преимущества алгоритма (да, даже у наивного они есть)
| |
| − | ## Поправить tex в конспекте и псевдокод
| |
| − | # ''fixed'' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
| |
| − | ## Добавить категории
| |
| − | ## Пример плохой строки, на которой хеширование не работает
| |
| − | # [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
| |
| − | # '''fixed''' [[Префикс-функция]]
| |
| − | ## Добавить неформальное определение
| |
| − | ## Отформатировать псевдокод {{---}} сейчас не совсем по-человечески выглядит
| |
| − | ## Поменять заголовки "Алгоритм" и "Оптимизация" на "Наивный алгоритм" и "Эффективный алгоритм"
| |
| − | ## Ужасная картинка! Перерисовать
| |
| − | ## Сделать описание эффективного алгоритма более понятным и адекватным
| |
| − | ## Категории!
| |
| − | ## Англоязычные термины
| |
| − | # '''взяли''' [[Алгоритм Кнута-Морриса-Пратта]]
| |
| − | ## И тут категории
| |
| − | ## Оформить нормально источники
| |
| − | ## Добавить, как осуществляется множественный поиск образцов в тексте и асимптотику этого
| |
| − | ## Поправить tex в описании, сделать описание более понятным. Например, сказать, что значение префикс функции в данной позиции равно длине бордера строки, а в данном случае это и будет ответом
| |
| − | ## Англоязычные термины
| |
| − | ## Индекс <tex> i </tex> в картинке слишком маленький относительно букв {{---}} поправить
| |
| − | # [[Z-функция]]
| |
| − | ## Категории
| |
| − | ## Ссылки на википедию оформить как интервики
| |
| − | ## Поправить ужасный псевдокод
| |
| − | # '''!!!''' [[Автомат для поиска образца в тексте]]
| |
| − | ## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)
| |
| − | # '''взяли''' [[Бор]]
| |
| − | ## Можно добавить задачи с использованием бора, например, как он позволяет проверять текст на соответствие шаблону
| |
| − | # '''!!!''' [[Алгоритм Ахо-Корасик]]
| |
| − | ## Написать асимптотику нормально
| |
| − | ## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать
| |
| − | | |
| − | == 3. Суффиксное дерево ==
| |
| − | # [[Суффиксный бор]]
| |
| − | # [[Сжатое суффиксное дерево]]
| |
| − | # '''взяли''' [[Алгоритм Укконена]]
| |
| − | ## Дописать нормальный псевдокод
| |
| − | ## Сделать понятное и нормальное описание
| |
| − | ## Подстроку переписать как <tex> s[i..j] </tex>
| |
| − | ## Константы и переменные взять в tex
| |
| − | ## Пробелы перед скобками в тексте
| |
| − | ## Интервики на леммы
| |
| − | ## В Cм. также добавить два других алгоритма построения суффиксных деревьев
| |
| − | ## Добавить ссылок в источники, оформить нормально
| |
| − | | |
| − | == 4. Суффиксный массив ==
| |
| − | # [[Суффиксный массив]]
| |
| − | # [[Построение суффиксного массива с помощью стандартных методов сортировки]]
| |
| − | # '''!!!''' [[Алгоритм цифровой сортировки суффиксов циклической строки]]
| |
| − | ## Добавить ссылку на цифровую сортировку куда-нибудь в конспект
| |
| − | ## Заменить картинку таблицы на теховскую таблицу
| |
| − | ## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
| |
| − | ## Возможно придётся чуточку переписать описание алгоритма
| |
| − | # [[Алгоритм Касаи и др.]]
| |
| − | ## Можно добавить псевдокод
| |
| − | # [[Алгоритм Карккайнена-Сандерса]]
| |
| − | # '''!!!''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
| |
| − | ## Отформатировать псевдокоды
| |
| − | ## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
| |
| − | | |
| − | == 5. Задача о наименьшем общем предке ==
| |
| − | # [[Метод двоичного подъема]]
| |
| − | ## Поправить ужасный псевдокод
| |
| − | # [[Сведение задачи LCA к задаче RMQ]]
| |
| − | # [[Решение RMQ с помощью разреженной таблицы]]
| |
| − | # '''!!!''' [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
| |
| − | ## Добавить оптимизацию по памяти
| |
| − | ## Написать псевдокод
| |
| − | ## Добавить сведение задачи RMQ к задаче +/-1 RMQ
| |
| − | # [[Алгоритм Шибера-Вишкина]]
| |
| − | # [[Сведение задачи RMQ к задаче LCA]]
| |
| − | | |
| − | == 6. Матроиды ==
| |
| − | # ''fixed'' [[Определение матроида]]
| |
| − | ## Англоязычные термины
| |
| − | ## Поправить источники информации
| |
| − | ## Заменить тире на [[Шаблон:---]]
| |
| − | # '''!!!''' [[Примеры матроидов]]
| |
| − | ## Англоязычные термины
| |
| − | ## Добавить ссылок, см. также
| |
| − | ## Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)
| |
| − | ## Длинные слова взять в \mathrm
| |
| − | ## Добавить интервики
| |
| − | ## Добавить примеры матроидов из дз как определения
| |
| − | ## Добавить примеры матроидов [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf отсюда] (ещё про бинарные) с доказательствами (может набраться на <tex> 10 </tex> баллов в итоге, если всё сделать очень хорошо)
| |
| − | # '''!!!''' [[Прямая сумма матроидов]]
| |
| − | ## Добавить в определение слова "прямая сумма"
| |
| − | ## Добавить ссылки, см. также, интервики
| |
| − | ## Пример разложения в прямую сумму (можно из дз)
| |
| − | # '''!!!''' [[Теорема Радо-Эдмондса (жадный алгоритм)]]
| |
| − | ## Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна
| |
| − | ## Ссылки, tex
| |
| − | # [[Жадный алгоритм поиска базы минимального веса]]
| |
| − | ## Добавить разных ссылок
| |
| − | # [[Теорема о базах]]
| |
| − | ## Англоязычные термины
| |
| − | ## Добавить ссылок, см. также
| |
| − | ## Поправить tex
| |
| − | ## Обернуть семейство в \mathcal
| |
| − | # [[Аксиоматизация матроида базами]]
| |
| − | ## Больше ссылок
| |
| − | # [[Теорема о циклах]]
| |
| − | ## Поправить tex
| |
| − | ## Заменить Ccl на \mathfrak{C}
| |
| − | ## Добавить ссылок
| |
| − | ## Англоязычные термины
| |
| − | # [[Аксиоматизация матроида циклами]]
| |
| − | # [[Ранговая функция, полумодулярность]]
| |
| − | ## tex
| |
| − | ## Ссылки
| |
| − | ## Англоязычные термины
| |
| − | # [[Двойственный матроид]]
| |
| − | ## Множество через фигурные скобки написать в определении
| |
| − | ## Англоязычные термины к определениям
| |
| − | ## Маркированный и нумерованный списки смотрятся ужасно вместе
| |
| − | ## Тире заменить на шаблон
| |
| − | ## Добавить ссылок и интервики
| |
| − | # [[Оператор замыкания для матроидов]]
| |
| − | ## Тире
| |
| − | ## Больше ссылок
| |
| − | | |
| − | == 7.Пересечение матроидов ==
| |
| − | # [[Пересечение матроидов, определение, примеры]]
| |
| − | ## Ссылки
| |
| − | ## 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>]]
| |
