1) теории и методы (теория подобия, множеств, графов, численные методы). 2) матем. модели.
3) алгоритмы (решения общ. задач выч. кат. упорядочивания и поиска @, проблемной ориентации, предметной ориентации, решения системных задач).
Математ. модель технического объекта – это сов-ть матем. объектов (числа, переменные, матрицы, мн-ва) и соотношений между ними, которая адекватно отображает св-ва технического объекта, интересующие разработчика. В САПР для каждого иерархического уровня разработаны свои модели.
Требования к Математич Моделям:
1)Адекватность. ММ считается адекватной, если отражает заданные св-ва объекта с приемлемой точностью.
2)Точность - степень совпадения значений вых. пар-ров модели и объекта.
3)Универсальность. Определяется числом и составом учитываемых в модели вх. и вых. пар-ров.
4)Экономичность. Определяется затратами выч. ресурсов для ее реализации (объем памяти и время работы)
Графы.
Графы называются изоморфными если у них одинаковое количество вершин и каждой паре вершин, соединенных в одном графе, соответствует пара вершин, соединенных в другом.
Цикл, в котором содержатся все ребра – Эйлеров цикл. Необходимое и достаточное условие его существования – четкость степеней всех вершин.
Граф, изоморфный плоскому, но имеющий пересечения ребер, называется планарным.
Достат. условие сущ-ия Гамильтонова цикла:
1) если в графе с n вершинами для любой пары вершин Xi, Xj выполяется условие: p(xi)+p(xj)>=n, то в таком графе сущ. гамильтонов цикл. или 2) в графе сущ. гамильтонов цикл, если для любой вершины xi выполнено условие p(xi)>=n/2.
Теорема Понтрягина-Куратовского: граф планарен тогда и только тогда, когда он не содержит подграфов гомеоморфных полному графу K5 и полному продольному графу К3,3.
Характеристические числа графа: 1)Цикломатическое число V(G) - число ребер, кот. необх. удалить из графа, чтобы он стал деревом (или лесом, если граф был несвязным)
k=|U| - число ребер графа, |T| = n-1 - число ребер дерева, V(G) = k-n+1, V(G)=k-n+p (если дерево)
2) Хроматическое число K(G)- наим. число непересекающихся подмн-в вершин, на кот. можно разбить вершины графа так, чтобы ребра графа соединял вершины только разных подмножеств (только разноокрашенные вершины).
Число внутренней устойчивости-a(G)- max кол-во несмежных вершин
Число внешней устойчивости - b(G) минимальная мощность Xs(b(G)=min|Xs|)
Граф в котором все вершины попарно смежны – полный Kn
Полный двудольный граф: все вершины из х1 связаны со всеми вершинами из х2: К3,3,
Алгоритм размещения- задача нахождения местоположения эл-ов на коммутационном поле, при кот. создаются наиболее благоприятные условия для соединений.
Делят на: 1) алгоритмы решения матем. задач, явл. моделями задач размещения а)Метод ветвей и границ
2) конструктивные алгоритмы начального размещения а) Пошаговый алгоритм.
3) итерационные алгоритмы улучшения начального размещ. а) Алгоритм парных перестановок. б) Алгоритм Штейнберга. 4) непрерывно-дискретные алгоритмы размещения
Алгоритмы трассировки межсоединений Задача геометрического построения на поле всех цепей данного конструктив., координаты начала и конца которых определены при размещении, с ограничениями:разрешено r проводников или нет; возможен переход со слоя на слой; сколько слоев для трассировки; под каким углом можно проводить проводник; допустимая ширина проводников и расстояние между ними; максимальная длина двух соседних параллельных проводников.
Задачу трассировки межсоединенийобычно делят на подзадачи:
1Построение списка соединений: а) алгоритм Прима б) алгоритм Коскала
2.Определение слоя (задача расслоения).
3.Определение порядка трассировки (порядок проведения соединений) Порядок влияет на качество трассировки: а) метод прямоугольников
4.Алгоритм трассировки: а) волновой алгоритм и модификации: - кодирование по mod3, - метод путевых координат. б) лучевые алгоритмы: - алг. Абрайтиса, - малоповоротный (+скорость на 2 поряддка выше, чем у волнового), - канальный (Достоинства:Скорость на 1-2 порядка выше, чем у волнового. Не нужно хранить все ДРП. Проводники проводятся с учетом следующих на обоих этапах. Недостаток: Используется только для регулярных структур).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.