Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010



Скачать 255.89 Kb.
страница1/4
Дата04.07.2013
Размер255.89 Kb.
ТипМетодические указания
  1   2   3   4
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Р

ЫБИНСКАЯ

ГОСУДАРСТВЕННАЯ АВИАЦИОННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ

имени П.А. СОЛОВЬЕВА


В.М. Барашков
Методические указания к выполнению лабораторных работ

Методы синтеза и оптимизации проектных решений


Рыбинск 2010

Содержание





Содержание 2

Лабораторная работа №1 3

Теоретические сведения 3

Варианты заданий к лабораторной работе 8

Лабораторная работа 2 9

Теоретические сведения 9

Контрольные вопросы 12

Лабороторн6ая работа №3 13

Теоретический материал 13

Контрольные вопросы 16

Лабораторная работа №4 17

1. Версии пакета. Назначение пакета 17

2. Состав системы 17

3. Структура библиотек 17

4. Менеджер библиотек 19

5. Редакторы корпусов Pattern Editor и символов Symbol Editor 19


Лабораторная работа №1


Цели работы: Научиться выполнять построение электрической схемы в виде графа. Выполнять анализ покрывающего дерева на наличие контуров и сечений.

Теоретические сведения


В последовательных алгоритмах "разрезание" исходного графа на " l " частей c числом вершин в каждой, соответственно, сводится к следующему.

В графе находят вершину с минимальной локальной степенью .

Если таких вершин несколько, то предпочтение отдаётся той вершине, которая имеет большее число кратных рёбер. С этой вершины начинается построение первого куска.

С этой целью в первоначально включаются и все вершины, смежные ей. Обозначим это множество .

Если полученное число вершин равно " png" name="graphics11" align=bottom width=22 height=13 border=0>", то считаем, что кусок образован.

Если это число больше " " , то удаляем "лишние" вершины, связанные с остающимися вершинами меньшим числом рёбер.

В случае, когда мощность множества меньше " " , то из выбирается вершина, удовлетворяющая условию



(19.7)

где - число рёбер, соединяющих вершину со всеми невыбранными вершинами.

Строим множество вершин , смежных , и процесс выборки вершин повторяется. Образованный подграф исключаем из исходного графа.

Получаем граф , где , .

Далее в графе выбирается вершина с минимальной локальной степенью. Производится её помещение в G_{ 2 }, и процесс повторяется до тех пор, пока граф не будет разрезан на "l" частей.

Описанный алгоритм прост, позволяет быстро получать результаты разбиения, однако в общем случае может привести к неоптимальным результатам. Наибольшая эффективность данного метода последовательного разбиения графа значительно больше числа вершин в любой части разбиения, т.е.



Рассмотрим принципиальную электрическую схему RC - генератора, рис. 1.




Рис. 1.  Принципиальная электрическая схема RC-генератора

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




Рис. 2.  Произвольный неориентированный граф

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

Таблица 1. Матрица смежности


























0

0

1

0

0

0

0






0

0

1

2

0

0

0






1

1

0

2

1

0

0

R=



0

2

2

0

0

1

0






0

0

1

0

0

1

0






0

0

0

1

1

0

1






0

0

0

0

0

1

0




















Суммируя элементы столбцов матрицы "", вычислим локальную степень каждой вершины . Полученные результаты запишем в нижнюю строку матрицы.

Пусть, граф, изображённый на рис. 2, надо разбить на три куска с количеством вершин 3, 2, и 2 в каждом куске, соответственно. Эти условия в данной задаче будут ограничениями. Целью разбиения является получение минимального количества внешних связей, т.е. ребер, связывающих куски графа между собой.

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




Рис. 3. 

Таблица 2.














0

0

0

0



0

0

1

0



0

1

0

1



0

0

1

0



0

1

2

1




Рис. 4. 

Определим локальную степень вершины по матрице смежности



Максимальную локальную степень имеет вершина , поместим ее и все связанные с ней вершины в кусок . Так как в нём должно быть две вершины, то исключаем. В результате будет следующее разбиение:



Окончательное разбиение графа приведено на рис. 5.




Рис. 5.  Окончательное разбиение графа

Рассчитаем коэффициент разбиения по формуле. Имеется четыре внешних и шесть внутренних связей вершин. Следовательно, коэффициент разбиения графа



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

Похожие:

Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации» Хабаровск Издательство тогу 2010
Методы одномерной оптимизации : методические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации»/...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации»
Тимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Много внимания уделено...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания к выполнению лабораторных работ санкт-Петербург 2012
Методические указания предназначены для проведения лабораторных работ со студентами дневного и вечернего обучения по специальности...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания по выполнению 1 и 2 лабораторных работ по курсу «Методы и средства защиты информации»
Методические указания предназначены для студентов IV курса направления «Информатика и вычислительная техника»
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания к выполнению лабораторных работ по исследованию биполярных транзисторов Санкт-Петербург 2010
Методические указания к выполнению лабораторных работ по исследованию биполярных транзисторов
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания к выполнению лабораторных и курсовых работ иркутск 2007
...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconКафедра прикладной информатики и информационных систем Нейронные сети Методические указания к выполнению лабораторных работ по курсу «Интеллектуальные информационные системы»
Методические указания к выполнению лабораторных работ по курсу «Интеллектуальные информационные системы» для студентов 4-го курса...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания к выполнению курсовых работ Системный анализ Рыбинск 2011 Указания к выполнению курсовых работ
Студентом формируется краткое формальное описание постановки задачи, определяется импульсная переходная функция системы, структурная...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconМетодические указания по выполнению лабораторных работ №1-5 по информатике для студентов дневной формы обучения
Решение задач в пакете Mathcad : методические указания по выполнению лабораторных работ №1 – 5 по информатике для студентов дневной...
Методические указания к выполнению лабораторных работ Методы синтеза и оптимизации проектных решений Рыбинск 2010 iconО. Ф. Власенко, И. В. Беляева изучение си после паскаля: циклы, развилки, функции, обработка одномерных массивов методические указания к выполнению лабораторных работ по программированию для студентов направления 552800 «Информатика и вычислительная
Методические указания к выполнению лабораторных работ по программированию для студентов направления 552800 «Информатика и вычислительная...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org