Алгоритмическая теория сложности

Пусть s S некоторая индивидуальная задача принятия решения из класса S и пусть x X - её решения на множестве X. Для решения любой задачи из класса S имеется алгоритм A, позволяющий с помощью программы P получить на универсальной машине (машина Тьюринга и машина Поста) со структурой (P,S) решение х задачи s.

Структура (P,S) - это частично рекурсивная функция, такая что (P,S)=х.

Обозначим через l() длину программы P, где - число знаковых символов её записи.

Чаще всего =2, т.к. для записи программы используется двоичный код.

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

(15)

Если (P,S)х , т.е. решение задачи s с помощью программы P не возможно, то .

Введение такого понятия сложности полезно для характеристики задач принятия решений, поскольку, во-первых, оно базируется на ключевых понятиях теории алгоритмов и вычисления, а во-вторых, его применяют для оценки индивидуальной задачи s ограниченного класса S, что необходимо в случае принятия оперативных решений. Однако для построения алгоритмов оперативного управления накладываются ограничения на вычисление самих характеристик сложности, они не должны быть слишком трудоёмкими. В этом отношении оценки алгоритмической сложности являются неудобными, т.к. - невычислимые функции.

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

Теория информационной сложности

Термин «информационная сложность» используют в основном для характеристики трудоёмкости вычислительного процесса при решении задач оптимизации и оптимизируемых задач принятия решений.

В информационной теории сложности используют предложенное Н.С.Бахваловым формальное понятие «метод решения».

Это понятие применяют к некоторому семейству задач математического программирования F, которое определяется тройкой , где E(X) - критерий оптимизации, зависящий от вектора переменных X размерности n;

G(X) - система ограничений вида

- линейные или нелинейные функции n переменных хi;

Х - область определения х, причём обычно X=R.

Дополнительно введём понятие оракула О, который определяется:

множеством допустимых вопросов, на которые О может «ответить», характеризуя параметры оптимизационного процесса, в том числе текущее состояние вектора X.

Множеством возможных ответов;

Функцией наблюдения , приводящей в соответствие каждому конкретному вопросу для любой индивидуальной задачи из семейства F конкретный ответ yY.

Любую индивидуальную задачу решают численным методом по итеративной схеме, причём на каждой итерации оракул «отвечает на вопрос», поставленный методом решения В.

Метод решения В - набор инструкций для формирования на каждой итерации вопросов «оракулу» и набор правил, определяющий момент останова процесса вычислений и момент формирования решения. По отношению к методу В «оракул О» можно трактовать как описание индивидуальной задачи из семейства F.

Ключевой характеристикой теории информационной сложности является трудоёмкость метода В по отношению к индивидуальной задаче FГF. Она определяется числом итераций, требуемых для получения решения с погрешностью не ниже заданной. Погрешность определяют как меру отклонения от оптимального решения.

Трудоёмкость метода В для семейства задач F определяют как верхнюю грань трудоёмкостей индивидуальных задач. Аналогично вычисляют и погрешность.

Информационной сложностью N() решения задач семейства F с помощью метода В и оракула О называют минимальную трудоёмкость, с которой методом В можно решить любую индивидуальную задачу из класса F с погрешностью, не превышающей .

 
< Пред   СОДЕРЖАНИЕ   Скачать   След >