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

УДК 004.3 + 519.6

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

gsivanova@gmail.com

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

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

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

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

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

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

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

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

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

3. Формирование куска H_l^к(X_l^к, U_l^к) гиперграфа.

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

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

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

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

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

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

s_i = s₀ + ∆s_i⁺ – ∆s_i^-,

где s₀ – количество ребер, находящихся в разрезе между кусками гиперграфа после выполнения предыдущего шага алгоритма, ∆s_i⁺ и ∆s_i^- – количество рёбер приходящих в разрез и уходящих из него при включении в Х_l вершины x_i. Из рёбер u_j Гx_i, т. е. инцидентных вершине x_i, приходят в разрез те, для которых выполняется условие:

            (1)

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

                        (2)

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

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

X_l= {x_q}.

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

U’ = Гx_q, s₀ = |U’|.

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

X_k = F₁x_q.

4.     Для каждой вершины x_i X_k определяем множество инцидентных ей ребер U_i, подмножество U_i^п U_i ребер, приходящих в разрез, и подсчитываем показатель ∆s_i. Для чего выполняем:

4.1. Ui = Гx_i, ∆s_i^-=0, ∆s_i⁺ = 0.

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

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

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

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

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

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

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

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

4.2.5. Включаем ребро u_j в множество U_i^п: U_i^п = U_i^п.u_j, подсчитываем показатель ∆s_i ∆s_i⁺ = ∆s_i⁺ + 1 и возвращаемся в п. 4.2.

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

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

∆s_t = min {∆s_i ∆S}, x_t↔ ∆s_t.

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

S₀ = S₀ + ∆s_t.

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

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

8. Включаем вершину x_t в множество X_l, и исключаем ее из X_k:

X_l= X_l. x_t, X_k = X_k\ x_t .

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

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

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

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

X_k = {X_k X_t^п }

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

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

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

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

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

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

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

|X_k|_max ≤ ρ× A× i ^½.

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

Для сравнительной оценки вычислительной сложности реализации процесса декомпозиции достаточно рассмотреть однократное выполнение процедур 1…4 и процедуру 6. Отметим, что при использовании операций над упорядоченными множествами сортировке подлежат только множество X_l в порядке возрастания индексов элементов, массив ∆S по возрастанию значений его элементов и элементы x_iмножества X_k в соответствии с положением ∆s_i в массиве ∆S.

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

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

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

2A×i×ρ×ρ×A×i^½ = 2A²×ρ²×i^3/2.

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

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

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

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

,

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

,

имеем

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

K_алг = 2A²×ρ²×i ^3/2 / (4A×ρ²×i ^3/2) = A/2.

2. Проверка условияi = 1 (| X_l^к | – 1) (x_i≠x_{i + 1}). Очевидно, что проверяя это условие, мы должны предполагать, что X_l^к может быть неупорядоченным кортежем. Например, в процессе упорядочивания множества X_l^к = {x₃, x₁, x₆, x₄, x₅, x₉} из-за искажения имени элемента x₉ на x₄ может быть получен кортеж < x₁, x₃, x₄, x₅, x₆, x₄>. Следовательно, в алгоритме, устанавливающем истинность или ложность этого выражения, никакие свойства упорядоченных множеств использовать нельзя.

3. Формирование куска H_l^к(X_l^к, U_l^к) гиперграфа. При оценке вычислительной сложности выполнения этого этапа процесса декомпозиции будем считать, что кусок гиперграфа должен быть получен в форме H_l^к(X_l^к, U_l^к, ГX_l^к, ГU_l^к). Подсчёт количества операций сравнения будем выполнять, используя выражения формального описания выполнения операции получения куска H₁^к гиперграфа [4].

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

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

где, например, при объединении трёх подмножеств рёбер {Гx_i Гx_j }{Гx_k} a_k= |Гx_k' | / |Гx_k|, Гx_k'– множество рёбер, принадлежащих вершине x_k и не принадлежащих вершинам множества {x_i, x_j}.

Считая| X_l^к| = n_l, получим:

N_3.1 = ρ² [n_l + a ×n_l× (n_l  – 3)/2].

Поскольку 0 ≤ a< 1, N_3.1 <ρ²× (n_l² – n_l)/2.

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

ОтсюдаN_{3.1 уп} < ρ× (n_l² + n_l) – n_l.

