WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Владимирский государственный университет» Кафедра Конструирования и технологии радиоэлектронных средств В. Р. АСЛАНЯНЦ УЧЕБНАЯ САПР ЭЛЕКТРОННЫХ СРЕДСТВ ПРАКТИКУМ Владимир 2007 УДК 621.396.6.001 (076.5) А90 Рецензенты:

Доктор технических наук, профессор, заведующий кафедрой «Конструирование, технология и производство РЭС» Московского авиационного института (Государственного университета) М.Н. Ушкар Кандидат технических наук, преподаватель Владимирского государственного университета Г.Ф. Долгов Печатается по решению редакционно-издательского совета Владимирского государственного университета Асланянц В.Р.

А90 Учебная САПР электронных средств:

Практикум / Владим. гос. ун-т; Владимир, 2007. 60 с.

ISNB Основное назначение практикума показать, как применяются объекты и методы дискретной математики: множества и отношения (нечеткие множества в том числе), исчисление высказываний и алгебра логики, алгоритмы, теория графов и математическое программирование (методы решения оптимизационных задач) для формирования математических моделей электронных средств и алгоритмов синтеза топологии коммутационных плат. Описана структура учебной САПР CROCUS-3 и методы работы с ней.

Содержит перечень заданий к лабораторным работам и УИРС, список из 40 контрольных вопросов.

Предназначен для студентов специальностей 210201 и 210202 дневного и заочного отделения, выполняющих лабораторные работы по дисциплине «Математические основы информатики и САПР» и УИРС на 3-м курсе, Ил. 18. Библиогр.: 12 назв.

УДК 621.396.6.001 (076.5) ISNB 5-230-04841-7 © Владимирский государственный университет, 2007 2 ВВЕДЕНИЕ Системы автоматизированного проектирования электронных средств (САПР ЭС) - основной инструмент проектировщика электронной аппаратуры. Математическое обеспечение САПР можно охарактеризовать двумя составляющими: математические модели (ММ) и алгоритмы решения проектных задач. ММ и алгоритмы синтеза топологии коммутационных плат основаны на следующих разделах дискретной математики: множества и отношения (нечеткие множества в том числе), исчисление высказываний и алгебра логики, алгоритмы, теория графов и математическое программирование (методы решения оптимизационных задач). Основная цель практикума - научить студентов специальностей 200800 и 220500 применять эти разделы математики в проектных задачах.

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

Эта цель достигается 2-мя средствами:

1. Студент имеет возможность посмотреть на экране видеомонитора процесс работы проектирующей процедуры в пошаговом режиме.

2. Студенты изучают и объясняют при защите лабораторных работ мелкомасштабные схемы алгоритма.

Использование практикума удобно, например, в цикле из 4-х лабораторных работ, в каждой из которых применяется одна из проектирующих программ, указанных в разделе 1. В результате студенты выполняют конструкторское проектирование небольшой ячейки ЭС. Фронтальный метод выполнения лабораторных работ создает у студента целостное представление о процессе проектирования.

1. ДИСКРЕТНАЯ МАТЕМАТИКА Наиболее важными разделами дискретной математики, которые применяются для формирования математических моделей (ММ) объектов проектирования в области электроники и для получения оптимальных проектных решений, являются следующие:

• теория множеств и отношений;

• математическая логика (логика Буля в частности);

• алгоритмы;

• теория графов и гиперграфов;

• математическое моделирование;

• математическое программирование (теория оптимизации).

Из перечисленных разделов математическое моделирование относится не только к дискретной математике, поскольку помимо дискретных ММ широко используются непрерывные ММ.

Рассмотрим кратко содержание перечисленных разделов.

Теория множеств и отношений Для задания множеств применяют 2 способа [7]:

• перечисление элементов множества;

• задание способа конструирования множества.

Упорядоченные множества называют кортежами (векторами).

В алгебре множеств применяются операции над множествами:

• объединение множеств;

• пересечение;

• разность (эта операция двухместная);

• дополнение (эта операция тоже двухместная);

• разбиение;

• декартово (прямое) произведение.

Отношения на множествах лежат в основе реляционного исчисления и применяются в наиболее распространенных в настоящее время реляционных базах данных.

Частные случаи отношений:

• отношения эквивалентности;

• отношения порядка и др.

Нечеткие множества – основа для нечеткой логики и нечеткой математики.

Исчисление высказываний (логика Буля) Формализация силлогистики (логики Аристотеля), выполненная Дж.

Булем, привела к появлению исчисления высказываний (булевой логики) [11]. В логике Буля сложные высказывания представляются в виде ППФ – правильно построенных формул логики.

