Файл: Шпоры переделан.docx

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

Некоторые компоненты СМО характеризуются более чем одним вход­ным и (или) выходным потоками заявок. Правила выбора одного из воз­можных направлений движения заявок входят в соответствующие модели компонентов. В одних случаях такие правила относятся к исходным дан­ным (например, выбор направления по вероятности), но в некоторых слу­чаях желательно найти оптимальное управление потоками в узлах разветв­ления. Тогда задача моделирования становится более сложной задачей синтеза, характерными примерами являются маршрутизация заявок или синтез расписаний и планов.

36. Имитационное моделирование смо

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

Для описания имитационных моделей на системном уровне (такие мо­дели иногда называют сетевыми имитационными моделями — СИМ) чаще используют языки, ориентированные на события или процессы. Примерами первых могут служить языки Симскрипт, SMPL и ряд других. К числу вто­рых относятся языки Симула, SOL, а также популярный язык GPSS.

Источник входного потока заявок представляет собой алгоритм, в соот­ветствии с которым вычисляются моменты t_к появления заявок на

входе источника. Источники могут быть зависимыми и независимыми. В зависи­мых источниках моменты появления заявок связаны с наступлением опреде­ленных событий, например, с приходом другой заявки на вход некоторого устройства. Типичным независимым источником является алгоритм выра­ботки значений t_к случайной величины с заданным законом распределения.

Устройства в имитационной модели представлены алгоритмами вы­работки значений интервалов (длительностей) обслуживания. Чаще всего это алгоритмы генерации значений случайных величин с заданным законом распределения. Но могут быть устройства с детерминированным временем обслуживания или временем, определяемым событиями в других частях СМИ. Модель устройства отображает также заданную дисциплину обслуживания, поскольку в модель входит алгоритм, управляющий очередями на входах устройства.

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

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

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

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

38. Геометрические модели

Важной составной частью геометрических моделей является описа­ние поверхностей. Если поверхности детали — плоские грани, то мо­дель может быть выражена достаточно просто определенной информа­цией о гранях, ребрах, вершинах детали. При этом обычно используется метод конструктивной геометрии. Представление с помощью плоских граней имеет место и 6 случае более сложных поверхностей, если эти поверхности аппроксимировать множествами плоских участков — по­лигональными сетками. Тогда можно поверхностную модель задать од­ной из следующих форм:

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

2) модель есть список ребер, для каждого ребра заданы инцидентные вершины и грани.

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

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

Геометрическими объектами нулевого, первого и второго уровней на­зывают соответственно точки, кривые, поверхности.

39. Методы и алгоритмы машинной графики.

Основные алгоритмы

1. Отсечение отрезка - алгоритм Кохена (Коэна)-Сазерленда (Cohen-

Sutherland, CS-алгоритм)

2. Классификация положения точки относительно отрезка (справа, слева,

спереди, сзади)

3. Расстояние от точки до прямой (плоскости)

4. Пересечение двух отрезков (плоскостей)

5. Проверка принадлежности точки полигону

6. Вычисление площади полигона

7. Построение выпуклой оболочки множества точек (заворачивание

подарка и др. алгоритмы)

8. Построение звездчатого полигона (ядра полигона: полигонализация

набора S вершин – все вершины должны быть видны из вершины s0 ,

принадлежащей ядру полигона)

9. Пересечение выпуклых полигонов (алгоритм Сазерленда-Ходжмана).

10. Построение триангуляции Делоне