Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками
Сортировка слиянием. Основная теорема для метода «разделяй и властвуй».
Алгоритм Карацубы умножения чисел, алгоритм Штрассена умножения матриц. Быстрое преобразование Фурье.
Оценка снизу количества сравнений при сортировке, быстрая сортировка Хоара, сложность в среднем и в худшем. Задача Дейкстры о голландском флаге, 3х-частное разбиение, эвристики выбора опорного элемента.
Алгоритмы нахождения k-й порядковой статистики - вероятностный и детерминированный. Метод сортировки TimSort.
Абстрактные типы данных, интерфейс и реализация, стек и очередь - реализация связанным списком и массивом.
Ассоциативные массивы, бинарные деревья поиска.
Сбалансированные деревья, 2-3 и красно-черные деревья.
B-деревья, геометрические приложения бинарных деревьев поиска.
Хеш-таблицы, реализация методом цепочек и открытой адресацией.
Распределенные хеш-таблицы. Фильтр Блума.
Графы, способы представления в программе. Поиск в глубину и поиск в ширину.
Топологическая сортировка. Алгоритм Косарайю поиска сильносвязанных компонент.
Очередь с приоритетами, реализация с помощью бинарной кучи. Пирамидальная сортировка. Алгоритм Дейкстры.
Минимальные остовные деревья. Алгоритмы Прима и Крускала.
Система непересекающихся множеств, (union-find), примитивная реализация, версия со взвешиванием и сокращением путей.
Жадные алгоритмы. Задача о расписании, задача о кэшировании, выбор непересекающихся интервалов. Оптимальные беспрефиксные коды, алгоритм Хаффмана.
Задача о рюкзаке. Задача о покрытии множествами. Оценка точности решения, получаемого с помощью жадного алгоритма.
Поиск кратчайших путей в графе из одной вершины. Алгоритм Дейкстры. Алгоритм Беллмана-Форда.
Поиск кратчайших путей в графе из всех вершин. Алгоритм Флойда. Алгоритм избавления от ребер отрицательной длины.
Динамическое программирование. Задача о максимальном независимом множестве в деревьях. Задача о наибольшей возрастающей последовательности. Расстояние редактирования и алгоритм Левенштейна.
Алгоритм динамического программирования в задаче о рюкзаке и задаче коммивояжёра. Задача о произведении матриц. Оптимальные бинарные деревья поиска. Динамика по профилю.
Максимальное паросочетание. Алгоритм Форда-Фалкерсона. Алгоритм Куна.
Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа.
Поразрядная сортировка. Сортировка строк. Tries.
Конечные автоматы. Регулярные выражения.
Поиск подстроки. Алгоритм Кнута-Морриса-Пратта. Алгоритм Ахо-Корасика. Алгоритм Бойера-Мура.
Суффиксные массивы и суффиксные деревья.
Линейное программирование. Стандартная форма. Двойственность. Симплекс-метод. Эвристики выбора входящей переменной.
Приложения линейного программирования. Траспортная задача, задача о паросочетании.
Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений. Сведение комбинаторных задач к задачам целочисленного линейного программирования.
Классы P и NP. Сведение задач. NP-полнота. 3-SAT, поиск гамильтонова пути, задача коммивояжёра, задача о рюкзаке, минимальное вершинное покрытие, уравнения в нулях и единицах.
Доказательство NP-полноты задач SAT, 3-SAT, о трехдольном сочетании, уравнений в нулях и единицах, о рюкзаке, целочисленного линейного программирования, о гамильтоновом цикле, коммивояжёра.
Приближенные методы решения NP-полных задач. Полиномиальный алгоритм решения задачи о рюкзаке с точностью (1-ε). Метод локального поиска при решении NP-задач.