24) Методы генерации сетки для численного моделирования.

Построение сетки включает: 1. определение положения узлов и элементов; 2. автоматически пронумеровать узлы, элементы; 3.задать плотность сетки и типы элементов.

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

2. Определение окружения при создании нового узла. При создании нового узла, необходимо убедиться в том, что он будет расположен на достаточном расстоянии от уже существующих узлов и отрезков. Для этого необходима специальная процедура, которая: определяет тип близости; определяет список узлов, располагающихся в опасной близости от новой точки.

3.Триангуляция криволинейных поверхностей (Делоне). 2 этапа: 1-построение диаграмм Вороного. Две соседние точки соединяются, делятся пополам и строится перпендикуляр – он равноудален от всех точек. Перпендикуляры образуют многоугольники. На таком принципе основано расположение базовых станций сотовый связи – покрытие связи. 2 – соединение узлов (центров граничащих многоульников). Они соединяются, если между ними есть границы.

4. Построение сетки для метода конечных элементов: создание узлов методом Кавендиша. Граничные узлы задаются вручную. Автоматически создаются внутренние узлы для заданной плотности ячейки. Объект делиться на участки по размеру элементов. На i-ом участке создается квадратная сетка масштаба r(i). В каждом квадрате создается 1 внутренний узел. Если узел попадет внутрь объекта, а расстояние от него до всех остальных узлов окажется больше, чем r(i), то узел считается принятым. Если узел не подошел – операция повторяется. Если узел не удалось построить после фиксированного числа попыток – ячейка пропускается.

5. Метод топологического разбиения. Разработан Ворден-Вебером. а) Объект апроксимируется многоугольником. б) Многоугольник разбивается на множество элементов до получения треугольников. Крупные элементы разбиваются на более мелкие, пока не будет достигнута желаемая плотность сетки.

25) Методы компоновки и размещения элементов устройств.

Компоновка: 1) разбиением. Суть в разбиении большой схемы, представленной на элементном уровне, на ряд подсхем, что соответствует различным модулям конструктивной реализации.

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

Известные алгоритмы компоновки можно условно разбить на 4 групп: 1) алгоритмы, использующие методы целочисленного программирования. 2) последовательные алгоритмы.3)параллельные алгоритмы.4)комбинированные алгоритмы

Алгоритмы первой группы позволяют получить точное решение задачи, но фактически не реализуемы на ЭВМ. Большее распространение получили приближенные алгоритмы компоновки.

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

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