Дж. Булем были введены также простейшие функции алгебры логики - конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность и др. Простейшие и более сложные булевы функции описываются таблицами истинности. В исчислении высказываний (одной из дедуктивных систем) к формулам (сначала к аксиомам) применяют правила вывода (правило отделения, правило резолюции и др.) и получают цепочку выводов.



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

Булевы функции могут быть представлены в дизъюнктивной (ДНФ), конъюнктивной (КНФ) нормальной форме, в совершенной ДНФ (СНДФ) или совершенной КНФ (СКНФ). Эти формы используются при синтезе логических схем ЭС, в том числе при программировании ПЛИС.

Теория алгоритмов Интуитивное понятие алгоритма подкрепляется эмпирическими свойствами алгоритмов:

• дискретность;

• детерминированность;

• массовость;

• результативность.

Существуют так называемые алгоритмически неразрешимые проблемы (задачи), например проблема самоприменимости (парадокс брадобрея) и др.

К способам представления алгоритмов относят:

• словесное описание алгоритма;

• схемное описание;

• псевдокоды;

• языки программирования.

Наиболее важными критериями оценки и сравнения алгоритмов являются следующие:

• быстродействие алгоритма;

• точность алгоритма;

• временная сложность.

Теория графов Графы и гиперграфы широко используются в качестве математических моделей (ММ) схем и конструкций в задачах синтеза и анализа ЭС [2,6,7,8].

Понятие граф опирается на теорию множеств и отношений. Граф представляет собой бинарное отношение на множестве объектов (вершин графа). Граф состоит из вершин и ребер (дуг для ориентированного графа).

К разновидности графа относят:

• мультиграф;

• двудольный граф;

• полный граф;

• дерево;

• гиперграф.

Гиперграф представляет собой n-арное отношение на множестве вершин, т.е. гиперребра могут быть инцидентны трем, четырем и белее вершинам.

К числовым способам представления графа относят:

• матричное представление;

• списковое представление.

Существует два особенных цикла в графе: эйлеров и гамильтонов.

Простой признак существования эйлеров цикла (это первый результат в теории графов) сформулирован в виде теоремы Эйлера.

Для гамильтонова цикла простого признака существования нет.

Нахождение гамильтонова цикла минимальной длины во взвешенном по ребрам графе называется задачей коммивояжера.

Изучение графов облегчается путем введения чисел графа [12]:

• цикломатического;

• хроматического;

• числа внутренней устойчивости;

• числа внешней устойчивости;

• числа планарности.

Для определения максимального ВУМ (внутренне устойчивого множества вершин) и раскраски вершин графа применяют метод Магу и эвристические алгоритмы.

При автоматизированном проектировании однослойных конструкций ЭС применяют теорию планарных графов. Для планаризации схем ЭС применяют циклический метод Аусландера и Портера, алгоритмы Демукрона и др.

Математическое программирование Процесс разработки конструкции ЭС включает в себя целый ряд задач поиска оптимальных конструктивно-технологических решений на множестве вариантов, число которых, как правило, велико [7]. В автоматизированном конструировании необходимо от содержательной постановки задачи перейти к математической модели [2]. Такой переход называется формализацией, в которой выделяют две стороны: построение модели конструкции ЭС и математическая формулировка оптимизационной задачи.

Для поиска оптимального решения необходимо сформулировать цель поиска, выраженную в виде критерия оптимизации F (целевой функции), экстремальное значение которого отыскивается. Предполагается, что любые два варианта из области поиска (области определения целевой функции) можно сравнить, т.е. поставить им в соответствие число – значение критерия F, следовательно, на множестве вариантов задано заранее неизвестное отношение порядка.

Критерий F зависит от управляемых параметров (вектор X), которые можно менять в процессе поиска оптимума, и неуправляемых (вектор Z).

Тогда оптимизационная задача в общем виде формулируется следующим образом.

Требуется найти экстремальное значение критерия F:

extr F(X,Z) при m ограничениях qк(X,Z) ak, k = 1,2, …m ;

X D, где D – область допустимых решений.

Методы решения оптимизационных задач (3.1), (3.2) рассматриваются в области математики, именуемой математическим программированием [7]. Эти методы существенно зависят от характера целевой функции и ограничений, что положено в основу приведенной ниже классификации разделов математического программирования.

Линейное программирование (ЛП) изучает оптимизационные задачи, в которых функции F и q линейны относительно параметров X и Z.

Ряд возникших в практической деятельности инженера оптимизационных задач приводят к линейной целевой функции и линейным ограничениям. В качестве примера рассмотрим производственную задачу о распределении ресурсов.

