Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

77-30569/239406 Оценка эффективности применения операций над упорядоченными множествами

# 10, октябрь 2011
Файл статьи: Овчинников_P.pdf (312.03Кб)
авторы: профессор Овчинников В. А., профессор Иванова Г. С.

УДК 004.3 + 519.6

МГТУ им. Н.Э. Баумана

gsivanova@gmail.com

Эффективность применения операций над упорядоченными множествами рассмотрим на примере решения задачи декомпозиции структуры сложной системы на подсистемы, например схемы электрической функциональной на подсхемы. Известна формальная постановка этой задачи как задачи разбиения множества вершин гиперграфа на совокупность непересекающихся подмножеств [1]. Там же рассмотрен и один из вариантов её решения посредством алгоритма последовательного разрезания гиперграфа. Результатом работы этого алгоритма является множество вершин куска гиперграфа XlЭl, где Эl – множество компонентов сформированной подсистемы.

Множество вершин Xl ↔Эl может быть также получено, например алгоритмом выделения минимальных массивов гиперграфа [2]. С практической точки зрения предпочтительней выделять квазиминимальные массивы с ограничением min | Xl |  max.

После окончания процесса декомпозиции необходимо проверить условия:

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

После определения Xlосновными проектными процедурами, реализующими процесс декомпозиции, являются: выделение части схемы, удаление её из разрезаемой схемы и повторный запуск алгоритма. Включим в процесс также контрольную операцию:

проверяющую возможность такого искажения информации, при которой один и тот же компонент системы будет указан неоднократно.

Таким образом, процесс декомпозиции структуры системы составят следующие процедуры:

1. Определение Xlк = Xl последовательным алгоритмом разрезания гиперграфа.

2. Проверка условия

3. Формирование куска Hlк(Xlк, Ulк) гиперграфа.

4. Удаление куска Hlк(Xlк, Ulк) из модели системы (гиперграфа после первого применения алгоритма разрезания и куска гиперграфа в дальнейшем).

5. Проверка условия окончания процесса декомпозиции | Xостк | > nl, где Xостк – множество оставшихся вершин гиперграфа (ещё не скомпонованных элементов системы), nl – допустимое количество компонентов подсистемы. При выполнении условия – переход к п. 1, в противном случае – к п. 6.

6. Проверка условий

Получим оценку сверху вычислительной сложности реализации описанного процесса в функции от мощности множеств X, (Xlк), U, (Ulк), Гx и Гu, учитывая только операции сравнения.

Приведём описание и схему первого варианта последовательного алгоритма разрезания гиперграфа [3]. Гиперграф задан аналитически в форме H(X, U, ГX, ГU, F1X). На текущем шаге алгоритма в качестве кандидатов на включение в формируемое подмножество Хl выступают  вершины, связанные с вершинами, уже вошедшими в Хl. Обозначим это множество через Хk.

Количество рёбер, попадающих в разрез, подсчитывается по рекуррентной формуле:

si = s0 + ∆si+ – ∆si-,

где s0 – количество ребер, находящихся в разрезе между кусками гиперграфа после выполнения предыдущего шага алгоритма, ∆si+ и ∆si- – количество рёбер приходящих в разрез и уходящих из него при включении в Хl вершины xi. Из рёбер uj Гxi, т. е. инцидентных вершине xi, приходят в разрез те, для которых выполняется условие:

            (1)

и уходят из него такие, для которых справедливо:

                        (2)

Множество вершин кандидатов Xk корректируется, исключая из него вершину, вошедшую в Xl, и добавляя новые, которые становятся кандидатами за счет включения в разрез новых ребер – это множество Xtп в п.10 алгоритма. Структуры данных для представления всех множеств и массива ∆S = <∆si> – динамические вектора.

1. Включаем в формируемое множество Xl некоторую вершину xq:

Xl= {xq}.

2. Определяем количество ребер s0, соединяющих xq с X \ xq:

U = Гxq, s0 = |U|.

3. Находим множество вершин Xk– кандидатов на включение в Xl:

Xk = F1xq.

4.     Для каждой вершины xi Xk определяем множество инцидентных ей ребер Ui, подмножество Uiп Ui ребер, приходящих в разрез, и подсчитываем показатель ∆si. Для чего выполняем:

4.1. Ui = Гxi, ∆si-=0, ∆si+ = 0.

4.2. Для  выполняем п.п. 4.2.1…4.2.5:

