Просмотр кода страницы Участник:Палионная/Моделирование надежности сложных модифицируемых информационных систем

= Свойства и структура алгоритма =

== Общее описание алгоритма ==

В данной задаче рассматривается байесовская рекуррентная модель роста надежности сложных модифицируемых информационных систем.
Так как любая впервые созданная сложная информационная система не обладает требуемой надежностью, она подвергается различным модификациям, целью которых является устранение дефектов, препятствующих правильному функционированию системы. Надежность системы зависит от соотношения параметров, интерпретируемых в теории надежности как показатели <<дефективности>> и <<эффективности>> средства, исправляющего ошибки в системе. При использовании байесовских моделей применительно к задачам теории надежности предполагается, что основные параметры системы не являются заданными, а известны только их априорные распределения. В частности данных алгоритм производит вычисления предельной надежности группы однотипных сложных модифицируемых информационных систем для случая параболического распределения параметров.

== Математическое описание алгоритма ==

Для формализации понятия надежности системы, будем характеризовать ее в каждый момент времени t параметром p(t), при этом время 
считаем непрерывным. Так как система подвергается модификациям в случайные моменты времени : <math> 0=Y_0\le~Y_1~\le Y_2~\le\ldots
</math>, параметр <math>p(t)</math> изменяется, принимая соответственно значения <math>p(t) = p(Y_j) = p_j</math> при <math>Y_j~\le~t<~ Y_{j+1}</math> (предполагается, что траектории процесса <math>p(t)</math> непрерывны справа, а модификации происходят мгновенно). Причем при модификациях параметр надежности может как увеличиваться, так и уменьшаться из-за некачественных модификаций.

К числу математических моделей, описывающих изменение надежности модифицируемых информационных систем, относятся рекуррентные модели роста надежности. Рассмотрим, в частности, дискретную экспоненциальную модель, которая определяется следующим образом:
<math>p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).</math>

Здесь <math>\{(\theta_j, \eta_j)\}</math>, <math>j\ge1</math>, -- последовательность независимых одинаково распределенных двумерных случайных векторов таких, что <math>0 < \eta_1 < 1</math>; <math>0 < \theta_1  < 1</math> почти наверное. Начальная надежность <math>p_0</math> считается заданной, случайные величины <math>\eta_j</math> (параметры <<дефективности>>) и <math>\theta_j</math>  (параметры <<эффективности>>)  описывают соответственно возможное уменьшение и повышение надежности.

Обозначим <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>.
В книге <ref> Королев В. Ю., Соколов И. А.  Основы математической теории надежности модифицируемых систем. --- М.: ИПИ РАН, 2006. 102~с. </ref> доказано, что при условии <math>\lambda+\mu\neq1</math>
<math>
p=\lim_{j\to\infty}E p_j = \frac{\mu}{\lambda+\mu}.
</math>
Величина <math>p</math> характеризует асимптотическое значение надежности системы в рамках некоторой рекуррентной модели, задаваемой набором <math>\{(\theta_j, \eta_j)\}</math>.

В рамках байесовского подхода в постановке задач теории надежности можно рассмотреть более сложную ситуацию, где основные параметры системы  <math>\lambda </math> и  <math>\mu </math> предполагаются случайными. В таком случае наиболее естественной и удобной для изучения характеристикой является усредненное значение предельной надежности, то есть
<math> 
p_{average} = Ep = E\frac{\mu}{\lambda+\mu}, 
</math>
где усреднение ведется по совместному распределению случайных величин   <math>\lambda </math> и  <math>\mu </math>.

Так как случайные величины  <math>\eta_1 </math> и  <math>\theta_1 </math> удовлетворяют ограничениям  <math>0 < \eta_1 < 1, 0 < \theta_1  < 1 </math>, средние значения  <math>\lambda </math> и  <math>\mu </math> величин  <math>1 - E\theta_j  </math> и  <math>E\eta_j </math> соответственно также находятся на отрезке [0,1]. В частном случае, рассмотрим независимые случайные параметры  <math>\lambda </math> и  <math>\mu </math>, имеющие параболические распределения на некоторых (вообще говоря, разных) отрезках, являющихся подмножествами отрезка [0,1].

