• /
• Алгоритмы и анализ сложности

Модели вычислений

• Машины с произвольным доступом к памяти. Меры сложности вычислений. РАМ (ПДП-машины) и машины Тьюринга.
• Линейные программы. Битовые линейные программы. Ветвящиеся программы (деревья сравнений).
• Модельный алгоритмический язык. Сложность реализации основных конструкций на ПДП-машине.

Базовые структуры данных и основные методы разработки эффективных алгоритмов

• Списки, стеки (магазины), очереди. Алгоритмы выполнения основных операций
• Графы, деревья, бинарные деревья. Способы представления. Алгоритмы обхода деревьев.
• Метод разработки алгоритмов "разделяй и властвуй". Алгоритм умножения двоичных чисел. Техническая теорема об оценке роста функций, заданных реккурентными соотношениями. Передача сообщений с открытыми ключами (экспоненциация).
• Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм эффективного распознавания кс-языков. Задача глобального выравнивания слов.

Сортировка и поиск k-ого наименьшего элемента.

• Нижние оценки числа сравнений (в "худшем" и в "среднем").
• Алгоритм сортировки обменами (методом "пузырька").
• Алгоритм сортировки слиянием.
• Алгоритм пирамидальной сортировки (с помощью дерева).
• Алгоритм быстрой сортировки Хоара. Оценка сложности"в среднем".
• Алгоритм лексикографической сортировки.
• Линейные алгоритмы нахождения k-го наименьшего элемента (в "худшем" и в "среднем").
• Нижняя оценка числа сравнений для нахождения 2-го по величине элемента множества (теорема Кислицына).

Задачи поиска. Метод расстановки (хеширование)

• Алгоритмы выполнения основных операций при использовании "внешних" и "внутренних" цепей.
• Открытая адресация и повторное хеширование.
• Анализ сложности . Практический выбор хеш-функции.

Задачи поиска и работа с множествами

• .Деревья двоичного поиска. Алгоритм построения оптимального дерева двоичного поиска.
• 2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.
• Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.
• Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).
• Алгоритм проверки эквивалентности конечных автоматов.
• Сливаемые деревья и сцепляемые очереди.
• Биномиальные и фиббоначиевы кучи и алгоритмы работы с ними.
• В-деревья и алгоритмы работы с ними.
• Структуры данных для представления пространственной информации: 2-d деревья, квадродеревья, R-деревья порядка k.

Алгоритмы на графах

• Минимальное остовное дерево.
• Поиск в глубину и поиск в ширину в неориентированных и ориентированных графах. Топологическая сортировка.
• Алгоритм определения двусвязных компонент графа.
• Алгоритмы построения транзитивного замыкания графа и нахождения кратчайших путей.
• Задача о кратчайших путях из одного источника (алгоритмы Дейкстры и Беллмана-Форда).
• Задача о максимальном потоке в сетях. Алгоритм Форда- Фалкерсона.
• Алгоритм нахождения максимального потока за кубическое время.
• Простые сети и задача о максимальном паросочетании для двудольных графов.

Умножение матриц и связанные задачи

• Алгоритм Штрассена для умножения матриц.
• НВП-разложение матриц.
• Сложность обращения матриц, вычисления определителя и решения системы линейных уравнений.
• Алгоритм ЧР для умножения булевых матриц.
• Связь между умножением булевых матриц и нахождением транзитивного замыкания графа.

Алгоритмы вычислительной геометрии

• Задача об охране галереи.
• Алгоритмы триангуляции многоугольников.
• Построение выпуклого замыкания множества точек на плоскости.
• Триангуляции Делоне и диаграммы Вороного. Их приложения.
• Нахождение оптимального пути робота на плоскости с препятствиями.

Алгоритмы на строках

• Регулярные выражения, языки и недетерминированные конечные автоматы. Распознавание образцов, задаваемых регулярными выражениями.
• Алгоритм Морриса-Пратта для задачи вхождения подслов.
• Алгоритм Бойера-Мура для задачи вхождения подслов.
• Алгоритм Кнута-Морриса-Пратта (Монте-Карло и Лас-Вегас).
• Суффиксные деревья и решаемые с их помощью задачи. Алгоритм Укконена для построения суффиксного дерева за линейное (от его размера) время.
• Применения суффиксных деревьев.

Синтез программ и базис функциональных зависимостей

• Вычислительные модели Тыугу и функциональные зависимости в реляционных БД. Алгоритм поиска от цели ("обратная волна").
• Алгоритм поиска от данных ("прямая волна") и его реализация за линейное время.

Обзор абстрактной сложности вычислений

• Аксиомы Блюма для абстрактных мер сложности.
• Существование сколь угодно сложно вычислимых предикатов (теоремы Цейтина и Рабина). Теорема об ускорении Блюма.

NP-полные задачи.

• Классы P и NP. Сводимость за полиномиальное время. Теорема Кука-Левина о NP-полноте задачи выполнимости булевых формул.
• Примеры NP-полных задач в логике, теории графов, алгебре, комбинаторике, математическом программировании: 3-КНФ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ, РАСКРАСКА, 3-СОЧЕТАНИЕ, РАЗБИЕНИЕ, РЮКЗАК, 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, КОММИВОЯЗЖЕР, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ, УРАВНЕНИЯ В СЛОВАХ и др.
• Подходы к решению NP-полных задач с использованием эвристических и приближенных алгоритмов.
• Класс PSPACE. Полнота задачи QBF в этом классе. PSPACE-полные игpы (обобщенная геогpафия, гекс).