Автор работы: Пользователь скрыл имя, 29 Мая 2013 в 18:03, курсовая работа
При конструкторском проектировании ЭВС решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска конструктивного оптимального решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки, до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.
Введение…………………………………………………………………………...3
1.Теоретическая часть…………………………………………………………….4
1.1. Постановка задачи компоновки………………………………………4
1.2. Алгоритмы компоновки……………………………………………….4
1.3. Последовательный алгоритм разбиения графа G=(X,E) на кусков с числом вершин в каждом куске……………………………..7
2.Практическая часть……………………………………………………………..8
2.1. Решение задачи компоновки………………………………………….8
2.2.Инструкция пользователя……………………………………………10
3.Заключение……………………………………………………………………..12
4.Список использованной литературы…………………………………………13
Приложение. Листинг программы……………………………………………...14
Министерство образования и науки Российской Федерации
Казанский национально исследовательский технический университет
им. А.Н. Туполева - КАИ
Факультет
технической кибернетики и
Кафедра ИТП ЭВС
Пояснительная записка к курсовой работе по дисциплине:
«Информационные технологии проектирования ЭВС»
на тему: Решение задачи компоновки последовательным алгоритмом разбиения графа G=(X,E) на кусков с числом вершин в каждом куске»
Выполнила: студентка гр.4414
М.М. Демченко__________
Научный руководитель:
доцент кафедры ИТП ЭВС
В.В. Воронова___________
Оценка___________
«____» ______________2011 г.
Казань 2011
Министерство образования и науки РФ
Казанский национальный исследовательский технический университет
им. А.Н.Туполева - КАИ
Кафедра Информационных технологий проектирования ЭВС
ЗАДАНИЕ
на курсовую работу ИТПЭВС
Студентка Демченко Марина Михайловна Группа 4414
Руководитель Воронова Валентина Васильевна .
Дата выдачи задания 07.09.2011 Срок сдачи задания 28.12.2011
Тема задания
Решить задачу компоновки последовательным алгоритмом. Разработать программу, разбивающую произвольный граф на куски, используя последовательный алгоритм разбиения графа ) на кусков с числом вершин в каждом куске.
Исходные данные: схема соединений элементов рис.1, стр.11, n=16, l=3, число элементов в каждом куске:
Воронова
В. В._________________
2011 г.
Оглавление
Введение…………………………………………………………
1.Теоретическая часть…………………………………………………………….4
1.1.
Постановка задачи компоновки……
1.2. Алгоритмы компоновки……………………………………………….4
1.3. Последовательный алгоритм разбиения графа G=(X,E) на кусков с числом вершин в каждом куске……………………………..7
2.Практическая
часть……………………………………………………………..
2.1. Решение задачи компоновки………………………………………….8
2.2.Инструкция
пользователя……………………………………………
3.Заключение………………………………………………
4.Список
использованной литературы……………
Приложение.
Листинг программы……………………………………………...
При конструкторском проектировании
ЭВС решаются задачи, связанные с
поиском наилучшего варианта конструкции,
удовлетворяющего требованиям технического
задания и максимально
Задача компоновки рассматривается как задача принятия решения в определенных или неопределенных условиях. Под задачей компоновки понимают объединение модулей низшего уровня в модули более высокого уровня. Среди методов компоновки ЭВС выделяются два класса:
Первый класс включает в себя задачи разбиения схемы на части. К задачам этого класса относятся: распределение ТЭЗ по панелям, распределение микросборок по печатным платам, разбиение коммутационной схемы на БИС или СБИС. В этом классе критерии оптимизации и ограничения могут быть сведены к определенным конструктивным параметрам расположения отдельных элементов и их межсоединений.
Второй класс включает задачи, которые возникают на этапе перехода от функционально-логической схемы (ФЛС) к коммутационной схеме, ориентированной на заданную систему элементов, и состоят в назначении элементов логической схемы в типовые модули из заданного набора. Это так называемые задачи покрытия (компоновки типовых блоков).
Для каждой задачи имеет место
использование своих
В общем виде задача компоновки может быть сформулирована следующим образом:
Дана функционально-логическая схема (ФЛС), число блоков, на которое необходимо разбить схему, число элементов в блоке. Требуется разделить ФЛС на части для последующего образования блоков, исходя из определенного соответствия необходимым критериям и наличия ограничений.
На этапе конструкторского
проектирования решаются вопросы, связанные
с компоновкой элементов
Компоновкой электрической схемы ЭВС на конструктивно законченные части называется процесс распределения элементов низшего конструктивного уровня в высший в соответствии с выбранным критерием. Основным для компоновки является критерий электромагнитно-тепловой совместимости элементов низшего уровня. Данный критерий определяет область допустимых разбиений схемы, на которой формулируются другие критерии. Такими критериями могут быть: минимум типов конструктивно законченных частей, плотность компоновки, минимум соединений между устройствами и др. Очевидно, что внешние соединения между частями схем являются одним из важнейших факторов, определяющих надежность ЭВС. Поэтому наиболее распространенным критерием является критерий минимума числа внешних связей. Выполнение этого критерия обеспечивает минимизацию взаимных наводок, упрощение конструкции, повышение.
Для построения формальной математической модели компоновочных задач удобно использовать теорию графов. При этом электрическую схему интерпретируют ненаправленным графом, в котором каждому конструктивному элементу (модулю) ставят в соответствие вершину графа, а электрическим связям схемы – его ребра.
Известные алгоритмы компоновки можно условно разбить на пять групп:
Алгоритмы первой группы, хотя и позволяют получить точное решение задачи, однако для устройства реальной сложности фактически не реализуемы на ЭВМ.
Наибольшее распространение получили приближённые алгоритмы компоновки (последовательные, итерационные, смешанные).
Основная идея последовательных алгоритмов состоит в том, что по определенным правилам формируется первый кусок разбиения, начиная с вершины, которая имеет наименьшую (наибольшую) локальную степень.
Если таких вершин несколько, то начинаем с первой по порядку. Затем для этой вершины выделяются ее связи с другими вершинами графа, т.е. определяется количество смежных с ней вершин.
Если оказывается, что мощность множества ½Г(xi)½=n1 для выбранной вершины, то первый кусок сформирован. Здесь n1 – число вершин первого куска. Затем из матрицы смежности Е исключаются все вершины, вошедшие в первый кусок. Это означает, что из нее удаляются соответствующие строки и столбцы. Если окажется, что ½Г(xi)½> n1, то в этом случае необходимо из списка Г1 удалить “лишние вершины”. При удалении такой вершины, ее связи с остающимися вершинами станут внешними, отсюда следует, что нужно удалить вершину, которая связана с остающимися вершинами меньшим числом ребер. Если окажется, что ½Г(xi)½< n1, то в этом случае необходимо добавить вершины в кусок G1 по условию:
где - локальная степень вершины xj,
- количество связей вершины xj с ещё не вошедшими в кусок G1 вершинами.
После того как кусок G1 сформирован, т.е. из матрицы смежности удалены строки и столбцы, соответствующие вершинам, вошедшим в первый кусок, для матрицы смежности пересчитываются локальные степени оставшихся вершин. Процесс повторяется, т.е. следует приступить к формированию куска G2.
Последовательный алгоритм разрезания графа G считается завершенным, если сформирован предпоследний кусок.
При использовании итерационных алгоритмов сначала граф разбивается на определённое число частей произвольным образом либо с помощью последовательного алгоритма. Затем по определённым правилам производится перестановка вершин из одной части в другую с целью минимизации числа внешних рёбер.
Оптимизация компоновки достигается парными или групповыми перестановками вершин графа из различных кусков.
Процесс перераспределения вершин заканчивают при получении локального экстремума целевой функции, удовлетворяющего требованиям разработчика.
В смешанных алгоритмах компоновки для получения начального варианта "разрезания" используется алгоритм последовательного формирования кусков; дальнейшая оптимизация решения осуществляется перераспределением вершин между отдельными кусками графа.
В алгоритмах разбиения, опирающихся
на идеи математического
Алгоритмы разбиения, использующие методы ветвей и границ, состоят из следующих этапов.
Сначала определяется нижняя оценка разбиения графа на заданное число частей. Затем производится построение дерева решений и осуществляется поиск оптимального результата.
Задачу разбиения графа схемы на части можно свести к задаче о назначении следующим образом.
Сначала отыскивают назначение кандидатов (вершин графа) на все части, дающие минимальные суммарные затраты, причём, каждая вершина графа может быть назначена только в одну часть и в каждой части должны содержаться различные вершины графа.
Замечание. Формирования начинаем с вершины с наибольшей локальной степенью.
1.Вычисление матрицы смежности .
2.Определение локальной степени каждой вершины
3.Выбор строки в матрице смежности, соответствующей вершине наибольшей локальной степенью. Если , то
4.Формирование массива вершин, смежных вершине причем Переход к п.5.
5. Если количество вершин в списке равно , то первый кусок сформирован и Переход к п.8, иначе к п.6.
6. Если , то из множества вершины, не вошедших в список выбирается вершина удовлетворяющая условию
где - вершин несколько, то берется вершина с большим значением список . Переход к п.5.
7.Если то из списка удаляются лишние вершины, то есть связанные с остающимися в куске меньшим числом ребер
8.Исключение из графа G куска , то есть удаление из матрицы смежности С строк и столбцов, соответствующих номерам вершин из. Пересчет локальных степеней оставшихся вершин.
9.Если число сформированных кусков , то повторение алгоритма для формирования следующего куска с п.З. Если то переход к п. 10.
10. Конец работы алгоритма
Дано:
1) Схема соединений элементов (рис.1);
2) Число элементов n=16;
3) Число кусков разбиения l=3;
4) Число элементов в каждом куске соответственно n1=5, n2=5, n3=6.
Рис.1. Схема соединений элементов.
Требуется:
Разбить схему на 3 части, используя последовательный алгоритм разбиения графа схемы на куски, начиная с вершины с наибольшей локальной степенью.
Решение:
Описываем схему графом
Проведем компоновку в соответствии с алгоритмом.
п.1. Составим матрицу смежности:
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
x15 |
x16 | ||
x1 |
0 |
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 | |
x2 |
2 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 | |
x3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 | |
x4 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 | |
x5 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 | |
x6 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 | |
x7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 | |
x8 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 | |
x9 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 | |
x10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 | |
x11 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
0 | |
x12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 | |
x13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
3 | |
x14 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 | |
x15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 | |
x16 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |