8. Алгоритмы с возвратом.

9. Алгоритм нахождения гамильтоновых циклов в графе.

10. Метод ветвей и границ.

11. Остовные деревья графа. Алгоритмы нахождения дерева минимального веса: алгоритм Прима, алгоритм Крускала.

12. Эффективность алгоритмов и её составляющие. Алгоритмы и их сложность. Доминирование. О-функции и их особенности.

Существует множество задач, решение которых с вычислительной точки зрения лежит за пределами возможностей человеческого мозга.

Эффективность программы является важной ее характеристикой и имеет две составляющие: память и время. Пространственная составляющая измеряется количеством памяти, требуемой для выполнения программы. Временная эффективность программы определяется временем, необходимым для ее выполнения. Лучший способ сравнения эффективности алгоритмов состоит в сопоставлении их порядков сложности, причем метод применим как к пространственной, так и к временной составляющей. Порядок сложности алгоритма выражает его эффективность через количество обрабатываемых данных.

Число шагов работы программы, как функции от размерности, называется сложностью алгоритма. Порядок алгоритма - это функция, доминирующая над точным выражением временной сложности. Говорят, что функция g(x) доминирует над функцией f(x), если существует некоторая константа C такая, что C*g(a) > f(a) для всех значений a.

При анализе сложности используют частный случай доминирования, известный как ассимптотическое доминирование. Функция g(x) синтаксически доминирует над f(x).

Хорошая функциональная оценка должна доминировать над действительной функцией и должна быть близка к действительной функции насколько это возможно.

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

Существуют три правила для определения сложности:

1. О(k*f) = O(f), где f - функция, а k - const.

Постоянные множители не имеют значения для определения порядка сложности.

2. O(f*g) = O(f) * O(g), где f, g - функции.

Порядок сложности произведения двух функций равен произведению их сложности.

3. O(f+g) = доминанта [O(f), O(g)]

Для применения третьего правила необходимо понимание различий доминирущих функций, поэтому рассмотрим список функционального доминирования функций, часто используемых для оценки сложности алгоритма. Функции приведем в порядке убывания доминирования.

X^x доминирует над X!

X! доминирует над a^x

a^x доминирует над b^x, если a > b

a^x доминирует над x^n, если a > 1

x^n доминирует над x^m, если n > ma

x доминирует над logax, если a > 1

loga(x) доминирует над logb(x), если b > a > 1

loga(x) доминирует над -1

где m, n, a, b - const

Алгоритмы O(1) принято называть алгоритмами константой сложности. Это алгоритмы, требующие одного и того же времени независимо от размера данных.

Порядок алгоритма полиномиальной сложности обозначается O(x^n).

Алгоритмы, имеющие сложность более высокого порядка называются NP-сложные. Приведем сравнение роста времени выполнения для алгоритмов, характеризующихся различными порядками сложности.

13. Правила для определения сложности. Функции, часто используемые для оценки сложности алгоритмов (список функционального доминирования). Сравнение алгоритмов с различными порядками сложности.

14. Анализ алгоритмов и определение их сложности по управляющим структурам. Контрольные замеры. Критический взгляд на О-анализ. (ограниченность О-анализа).

15. Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач. Недетерминированное вычисление и класс NP.

16. Теория NP-полных задач. Структура класса NP.

17. Методы решения NP-полных задач. Применение теории NP-полноты для анализа задач.