Главная Прочее
Проблемы автоматизированной обработки информации
|
|
|||||
Теория -сложности.В 1980 г. (США) появилась первая монография о результатах работы по теории сложности, проводимой в … университете. Первоначально теорию называли: теория аналитической сложности, затем -сложности, наконец, теорией информационной сложности. Далее будем использовать термин «-сложность», чтобы существовало отличие от теории информационной сложности. Отличие от вычислительной сложности(оперируют с точной, полной и бесплатной информацией) в следующем: -сложность: изучают сложность задач, решаемых на основе неполной, неточной или платной информации, центральную роль играют понятия «информация», «реализуемый алгоритм». Точные нижние оценки погрешности решения в данной теории определяют без введения нормы, используя радиусы или диаметры информации, которые формируются различно для задач с полной или приближённой информацией и для класса реализуемых алгоритмов. Применяя теорию -сложности, можно ответить на следующие вопросы: можно ли решить данную задачу с точностью ; сколько это будет стоить или какова сложность задачи; Рассмотрим основные понятия этой теории. Пусть имеются два множества F={f} и G={g}, в которых f - элемент задачи, g - элемент решения. Класс всех подмножеств множества G обозначим 2G и введём оператор решения S Оператор решения S должен обладать следующими свойствами: а) для всех fF б) при h1 h2 (19) Пусть задано 0, характеризующее допустимую погрешность решения. Элемент gG, удовлетворяющий условию будем называть -приближённым. Для поиска -приближённого произвольного неизвестного пока f необходимо ввести информационный оператор , где H - образ множества F, N(f) - располагаемая информация об элементе f. Информационный оператор N называют полным, если он содержит всю информацию об f , и неполным в противном случае. Рассмотрим множество ![]() ![]() где V(N,f) - множество всех элементов f, неотличимых с помощью информации N(f) от некоторых фиксированных . Т.к. множество А должно удовлетворять условию типа (19), то существует оценка , которую называют локальным радиусом информации. Глобальный радиус информации в теории -сложности ![]() ![]() Очевидно, что если заданная допустимая погрешность , то получить решение с заданной точностью невозможно. Для введения понятия «сложность» необходимо задать множество P простейших операций: арифметические операции, операции сравнения, операции определения максимума из n чисел и т.п. Пусть N0 - приближённый информационный оператор. Его называют допустимым, если для всех fF существует программа вычисления N0(f) , состоящая из конечного числа простейших операций. Если такими операциями являются p1, p2, …, pl, то сложностью оператора N0(f) называют сумму ![]() ![]() Аналогично вводят определение сложности алгоритма . Эту сложность comp() называют комбинаторной, и в ней не учтены информационный оператор и заданная погрешность решения. Пусть R(N0) - класс реализуемых алгоритмов, для которых радиус информации r(R(N0),N0) не превосходит заданную погрешность. Сложность алгоритма ![]() ![]() а -сложность и характеризует минимальный по сложности алгоритм , способный решать данную задачу с необходимой точностью. В теории -сложности в качестве простейших операций выбирают пока 4 арифметические операции над вещественными числами и полагают, что сложность каждой из них равна 1. Это затрудняет использование данной теории даже в традиционных разделах математического программирования. Число практических приложений -сложности невелико. |
<< | СОДЕРЖАНИЕ | >> |
---|