Участник:Shersh/Тикеты по конспектам year2012

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

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

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

• Наивный алгоритм поиска подстроки в строке
• Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
• Поиск наибольшей общей подстроки двух строк с использованием хеширования
• Префикс-функция
• Алгоритм Кнута-Морриса-Пратта
• Z-функция
• Автомат для поиска образца в тексте
• Бор
• Алгоритм Ахо-Корасик

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

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

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

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

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

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

Матроиды

• Определение матроида
• Примеры матроидов
• Прямая сумма матроидов
• Теорема Радо-Эдмондса (жадный алгоритм)
• Жадный алгоритм поиска базы минимального веса
• Теорема о базах
• Аксиоматизация матроида базами
• Теорема о циклах
• Аксиоматизация матроида циклами
• Ранговая функция, полумодулярность
• Двойственный матроид
• Оператор замыкания для матроидов

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

• Пересечение матроидов, определение, примеры
• Лемма о паросочетании в графе замен
• Лемма о единственном паросочетании в графе замен
• Граф замен для двух матроидов
• Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
• Алгоритм построения базы в пересечении матроидов
• Теорема Эдмондса-Лоулера

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

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

Теория расписаний

• Классификация задач
• Методы решения задач теории расписаний
• Правило Лаулера
• Flow shop
• [math]1 \mid \mid \sum U_{i}[/math]
• [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math]
• [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math]
• [math]1 \mid outtree \mid \sum w_i C_i[/math]
• [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math]
• [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math]
• [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]
• [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math]
• [math]P \mid pmtn, r_i \mid L_{max}[/math]
• [math]Q \mid pmtn \mid C_{max}[/math]
• [math]Q \mid pmtn, r_{i} \mid L_{max}[/math]
• [math]Q\mid\mid\sum{C_i}[/math]
• [math]R2 \mid \mid C_{max}[/math]
• [math]F2 \mid \mid C_{max}[/math]
• [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math]
• [math]O2 \mid \mid C_{max}[/math]
• [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
• [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math]
• [math]J2\mid p_{ij} = 1\mid L_{max}[/math]