Пример пооперационного временного анализа
В ряде случаев именно пооперационный анализ позволяет выявить тонкие аспекты рационального применения того или иного алгоритма решения задачи. В качестве примера рассмотрим задачу умножения двух комплексных чисел:
(a+bi)*(c+di)=(ac - bd) + i(ad + bc)=e + if
- Алгоритм А1 (прямое вычисление e, f – четыре умножения)
- Алгоритм А2 (вычисление e, f за три умножения)
Пооперационный анализ этих двух алгоритмов не представляет труда, и его результаты приведены справа от записи соответствующих алгоритмов.
По совокупному количеству элементарных операций алгоритм А2 уступает алгоритму А1, однако в реальных компьютерах операция умножения требует большего времени, чем операция сложения, и можно путем пооперационного анализа ответить на вопрос: при каких условиях алгоритм А2 предпочтительнее алгоритма А1?
Введем параметры q и r, устанавливающие соотношения между временами выполнения операции умножения, сложения и присваивания для операндов действительного типа.
Тогда мы можем привести временные оценки двух алгоритмов к времени выполнения операции сложения/вычитания – 
:
= q* , q>1;
=r* , r<1, тогда приведенные к временные оценки имеют вид:
= 4*q* +2* +2*r* = *(4*q+2+2*r);
= 3*q* +5* +5*r* = *(3*q+5+5*r).
Равенство времен будет достигнуто при условии:
4*q+2+2*r = 3*q+5+5*r, откуда:
q = 3 + 3r и следовательно при q > 3 + 3r алгоритм А2 будет работать более эффективно.
Таким образом, если среда реализации алгоритмов А1 и А2 – язык программирования, обслуживающий его компилятор и компьютер на котором реализуется задача – такова, что время выполнения операции умножения двух действительных чисел более чем втрое превышает время сложения двух действительных чисел, в предположении, что r << 1, а это реальное соотношение, то для реализации более предпочтителен алгоритм А2.
|
|
|
Конечно, выигрыш во времени пренебрежимо мал, если мы перемножаем только два комплексных числа, однако, если этот алгоритм является частью сложной вычислительной задачи с комплексными числами, требующей существенно значимого по времени количества умножений, то выигрыш во времени может быть ощутим. Оценка такого выигрыша на одно умножение комплексных чисел следует из только что проведенного анализа:
T = (q – 3 – 3*r)*
ТЕОРИЯ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ И СЛОЖНОСТНЫЕ КЛАССЫ ЗАДАЧ
Теоретический предел трудоемкости задачи
Рассматривая некоторую алгоритмически разрешимую задачу, и анализируя один из алгоритмов ее решения, мы можем получить оценку трудоемкости этого алгоритма в худшем случае – fa( 
)=O(g( )). Такие же оценки мы можем получить и для других известных алгоритмов решения данной задачи. Рассматривая задачу с этой точки зрения, возникает резонный вопрос – а существует ли функциональный нижний предел для g( ) и если «да», то существует ли алгоритм, решающий задачу с такой трудоемкостью в худшем случае.
|
|
|
Другая, более точная формулировка, имеет следующий вид: какова оценка сложности самого «быстрого» алгоритма решения данной задачи в худшем случае? Очевидно, что это оценка самой задачи, а не какого либо алгоритма ее решения. Таким образом, мы приходим к определению понятия функционального теоретического нижнего предела трудоемкости задачи в худшем случае:
= min { 
( 
(D)) }
Если мы можем на основе теоретических рассуждений доказать существование и получить оценивающую функцию, то мы можем утверждать, что любой алгоритм, решающий данную задачу работает не быстрее, чем с оценкой в худшем случае:
(D) = 
( )
Приведем ряд примеров:
1. Задача поиска максимума в массиве A=(a1,…,an) – для этой задачи, очевидно должны быть просмотрены все элементы, и = (n).
2. Задача умножения матриц - для этой задачи можно сделать предположение, что необходимо выполнить некоторые арифметические операции со всеми исходными данными, теоретическое обоснование какой–либо другой оценки на сегодня не известно, что приводит нас к оценке =Q ( 
). Отметим, что лучший алгоритм умножения матриц имеет оценку Q ( 
). Расхождение между теоретическим пределом и оценкой лучшего известного алгоритма позволяет предположить, что либо существует, но еще не найден более быстрый алгоритм умножения матриц, либо оценка Q ( ) должна быть доказана, как теоретический предел.
|
|
|
Сложностные классы задач
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач.
1) Класс P (задачи с полиномиальной сложностью)
Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с 
(n)=O( 
), где n - длина входа алгоритма в битах n = |D| [6].
Задачи класса P – это интуитивно, задачи, решаемые за реальное время.
Отметим следующие преимущества алгоритмов из этого класса:
o для большинства задач из класса P константа k меньше 6;
|
|
|
o класс P инвариантен по модели вычислений (для широкого класса моделей);
o класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).
Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи.
2) Класс NP (полиномиально проверяемые задачи)
Представим себе, что некоторый алгоритм получает решение некоторой задачи – соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность?
Рассмотрим, например задачу о сумме:
Дано N чисел – А = (a1,…an) и число V.
Задача: Найти вектор (массив) X=(x1,…,xn), xiє{0,1}, такой, что 
aixi = V.
Содержательно: может ли быть представлено число V в виде суммы каких-либо элементов массива А.
Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложно-стью: проверка aixi = V требует не более Q (N) операций.
Формально: 
Dє , |D|=n поставим в соответствие сертификат Sє 
, такой что |S|=O ( 
) и алгоритм 
= (D,S), такой, что он выдает «1», если решение правильно, и «0», если решение неверно. Тогда задача принадлежит классу NP, если F ( )=O ( 
).
Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (полиномиально) проверено.
3. Проблема P = NP
После введения в теорию алгоритмов понятий сложностных классов Эдмондсом (Edmonds, 1965) была поставлена основная проблема теории сложности – P = NP ? Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время ?
Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть полиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи.
На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пусто – рис 6.1
Дата добавления: 2018-02-28; просмотров: 559; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!