Автоматизированное проектирование. Норенков И.П. - 115 стр.

 5@!"! 4                            %!#*%!#&F*:,$*   $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

      QD./.0-1 -.48++ ,D4L04,-+. В теории сложности выделяют массовые и индивидуальные за-
дачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовы-
ми значениями исходных данных. Исследования сложности проводятся в отношении массовых задач
и получаемые выводы, как правило, относятся к наихудшему случаю — к наиболее неблагоприятно-
му возможному сочетанию исходных данных.
      Цель исследований — установление вида зависимости объема Q требуемых вычислений от раз-
мера задачи N. Объем вычислений может определяться числом арифметических и логических опера-
ций или затратами процессорного времени ЭВМ с заданной производительностью. Размер задачи в
общем случае связывают с объемом описания задачи, но в приложениях понятие размера легко напол-
няется более конкретным содержанием.
      Далее, в теории сложности задач выбора вводят понятие эффективных и неэффективных алго-
ритмов. К эEE$%&'(*./ относят алгоритмы с полиномиальной зависимостью Q от N, например, ал-
горитмы с функцией Q(N) линейной, квадратичной, кубической и др. Для *$BEE$%&'(*., алгоритмов
характерна экспоненциальная зависимость Q(N).
      Важность проведения резкой границы между полиномиальными и экспоненциальными алгорит-
мами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличени-
ем быстродействия Б используемых ЭВМ (табл. 4.1, в которой указаны размеры задач, решаемых за
одно и то же время ? на ЭВМ с быстродействием Бi при различных зависимостях сложности Q от раз-
мера N). Эти примеры показывают, что выбирая ЭВМ в O раз более быстродействующую, получаем
увеличение размера решаемых задач при линейных алгоритмах в O раз, при квадратичных алгорит-
мах в К1/2 раз и т.д.                                                                   M:BD+=: 4.)
      Иначе обстоит дело с неэффективными
алгоритмами. Так, в случае сложности 2N для       Q(N)       Б1        Б2 = 100 Б1  Б3 = 1000 Б1
одного и того же процессорного времени раз-       N          N1        100 N1       1000 N1
мер задачи увеличивается только на lgK / lg2
единиц. Следовательно, переходя от ЭВМ с          N2         N2        10 N2        31.6 N2
Б = 1 Gflops к суперЭВМ с Б = 1 Tflops, мож-      N3         N3        4.64 N3      10 N3
но увеличить размер решаемой задачи только
на 10, что совершенно недостаточно для прак-      2N         N4        6.64+N4      9.97+N4
тических задач. Действительно, в таких зада-
чах, как например, синтез тестов для БИС число входных двоичных переменных может составлять бо-
лее 150 и поэтому полный перебор всех возможных проверяющих кодов потребует выполнения более
2150 вариантов моделирования схемы.
      В теории сложности все комбинаторные задачи разделены на классы:
      — класс неразрешимых задач, в который входят массовые задачи, решение которых полным пе-
ребором принципиально невозможно с точки зрения современных научных представлений; этот класс
отделяется от других задач так называемым пределом Бреммермана, оцениваемым величиной N =
1093; отметим, что реальный предел неразрешимости значительно ниже;
      — класс P, к которому относятся задачи, для которых известны алгоритмы решения полиноми-
альной сложности;
      — класс NP, включающий задачи, для которых можно за полиномиальное время проверить пра-
вильность решения, т.е. ответить на вопрос, удовлетворяет ли данное решение заданным условиям;
очевидно, что P включено в NP, однако вопрос о совпадении этих классов пока остается открытым,
хотя по-видимому на этот вопрос будет получен отрицательный ответ;
      — класс NP-полных задач, характеризующийся следующими свойствами: 1) для этих задач не-
известны полиномиальные алгоритмы точного решения; 2) любые задачи внутри этого класса могут
быть сведены одна к другой за полиномиальное время. Последнее означает, что если будет найден по-
линомиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то за полиномиаль-
ное время можно будет решить любую задачу этого класса.
      Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к
решению некоторой комбинаторной задачи, следует сначала проверить, не принадлежит ли она к

 &.+.)$(*),$" . !"#$%!#&'&($"!))$*        +($*,#&($"!)&*                                   115