ОО – организационное обеспечение – сов-ть док-ов, устанавливающая состав проектной организации и ее подразделений, связи м/ду ними, их ф-ции и форму представления ру-тов АП.
МтО – методическое обеспечение – сов-ть док-тов, устанавливающих состав и правила отбора для эксплуатации средств АП.
Математическое обеспечение САПР
1) теории и методы (теория подобия, множеств, графов, численные методы)
2) матем. модели
3) алгоритмы (решения общ. задач выч. кат. упорядочивания и поиска @, проблемной ориентации, предметной ориентации, решения системных задач)
Математ. модель технического объекта – это сов-ть матем. объектов (числа, переменные, матрицы, мн-ва) и соотношений между ними, которая адекватно отображает св-ва технического объекта, интересующие разработчика. В САПР для каждого иерархического уровня разработаны свои модели.
Требования к ММ:
1) Адекватность. ММ считается адекватной, если отражает заданные св-ва объекта с приемлемой точностью.
Точность - степень совпадения значений вых. пар-ров модели и объекта.
2) Универсальность. Определяется числом и составом учитываемых в модели вх. и вых. пар-ров.
3) Экономичность. Определяется затратами выч. ресурсов для ее реализации (объем памяти и время работы)
Наиболее широко в САПР исп-ся теория графов.
Основные понятия теории графов
Совокупность множества вершин Х и множества связей между ними U называется графом G(X,U). Если связь имеет направление, то она называется дугой, иначе - ребром. Если все связи графа дуги, то такой граф называется ориентиров., орграфом; если ребра - неорграф. Если в графе присутствуют и ребра и дуги - граф наз. смешанным. Две вершины наз. смешаными, если они соединены ребром или дугой. Две связи наз. смешаными, если они имеют общ. вершину. Вершина Хi инцидента Uij, если она является началом или концом Uij. Ребро/дуга Uij инцидентна Xi, если она входит или выходит из этой вершины. Число дуг/ребер, инцидентных вершине Xi наз. степенью этой вершины Px(Xi).
Для неорграфа EP(Xi)=2|U|.
Геометрически граф представляют мн-вом точек и мн-вом кривых, соединяющих эти точки.
Вершина, не имеющяя инцидентых ребер (дуг) наз. изолированной. Р(Хi)=0. Вершина, инцидентная только одному ребру/дуге, наз. висячей. Граф, в котором перемещаясь от вершины к вершине можно попасть в любую вершину называется связным; иначе - несвязным. Граф, в котором все вершины попарно смежны - полный. Kn (n-кол-во вершин).
Для полного графа |U|=n(n-1)/2
Граф, имеющий кратные ребра, наз-ся мультиграфом.
Граф, в котором опущены некот. ребра, а число вершин осталось прежним, наз.
частичным или суграфом. Граф, в кот. опущены некоторые вершины и инцидентные им
ребра, наз. подграфом. Граф, имеющий кратные ребра и петли, наз. псевдографом.
Если вершины графа можно разбить на два непересекающихся подмножества 
так, что не существует
ребер, соединяющих вершину из Х1 с вершиной Х2, то такой граф называют
двудольным, бихроматическим, Кенига.
Полный двудольный граф; все вершины из Х1 связаны со всеми вершинами из Х2: К3,3.
Графы наз. изоморфными, если у них одинаковое кол-во вершин и каждой паре вершин, соединенных в одном графе, соотв-т пара вершин, соединенным в другом:
Посл-ть ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину - маршрут. Маршрут, в котором все ребра различны - цепь.
Маршрут, для кот. различны все вершины - простая цепь. Замкнутая цепь - цикл, замкнутая простая цепь - простой цикл. Цикл, в кот. содержатся все ребра - Эйлеров цикл; необходимое и достаточное условие его сущ-ия - четность степеней всех вершин.
Простой цикл, кот. проходит через все вершины, называют гамильтоновым циклом.
Достат. условие сущ-ия: 1) если в графе с n вершинами для любой пары вершин Xi, Xj выполяется условие: p(xi)+p(xj)>=n, то в таком графе сущ. гамильтонов цикл. или 2) в графе сущ. гамильтонов цикл, если для любой вершины xi выполнено условие p(xi)>=n/2.
Несвязный граф без циклов, отдельные компоненты кот. являются деревом - лес. Связный граф без циклов - дерево. дерево, построенное на n вершинах содержит (n-1) ребро; а лес, состоящий из n вершин, p деревьев, содержит (n-p) ребер. Число различных деревьев связанного помеченного графа равно n(n-2) (определено химиком Каллом).
Различают два крайних дерева: последовательное
и звездное
. Дерево м.б. выделено из любого
графа, если оно содержит все вершины графа (это остов или покрывающее дерево).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.