4.2.1. Находим множество вершин Xj, входящих в ребро uj: Xj= Гuj.

4.2.2. Проверяем условие

Если условие не выполняется, то ребро uj находится в разрезе – переходим к п.п. 4.2.4. Выполнение условия означает, что ребро уходит из разреза – переходим к п. п. 4.2.3.

4.2.3. Подсчитываем показатель ∆si- : ∆si- = ∆si- +1

и переходим к п. 4.2.

4.2.4. Проверяем условие .

Если условие выполняется (это означает, что ребро uj  приходит в разрез при включении xi  в Xl), то переходим к п.п. 4.2.5. При невыполнении условия переходим к анализу следующего ребра, т.е. к п. 4.2.

4.2.5. Включаем ребро uj в множество Uiп: Uiп = Uiп.uj, подсчитываем показатель ∆sisi+ = ∆si+ + 1 и возвращаемся в п. 4.2.

4.3. Определяем значение ∆si: ∆si = ∆si+.

5. Находим вершину xt Xk, для которой ∆sминимально:

st = min {∆si ∆S}, xt↔ ∆st.

6. Подсчитываем количество ребер S0, соединяющих множества Xl и X \ Xl после включения xt в Xl:

S0 = S0 + ∆st.

7. Проверяем ограничение на количество внешних выводов l-й  части схемы: S0≤ [sl]доп.

Если условие выполняется, то переходим к п.8, иначе – к п. 12.

8. Включаем вершину xt в множество Xl, и исключаем ее из Xk:

Xl= Xl. xt, Xk = Xk\ xt .

9. Проверяем условие: |Xl| <nl,

где nl– требуемое количество элементов в l-ой части схемы. Если условие выполняется, то переходим к п.10, иначе – к п.13.

10. Определяем множество вершин, входящих в множество ребер Utп:

11. Корректируем множество вершин кандидатов Xk:

Xk = {Xk Xtп }

и возвращаемся к п.4.

12. Дальнейшее формирование Xl невозможно из-за нарушения ограничения на число внешних выводов. Переход на окончание работы алгоритма к п. 14.

13. Вывод результатов.

14. Конец работы алгоритма.

Схема изложенного алгоритма показана на рис. 1, нумерация пунктов описания и блоков схемы совпадает.

На схеме в комментариях показаны размерности массивов (множеств) и количества операций сравнения, выполняемых в ходе работы алгоритма. Все оценки, кроме размера множеств Xk (и массива ∆S) и количества операций сравнения, необходимых для нахождения массива Xtп в п. 10, очевидны. Максимальное количество вершин кандидатов |Xk|max оценим, используя закон Рента [2]. На основании этого закона количество внешних выводов схемы от числа элементов в ней оценивается по формуле Nв. = α×Np, где α - среднее количество входных и выходных выводов элементов схемы, = 0, 5…0,75 – показатель Рента. В наших обозначениях α – это |Гx| = ρ. Примем α равным ρmax (в дальнейшем будем ρmax обозначать просто ρ) и p= 0,5. Тогда количество ребер в разрезе |U|max = ρ×|Xl|½, где |Xl| = i=1, 2…nl.

Так как в каждое ребро входит не более А вершин, то

|Xk|maxρ× A× i ½.

Рис. 1. Схема последовательного алгоритма разрезания гиперграфа

Для сравнительной оценки вычислительной сложности реализации процесса декомпозиции достаточно рассмотреть однократное выполнение процедур 1…4 и процедуру 6. Отметим, что при использовании операций над упорядоченными множествами сортировке подлежат только множество Xl в порядке возрастания индексов элементов, массив S по возрастанию значений его элементов и элементы xiмножества Xk в соответствии с положением si в массиве S.

1. Определение Xlк = Xl последовательным алгоритмом разрезания гиперграфа. Основной вклад в вычислительную сложность алгоритма вносит его циклическая часть – п. п. 4…11.

Выполнение цикла 4.

Неупорядоченные множества. Проверка условий блоков 4.2.2 и 4.2.4 требует не более 2А×i операций сравнения элементов массивов Xj и Xl, следовательно, вычислительная сложность цикла 4 не более

2A×i×ρ×ρ×A×i½ = 2A2×ρ2×i3/2.

Упорядоченные множества. Проверка условий блоков 4.2.2 и 4.2.4 на основании (2) и (1) требует не более 2iи 2(i + А – 1) операций сравнения соответственно. Отсюда вычислительная сложность реализации п. 4 будет не более

