ПОИСК Статьи Чертежи Таблицы Элементы теории сложности из "Основы автоматизированного проектирования " В теории сложности выделяют массовые и индивидуальные задачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовыми значениями исходных данных. Исследования сложности проводятся в отношении массовых задач, и получаемые выводы, как правило, относятся к наихудшему случаю — к наиболее неблагоприятному возможном сочетанию исходных данных. [c.180] Цель исследований — установление вида зависимости объема Q требуе-мьгх вычислений от размера задачи N. Объем вычислений может определяться числом арифметических и логических операций или затратами процессорного времени ЭВМ с заданной производительностью. Размер задачи в общем случае связывают с объемом описания задачи, но в приложениях понятие размера легко наполняется более конкретным содержанием. [c.180] Важность проведения резкой границы между полиномиальными и экспоненциальными алгоритмами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличением быстродействия Б используемых ЭВМ (табл. 4.1, в которой указаны размеры задач, решаемых за одно и то же время Т на ЭВМ с быстродействием Б. при различньпс зависимостях сложности Q от размера N). Эти примеры показывают, что выбирая ЭВМ в раз более быстродействующую, получаем увеличение размера решаемых задач при линейных алгоритмах в К раз, при квадратичных алгоритмах в. Г раз и т. д. [c.181] Иначе обстоит дело с неэффективными алгоритмами. Так, в случае сложности 2 для одного и того же процессорного времени размер задачи увеличивается только на Ig / Ig 2 единиц. Следовательно, переходя от ЭВМ с Б = 1 Гфлопс к суперЭВМ с Б = 1 Тфлопс, можно увеличить размер решаемой задачи только на 10, что совершенно недостаточно для практических задач. Действительно, в таких задачах, как, например, синтез тестов для БИС, число входных двоичных переменных может составлять более 100 и поэтому полный перебор всех возможных проверяющих кодов потребует выполнения более 2 вариантов моделирования схемы. [c.181] Из результатов теории сложности следуют важные практические рекомен-дащш 1) приступая к решению некоторой комбинаторной задачи, необходимо сначала проверить, не принадлежит ли она к классу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и программ точного решения 2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальное время. [c.182] Вернуться к основной статье