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

Материал из Викиконспекты
Перейти к: навигация, поиск
(1. Основные определения. Простые комбинаторные свойства слов)
Строка 5: Строка 5:
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
# [[Основные определения, связанные со строками]]
 
# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
+
# '''!!!''' [[Период и бордер, их связь]]
 +
## Нормальное и правильное доказательство про НОД
 
# [[Слово Фибоначчи]]
 
# [[Слово Фибоначчи]]
# [[Слово Туэ-Морса]]
+
# '''!!!''' [[Слово Туэ-Морса]]
 +
## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
 +
## А ещё сделать ссылки на Википедию через интервики
  
 
== 2. Поиск подстроки в строке ==
 
== 2. Поиск подстроки в строке ==

Версия 20:51, 15 апреля 2014

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

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

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

  1. Основные определения, связанные со строками
  2. !!! Период и бордер, их связь
    1. Нормальное и правильное доказательство про НОД
  3. Слово Фибоначчи
  4. !!! Слово Туэ-Морса
    1. Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
    2. А ещё сделать ссылки на Википедию через интервики

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

  1. Наивный алгоритм поиска подстроки в строке
  2. Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
  3. Поиск наибольшей общей подстроки двух строк с использованием хеширования
  4. Префикс-функция
  5. Алгоритм Кнута-Морриса-Пратта
  6. Z-функция
  7. Автомат для поиска образца в тексте
  8. Бор
  9. Алгоритм Ахо-Корасик

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

  1. Суффиксный бор
  2. Сжатое суффиксное дерево
  3. Алгоритм Укконена

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

  1. Суффиксный массив
  2. Построение суффиксного массива с помощью стандартных методов сортировки
  3. Цифровая сортировка
  4. Алгоритм цифровой сортировки суффиксов циклической строки
  5. Алгоритм Касаи и др.
  6. Алгоритм Карккайнена-Сандерса
  7. Алгоритм поиска подстроки в строке с помощью суффиксного массива

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

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

6. Матроиды

  1. Определение матроида
  2. Примеры матроидов
  3. Прямая сумма матроидов
  4. Теорема Радо-Эдмондса (жадный алгоритм)
  5. Жадный алгоритм поиска базы минимального веса
  6. Теорема о базах
  7. Аксиоматизация матроида базами
  8. Теорема о циклах
  9. Аксиоматизация матроида циклами
  10. Ранговая функция, полумодулярность
  11. Двойственный матроид
  12. Оператор замыкания для матроидов

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

  1. Пересечение матроидов, определение, примеры
  2. Лемма о паросочетании в графе замен
  3. Лемма о единственном паросочетании в графе замен
  4. Граф замен для двух матроидов
  5. Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
  6. Алгоритм построения базы в пересечении матроидов
  7. Теорема Эдмондса-Лоулера

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

  1. Объединение матроидов, проверка множества на независимость
  2. Объединение матроидов, доказательство того, что объединение является матроидом
  3. Алгоритм построения базы в объединении матроидов

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]