Участник:Shersh/Тикеты по конспектам year2012 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(2. Поиск подстроки в строке)
(Перенаправление на Участник:Shersh/Тикеты к 4ому терму)
 
(не показано 75 промежуточных версий этого же участника)
Строка 1: Строка 1:
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
+
#перенаправление [[Участник:Shersh/Тикеты к 4ому терму]]
 
 
Помним про добавление англоязычных терминов в конспекты.
 
 
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
# [[Основные определения, связанные со строками]]
 
# '''!!!''' [[Период и бордер, их связь]]
 
## Нормальное и правильное доказательство про НОД
 
# [[Слово Фибоначчи]]
 
# '''!!!''' [[Слово Туэ-Морса]]
 
## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
 
## А ещё сделать ссылки на Википедию через интервики
 
 
 
== 2. Поиск подстроки в строке ==
 
: 0. '''!!!''' добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как [[ Сортировка | здесь]]
 
# [[Наивный алгоритм поиска подстроки в строке]]
 
## Добавить категории
 
## Преимущества алгоритма (да, даже у наивного они есть)
 
# '''!!!''' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
## Добавить категории
 
## Пример плохой строки, на которой хеширование не работает
 
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 
# '''!!!''' [[Префикс-функция]]
 
## Добавить неформальное определение
 
## Отформатировать псевдокод {{---}} сейчас не совсем по-человечески выглядит
 
## Поменять заголовки "Алгоритм" и "Оптимизация" на "Наивный алгоритм" и "Эффективный алгоритм"
 
## Ужасная картинка! Перерисовать
 
## Сделать описание эффективного алгоритма более понятным и адекватным
 
## Категории!
 
## Англоязычные термины
 
# '''!!!''' [[Алгоритм Кнута-Морриса-Пратта]]
 
## И тут категории
 
## Оформить нормально источники
 
## Добавить, как осуществляется множественный поиск образцов в тексте и асимптотику этого
 
## Поправить tex в описании, сделать описание более понятным. Например, сказать, что значение префикс функции в данной позиции равно длине бордера строки, а в данном случае это и будет ответом
 
## Англоязычные термины
 
# [[Z-функция]]
 
## Категории
 
## Ссылки на википедию оформить как интервики
 
# '''!!!''' [[Автомат для поиска образца в тексте]]
 
## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)
 
# '''взяли''' [[Бор]]
 
## Можно добавить задачи с использованием бора, например, как он позволяет проверять текст на соответствие шаблону
 
# '''!!!''' [[Алгоритм Ахо-Корасик]]
 
## Написать асимптотику нормально
 
## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать
 
 
 
== 3. Суффиксное дерево ==
 
# [[Суффиксный бор]]
 
# [[Сжатое суффиксное дерево]]
 
# '''взяли''' [[Алгоритм Укконена]]
 
## Дописать нормальный псевдокод
 
## Сделать понятное и нормальное описание
 
 
 
== 4. Суффиксный массив ==
 
# [[Суффиксный массив]]
 
# [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
# [[Цифровая сортировка]]
 
# [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
# [[Алгоритм Касаи и др.]]
 
## Можно добавить псевдокод
 
# [[Алгоритм Карккайнена-Сандерса]]
 
# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
## Над этим конспектом ещё нужно помедитировать...
 
 
 
== 5. Задача о наименьшем общем предке ==
 
# [[Метод двоичного подъема]]
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# '''!!!''' [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
## Добавить оптимизацию по памяти
 
## Написать псевдокод
 
## Добавить сведение задачи RMQ к задаче +/-1 RMQ
 
# [[Алгоритм Шибера-Вишкина]]
 
# [[Сведение задачи RMQ к задаче LCA]]
 
 
 
== 6. Матроиды ==
 
* Тут вообще все конспекты нужно править. Добавлять категории и по мелочи красоту наводить. Могут даваться в нагрузку, если выбранная тема будет маленькой
 
# [[Определение матроида]]
 
# [[Примеры матроидов]]
 
# [[Прямая сумма матроидов]]
 
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
# '''!!!''' [[Жадный алгоритм поиска базы минимального веса]]
 
## Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна.
 
# [[Теорема о базах]]
 
# [[Аксиоматизация матроида базами]]
 
# [[Теорема о циклах]]
 
# [[Аксиоматизация матроида циклами]]
 
# [[Ранговая функция, полумодулярность]]
 
# '''!!!''' [[Двойственный матроид]]
 
## Можно добавить доказательство через ранговую функцию
 
# [[Оператор замыкания для матроидов]]
 
 
 
== 7.Пересечение матроидов ==
 
# [[Пересечение матроидов, определение, примеры]]
 
# [[Лемма о паросочетании в графе замен]]
 
# [[Лемма о единственном паросочетании в графе замен]]
 
# [[Граф замен для двух матроидов]]
 
# [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
# [[Алгоритм построения базы в пересечении матроидов]]
 
# [[Теорема Эдмондса-Лоулера]]
 
== 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>]]
 

Текущая версия на 17:27, 31 августа 2014