Итак, пусть средний параметр <<эффективности>>  <math>\lambda </math> и средний параметр <<дефективности>>  <math>\mu </math> независимы и имеют параболическое распределение  <math>P(a_\lambda, b_\lambda) </math>,  <math>0\le a_\lambda<b_\lambda\le1 </math>, и  <math>P(a_\mu, b_\mu) </math>,  <math>0\le a_\mu<b_\mu\le1 </math>, соответственно.

Для плотности  <math>f_\xi(x) </math> некоторой случайной величины  <math>\xi </math>, имеющей параболическое распределение с параметрами  <math>(a_\xi, b_\xi) </math>, справедливо:
 <math> f_\xi(x) = \frac{6(x-a_\xi)(b_\xi-x)}{(b_\xi-a_\xi)^3},\ \ \ \ x\in[a_\xi, b_\xi].  </math>

== Вычислительное ядро алгоритма ==
Пусть рассматривается изменение надежности группы однотипных системы на интервале времени [0, T].

'''1.''' Для каждой системы моделируем модификации, происходящие в случайные моменты времени <math>t_j: \sum_{j}t_j <= T</math>, следующим образом:

* Генерируем реализацию случайных величин  <math>\lambda </math>,  <math>\mu </math> с параболическим распределением на заданных интервалах  <math>[a_\lambda, b_\lambda], [a_\mu, b_\mu]</math> соответственно. Задаем начальную надежность системы, как реализацию случайной величины с равномерным на [0,1] распределением.

* Пока <math> \sum_{j}t_j <= T </math>, моделируем поступления модификаций в систему в момент времени <math>t_j</math>: генерируем реализацию случайных величин  <math>\theta_j </math>, <math>\eta_j </math> таких, что <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>, изменяем надежность системы по формуле <math> p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).</math>

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

== Макроструктура алгоритма ==
Основную часть алгоритма составляет расчет надежности модифицируемых объектов после каждой модификации. Могут быть рассмотрены другие априорные распределения параметров <math>\lambda и \mu</math> в рамках данной модели или совершенно другие математические модели, описывающие изменение надежности сложных модифицируемых систем.

== Схема реализации последовательного алгоритма ==

Схема реализации последовательного алгоритма приведена в [[#Вычислительное ядро алгоритма|описании вычислительного ядра алгоритма]].
 
== Последовательная сложность алгоритма ==
* <math>[0;T]</math> - рассматриваемый временной интервал;
* <math>N</math> - количество модифицируемых систем.
Тогда для вычисления средней надежности <math>N</math> модифицируемых объектов за время <math>T</math> в последовательном (наиболее медленном) варианте требуется:
* <math>N(34+6T)+1</math> сложений (вычитаний),
* <math>N(51+5T)</math> умножений.

== Информационный граф ==
'''Дополнить'''
== Ресурс параллелизма алгоритма ==
Ресурс параллелизма алгоритма заключается в независимости модифицируемых объектов. Таким образом на разных процессах могут происходить вычисления для разных объектов независимо друг от друга.

== Входные и выходные данные алгоритма ==
'''Входные параметры:''' 
* <math>N</math> - количество объектов в рассматриваемой группе; 
* <math>T</math> - временной интервал, <math>T>0 ;</math> 
* <math>a_l, b_l</math> - интервалы параболического распределения для случайной величины <math>\lambda, a_l >= 0, b_l <=1 ;</math>  
* <math>a_m, b_m</math> - интервалы параболического распределения для случайной величины <math>\mu, a_m >= 0, b_m <=1 .</math>  
Выходные параметры: усредненная надежность группы однотипных объектов.
== Свойства алгоритма ==

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
Дополнить
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Для данной постановки задачи существующих реализаций не найдено.
= Литература =
<references />  
2.  Кудрявцев А. А.  Байесовские модели массового обслуживания и надежности: априорные распределения с компактным носителем //
Информатика и ее применения, 2016. Т. 10. Вып. 1. С. 00--00.


[[en:Description of algorithm properties and structure]]