Пусть имеются некоторые ресурсы (сырье, рабочая сила и т.п.) в ограниченных количествах b1, b2, …, bm. Известно, что для производства единицы j-й продукции необходим i-й ресурс в количестве aij. Требуется определить оптимальный план выпуска: какое количество хj каждого вида продукции следует выпускать, чтобы получить максимальную прибыль, если известна чистая прибыль сij от реализации единицы j-й продукции.





Математически эта задача сводится к поиску максимума линейной формы n Max F = хj c j j=при линейных ограничениях-неравенствах n xj bi, i = 1, 2, …, n ;

a j j= хj 0.

Если известны условия спроса, то на хj накладываются дополнительные ограничения xj pi, где pi – максимальное в условиях спроса количество j-й продукции.

Для решения задачи ЛП применяют симплекс-метод [7].

Нелинейное программирование (НП) - функции F и q нелинейны относительно X и Z, область допустимых решений D может быть невыпуклой и содержать бесконечное множество решений, а целевая функция чаще всего многоэкстремальна.

Общего метода решения задач НП не существует. Выбор метода осуществляется на основе априорной информации о характере целевой функции и ограничений.

Например, для одномерных задач НП (n = 1) известны классические методы: метод, основанный на числах Фибоначчи, метод «золотого сечения» и др.

Ограниченное применение в многомерных задачах находят дифференциальное исчисление, метод множителей Лагранжа.

К поисковым методам, основанным на итерационном принципе (принципе последовательных приближений), относятся:

• метод локального поиска на сетке;

• градиентный метод;

• метод наискорейшего спуска;

• метод покоординатного спуска;

• метод штрафных функций;

• метод случайного поиска.

Указанные методы обеспечивают нахождение одного из локальных экстремумов. Для отыскания глобального экстремума применяют:

• метод «кенгуру и мыши»;

• метод Монте-Карло.

Динамическое программирование – процесс решения естественным образом (или искусственно) распадается на этапы, и значение функции F определяется как сумма (произведение) соответствующих значений F на отдельных этапах, т.е. целевая функция F аддитивна (мультипликативна).

Примером может служить задача отыскания кратчайшего пути на взвешенном по ребрам графе, для решения которой может быть применен алгоритм Беллмана-Калаба. Частный случай этой задачи – трассировка проводников на печатной плате, для которой применяется волновой алгоритм [6].

Стохастическое программирование – параметры Z – случайные величины, и вместо функции F отыскивается экстремум ее математического ожидания.

Дискретное программирование – на X, Z наложено условие дискретности (например, целочисленности), т.е. область определения D представляет собой конечное множество. В зависимости от вида функции F и q задачи дискретного программирования могут быть линейными (целочисленное линейное программирование - ЦЛП) и нелинейными (дискретное нелинейное программирование - ДНП).

Для решения задач ЦЛП применяют:

• метод отсечений, основанный на многократном применении симплекс-метода;

• метод ветвей и границ;

• итерационные эвристические алгоритмы, которые можно назвать дискретными аналогами градиентных методов и др.

Для решения задач ДНП применяют:

• метод ветвей и границ;

• метод случайного поиска;

• эвристические алгоритмы (последовательные итерационные, дихотомические, генетические и др.). В этом случае можно говорить об эвристическом программировании.

Эвристическое программирование. Если решение задачи точными методами трудоемко, то довольствуются приближенным достаточно хорошим для практики решением, которое отыскивается с использованием специальных приемов – эвристик, позволяющих сокращать число просматриваемых вариантов. Эвристики разрабатываются на основе изучения и использования специфики конкретных задач.

Потребности практики автоматизированного конструирования ЭС обусловили развитие и широкое использование методов оптимизации, в которых ценой отказа от получения точного решения экстремальной задачи существенно уменьшается высокая трудоемкость, присущая описанным выше методам решения задач дискретного программирования. Для этого направления характерны два принципиально разных подхода: методы случайного поиска и эвристические методы.

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

Примером эвристических алгоритмов могут служить последовательные алгоритмы размещения конструктивных элементов и разбиения схем ЭС [1, 3, 5, 6], а также комбинаторные аналоги градиентных методов, рассмотренные в подразделе 4.1. Действительно, как известно градиентные методы основаны на свойстве непрерывности целевой функции, и применение идей градиентных методов к дискретным задачам может дать хорошие результаты только для определенного класса задач, что определяется экспериментально.

Один из путей построения эвристических алгоритмов – анализ процесса решения задачи некоторым точным методом и введение эвристик в этот процесс, обеспечивающих существенное сокращение объема вычислительной работы. Так, например, если в методе ветвей и границ после каждого ветвления сохранять лишь одно (или небольшое число) наиболее перспективных подмножеств решений, то процесс быстро сходится. Однако гарантий получения оптимального решения уже нет: оно может оказаться в отброшенном подмножестве решений.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.