Нетрудно видеть, что отношение К_3.1 = N_3.1 / N_{3.1 уп} при росте n_l стремится к ρ/2.

3.2. Определение множества U_l^к_int= {u_j U_l^к : Гu_j X_l^к / Гu_j ГU}.

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

N_3.2 = A×n_l×m_l.

Упорядоченные множества. На основании (1) из [5] – N_{3.2 уп} = 2n_l×m_l.

Отсюда отношение К_3.2 = N_3.2 / N_{3.2 уп} равно A /2.

3.3. Определение множества U_l^к_ext= U_l^к \ U_l^к_int.

Неупорядоченные множества. Считая |U_l^к_int| =|U_l^к| /2, имеем: N_3.3 = m_l²/2.

Упорядоченные множества. N_{3.3 уп} = 2(m_l + m_l/2 – 1).

При росте m_l отношение К_3.3 = N_3.3 / N_{3.3 уп} стремится к m_l.

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

3.5. Определение множества ГU_l^к = {Гu_j: u_j U_l^к_int Гu_j X_l^к : u_j U_l^к_ext/ u_j U_l^к, Гu_j ГU}. Операция Гu_j X_l^к будет выполняться |U_l^к_ext| = |U_l^к|/2 раз. Не будем учитывать проверки u_j U_l^к_int и  u_j U_l^к_ext.

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

Упорядоченные множества: N_{3.5 уп} = m_l/2 [2(n_l + A – 1)] = m_l× (n_l + A – 1).

При росте n_l и m_l отношение К_3.5 = N_3.5 / N_{3.5 уп} стремится к A /2.

4. Удаление куска H_l^к(X_l^к, U_l^к) из модели системы. Для простоты символики будем рассматривать выполнение этой операции после первого применения алгоритма разрезания. Удаление выделенной части схемы реализуется операцией «Дополнение части до ультраграфа H_U и гиперграфа H»[6] в варианте H(X, U) \ H₁^к(X₁^к, U₁^к). Обозначим получаемый кусок гиперграфа как H_сл (X_сл^к, U_сл^к).

4.1. Определение X_сл^к = X\ X₁^к.

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

Упорядоченные множества: N_{4.1 уп} = 2 (n_l + n – 1).

Отношение К_4.1 = N_4.1 / N_{4.1 уп} стремится к n_l. Напомним, что n_l = n / L, где L – константа.

4.2. Определение U_сл^к_int = U \ U₁^к.

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

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

Отношение К_4.2 = N_4.2 / N_{4.2 уп} стремится к m_l. Отметим, что m_l = m / L.

4.3, 4.4 и 4.5. Определение U_сл^к_ext = U₁^к_ext, U_сл^к = U_сл^к_int.U_сл^к_ext и ГX_сл^к = {Гx_i ГX/ x_i X_сл^к}. Очевидно, что на вычислительную сложность выполнения этих операций упорядочивание множеств не влияет.

4.6. Определение ГU_сл^к = {Гu_j: u_j U_сл^к_int Гu_j\ X₁^к : u_j U_сл^к_ext/u_j U_сл^к, Гu_j ГU}. Количество операций сравнения определяется выражением | X₁^к |× |Гu_j|× |U_сл^к_ext|.×Будем считать, что |U_сл^к_ext| = |U_сл^к | / 2.

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

Упорядоченные множества: N_{4.6 уп} = (n_l + A×– 1)×m_l×(L – 1).

При росте n_l и m_l отношение К_4.6 = N_4.6 / N_{4.6 уп} стремится к A / 2.

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

Эти условия логически эквивалентны условию X = Y, где Y= {X₁. X₂.X₃. …. X_L}, проверка которого требует меньшего количества операций сравнения.

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

N₆ = n² и N_{6 уп} = 4(n– 1).

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

К₆ = N₆ / N_{6 уп} = n² / (4(n– 1) + n log₂ n) = n / log₂n.

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

– формирование куска H_l^к(X_l^к, U_l^к) гиперграфа в п. 3.3 в m_l раз;

– удаление куска H_l^к(X_l^к, U_l^к) из гиперграфа в п. 4.1 в n_l и в п. 4.2 в m_l раз;

– проверка условия X = { X₁. X₂.X₃. ….X_L} в n / log₂n раз.

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

Литература

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

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

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

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

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

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