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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
 +
Помним про добавление англоязычных терминов в конспекты.
 +
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
# [[Основные определения, связанные со строками]]
 
# [[Основные определения, связанные со строками]]

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

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. Помним про добавление англоязычных терминов в конспекты.

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

  1. Основные определения, связанные со строками
  2. Период и бордер, их связь
  3. Слово Фибоначчи
  4. Слово Туэ-Морса

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]