2(2i + А) × ρ×ρ×A×i½ = 4A×ρ2×i 3/2 + 2A×ρ2×i ½.

Как видно из схемы алгоритма количество операций сравнения, необходимых для выполнения п. п. 5, 8 и 11 имеет на единицу меньший порядок сложности.

Оценим вклад, вносимый процедурой сортировки при упорядочивании множеств Xkи Xl. После выполнения п.3 |Xk| < ρ×A. При каждом i – м выполнении тела цикла 4 удаляем одну вершину и 3 |Xtп| < ρ×A вершин добавляем. Ориентируясь на сортировку с помощью двоичной кучи, получим для Xk

,

где NΣ– суммарное количество операций сравнения, выполняемых при формировании множества Xl. Найдя через интеграл оценку

,

имеем

Упорядочивание множества Xkтребует nllog2nl операций сравнения. Таким образом, вклад процедур упорядочивания также имеет меньший порядок, чем цикла 4. Оценивая эффективность использования операций над упорядоченными множествами при получении Xl последовательным алгоритмом как отношение членов старшего порядка вычислительной сложности цикла 4, получим:

Kалг = 2A2×ρ2×i 3/2 / (4A×ρ2×i 3/2) = A/2.

2. Проверка условияi = 1 (| Xlк | – 1) (xixi + 1). Очевидно, что проверяя это условие, мы должны предполагать, что Xlк может быть неупорядоченным кортежем. Например, в процессе упорядочивания множества Xlк = {x3, x1, x6, x4, x5, x9} из-за искажения имени элемента x9 на x4 может быть получен кортеж < x1, x3, x4, x5, x6, x4>. Следовательно, в алгоритме, устанавливающем истинность или ложность этого выражения, никакие свойства упорядоченных множеств использовать нельзя.

3. Формирование куска Hlк(Xlк, Ulк) гиперграфа. При оценке вычислительной сложности выполнения этого этапа процесса декомпозиции будем считать, что кусок гиперграфа должен быть получен в форме Hlк(Xlк, Ulк, ГXlк, ГUlк). Подсчёт количества операций сравнения будем выполнять, используя выражения формального описания выполнения операции получения куска H1к гиперграфа [4].

3.1. Определение множества

Неупорядоченные множества. Количество операций сравнения, необходимых для определения Ulк будет определяться как:

где, например, при объединении трёх подмножеств рёбер {Гxi Гxj }xk} ak= |Гxk' | / |Гxk|, Гxk'– множество рёбер, принадлежащих вершине xk и не принадлежащих вершинам множества {xi, xj}.

Считая| Xlк| = nl, получим:

N3.1 = ρ2 [nl + a ×nl× (nl  – 3)/2].

Поскольку 0 a< 1, N3.1 <ρ2× (nl2nl)/2.

Упорядоченные множества. При i-м объединении упорядоченного множества Гxi мощность множества, полученного на предыдущем шаге, равна ρ + a×ρ× (i – 1). Поскольку | Гxi| = ρ, то используя (2) из [5], запишем:

ОтсюдаN3.1 уп < ρ× (nl2 + nl) – nl.

Нетрудно видеть, что отношение К3.1 = N3.1 / N3.1 уп при росте nl стремится к ρ/2.

3.2. Определение множества Ulкint= {uj Ulк : Гuj Xlк / Гuj ГU}.

Неупорядоченные множества. Обозначив |Ulк | = mlи считая ml = |U| /L, получим количество операций сравнения, необходимых для определения множества Ulкint:

N3.2 = A×nl×ml.

Упорядоченные множества. На основании (1) из [5] – N3.2 уп = 2nl×ml.

Отсюда отношение К3.2 = N3.2 / N3.2 уп равно A /2.

3.3. Определение множества Ulкext= Ulк \ Ulкint.

Неупорядоченные множества. Считая |Ulкint| =|Ulк| /2, имеем: N3.3 = ml2/2.

Упорядоченные множества. N3.3 уп = 2(ml + ml/2 – 1).

При росте ml отношение К3.3 = N3.3 / N3.3 уп стремится к ml.

3.4. Определение множества ГXlк = {Гxi ГX /xi Xlк}. Как видно из выражения при формировании ГXlк, даже если учитывать операции записи, вычислительная сложность не зависит от упорядоченности множеств.

