Основные понятия и определения дисциплины

Временная и вычислительная сложность.

Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.
Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

19. 
    Понятие P и NP-задач.
    

В зависимости от значений функции f(N) различают следующие классы алгоритмов:
1) Задачи, для которых
f(N)=aN (линейная сложность)
Примеры: топологическая сортировка, отыскание остовного дерева и связанных компонент дерева.
2) Задачи, для которых f(N) является нелинейной, но не более чем полиномиальной
f(N)=N^m, m2
Примеры: умножение матриц, нахождение кратчайшего пути в дереве, нахождение минимума остовных деревьев.
3) Задачи, о которых нельзя сказать, что они обязательно имеют экспоненциальную сложность, но для которых не известны быстрые алгоритмы, требующие менее, чем kⁿ операций.
Примеры: задача коммивояжера (TSP), определение изоморфизма, алгоритм нахождения максимальной клики в графе.
4) Задачи с обязательной экспоненциальной сложностью
f(N)=K^N , K2
Для этого класса не существует быстрых алгоритмов.
Примеры: прохождение всех остовных деревьев графа, всех его циклов и всех клик.
Для таких задач невозможно открыть новый алгоритм с меньшей сложностью.
Замечание: Для 3-го класса задач существуют теоретические предпосылки разработки эффективных алгоритмов с полиномиальной сложностью (класса 2), но которые пока не найдены. Разработка полиномиального алгоритма для любой из задач 3-го класса автоматически означала бы решение всех задач этого класса за полиномиальное время.
В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.
НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов).