Полупроводниковые микросхемы. Многокристальная и однокристальная микросхема. Гибридно-плёночные микросхемы, страница 15

1)  Множество ограничений: минимальная длина двух параллельно идущих проводников.

Противоречивость требований.

17. Виды обеспечения САПР

САПР – это организационно-техническая схема, состоящая из комплекса средств САПР, взаимосвязанных с необходимыми подразделениями или специалистами пользователей  и выполняющие автоматизированное проектирование.

КСАП – совокупность видов обеспечения автоматизированного проектирования.

Существует 7 видов обеспечения САПР:

·  ТО – техническое обеспечение – совокупность взаимосвязанных и взаимодействующих технических средств, предназначенных для автоматизированного проектирования.

·  МО – математическое обеспечение – совокупность математических методов, математических моделей и алгоритмов проектирования, необходимых для выполнения автоматизированного проектирования.

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

·  ПО – программное обеспечение – совокупность машинных программ, необходимых для выполнения автоматизированного проектирования.

·  ЛО – лингвистическое обеспечение – совокупность языков проектирования, включая термины и определения, правила формализации естественного языка, методы сжатия и развертки текста.

·  ОО – организационное обеспечение – совокупность документов, устанавливающих состав проектной организации и ее подразделений, связи между ними, их функции и форму представления результатов проектирования.

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

Основные требования к математической модели:

·  Адекватность. Модель считается адекватной, если отражает заданные свойства объекта с приемлемой точностью. Под точность понимается степень совпадения значений параметров объекта и модели.

·  Универсальность – определяется числом и составом, учитываемых в модели входных и выходных параметров. Экономичность – учитывается затратами вычислительных ресурсов для ее реализации.

Наиболее широко в САПР используется теория графов.

18. Классы математических задач. Эффективность алгоритмов.

Разделим математические задачи на 2 класса:

1)  задачи, которые могут быть решены с помощью алгоритмов; 2) задачи, для которых алгоритмы не могут быть написаны Таким образом, переформулируем классы решаемых задач:

1)  P–задачи, для которых могут быть использованы полиномиальные алгоритмы;

2)  NP–задачи, для которых существуют только экспоненциальные алгоритмы.  – свойства экспоненциального роста.  – свойства полиномиального роста. Эффективность алгоритма – максимальное количество элементарных операций, выполняемых при его работе. Обозначение: .Множество функций, для которых существуют константа C и номер  такие, что:       при          Алгоритм зависит от исходных данных (их количества и характера):  покрывает все  при . Если  полиномиальная функция, то это P-задача и наоборот. Существуют NP полные задачи, которые за полиномиальное время можно свести NP трудную задачу. Большинство задач граф. являются NP-трудными задачами. В САПР в основном используются полиномиальные алгоритмы.