3.5. Определение множества ГUlк = {Гuj: uj Ulкint Гuj Xlк : uj Ulкext/ uj Ulк, Гuj ГU}. Операция Гuj Xlк будет выполняться |Ulкext| = |Ulк|/2 раз. Не будем учитывать проверки uj Ulкint и  uj Ulкext.

Неупорядоченные множества: N3.5 = A×nl×ml/2.

Упорядоченные множества: N3.5 уп = ml/2 [2(nl + A – 1)] = ml× (nl + A – 1).

При росте nl и ml отношение К3.5 = N3.5 / N3.5 уп стремится к A /2.

4. Удаление куска Hlк(Xlк, Ulк) из модели системы. Для простоты символики будем рассматривать выполнение этой операции после первого применения алгоритма разрезания. Удаление выделенной части схемы реализуется операцией «Дополнение части до ультраграфа HU и гиперграфа H»[6] в варианте H(X, U) \ H1к(X1к, U1к). Обозначим получаемый кусок гиперграфа как Hсл (Xслк, Uслк).

4.1. Определение Xслк = X\ X1к.

Неупорядоченные множества: N4.1 = n×nl.

Упорядоченные множества: N4.1 уп = 2 (nl + n – 1).

Отношение К4.1 = N4.1 / N4.1 уп стремится к nl. Напомним, что nl = n / L, где L – константа.

4.2. Определение Uслкint = U \ U1к.

Неупорядоченные множества: N4.2 = m×ml.

Упорядоченные множества: N4.2 уп = 2× (ml + m – 1).

Отношение К4.2 = N4.2 / N4.2 уп стремится к ml. Отметим, что ml = m / L.

4.3, 4.4 и 4.5. Определение Uслкext = U1кext, Uслк = Uслкint.Uслкext и ГXслк = {Гxi ГX/ xi Xслк}. Очевидно, что на вычислительную сложность выполнения этих операций упорядочивание множеств не влияет.

4.6. Определение ГUслк = {Гuj: uj Uслкint Гuj\ X1к : uj Uслкext/uj Uслк, Гuj ГU}. Количество операций сравнения определяется выражением | X1к |×uj|× |Uслкext|.×Будем считать, что |Uслкext| = |Uслк | / 2.

Неупорядоченные множества: N4.6 = nl×A×ml×(L – 1) / 2.

Упорядоченные множества: N4.6 уп = (nl + A×– 1)×ml×(L – 1).

При росте nl и ml отношение К4.6 = N4.6 / N4.6 уп стремится к A / 2.

6. Проверка условий

Эти условия логически эквивалентны условию X = Y, где Y= {X1. X2.X3.. XL}, проверка которого требует меньшего количества операций сравнения.

Для неупорядоченных и упорядоченных множеств соответственно имеем:

N6 = n2 и N6 уп = 4(n– 1).

С учётом необходимости упорядочивания множества Y получаем:

К6 = N6 / N6 уп = n2 / (4(n– 1) + n log2 n) = n / log2n.

Проанализировав полученные результаты, можно сделать вывод, что наиболее существенный вклад в снижение вычислительной сложности описанного процесса декомпозиции за счёт использования операций с упорядоченными множествами вносят:

формирование куска Hlк(Xlк, Ulк) гиперграфа в п. 3.3 в ml раз;

удаление куска Hlк(Xlк, Ulк) из гиперграфа в п. 4.1 в nl и в п. 4.2 в ml раз;

– проверка условия X = { X1. X2.X3..XL} в n / log2n раз.

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

Литература

1. Савельев А. Я., Овчинников В.А. Конструирование ЭВМ и систем: Учебник для технич. вузов по спец. «Электрон. выч. маш.» –М.: Высш. шк., 1984 – 248 с.

2. Савельев А. Я., Овчинников В.А. Конструирование ЭВМ и систем: Учеб. для вузов по спец. «Выч. маш., компл., сист. и сети.» – 2-е изд., перераб. и доп. – М.: Высш. шк., 1989 – 312 с.

3. Овчинников В. А. Алгоритмизация комбинаторно‑оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов.– М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. – 288 с.

4. Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: Эл. Науч. Издание. – 2009. – № 11.

5. Овчинников В.А. Операции над упорядоченными множествами: Наука и образование. Инженерное образование: Эл. Науч. Издание. – 2011. – № 6.

6. Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: Эл. Науч. Издание. – 2009. – № 12.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)