Главная Прочее
Проблемы автоматизированной обработки информации
|
|
|||||
Теория вычислительной сложности![]() ![]() В теории вычислительной сложности формируется пара , составленная из алгоритма А, предназначенного для решения системы задач S и , в частности, конкретной (индивидуальной) задачи s из семейства S. Для любой пары сложность можно оценивать системой показателей, каждый из которых называют сигнализирующей функцией. Наибольшее распространение получила сигнализирующая времени TA(S) , определяющая число шагов, которые необходимо проделать алгоритму А для решения индивидуальной задачи sS. Для оценки эффективности алгоритма А на семействе задач S в теории вычислительной сложности используется верхняя оценка сигнализирующей времени ![]() ![]() (17) а для выбора алгоритма из заданного набора {A}, наиболее эффективного для решения задач S, минимальная оценка ![]() ![]() (18) Помимо сигнализирующей времени формируют следующие функции сложности: сигнализирующая ёмкости - число ячеек оперативной памяти, необходимых для решения задачи sS алгоритмом А; сигнализирующая колебаний (поворотов) - количество циклов в программе для реальной ЭВМ, которые изменяют типовую последовательность вычислений; сигнализирующая режима - число обращений к долговременным запоминающим устройствам. (17) и (18) применяются ко всем сигнализирующим функциям. Наибольшее значение в теории имеют сигнализирующая времени, которую называют вычислительной сложностью и обозначают в виде функции, пропорциональной параметрам задачи. Различают задачи полиномиальной и экспоненциальной сложности: O(n2), O(n3) O(an), O(bnlogn) и т.п. Для (1) относятся задачи а) перемножения двух матриц порядка n; б) о кратяайшем маршруте на графе с n вершинами. Для (2) - экстремальные задачи комбинаторного типа и задачи теории графов. Задачи, для решения которых разработаны алгоритмы полиномиальной сложности, относятся к классу P-сложных задач. Задачи, для решения которых разработаны алгоритмы экспоненциальной сложности, относятся к классу NP-полных задач. Класс задач P-сложности является подклассом NP-сложных задач. В книге Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», Мир, 1982 предложена классификация задач принятия решений. Приведён список 300 NP-сложных задач. Этот подкласс характерен тем, что, если хотя бы для одной из них будет разработан алгоритм решения полиномиальной сложности, то аналогичные алгоритмы можно получить для всех NP-полных задач. Основная ценность теории вычислительной сложности - глубокий анализ проблемы построения эффективных алгоритмов и наличие алгоритмов для решения конкретных задач. |
<< | СОДЕРЖАНИЕ | >> |
---|