close

Вход

Забыли?

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

?

Lab2(1)

код для вставкиСкачать
Федеральное агентство по образованию
ТГТУ
Кафедра ЭВМ
Отчёт по лабораторной работе №2
по дисциплине КТО
Решение задачи покрытия схем БИС эвристическим алгоритмом при компоновке
Вариант
Выполнил:
Группа:
Принял:№1
Лукин А.С.
0203 ВМКСС
Лебедев В.В.
Тверь,2005
Выполнение:
Вопросы
1. Можно ли отнести эвристический алгоритм к классу последовательных? Обосновать ответ
2. Объяснить смысл задачи покрытия.
3. Объяснить результат работы программы.
4. Объяснить смысл целевой функции относительно избыточности реализации.
Контрольные вопросы
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 }.
Документ
Категория
Рефераты
Просмотров
3
Размер файла
86 Кб
Теги
lab2
1/--страниц
Пожаловаться на содержимое документа