I ші халықаралық ғылыми-тəжірибелік конференцияның ЕҢбектері
жүктеу/скачать 11,62 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Определение 1.
- Утверждение 2.
- Утверждение 3.
- Теорема 1.
- Доказательство теоремы 1: Случай 1.
- АНАЛИТИЧЕСКИЕ ИССЛЕДОВАНИЯ РАБОТОСПОСОБНОСТИ РКС ЧАСТЬ 2 Шарипбаев А.А., Ускенбаева Р.К., Куандыков А.А.
- Теорема Фробениуса - Кёнига.
- Теорема (расширенная теорема Минка).
| ЧАСТЬ 1
Шарипбаев А.А., Ускенбаева Р.К., Куандыков А.А. Казахский национальный технический университет имени К.И.Сатпаева
Работоспособность и функциональность распределенной компьютерной системы (РКС) являются сложными свойствами, состоящими из надежности, защищенности, безопасности (регулирование доступа к внутренним ресурсам), корректности, производительности, масштабности. Но среди них основным является надежность. Поэтому в работе рассматриваются вопросы надежности РКС. Пусть задана система (РКС) из: функциональных ресурсов ФМ ⊆ ФР, ФМ = {ФМi}; прикладных функций (ПФ) F={f 1 ,f
…f n }, выполняемых РИС; для выполнения ∀f i
∈ F имеется критерий We(q)→ max; матрицы инцидентности между ФМ и ПФ (F): Ψ = ||ϕ ij ||
; стратегий назначения ФМ по ПФ в виде: СН: [α/β/γ], We(q)→ max; стратегий распределения ФМ по ПФ вида: СР:[I/J/K], Wu(q)→ max. Необходимо оценить работоспособность данной системы на текущий момент состояния и/или после сбоя или отказа. Целью исследования являются математические исследования и оценка уровней работоспособности РИС при различных состояниях; эффективности распределения функциональных ресурсов по прикладным функциям, осуществленным по стратегиям [1]: СР:[I/J/K].
Исследование работоспособности РИС проводится при различных стратегиях распределения ресурсов, осуществляется на основе теории перманента матрицы. Введем новые понятия «обобщенная диагональ» и «обобщенный перманент» для полного исследования свойств всех стратегий распределения ресурсов. Основываясь на эти понятия, сформулируем ряд теорем и утверждений. Определение 1. Обобщенной диагональю матрицы Ψ = || ϕ
||
назовем последовательность ℘ из п ее элементов, такой что: ℘ = (ϕ(1, σ 1 ),
ϕ(2, σ 2 ), ϕ(3, σ 3 ), ..., ϕ(i, σ j ), ..., ϕ(n, σ m )), (3.6) σ j
) fp ( МФ m 1 j j I = = n,
∀i ⇒ ( ) , i ( j m 1 j σ ϕ ∑ = σ = 1), ∃j ⇒ (0 < ∑ = σ ϕ n 1 i j ) , i (
≤ d), Жоғары оқу орындарында ақпараттық технологияларды оқыту сапасын жақсарту: жолдары мен мүмкіндіктері
370 d ∈(1, 2, 3,…h, …, n), где ϕ(i, σ j ) – единственный элемент, находящийся на пересечении i-й строки с σ j -им столбцом матрицы Ψ. Если для ∀i, k ⇒ (σ j
k ), то
σ является диагональю в классическом варианте теории перманент, наоборот, если ∀i, k ⇒ (σ j =
σ k ), то σ является одним из столбцов матрицы Ψ для которого выполняется условие d = n. Обобщенным диагональным произведением матрицы Ψ назовем произведение элементов ℘ = (ϕ(1, σ 1 ),
ϕ(2, σ 2 ), ϕ(3, σ 3 ), .., ϕ(i, σ j ), .., ϕ(n, σ m )). Определение 2. Обобщенный перманент матрицы Ψ является суммой обобщенных диагональных произведений данной матрицы Per[ Ψ] =
)) , ( ( * ... * ) , ( ( * ... *
)
(2, ( *
)
(1, ( n i 2 1 n i σ ϕ σ ϕ σ ϕ σ ϕ ∑ σ . В случае квадратной матрицы Ψ, когда n=m, перманент обозначается через per[Ψ]. Определение 3. Система (РИС) работоспособна, только тогда, когда все прикладные функции F={f 1 , f
2 , …, f
n } выполнимы имеющимися в системе функциональными ресурсами.
возникновения можно восстановить такое состояние РИС, функциональная возможность, которой не ниже того состояния, в котором РИС находился до отказа, т.е.: во-первых, все ПФ выполнимы; во-вторых, эффективность их выполнения не хуже, чем до отказа. Таким образом, при малом отказе функциональное состояние РИС и ее программная система (ПС) полностью восстановит то состояние, которое было до отказа, т.е. восстановленное состояние ( )
t S полностью войдет в состав целевой ситуации до отказа Ц j S . Утверждение 1. Система работоспособна, если для ее матрицы инцидентности Ψ, реализующей стратегию распределения функциональных ресурсов по СР:[I/J/K] выполняется Per[Ψ]>0 и неработоспособна, если Per[
Ψ]=0. Утверждение 2. Для перманента матрицы инцидентности Ψ системы порядка n выполняется Per[Ψ] = ∑ ∏ σ
σ m 1 i ) i ( i a = 0, если Ψ содержит нулевую подматрицу минимального сечения, состоящего из нулевых элементов с размерами s X t с t=n-s+1. Утверждение 3. Обобщенный перманент Per[Ψ] матрицы Ψ инвариантен к перестановке ее столбцов и строк. Справедливость утверждения 3. следует из определения Обобщенный перманент и подтверждает условность нумерации функций и модулей. Утверждение 4. Для обобщенного перманента матрицы Ψ Per[Ψ] Жоғары оқу орындарында ақпараттық технологияларды оқыту сапасын жақсарту: жолдары мен мүмкіндіктері
371 выполняется условия Per[Ψ] ≥ 0. Справедливость утверждения 4. следует из того, что по определению для всех элементов матрицы Ψ выполняется ∀ ϕ
≥0 и, соответственно, каждое диагональное произведение и их сумма - не отрицательным. Определим теперь условия равенства обобщенный перманент Per[Ψ] нулю и образования в матрице Ψ подматриц минимального сечения. Подматрицей минимального сечения матрицы Ψ назовем ее подматрицу, равенство нулю всех элементов которой необходимо и достаточно для соответствия матрицы Ψ неработоспособному состоянию системы. Все элементы подматрицы минимального сечения соответствуют множеству элементов оборудования (минимальному сечению), отказ вызывает отказ системы, причем никакое собственное его подмножество этим свойством не обладает. Для подматрицы минимального сечения, содержащей все нули, переход хотя бы одного из ее элементов в единичное состояние связан с отображением матрицей Ψ смены состояния системы с отказавшего на работоспособное. Теорема 1.
Система, реализующая стратегию распределения функциональных ресурсов по СР:[I/J/K] при возникновении отказов в количестве s функциональных модулей (ФМ): работоспособна, если Per[Ψ] > 0; не работоспособна, если: Per[
Ψ] = 0; система не в состоянии выполнить прикладные функции в количестве (n - ∑
s 1 k k l d + 1); матрица Ψ имеет подматрицу с размерами (n - ∑ =
1 k k l d + 1) Х s, где k l d - количество функций, выполняемых отказавшим модулем k l
, (l 1 , l 2 , l 3 , …, l k , …, l 1 , …, l s ) ⊆ s. Последняя подматрица называется нулевой
подматрицей или
минимальным сечением матрицы Ψ. Доказательство теоремы 1: Случай 1. В случае d=1 и l=1 доказательство теоремы 1 для s отказов и s невыполняемых прикладных функций сводится к доказательстве теоремы Фробениуса — Кёнига – Минка. Для этого обозначение размеров нулевой подматрицы s X s, возникаемой в составе матрицы инцидентности Ψ в результате отказа ФМ в количестве s, которые приведут к невозможности выполнения s прикладных функций. следует переобозначить на t X s с s + t = n + 1, которые приняты в теореме Фробениуса — Кёнига – Минка. Жоғары оқу орындарында ақпараттық технологияларды оқыту сапасын жақсарту: жолдары мен мүмкіндіктері
372 Случай 2. Когда d > 1 ведем новое обозначение s′ = ∑ = s 1 k k d
или s
) ( 1 fp M Ф m j j U = , которое соответствует числу прикладных функций, которые не могут быть выполнены из-за того отказались s функциональных модулей, каждый из которых выполняли
d прикладных функций до отказа. Тогда доказательство теоремы 1 для s отказов и s′ невыполняемых прикладных функций сводится к доказательству теоремы Фробениуса – Кёнига – Минка. Для этого обозначения размеров нулевой подматрицы s′ X s, возникаемой в составе матрицы инцидентности Ψ в результате отказа ФМ в количестве s′, которые приведут к невозможности выполнения s прикладных функций следует переобозначить на t X s с s + t = n + 1, которые приняты в теореме Фробениуса – Кёнига – Минка. Таким образом, в результате выполненного преобразования выражения для размерности нулевой подматрицы матрицы инцидентности Ψ (n - ∑ =
1 k k l d + 1) Х s на (n - s ′ + 1) Х s, а затем на вид t X s с s + t = n + 1 получаем формулировку теоремы Фробениуса — Кёнига – Минка.
Литература 1. Ускенбаева Р.К. Математическое и программное обеспечение надежности распределенных информационных систем. Автореферат диссертации на соискание ученой степени доктора технических наук. Алматы, 2007 АНАЛИТИЧЕСКИЕ ИССЛЕДОВАНИЯ РАБОТОСПОСОБНОСТИ РКС ЧАСТЬ 2 Шарипбаев А.А., Ускенбаева Р.К., Куандыков А.А. Казахский национальный технический университет имени К.И.Сатпаева
Для полноты изложений приведем доказательство теоремы Фробениуса – Кёнига – Минка [1]. Наиболее важным результатом комбинаторной теории матриц и теории перманентов неотрицательных матриц является теорема Фробениуса - Кёнига. Теорема Фробениуса - Кёнига. Пусть А - матрица порядка n . Для того чтобы каждая диагональ матрицы А содержала нуль, необходимо и достаточно, чтобы в А существовала нулевая подматрица размера 1 + = + × n t s c t s , где s и t количество столбцов и строк нулевой подматрицы. Данной теореме эквивалентна следующая теорема. Теорема Минка. Пусть А — неотрицательная матрица порядка n. Тогда Per(A) = 0 только в том случае, когда А содержит нулевую подматрицу размера Жоғары оқу орындарында ақпараттық технологияларды оқыту сапасын жақсарту: жолдары мен мүмкіндіктері
373 s X t с s + t = n + 1, где s и t количество столбцов и строк. Доказательство. Необходимость докажем индукцией по n . Пусть ( )
0 =
per . Если
1 =
, то [ ]
0 =
. Предположим, что условие необходимо для всех квадратных (0,1) -матриц порядка, меньшего n . Если А составлена из нулей, то доказывать нечего. Предположим, что 0 > hk a . Тогда
( )
( ) ( ) ∑ = = =
j hj j h A per a A per 1 / 0 ;
Так как все произведения ( ) ( )
h A per a hj / неотрицательны, а hk a
положительно, должно быть ( ) ( ) 0 / =
h A per .
Следовательно, по индуктивному предположению в ( ) k h A / можно найти нулевую подматрицу размера ( ) 1 1 1 1 1 1 + − = + ×
t s c t s . Переставим строки и столбцы А так, чтобы эта нулевая подматрица заняла правый верхний угол:
} } } 1 1 1 1 0 s n s Y Z X PAQ B t t n − = = − L L 8 7 6 M . Эта перестановка производится только лишь для удобства обозначений и не является существенной частью доказательства). Ни 1
n − , ни 1 t n − не могут быть равны нулю, так как 1
и 1
положительны и n t s = + 1 1 . Так как 1 1
s n = − , и 1 1 s t n = − , то Y X , - квадратные матрицы порядков соответственно 1 1
s . Таким образом, ( )
( ) ( )
Y per X per A per = = 0 ,
и либо ( )
X per , либо
( ) Y per должен обратиться в нуль. Без ограничения общности предположим, что ( )
0 =
per . Тогда по предположению индукции X содержит нулевую подматрицу размера 1 1 + = + × s u c u υ υ . Предположим, что
[ ] 0 ,..., ,...,
1 1 = υ β β α α
X , т.е. [ ] 0 ,..., ,...,
1 1 = υ β β α α
B . Рассмотрим подматрицу
[ ] n s s B C u ,...,
2 , 1 , ,...,
,..., 1 1 1 1 + + = υ β β α α .
Это нулевая подматрица матрицы A с u строками и ( ) 1 s n − + υ
Жоғары оқу орындарында ақпараттық технологияларды оқыту сапасын жақсарту: жолдары мен мүмкіндіктері
374 столбцами. Более того,
( ) ( ) 1 1 1 1 1 1 + = − + + = − + + = − + + n s n s s n u s n u υ υ . Доказательство необходимости завершено. Чтобы доказать обратное утверждение, предположи, что А содержит нулевую подматрицу размера 1 + = + × n t s c t s . Переставим строки и столбцы А так, чтобы }}
= = M K L PAQ B t L L M 0 . (7) По теореме Лапласа о разложении
( )
( ) [ ] ( ) ( ) ( ) ∑ ∈ = = n s Q s B per s B per B per A per , ,..., 1 ,...,
1 ω ω ω . (8)
Но
[ ] ω s B ,...,
1 - подматрица порядка s матрицы [ ]
s B ,...,
1 ,...,
1 , а эта последняя имеет не более
1 1 − = − − + = −
t t s t n
ненулевых столбцов. Поэтому каждая подматрица вида [ ] ω s B ,...,
1 должна
иметь по
крайней мере
один нулевой
столбец; следовательно, [ ]
) 0 ,..., 1 = ω s B per для любой n s Q , ∈ ω . Отсюда вытекает, что ( ) 0
A per .
Следующая теорема является несколько расширенным вариантом теоремы Минка. Теорема (расширенная теорема Минка). Пусть A -неотрицательная матрица размера n m n m ≤ × , . Тогда ( )
0 =
Per в том и только том случае, когда A содержит нулевую подматрицу размера ( ) 1 + − × s n s . Доказательство. Если n m < , то пусть
= C A B ,
где C - матрица из единиц размера ( ) n m n × − . Тогда по основной теореме жүктеу/скачать 11,62 Mb. Достарыңызбен бөлісу:
|