close

Вход

Забыли?

вход по аккаунту

?

Экстремальные оценки процедуры покрытия топологии бис.

код для вставкиСкачать
Раздел
«Автоматизация проектирования»
Принципиальное отличие второго этапа от первого заключается в том, что
координаты выбранных на первом этапе конструктивных элементов могут изменяться как непрерывные величины в довольно широких пределах. Процедура размещения элементов наименее формализована, поэтому для ее выполнения можно
использовать генетический алгоритм с операцией управляемого кроссинговера
[10] по координате. В качестве фитнес-функции задачи можно использовать глобальную определенность конструкции, приближая ее к заданной основными параметрами.
Важным направлением будущих исследований является разработка методов
оптимального гранулирования конструкторской информации и оптимального распределения достоверности в нечетких задачах [10].
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Suh N.P. The Principles of Design, New York : Oxford University Press, 1990.
2. Нариньяни А.С. Модель или алгоритм – новая парадигма информационной технологии.
Информационные технологии, №4, 1997. – С.18-22.
3. Zadeh, L.A. A New Direction of AI—Toward a Computational Theory of Perceptions AI
Magazine, pp. 73-84, Spring 2001.
4. Zadeh L.A. From Computing with Numbers to Computing with Words—From Manipulation
of Measurements to Manipulation of Perceptions. IEEE Trans. On Circuits and Systems –
Fundamental Theory and Applications, vol. 45, No. 1, January, 1999, pp. 105-119.
5. Batyrshin I., Panova A. On Granular Description of Dependences// Proc. Of 9th Zittay Colloquium (Zittay, Germany, 2001). – 2001, pp. 1-8.
6. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. – М.: Наука, 1973.
7. Pal N.R, Bezdek J.C., Measuring fuzzy uncertainty, IEEE Transcriptions on Fuzzy Systems,
Vol. 2, No., 2, pp.107-118, 1994.
8. Ullah S. F-granular design information based Information axiom. In Proc. of ICAD 2002,
Cambridge MA, June 2002, pp. 1202-129.
9. R. Halfman Dynamics, Addison-Wesley PC Inc., Reading, Palo Alto, London, 1970.
10. Бутенков С.А. Обобщенные геометрические модели и новая парадигма обработки геометрической информации. Известия ТРТУ, 3, 2002. – С.150-157.
УДК.621.382.82–181.2
Н.К. Лисяк, В.В. Лисяк
ЭКСТРЕМАЛЬНЫЕ ОЦЕНКИ ПРОЦЕДУРЫ
ПОКРЫТИЯ ТОПОЛОГИИ
БИС*
Процедура покрытия топологии БИС системой разрешенных диафрагм
микрофотонаборной установки (МФНУ) является комбинаторно-логической. В
связи с этим практический интерес представляет вопрос: какие экстремальные характеристики по числу покрывающих прямоугольников может иметь произвольный контур топологии? Иными словами нужна априорная информация о том какой
эффект следует ожидать от затраченных средств, следует ли разрабатывать сложные алгоритмы минимизирующие целевую функцию или результаты простых по
структуре алгоритмов могут удовлетворить практическим требованиям. Ответ на
*
Работа выполнена при поддержке Мин. образования, грант № 12391 (ТО2-02.3-491)
73
Известия ТРТУ
Тематический выпуск «Интеллектуальные САПР»
поставленные вопросы, если не в полной мере, то частично дает предлагаемая работа.
Рассмотрим класс простых n-угольников, где каждая сторона параллельна
одному из z допустимых направлений (z≥4), а углы между смежными сторонами
кратны минимальному углу для выбранного значения z.
dz=360/z,
(1)
т.е. d4=900, d6=600, d8=450 и т.д.
Граница (контур) n-угольника разбивает плоскость на две области – внутреннюю Ф , и внешнюю Ф . Связность области важная характеристика контура,
так как реальные элементы топологии БИС часто представляют собой многосвязные области. Рассмотрим сначала односвязные простые dzn-угольники.
Выбрав направление обхода (по часовой стрелке или против), обозначим
вершины контура элементами множества V={v1,v2,…,vn}. Угол контура vi будем считать положительным (отрицательным), если отрезок, соединяющий точки vi-1 и vi+1
целиком принадлежит области Ф ( Ф ). Число положительных углов
n-угольников обозначим α, а отрицательных – β. Очевидно, что
α + β= n.
(2)
Назовем положительные (отрицательные) углы α -углами (β -углами). Сузим класс рассматриваемых n-угольников и введем следующее ограничение: крат-
ность каждого угла
tz=(z/2)-1.
(3)
например, t4=1, t6=2, t8=3, t12=5.
Теорема 1. Для любого односвязного n–угольника, построенного с учетом
ограничения (3), выполняется равенство
α - β= z.
(4)
Доказательство. Исходя из теоремы о сумме внутренних углов простого
n-угольника φz=1800 (n -2) или с учетом (1) и (2)
φz= (z dz /2) (α + β-2).
(5)
Величина φz определяется суммой внутренних углов. Внутренний положи-
тельный угол равен tzdz , а отрицательный 360- tzdz или zdz - tzdz., поэтому
Φ = Ά TZ DZ + Β(Z DZ - TZ DZ.).
На основании (5) и (6) находим
откуда
зать.
(6)
ά z dz+ β z dz -2 z dz= 2 ά tz dz + 2 β z dz - 2 β tz dz,
ά - β= 2z / z - 2tz.
(7)
Подставив в (7) ограничение (3), получим ά – β = z , что и требовалось дока-
Следует отметить, что в ортогональных n–угольниках (z=4) ограничение (3)
не уменьшает число контуров, для которых справедлива теорема, так как нельзя
построить d4 n-угольник, кратность углов которого отличалась бы от единицы.
Теорема дает возможность определить число положительных и отрицательных углов многоугольника как функцию от числа его сторон (или углов) и числа
направлений, т.е.
Следствие 1.
ά =fά (n, z),
β= fβ (n, z).
Суммируя правые и левые части выражений (2) и (4), получим
Следствие 2.
ά =( n+ z)/2.
Подставив равенство (8) в (2), получим
74
(8)
Раздел
«Автоматизация проектирования»
β =( n- z)/2.
(9)
Таким образом, для любого d4 n-угольника ά = n/2 +2, β = n/2 –2. Так как
топологические элементы БИС представляют собой множество одно или многосвязных d4n-угольников (за редким исключением, когда встречаются
d8n-угольники), рассмотрим только ортогональные многоугольники. Покрытие
d4n-угольника объединением непересекающихся прямоугольников можно рассматривать как разрезание области Ф на прямоугольники с помощью некоторого
множества линий сечения, параллельных допустимым направлениям. При этом
целесообразно получить минимальное число покрывающих прямоугольников.
Границу области и нанесенные на нее секущие линии рассмотрим как некоторый граф G(X,U), в котором множество вершин X однозначно соответствует
множеству угловых точек границы и точек пересечения границы линиями сечения,
а множество ребер соответствует фрагментам сторон границы и линий сечения.
Вершины из подмножества X α ⊆ X (X β ⊆ X ) , соответствующие положительным (отрицательным) углам, назовем ά-вершинами (β-вершинами). Очевидно, что
X = Xα U Xβ и Xα U Xβ= Ф , Xα|= ά, | Xβ|= β.
Обозначим локальную степень вершины xi ∈ X ρ(xi) и заметим, что до
проведения линий сечения локальные степени всех вершин графа G равны двум.
Область Ф назовем полностью покрытой, если в ней проведены линии сечения
так, что нельзя выделить ни одной фигуры, окаймленной фрагментами линий сечения и границы области не отличающейся от прямоугольника. В противном случае заметим, что область покрыта частично.
Лемма 1. При полном покрытии области Ф прямоугольниками локальная
степень каждой β-вершины более двух, т.е. каждый отрицательный угол контура
инцидентен по крайней мере одной линии сечения.
Предположим, что область Ф полностью покрыта и при этом имеется хотя
бы одна β-вершина xi ∈ Xβ, локальная степень которой ρ(xi )=2. Выделим угол и
фрагмент области, ограниченный линиями сечения, сторонами угла vi и, возможно,
другими сторонами контура. Полученная область содержит как минимум один
отрицательный угол (vi), т.е. β ≥ 1, на основании (9) β = n/2 –2 ≥ 1, следовательно
число вершин фрагмента области n0 ≥ 6 и последний не является элементарным
прямоугольником, что противоречит допущению о полном покрытии области Ф .
Лемма 2. Для получения полного покрытия области Ф прямоугольниками
необходимо и достаточно, чтобы из каждого отрицательного угла исходила по
крайней мере одна линия сечения, т.е. чтобы β (xi )=3 для всех xi ∈ Xβ.
Необходимость следует из леммы 1. Докажем достаточность. Допустим, что
из каждого отрицательного угла контура проведена линия сечения в области Ф до
встречи с контуром или с другой линией сечения. При этом возможно появление
точек пересечения линий. Отметим, что в точке пересечения секущих линий образуются только прямые углы или два прямых и один угол 180 градусов. При встрече секущей линии с контуром возникает следующая альтернатива: линия пересекает сторону контура и при этом образуется два прямых угла или секущая попадает в вершину отрицательного угла, и при этом образуются углы 90 и 180 градусов,
то есть в любом случае общее число отрицательных углов не возрастает. Поэтому
если предположить, что из всех β-углов проведены секущие и полученное покрытие не является полным, то при определении частичного покрытия в нем должна
75
Известия ТРТУ
Тематический выпуск «Интеллектуальные САПР»
иметься фигура с отрицательным углом, который может принадлежать только
контуру. В таком случае не из всех отрицательных углов контура проведены линии сечения, что противоречит допущению.
Доказанные выше теорема, её следствия и лемма 2 позволяют получить
верхнюю и нижнюю оценки минимального числа покрывающих прямоугольников
P как функцию числа сторон контура, т.е. P=fp(n) без детального анализа конфигурации конкретного контура.
Так как из каждого β-угла исходит только одна секущая линия, то общее
число прямоугольников покрытия
P= β+1.
(10)
В общем случае одна линия сечения может быть инцидентна двум β-углам.
Поэтому в лучшем случае все β-углы попарно объединяются линиями сечения так,
что будет выполняться условие леммы 2 и тогда
β /2 +1≤ P при β≡0 (mod2),
(11)
или
(12)
(β-1)/2 +1≤ P при β≡1 (mod2).
Из выражений (9-12) находим
(13)
n/4≤ P ≤ n/2 –2 для n≡0 (mod4)
и [(n+2)/4]≤ P ≤ n/2 –1 для n≡2 (mod4).
(14)
Если [А] обозначает целую часть числа, то
(15)
(n+2)/4≤ P ≤ n/2 –1 для любого n≡0 (mod2).
Из (13) и (14) следует, что максимальная ошибка ∆P при использовании
любого алгоритма покрытия
∆P ≤ (n/4) –1 для любого n≡0 (mod4)
(16)
и ∆P ≤ (n/4) –1,5 для любого n≡2 (mod4),
(17)
или ∆P ≤ [n/4].
(18)
Выше рассматривались только односвязные области. Чтобы получить оценки типа (13)-(18) для k-связных областей, достаточно заметить, что к-связная область может быть преобразована в односвязную путем предварительного введения
(k-1) линий сечения, соединяющих одну из β-вершин каждого внутреннего контура с границей внешнего контура или любой другой внутренней области.
Так как каждый внутренний контур не имеет вырожденных сторон по отношению к другим, то число вершин n* односвязного контура, полученного из kсвязного, определится выражением
(19)
n*= n+2 (k -1),
откуда с учетом (13) и (14) получим
(20)
(n+2)( k -1)/4≤ P ≤ n/2 + kк-2 для n*≡0 (mod4)
и (n+2 k)/4≤ P ≤ n/2 + k-2 для n*≡2 (mod4).
(21)
Использовать выражения (20-21) в практике неудобно из-за необходимости
убеждаться в отсутствии вырожденных сторон в многоугольнике. Поэтому для
k-связных d4 n-угольников целесообразно рассмотреть другой способ нахождения
оценок числа покрывающих прямоугольников. Достаточно заметить, что для внут-
реннего контура
76
αi=(ni-4)/2, βi==(ni+4)/2,
(22)
Раздел
«Автоматизация проектирования»
т.е. понятия «положительный» и «отрицательный» угол меняются местами.
Пусть внешний контур Г0 состоит из n0 сторон и имеется множество внутренних контуров Г1, Г2,…, Гк-1 с числом сторон n1, n2,….., nк-1 соответственно. Тогда общее число β-углов определим с помощью выражений (9) и (22)
к−1
( n0 -4)/2 +
∑ (n
i+4)/2.
(23)
i =1
В наихудших условиях для того, чтобы k-связный n-угольник сделать односвязным, потребуется провести k-1 сечение, при этом согласно лемме 2 число βуглов уменьшается на k-1, т.е. p≤ β+1-( k-1), или
р ≤ n/2 –2+2(k-1)+1-k+1, откуда p ≤ n/2 +k-2.
В наилучших условиях при проведении каждого (k-1) сечения 2(k-1) β –
углов объединятся в пары, т.е. в результате останется
β*= β-2(k-1) или β*= n/2 –2+2(k-1)-2(k-1)= n/2 –2
отрицательных углов.
Согласно (11,12) β*/2+1 ≤ p при β* ≡0 (mod2);
(β*-1)/2 +1+1≤ β при β* ≡1 (mod2);
[(n+2)/4] ≤ р при n≡0 (mod2).
Таким образом,
(n+2)/4 ≤ p ≤ n/2 +k-2 для всех n≡0 (mod2).
(24)
Отметим, что обе границы достижимы, так как существует k-связные
n-угольники, для которых Рmin совпадает с верхней или нижней оценкой.
Лемма 3. Не существует k-связных dzn–угольников с n < zk.
Действительно k-связный dzn–угольник состоит из k контуров, причем минимальное число сторон каждого из них не может быть меньше z, что доказывает
справедливость леммы.
С учетом леммы 3 построен график зависимости диапазона возможного
числа прямоугольников покрытия от числа сторон k-связного d4 n–угольника
(рис.1), который иллюстрирует выражение (24).
Рис.1
Если топология БИС представляет собой савокупность М многосвязных d4 n
то с помощью (24) можно получить интегральные оценки числа покрывающих прямоугольников
–угольников,
М
∑
i =1
(ni+2)/4 ≤ p ≤
М
∑
( ni /2 +ki -2).
(25)
i =1
77
Известия ТРТУ
Тематический выпуск «Интеллектуальные САПР»
В заключении отметим, что приведенные в работе оценки (15,24,25) могут
быть полезны разработчикам автоматизированных систем проектирования фотошаблонов БИС при решении вопроса выбора алгоритмов покрытия в зависимости
от конкретных особенностей топологии БИС.
УДК 681.3
Ю.А. Кравченко
ПОСТАНОВКА ЗАДАЧИ И СИНТЕЗ ПРОГРАММЫ ИСПЫТАНИЙ CALS
ИМИТАЦИОННЫХ МОДЕЛЕЙ НА ОСНОВЕ
НЕЙРОСЕТЕВОГО
АЛГОРИТМА*
Введение. Современные САПР технологических процессов обеспечивают
сквозное проектирование и имеют многомодульную структуру. Для решения актуальных проблем совместного функционирования компонентов САПР различного
назначения, в составе модулей конкретной системы должны разрабатываться PDM
системы управления проектными данными. Для достижения эффективного взаимодействия промышленных автоматизированных систем, необходимо создать
единое информационное пространство, посредством унификации, как формы, так
и содержания используемой информации. При разработке сложных систем и процессов широко применяются методы имитационного моделирования. Актуальной
задачей является исследование смоделированных сложных систем и технологических процессов. Постановка задачи и синтез программы исследования (испытаний)
может осуществляться на основе методов эволюционного моделирования (в частности, на основе нейросетевых алгоритмов).
В настоящий момент изготовление сложных промышленных объектов подразумевает согласованность работы многих предприятий – участников жизненного
цикла. CALS- технологии служат средством интеграции промышленных автоматизированных систем в многофункциональную систему, обеспечивающую создание
единого информационного пространства. При этом существующие автоматизированные системы проектирования и управления не отвергаются, CALS – технологии являются средством их эффективного взаимодействия. По аналогии с автоматизированным проектированием в CALS выделяют: лингвистическое, информационное, программное, математическое, методическое, техническое и организационное обеспечения.
1. Аппарат сетей Петри для моделирования и исследования сложных
динамических дискретных систем. Математическое обеспечение CALS-
технологий включает в себя методы имитационного моделирования сложных систем и оптимизации логистических процессов, включая планирование процессов и
распределение ресурсов. Имитационное моделирование сложных систем в большинстве случаев базируется на теории массового обслуживания. В некоторых случаях для исследования сложных имитационных моделей применяют аппарат сетей
Петри.
Сети Петри используются чаще всего для моделирования и исследования
сложных динамических дискретных систем. Сеть определяется четверкой
Работа выполнена при поддержке Мин. образования, грант № 12392 Е02-2.0-44 и
РФФИ, грант № 12387 02-01-01275
*
78
Документ
Категория
Без категории
Просмотров
3
Размер файла
214 Кб
Теги
оценки, экстремальных, процедур, покрытия, топология, бис
1/--страниц
Пожаловаться на содержимое документа