Математические основы криптологии. Галуев Г.А. - 10 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

19
всем входам данного размера, то она называется
средней слож-
ностью. Обычно среднюю сложность найти труднее чем слож-
ность в худшем случае.
Теория сложности в основном имеет дел со сложностью
задач в худшем случае. Для анализа работы алгоритма нужны
модели вычислительных машин, достаточно точно отражающих
основные черты реальных машин. В качестве таких моделей ис-
пользуются машины с
произвольным доступом к памяти, ма-
шины с
произвольным доступом к памяти и хранимой про-
граммой, детерминированная и недетерминированная маши-
ны Тьюринга и другие.
Если алгоритм обрабатывает входы размера
n за время
τ
=
2
cn ,где с - const, то говорят что временная сложность этого ал-
горитма есть
)(
2
no
(читается порядка
2
n ). Строго в математи-
ческом смысле: неотрицательная
))(( ) (
N
f
Oестьn
g
если
существуют постоянные
с и
0
n , для которых
0
( ) | ( ) | .gn c f N ïðèn n
≤
≥
1
110
( ) ...
mm
mm
Å
ñëè g n a n a n a n a
−
−
=
++++
, то
)(n
g
явля-
ется
полиномиальной функцией степени m т.е.
)( ) (
m
nOng =
.
Полиномиальным алгоритмом или алгоритмом поли-
номиальной временной сложности называется алгоритм, у ко-
торого временная сложность равна
τ
=
))(( n
P
O
, где Р(n) - неко-
торый полином, а n - размер задачи (входа). Алгоритмы, вре-
менная сложность которых есть
τ
=0(
)(nP
c ), где с -const, Р(n) -
полином, называется
экспоненциальными.
Для примера в таблице приведены времена для различных
классов алгоритмов при
6
10=n
на обычной последовательной
ЭВМ с быстродействием
6
10
операций в секунду.
Класс
алгоритма
Слож-
ность
Число опера-
ций при
6
10
n
Реальное
время
20
Полиномиаль-
ный
O(1)
1 1 мс.
Линейный
O(n)
10
6
1сек.
Квадратичный
O(n
2
)
10
12
10 дней.
Кубический
O(n
3
)
10
18
27397 лет.
Экспоненци-
альный
O(2
n
)
10
30130
10
301016
лет.
Из таблицы видно, что при
τ
=О(n
3
)выполнение алгоритма
становится практически невозможно на последовательной ма-
шине. Однако на машине с 10
6
параллельно работающими про-
цессорами вычисление алгоритма сложностью
τ
=О(n
3
) может
занять 10 дней. В тоже время вычисление алгоритма сложностью
τ
=О(2
n
) практически невозможно даже на параллельной машине
с одним триллионом процессоров.
Задачи, которые решаются за полиномиальное время назы-
ваются
решаемыми, так как они обычно могут быть решены для
задач достаточно большой размерности
n. Задачи, которые не
могут быть систематически решаемыми за полиномиальное вре-
мя называют нерешаемыми или просто трудными.
Существуют и
алгоритмически неразрешимые задачи,
для которых невозможно создать алгоритм решения. Например,
десятая проблема Гильберта: существует ли алгоритм, решаю-
щий в целых числах уравнение
0),...,(
1
=
n
xxP
для многочлена
Р с целыми коэффициентами. Доказано,
что такого алгоритма не существует.
На рисунке представлена классификация задач по степени
их сложности и дано их возможное наглядное соотношение друг
с другом (точно это соотношения не известно).

Страницы