close

Вход

Забыли?

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

?

Lab1(1)

код для вставкиСкачать
Федеральное агентство по образованию
ТГТУ
Кафедра ЭВМ
Отчёт по лабораторной работе №1
по дисциплине КТО
Изучение компоновки элементов схемы последовательным и итерационным алгоритмами
Вариант
Выполнил:
Группа:
Принял:№1
Лукин А.С.
0203 ВМКСС
Лебедев В.В.
Тверь,2005
Вариант №1
Задание: Собрать схему, выполнить последовательную и итерационную компоновки схемы, используя следующие параметры:
Кол-во групп: 6
Максимальное количество элементов в группе: 10
Глубина: 2
Исходная схема
Результат разбиения
Вопросы
1. Понятие операции факторизации (свертки).
2. Суть итерационного алгоритма компоновки.
3. Какой критерий оптимизации при компоновке используют в алгоритме выделения минимальных массивов гиперграфов схем.
Контрольные вопросы
1. Формулировка задачи выделения минимальных массивов гиперграфа схемы.
Некоторое подмножество Xi множества X вершин гиперграфа называется минимальным массивом из ni вершин , где ni = Xi , если для любого другого подмножества Xi` Xi справедливо:
( Xi`) > ( Xi), где ( Xi`) и ( Xi)- количество внешних ребер кусков гиперграфа, множествами вершин которых являются подмножества Xi` и Xi соответственно. Удаление любой вершины из подмножества Xi приводит к увеличению числа соединительных ребер.
2. Условие возможности образования минимального массива из 3-х вершин.
В результате выкладок, аналогичных для двух вершин, условие возможности образования в гиперграфе минимальных массивов из трех вершин xi , xj, xk таково:
K = 3 Ki,j,k + 2( Ki,j,k,p + Ki,j + Ki,k + Kj,k) + Ki,j,l+ Ki,k,r+ Kj,k,t > ( xi) + ( xj) + ( xk) - min{( xi), ( xj), ( xk)},
где Ki,j,k - количество ребер, содержащих только вершины xi , xj, xk;
Ki,j,k,p - количество ребер, инцидентных вершинам xi , xj, xk и хотя бы одной вершине xpX \ { xi, xj, xk }; Ki,j , Ki,k , Kj,k - количество ребер, содержащих только вершины xi и xj, xi и xk, xj и xk__ соответственно ; Ki,j,l, Ki,k,r, Kj,k,t - количество ребер, инцидентных вершинам xi и xj, xi и xk, xj и xk и хотя бы одной вершине __ xl, xr, xt X \ { xi, xj, xk }.
3. Привести формулу расчёта количества инциндентных рёбер факторизованной вершины, соответствующей минимальному массиву из 2-х элементов. Показать справедливость на примере.
Обозначим через ( xi`) и ( xj) количество ребер , инцидентных вершинам xi, и xj соответственно. При поиске минимального массива важно только количество внешних ребер, поэтому вершины , входящие в массив, можно заменять одной. Эта операция называется факторизацией или сверткой. Ребра, инцидентные только факторизованным вершинам, из рассмотрения исключают, т.е. стягивают в одну точку. Для минимального массива Xi такое ребро uf должно удовлетворять условию: Г uf.
Обозначим через xi,j факторизованную вершину , соответствующую минимальному массиву g2 = { xi, xj }, и через ( xi,j) - количество внешних ребер этого массива .
Получим формулу для оценки ( xi,j), т.е. количества ребер, соединяющих xi,j = { xi, xj } с вершинами множества X\{ xi, xj }.
Рассмотрим для этого возможные изменения состояния различных ребер, инцидентных вершинам xi, xj , при замене этих вершин одной - xi,j. Ребра, которые содержат только вершины xi и xj , не войдут в ( xi,j), причем при определении показателей ( xi) и ( xj) эти ребра считались дважды . Ребра инцидентные вершинам xi , xj и хотя бы одной вершине xkX \ { xi, xj } , войдут в ( xi,j) и каждое такое ребро при определении ( xi) и ( xj) считалось также дважды. Ребра , содержащие вершину xi или xj и хотя бы одну вершину xlX \ { xi, xj }, входили в ( xi) или ( xj) и войдут в ( xi,j), отсюда
( xi,j) = ( xi) + ( xj) - 2Ki,j - Ki,j,k (1), где Ki,j - количество ребер, соединяющих только вершины xi и xj; Ki,j,k - количество ребер, инцидентных вершинам xi и xj и хотя бы одной вершине xkX \ { xi, xj }.
Документ
Категория
Рефераты
Просмотров
31
Размер файла
114 Кб
Теги
lab1
1/--страниц
Пожаловаться на содержимое документа