Элементы теории алгоритмов. Абстрактный алфавит, алфавитный оператор, массовость, результативность, страница 4

Для успешной обработки конкретных данных с помощью алгоритмов надо получить оценки объема памяти и, что особенно важно, — времени работы.

Один из основных результатов Тьюринга—разделение всех представляемых в математике задач на два класса: для которых алгоритмы никогда не могут быть написаны, т. е. в формальном смысле постоянно нерешаемые; которые могут быть решены посредством алгоритмов. Класс решаемых задач может быть разделен на два подкласса: в котором эффективны только полиномиальные алгоритмы; в котором эффективны только экспоненциальные алгоритмы. Пусть А—алгоритм решения некоторого класса задач и n— размерность одной задачи из этого класса. В частном случае n может быть числом технологических операций, элементов в модели схемы, массивом, длиной входных данных и т. п. Функция  даст верхнюю границу для максимального числа основных операций (сдвиг, сравнение, сложение и т. п.), которые должен выполнить алгоритм для решения любой задачи размерности п. Тогда алгоритм называется полиномиальным, если    растет не быстрее, чем полином от n, в противном случае алгоритм А называется экспоненциальным.

Функции типа  могут рассматриваться как имеющие одинаковое свойство экспоненциального роста. Функции типа kn, kn², kn³, ..., где k—коэффициент, могут рассматриваться как полиномиальные. Для достаточно больших n значение экспоненциальной функции превышает значение полиномиальной функции. Для малых n полиномиальная функция может превышать экспоненциальную, но всегда есть п, для которой экспоненциальная функция больше. Заметим, что не каждый экспоненциальный (степенной) алгоритм будет неэффективным. Многие алгоритмы экспоненциального типа могут иметь, в частности, значительно меньшую действительную эффективность. Говорят, что время, затраченное алгоритмом, как функция размерности задачи называется временной сложностью алгоритма (ВСА). Другими словами, ВСА—это число единиц времени, требуемого для обработки входных данных задачи. Обозначается ВСА

Отметим, что известны некоторые экспоненциальные алгоритмы, применяющиеся в практике конструкторского и технологического проектирования, например метод ветвей и границ. Если алгоритм имеет ВСА  это означает, что решение по крайней мере одной индивидуальной задачи размерности п требует времени порядка  Но может оказаться, что большинство индивидуальных задач из этого класса требует для своего решения меньших затрат времени,

Алгоритмы, имеющие ВСА 0(kn}, 0(kn²) и О (kn³), считают эффективными и основными при решении конструкторских и технологических задач с помощью САПР. Многие задачи САПР могут иметь более чем один алгоритм решения. Причем скорость реализации алгоритма является в большинстве случаев свойством самого алгоритма и слабо зависит от ЭВМ, на которой он решается.

Кроме времени реализации алгоритма существуют другие меры оценки сложности. Сложность алгоритма можно характеризовать числом операций N и общим объемом информации Р, используемой алгоритмом. С числом операций алгоритма связано время его выполнения на конкретной ЭВМ. Объем информации связан с объемом памяти ЭВМ, необходимой машине для реализации этого алгоритма. Следовательно, время реализации алгоритма есть функция T=f(N).

В настоящее время наиболее перспективными методами оценки временной сложности алгоритмов при конструировании РЭА и ЭВА являются методы, позволяющие оценить алгоритм до его представления на алгоритмическом языке.

Отметим, что в современных САПР распределением памяти занимается операционная система и пользователь не знает, какую память (внешнюю или оперативную) ЭВМ он использует. Причем в связи с ростом объема обрабатываемой информации в современных ЭВМ основной характеристикой становится объем не оперативной, а внешней памяти.

Основной путь повышения скорости реализации алгоритма—это параллельное выполнение большого числа операций ввода, вывода и вычислений, проверки ветвей, поиска, сортировки, функциональных преобразований, конвейерной обработки и т. п.

В практике конструирования СБИС разрабатывают рекурсивные алгоритмы, разбивающие задачи произвольной размерности на / равных частей, где / велико как возможно. Эти алгоритмы в основном эффективнее тех, которые не используют процедуру разбиения.