close

Вход

Забыли?

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

?

Gilmytdinov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
М. Р. Гильмутдинов, Н. В. Марковская, А. М. Тюрликов
ИСПОЛЬЗОВАНИЕ СЛУЧАЙНЫХ ГРАФОВ
ДЛЯ ОЦЕНКИ НАДЕЖНОСТИ
ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
Учебное пособие
Санкт-Петербург
2014
УДК 004.9(075)
ББК 32.97я73
Г47
Рецензенты:
доктор технических наук, профессор В. А. Богатырёв;
кандидат технических наук, доцент О. И. Курсанов
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
Г47
Гильмутдинов, М. Р.
Использование случайных графов для оценки надежности
вычислительных сетей: учеб. пособие / М. Р. Гильмутдинов, Н. В. Марковская, А. М. Тюрликов. – СПб.: ГУАП,
2014. – 46 с.
ISBN 978-5-8088-0963-5
Рассматривается использование случайных графов для анализа
надежности сетей связи. Теоретический материал сопровождается
практическими примерами и алгоритмами, что поможет студентам
лучше усвоить материал.
Издание предназначено для бакалавров, обучающихся по
направлениям 11.03.02 «Инфокоммуникационные технологии
и системы связи» и 10.03.01 «Информационная безопасность».
УДК 004.9(075)
ББК 32.97я73
ISBN 978-5-8088-0963-5
© Гильмутдинов М. Р.,
Марковская Н. В., Тюрликов А. М., 2014
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2014
Оглавление
Введение .................................................................................................. 4
1 Использование случайных графов для оценки надежности сетей 6
1.1 Постановка задачи.................................................................. 6
1.2 Определение случайного графа ............................................ 7
1.3 Переборный алгоритм вычисления вероятностных
характеристик случайных графов. ............................................ 11
1.4 Способы ускорения вычисления вероятностных
характеристик случайных графов ............................................. 14
1.4.1 Перебор по путям .............................................................. 14
1.4.2 Декомпозиция случайного графа ..................................... 14
1.4.3 Упрощение структуры графа ........................................... 18
2 Использование имитационного моделирования для оценки
надежности (на примере случайных графов)............................ 22
2.1 Использование имитационного моделирования для оценки
вероятностных характеристик случайных графов .................. 22
2.2 Методы ускорения моделирования .................................... 30
2.2.1 Снижение временных затрат на проведение некоторых
экспериментов ............................................................................ 31
2.2.2 Уменьшение дисперсии оценки. Метод расслоенной
выборки ....................................................................................... 37
Заключение............................................................................................ 44
Литература ............................................................................................ 45
3
Введение
В настоящее время для анализа надежности технических
систем достаточно широко используется подход, при котором
анализируемая система описывается в виде так называемого
случайного графа. Анализ надежности сети связи с помощью
случайного графа является наиболее наглядным примером,
иллюстрирующим данный подход. В этом случае с вершинами
ассоциируются узлы связи, входящие в сеть, а с ребрами – линии
связи, соединяющие узлы друг с другом. При этом вершины графа
считают абсолютно надежными элементами, а ребра – не надежными
элементами. Анализ надежности сети сводится к вычислению
вероятности некоторого события (например, вероятности
существования пути между заданной парой вершин в графе).
Сети связи - это не единственное применение случайных
графов. Любая многоэлементная система при анализе надежности
может быть представлена подобным образом. В России и за рубежом
разработаны и совершенствуются программные средства,
реализующие этот подход. Наиболее известными отечественными
программными средствами, являются: АРБИТР; ПК АСМ;
АСОНИКА-К; УНИВЕРСАЛ [1].
Данное учебное пособие в первую очередь посвящено методам
оценки надежности вычислительных сетей. Пособие включает два
раздела. В первом разделе излагается ряд общих сведений из теории
графов, обеспечивающих, по мнению авторов, терминологическое и
понятийное содержание излагаемого материала. Рассматривается
переборный алгоритм вычисления вероятностных характеристик
случайных графов и способы ускорения вычисления этих
характеристик.
4
Второй раздел посвящен способам оценивания вероятностных
характеристик случайных графов с помощью имитационного
моделирования. на основе аппарата теории графов. Описаны методы
ускорения имитационного моделирования за счет снижения
временных затрат на проведение некоторых экспериментов и за счет
уменьшения дисперсии оценки и, как следствие, уменьшения числа
экспериментов при сохранении точности оценки.
5
1
Использование случайных графов для
оценки надежности сетей
1.1 Постановка задачи
Графы нашли практическое применение во всех областях, где
нужно смоделировать сложные сети. В данном пособии речь пойдет
о представлении при помощи случайных графов сетей связи.
В качестве примера рассмотрим вычислительную сеть.
Вычислительная сеть − это совокупность компьютеров,
соединенных между собой с помощью каналов связи в единую
систему и использующих общие ресурсы.
Таким образом, вычислительную сеть можно представить в
виде случайного графа, как это показано на рис. 1. В этом случае с
вершинами ассоциируются вычислительные машины, входящие в
сеть, а с ребрами – двунаправленные каналы связи, соединяющие
машины друг с другом. Предположим, что отказы каналов - это
независимые события, а узлы абсолютно надежны и никогда не
отказывают. Вероятности работоспособности каналов задаются
следующим образом:
Pr {работоспособен канал (1, 3)} = p1
Pr {работоспособен канал (1, 4 )} = p2
Pr {работоспособен канал ( 2, 3)} = p3
Pr {работоспособен канал ( 3, 4 )} = p4
Здесь и далее мы будем использовать следующие обозначения
для вероятностей событий:
Pr{описание события}=численное значение вероятности
6
Существует два типа задач:
найти вероятность того, что существует связь между двумя
узлами, например, узлами 1 и 2:
1)
Pr {связь(1, 2)}
найти вероятность того, что существует связь между всеми
узлами сети:
2)
Pr {связь между любыми узлами}
Далее дадим основные определения из теории графов,
сформулируем и решим эти задачи в понятиях теории графов.
1
2
1
p1
p1
p3
3
p2
2
p3
p2
3
p4
p4
4
4
а) сеть связи
б) случайный граф
Рис.1. Пример описания сети связи с помощью случайного графа
1.2 Определение случайного графа
Введем в рассмотрение множество X , состоящее из n
элементов, т.е. X = n , где символом . обозначается мощность
7
множества. Элементы множества X будем называть вершинами.
2
Обозначим за X ( ) множество всевозможных пар из X и введем в
2
рассмотрение множество Y , являющееся подмножеством X ( ) .
Графом G будем называть пару множеств
( xa , xb )
( X ,Y ) .
Пара
называется неупорядоченной, если ( xa , xb ) ≡ ( xb , xa ) . Если
множество X ( ) состоит из неупорядоченных пар, то граф называют
неориентированным, а элементы множества Y называют ребрами,
2
Y = l . Поскольку ребро задается парой вершин, можно говорить,
что ребро соединяет одну вершину с другой.
Дадим
несколько
определений,
последующего изложения [2, 3].
8
необходимых
для
−
Вершины, которыми задается ребро, называются концевыми
вершинами для этого ребра.
−
Ребро и вершина являются инцидентными, если вершина
концевая для данного ребра.
−
Ребро называется петлей, если оно соединяет вершину саму
с собой.
−
Два или более ребер называются кратными ребрами, если
они соединяют одну и ту же пару вершин. При этом
степенью кратности будем называть число ребер,
соединяющих данную пару вершин.
−
Граф называется обыкновенным графом, если он не имеет
петель и кратных ребер.
−
Ребра называются смежными ребрами, если они имеют
общую концевую вершину.
−
Вершины называются смежными вершинами, если они
соединены ребром.
−
Путем в графе из вершины xa в вершину xb называется
последовательность из неповторяющихся вершин, каждая из
которых смежна со своими соседями. При этом данная
последовательность начинается с xa и заканчивается xb .
−
Граф называется связным графом, если существует хотя бы
по одному пути из одной вершины до всех остальных.
Минимальное множество рёбер, удаление которого делает
граф несвязным, называется коциклом.
В настоящем пособии ограничимся рассмотрением только
обыкновенных неориентированных графов.
Граф, как правило, изображают двумя способами. В виде
диаграммы или в виде матрицы смежности, как это показано на
рис. 2.
−
2
1
4
1
2
3
4
1
0
1
1
0
2
1
0
1
1
3
1
1
0
0
4
0
1
0
0
3
а) диаграмма
б) матрица смежности
Рис.2. Способы представления графов
Матрица заполняется следующим образом. В ячейке с
индексом
( a, b )
записывается коэффициент кратности для ребер
между вершинами a и b . Таким образом, матрица смежности
9
является квадратной матрицей, симметричной относительно главной
диагонали. Размер матрицы равен числу вершин (или мощности
множества X ).

В так называемом случайном графе G каждому ребру ставится
в соответствие вероятность его существования. Таким образом,
случайным графом будем называть совокупность трех множеств
( X ,Y , P) .
Первые два множества – это множество вершин и
множество ребер. Третье множество – это множество вероятностей
существования ребра, причем Y = P .
Сформулируем теперь задачу, поставленную в п.1.1, в
терминах теории графов:
1)
найти вероятность существования пути из вершины xa в
вершину xb :
Pr {путь xa , xb }
2)
найти вероятность связности графа:
Pr {граф связен} .
Для сокращения записи обозначим:

Pr {граф связен} = Pсв G ,
( )
Pr {путь xa , xb } = Pсв ( xa , xb ) .
Существуют другие варианты случайных графов, у которых
множество вероятностей P также может быть связано с множеством
вершин, определяя существование или отсутствие последних.
Однако в данном курсе будут рассматриваться только случайные
графы со случайными ребрами.
10
1.3 Переборный алгоритм вычисления вероятностных
характеристик случайных графов.
Задача 1.

Пусть задан случайный граф G , изображенный на рис. 3, и
требуется определить вероятность существования пути из вершины 1
в вершину 2 Pсв (1, 2) .
р12
1
2
Ğ
р23
р13
3
Рис.3. Случайный граф для задачи 1
Рассмотрим множество
Γ ={ g1 ,  , g N }
всех возможных
неслучайных графов (подграфов), которые можно получить на
основе случайного. Число таких подграфов N = 2l . Каждый такой
граф g i может появиться со своей вероятностью p ( g i ) . Среди них
выделим подмножество Γ′ ={ g1′ ,  , g K′ } , где K ≤ N , в котором путь
из вершины 1 в вершину 2 существует.
Для рассматриваемой задачи 1:
N = 8,
K = 5 . Список
элементов Γ и вероятности появления такого графа представлены в
таблице 1.
11
Таблица 1. Список элементов Г и вероятности появления графа
N
Подграф
Вероятность появления
P ( gi )
g1
1
2
Существование
пути из
вершины 1 в
вершину 2
(1 − p12 ) ⋅ (1 − p13 ) ⋅ (1 − p23 )
не существует
p12 ⋅ (1 − p13 ) ⋅ (1 − p23 )
существует
(1 − p12 ) ⋅ p13 ⋅ (1 − p23 )
не существует
(1 − p12 ) ⋅ (1 − p13 ) ⋅ p23
не существует
3
g2
1
2
3
g3
1
2
3
g4
1
2
3
12
Таблица 1. Список элементов Г и вероятности появления графа
(Продолжение)
N
Подграф
Вероятность появления
P ( gi )
g5
1
2
Существование
пути из
вершины 1 в
вершину 2
p12 ⋅ p13 ⋅ (1 − p23 )
существует
p12 ⋅ (1 − p13 ) ⋅ p23
существует
(1 − p12 ) ⋅ p13 ⋅ p23
существует
p12 ⋅ p13 ⋅ p23
существует
3
g6
1
2
3
g7
1
2
3
g8
1
2
3
13
Теперь
просуммируем
вероятности,
соответствующие
элементам множества Γ′ (в которых путь из вершины 1 в вершину 2
существует), и получим окончательный ответ:
5
Pсв (1, 2 ) = ∑ P ( gi′ ) = p12 + p13 ⋅ p23 − p12 ⋅ p13 ⋅ p23 .
(1)
i =1
1.4 Способы ускорения вычисления вероятностных
характеристик случайных графов
1.4.1 Перебор по путям
Вернемся к задаче 1. Сначала рассмотрим все возможные пути
из вершины 1 в 2.
Всего их два:1→2; 1→3→2.
Вероятность существования первого пути:
Pr {∃1 → 2} =p12 ,
второго:
Pr {∃1 → 3 → 2}= p12 ⋅ p23 .
Следовательно, путь из вершины 1 в вершину 2 существует с
вероятностью:
Pсв (1, 2=
) Pr {∃1 → 2 ∪ ∃1 → 3 → 2}= p12 + p13 ⋅ p23 − p12 ⋅ p13 ⋅ p23 ,
что совпадает с формулой (1).
Перебор по путям удобно использовать, если пути независимы.
1.4.2 Декомпозиция случайного графа
Задача 2.

Пусть задан случайный граф G , изображенный на рис. 4, и
требуется определить вероятность существования пути из вершины
1 в вершину 2 Pсв (1, 2 ) .
14
Рассмотрим две ситуации. Для первой будем полагать, что
ребро 3 − 4 всегда существует. Для второй ситуации будем полагать,
что ребро 3 − 4 не существует. В этом случае можно перейти к
рассмотрению двух новых случайных графов:
3
р23
р13
Ğ
р34
1
р14
2
р24
4
Рис.4. Случайный граф для задачи 2


G1 , появление которого возможно с вероятностью Pr G1 = p34 , и
{ }


G 2 , который может появиться с вероятностью Pr G 2 = 1 − p34 , как
{ }
это показано на рис. 5.
Поскольку ребро 3 − 4 для случайного графа Ğ1 существует
всегда, то вершины 3 и 4 можно объединить в одну, как показано на

рис. 5. Для G 2 же ребро 3 − 4 просто отсутствует.
Такую процедуру получения более простых случайных графов
на основе одного сложного будем называть декомпозицией.
Для полученных с помощью декомпозиции случайных графов
определим вероятность существования пути из вершины 1 в
вершину 2.
15
Для описания вероятности события, происходящего при
некотором условии, будем использовать следующие обозначения:
Pr {описание события условие} = численное значение вероятности
Для сокращения записи обозначим:
Pr {описание события условие} = Pсв ( xa , xb условие )
3
р23
р13
1
Ğ
р34
р14
2
р24
4
р34
1-р34
3
р13
р13
1
3,4
Ğ1
р14
р23
р23
2
р24
2
Ğ2
1
р14
р24
4
Рис.5. Декомпозиция случайного графа для задачи 2
16
Применительно к рассматриваемой задаче:

Pr {путь 1, 2 ребро 3,4 существует} = Pсв 1, 2 G1 ;

Pr {путь 1, 2 ребро 3,4 не существует} = Pсв 1, 2 G 2 .
(
)
(
Тогда:

Pсв 1, 2 G1 =
(
)
)
( p13 + p14 − p13 ⋅ p14 ) ⋅ ( p23 + p24 − p23 ⋅ p24 )

Pсв 1, 2 G 2 = p13 ⋅ p23 + p14 ⋅ p24 − p13 ⋅ p23 ⋅ p14 ⋅ p24
(
)
2
р
р
р
6
Ğ
р
4
(3)
3
р
р
1
(2)
р
р
р
5
Рис.6. Случайный граф для задачи 3
Теперь, чтобы получить вероятность существования пути из

вершины 1 в вершину 2 для случайного графа G воспользуемся
формулами (2) и (3):


P
=
Pсв 1, 2 G1 ⋅ p34 + Pсв 1, 2 G 2 ⋅ (1 − p34 ) .
св (1, 2 )
(
)
(
)
(4)
Декомпозицию для новых графов можно продолжать. При
этом в узлы построенного таким образом «двоичного дерева» будут
отображаться случайные графы. Существенно то, что случайные
графы, находящиеся на нижних ярусах, будут иметь более простую
топологию по сравнению с графами на вышестоящих ярусах.
17
Основная цель процедуры декомпозиции состоит в замене
одного сложного графа на несколько простых, для которых проще
произвести расчет вероятности существования пути между
вершинами.
1.4.3 Упрощение структуры графа
Структура графа упрощается за счет того, что некоторые
фрагменты графа заменяются ребрами с соответствующим
пересчетом существования этих ребер.
Задача 3.
Пусть
есть
сеть,
заданная
случайным
графом

G,
изображенным на рис. 6, в котором вероятности существования
ребер
одинаковы и равны некоторому числу
p . Требуется
определить вероятность существования пути из вершины 2 в
вершину 4 Pсв ( 2, 4 ) .
Выполним декомпозицию по ребру 1 − 3 и рассмотрим две
ситуации (рис.7).
Шаг 1.1
В первом случае будем полагать, что ребро всегда 1 − 3

существует (граф G1 ). Тогда вершины 1 и 3 можно объединить в
одну (1,3) .
Шаг 1.2

Упростим структуру графа G1 , пересчитав вероятность
существования ребер 2 − (1,3) и (1,3) − 5 :
=
X 2 p − p2 ,
Y =p + p 2 − p 3 .
18
Шаг 1.3
Проведем дальнейшее упрощение структуры, пересчитав
вероятность существования ребра (1,3) − 4 :
Z =p + Yp − p 2Y =p + p ( p + p 2 − p 3 ) − p 2 ( p + p 2 − p 3 )
=p + p 2 − 2 p 4 + p 5 .
Применим способ перебора по путям и найдем вероятность
существования пути из вершины 2 в вершину 4 при условии, что
ребро 1 − 3 существует:

Pсв 2, 4 G1 =p + XZ − pXZ =p + ( 2 p − p 2 )( p + p 2 − 2 p 4 + p 5 ) −
(
)
− p ( 2 p − p 2 )( p + p 2 − 2 p 4 + p 5 ) =
=p + 2 p 2 − p 3 − 2 p 4 − 3 p 5 + 8 p 6 − 5 p 7 + p8 .
Шаг 2.1
Для второй ситуации будем полагать, что ребро 1 − 3 не

существует (граф G 2 ).
Шаг 2.2

Упростим структуру графа G 2 , пересчитав вероятность
существования ребра 3 − 5 :
Y =p + p 2 − p 3 .
Шаг 2.3
Проведем дальнейшее упрощение структуры, пересчитав
вероятность существования ребра 2 − 4 :
W =p + p 2Y − p 3Y =p + p 2 ( p + p 2 − p 3 ) − p 3 ( p + p 2 − p 3 ) =
=p + p 3 − 2 p 5 + p 6 .
19
2
р
р
р
1
Ğ
р
р
Шаг 1.1
3
р
р
р
4
р
6
р
5
Шаг 2.1
1-р
р
2
2
1,3
р
р
р
р
Ğ1
р
4
р
р
6
р
3
р
1
р
р
Ğ2
р
5
6
р
р
4
5
Шаг 2.2
Шаг 1.2
2
1,3
Х
2
1
Y
р
р
4
3
р
р
р
р
5
Y
р
р
4
5
Шаг 1.3
Шаг 2.3
2
2
1,3
Х
р
р
р
1
W
Z
р
4
р
4
Рис.7. Решение задачи 3
20
р
Применим способ перебора по путям и найдем вероятность
существования пути из вершины 2 в вершину 4 при условии, что
ребро 1 − 3 не существует:

Pсв 2, 4 G 2 =W + p 2 − Wp 2 =
(
)
=p + p 3 − 2 p 5 + p 6 + p 2 − p 2 ( p + p 3 − 2 p 5 + p 6 ) =
=p + p 2 − 3 p 5 + p 6 + 2 p 7 − p8 .
Теперь найдем вероятность Pсв ( 2, 4 ) для исходного графа:


P
=
Pсв 2, 4 G1 ⋅ p + Pсв 2, 4 G 2 =
⋅ (1 − p )
св ( 2, 4 )
(
)
(
)
= ( p + 2 p 2 − p3 − 2 p 4 − 3 p 5 + 8 p 6 − 5 p 7 + p8 ) p +
+ ( p + p 2 − 3 p 5 + p 6 + 2 p 7 − p8 ) (1 − p ) =
=p + p 2 + p 3 − p 4 − 5 p 5 + p 6 + 9 p 7 − 8 p8 + 2 p 9 .
В результате получили
Pсв ( 2, 4 ) =p + p 2 + p 3 − p 4 − 5 p 5 + p 6 + 9 p 7 − 8 p8 + 2 p 9 .
21
2
Использование имитационного
моделирования для оценки надежности
(на примере случайных графов)
2.1 Использование имитационного моделирования для
оценки вероятностных характеристик случайных графов
Определение Pсв ( xa , xb ) - вероятности существования пути


из вершины xa в вершину xb в случайном графе G ( X , Y , P ) ( Pсв G
( )
− вероятности связности графа) путем полного перебора всех
возможных вариантов графа фактически является универсальным
алгоритмом, позволяющим получить точное значение этой
вероятности (см. п.1.2.). С помощью него можно исследовать
надежность систем, для которых справедлива модель на основе
случайного графа. Однако, как правило, эта задача является
достаточно трудоемкой, так как ее сложность экспоненциально
зависит от числа ребер в случайном графе. По сути, необходимо
рассмотреть связность пары вершин (связность графа) для
множества Γ ={ g1 ,  , g N } всех возможных вариантов графа,

которые могут быть получены на основе G , и после этого вынести
решение о вероятности существования пути между вершинами для


самого случайного графа G (связности G ).
Временные затраты (т.е. сложность) можно уменьшить,
применив имитационное моделирование, основанное на методе
статистического моделирования, при котором многократно
повторяются эксперименты со случайным исходом и оценка
искомого результата определяется путем осреднения результатов
отдельных экспериментов [4].
22
Уменьшение временных затрат происходит за счет того, что
существование пути между парой вершин (связность графа)
рассматривается для подмножества Γ′ ∈ Γ , элементы которого
случайным образом выбираются из множества Γ (при этом
множество Γ′ может содержать несколько одинаковых элементов
Γ ). Рассмотрение элементов множества Γ′ на предмет
существования пути между парой вершин (связности графа) в
дальнейшем будем называть экспериментом.
Сформулируем теперь задачу имитационного моделирования
для определения вероятности существования пути между парой
вершин в случайном графе следующим образом.
Пусть имеется некоторая система (в данном случае

случайный граф G ( X , Y , P ) ), состояние которой описывается
из
случайным двоичным вектором Y (в данном случае длина вектора
Y соответствует множеству ребер Y = l , и нулевое значение
компоненты вектора
соответствует отсутствию ребра, а

единичное – его наличию в случайном графе G ). От значения
Y
вектора Y зависит состояние системы ξ (Y ) , которое является
двоичным значением
(в данном случае
ξ (Y )
определяет
существование пути между парой вершин xa и xb при единичном
значении и отсутствие пути при нулевом). Поскольку Y
случайным, то и значение ξ (Y )
является
также является случайной
величиной. Тогда оценка для вероятности Pсв ( xa , xb ) может быть
получена следующим образом:
23
( ( )),

∑ i =1 ξ Y
Pсв ( xa , xb ) =
N exp
N exp
i
(5)
где N exp – количество экспериментов,
( )
ξ Y ( i ) – результат i -го эксперимента:
0, с вероятностью (1 − Pсв ( xa , xb ) )
 1, с вероятностью Pсв ( xa , xb )
( )
ξ Y (i ) = 
(6)
Алгоритм моделирования (см. рис. 8) строится так, что
математическое ожидание результата одного эксперимента
совпадает с искомым результатом, т.е.
( )
M ξ Y ( i )  = Pсв ( xa , xb ) .


(7)
При этом оценка оказывается несмещенной, т.е.:

M  Pсв ( xa , xb )  = Pсв ( xa , xb ) .
Хотя в среднем оценка совпадает с Pсв ( xa , xb ) , в каждом
конкретном случае она отличается от Pсв ( xa , xb ) на случайную
величину, средний квадрат которой представляет собой дисперсию
оценки. Чем больше дисперсия, тем больше случайные отклонения
оценки от искомого результата, т.е. меньше ее точность. С
увеличением
числа
экспериментов
дисперсия
N exp
оценки
уменьшается, а точность, соответственно растет. Поскольку оценка
является случайной величиной, точность ее рассматривается
применительно ко всему множеству возможных значений оценки с
учетом вероятностей этих значений. Требования к точности обычно
формулируются в виде вероятностного утверждения (см. рис. 9):

(8)
Pr Pсв ( xa , xb ) − Pсв ( xa , xb ) ≤ ε =
Pconf ,
{
24
}
где ε – допустимая погрешность, Pconf – заданный коэффициент
доверия.
Начало
i=1; S=0
нет
i<Nexp
да
Генерация случайного вектора
Ӯ(i)(Y1,…,Yl):
1,
с вероятностью р
Yk=
0, с вероятностью 1-р
{
l
W(Ӯ(i))=∑Yk
k=1
Построение подграфа Ğ
с числом ребер, равным W(Ӯ(i))
Вычисление ξ(Ӯ(i)):
ξ(Ӯ(i))=
x и x связны
{1,0,если
если x и x несвязны
a
b
a
b
S=S+ξ(Ӯ(i))
i++
Рˆсв(xa,xb)=S/Nexp
Конец
Рис. 8. Алгоритм имитационного моделирования
25
Рсв(xa,xb)
Рˆ св(xa,xb)
ε
X
2ε
Рис. 9. Точность имитационного моделирования
Определим количество экспериментов N exp , обеспечивающее
заданную точность оценки вероятности существования пути между
парой вершин. Для этого вычислим дисперсию получаемой в ходе
имитационного моделирования оценки.
Поскольку результаты экспериментов независимы, то
 Nexp

ξ Y (i ) 

∑

1
 i =1

 Pсв ( xa , x b )  D=
D=
2
 N exp  N exp




( )
∑ D ξ (Y ( ) ).
N exp
(9)
i
i =1
Из свойств дисперсии [5] следует:
( )
( )
( )
D ξ Y ( i )  M ξ 2 Y ( i )  − M 2 ξ Y ( i )  .
=






( )
(10)
( )
M ξ Y ( i )  и D ξ Y ( i )  для всех экспериментов одинаковы,




поэтому далее индекс i будем опускать.
Найдем M ξ (Y )  , подтвердив формулу (7). Воспользуемся
определением математического ожидания случайной дискретной
величины [5] и формулой (6):
{
}
{
}
M ξ (Y )  =
0 ⋅ Pr ξ (Y ) =
0 + 1 ⋅ Pr ξ (Y ) =
1 =
= 0 ⋅ (1 − Pсв ( xa , xb ) ) + 1 ⋅ Pсв ( xa , xb ) = Pсв ( xa , xb ) .
26
Определим M ξ 2 (Y )  :
{
}
{
}
M ξ 2 (Y )  =
02 ⋅ Pr ξ (Y ) =
0 + 12 ⋅ Pr ξ (Y ) =
1 =
= 02 ⋅ (1 − Pсв ( xa , xb ) ) + 12 ⋅ Pсв ( xa , xb ) = Pсв ( xa , xb ) .
По формуле (10) получим:
D ξ (Y )  = Pсв ( xa , xb ) − Pсв2 ( xa , xb ) = Pсв ( xa , xb ) (1 − Pсв ( xa , xb ) ) .
(11)
Пользуясь результатами формул (9) и (11) получаем
следующее равенство:
N
N exp ⋅ D ξ (Y ) 

1 exp


D  Pсв ( xa , xb ) 
D ξ (Y )  =
=
=
2 ∑
2
N exp i =1
N exp
=
Pсв ( xa , xb ) (1 − Pсв ( xa , xb ) )
N exp
(12)
.
Теперь воспользуемся центральной предельной теоремой и
правилом «трех сигма» [5]. Согласно центральной предельной
теореме, сумма n независимых случайных величин, распределенных
по произвольному закону, при больших значениях n является
случайной величиной, распределенной по нормальному закону.
Из правила «трех сигма», справедливого для случайных
величин, распределенных по нормальному закону, следует, что

Pr Pсв ( xa , xb ) − Pсв ( xa , xb ) ≤ 3 ⋅ σ ≈ 0,9973,
{
}
где σ – среднеквадратичное отклонение

σ = D  Pсв ( xa , xb )  .
Отсюда
Pconf ≈ 0,9973,
27
Pсв ( xa , xb ) (1 − Pсв ( xa , xb ) )
ε =3 ⋅ σ =3 ⋅
N exp
(13)
.
Воспользовавшись равенством (13), получим формулу для
числа экспериментов:
N exp = 9 ⋅
Pсв ( xa , xb ) (1 − Pсв ( xa , xb ) )
ε2
.
(14)
В формуле (14) вероятность Pсв ( xa , xb ) является неизвестной
величиной. Построим верхнюю оценку для Pсв ( xa , xb ) − Pсв2 ( xa , xb ) .
Решением этой оптимизационной задачи является Pсв ( xa , xb ) = 0,5
(см. рис. 10).
0,3
Рсв(xa,xb)-Рсв2 (xa,xb)
0,25
0,2
0,15
0,1
0,05
0
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
Рсв(xa,xb)
Рис. 10. Решение оптимизационной задачи
Таким образом, получаем окончательную формулу для числа
экспериментов:
N exp =
Следовательно,
для
2, 25
ε2
.
получения
(15)
оценки
вероятности
существования пути между вершинами xa и xb с допустимой
28
погрешностью
ε = 10−4
необходимо
провести
N=
2, 25 ⋅ 108
exp
экспериментов.
Заметим, что, если известна верхняя оценка вероятности
существования пути между вершинами xa и xb Pсв ( xa , xb ) < P + < 0,5
(см. рис. 11), то в формулу (14) можно подставить значение p + :
N exp = 9 ⋅
p + (1 − p + )
ε2
.
0,3
Рсв(xa,xb)-Рсв2 (xa,xb)
0,25
0,2
0,15
0,1
0,05
0
0
0,1
+
0,2р 0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
Рсв(xa,xb)
Рис. 11. Решение оптимизационной задачи при известной
верхней оценке p +
Аналогично можно поступить, если известна нижняя оценка
вероятности существования пути между вершинами xa и xb
Pсв ( xa , xb ) > P − > 0,5 (см. рис. 12). В данном случае в формулу (14)
можно подставить значение p − :
N exp = 9 ⋅
p − (1 − p − )
ε2
.
29
0,3
Рсв(xa,xb)-Рсв2 (xa,xb)
0,25
0,2
0,15
0,1
0,05
0
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
р- 0,9
1
Рсв(xa,xb)
Рис. 12. Решение оптимизационной задачи при известной
нижней оценке p −
2.2 Методы ускорения моделирования
Способ имитационного моделирования, описанный в
предыдущем
разделе,
имеет
существенный
недостаток.
Предположим, что имеется высоконадежная система, заданная

случайным графом G ( X , Y , P ) , в котором ребра отсутствуют с очень
маленькой вероятностью 1 − p < 10−10 и необходимо определить
вероятность отсутствия пути между смежными вершинами xa и xb
(1 − P ( x , x
св
a
b
xa , xb смежные )
)
с
допустимой
погрешностью 0,1% . Тогда
0,1
= 10−13 ,
100
p − = 1 − 10−10 ,
ε = 10−10 ⋅
30
относительной
N exp
(
)
1 − 10−10 ) ⋅ 1 − (1 − 10−10 )
p − (1 − p − )
(
9⋅
9⋅
=
=
≈
2
ε2
(10−13 )
≈ 9⋅
1 ⋅ (1 − 1 + 10−10 )
10
−26
= 9⋅
10−10
= 9 ⋅ 1016.
−26
10
Если один эксперимент будет длиться 1мкс, то потребуется
примерно три тысячи лет для проведения моделирования. Поэтому,
чтобы избежать больших временных затрат, применяют методы
ускорения имитационного моделирования.
Все методы ускорения имитационного моделирования можно
разбить на два класса:
1. Снижение временных затрат на проведение некоторых
экспериментов.
2. Уменьшение дисперсии оценки и, как следствие,
уменьшение числа экспериментов при сохранении точности оценки.
2.2.1 Снижение временных затрат на проведение некоторых
экспериментов
Во множестве Γ всевозможных графов, которые можно

получить на основе случайного графа G , есть два подмножества. В
первое множество входят подграфы, для которых достоверно
известно, что путь между рассматриваемой парой вершин в них не
существует (подграфы несвязны). Второе множество составляют
подграфы, для которых также достоверно известно, что путь между
рассматриваемой парой вершин в них существует (подграфы
связны). Наиболее простым способом ускорения моделирования
является исключение процедуры вычисления связности для таких
подграфов.
31
Установим значения lmin и lmax со следующими свойствами:

1)
для любых подграфов G с числом ребер l < lmin ,
достоверно известно, что путь между рассматриваемой парой
вершин в них не существует (подграфы несвязны);

2)
для любых подграфов G с числом ребер l > lmax ,
достоверно известно, что путь между рассматриваемой парой
вершин в них существует (подграфы связны).
Из приведенных выше определений lmin и lmax следует, что
при определении вероятности существования пути между парой
вершин:
−
lmin
совпадает
с
длиной
кратчайшего
пути
между
рассматриваемой парой вершин (см. п.1.1.),
−
lmax= Y − Y ( xa , xb ) ,
где
Y ( xa , xb )
−
минимальное
количество рёбер, при удалении которых пути между
заданной парой вершин нет;
при определении вероятности связности графа:

− lmin= n − 1 , где n – число вершин графа G ,
−
lmax= Y − K , где K – коцикл (см. п. 1.1.).
Например, для графа на рис. 6 (см. п.1.3.3.):
при определении вероятности существования
пути
между
вершинами 2 и 4 Pсв ( 2, 4 ) Рсв(2,4):
−
lmin = 1 (т.к. кратчайший путь из вершины 2 в вершину 4 одно
ребро 2 − 4 ),
−
lmax = 9 − 3 = 6 (т.к. при удалении трех ребер 2 − 1 , 2 − 4 , 2 − 3
или трех ребер 4 − 1 , 4 − 2 , 4 − 5 пути между вершинами 2 и
4 нет, Y ( xa , xb ) = 3 ),
32
при
определении
вероятности
существования
пути
между
вершинами 2 и 6 Pсв ( 2,6 ) :
−
lmin = 2 (т.к. кратчайший путь из вершины 2 в вершину 6 два
ребра 2 − 3 , 3 − 6 ),
−
lmax = 9 − 2 = 6 (т.к. при удалении двух ребер 6 − 3 , 6 − 5 или
трех ребер 2 − 1 , 2 − 4 , 2 − 3 пути между вершинами 2 и 6
нет, Y ( xa , xb ) = 2 .

при определении вероятности связности графа Pсв G :
( )
−
lmin = 6 − 1 = 5 (т.к. в графе шесть вершин),
−
lmax = 9 − 2 = 7 (т.к. при удалении двух ребер 6 − 3 , 6 − 5 граф
перестает быть связным, K = 2 ).
Снижение временных затрат на проведение некоторых
экспериментов при имитационном моделировании возможно, если
до проведения экспериментов проанализировать структуру графа и
определить lmin и lmax . Общий алгоритм моделирования в этом
случае представлен на рис. 13.
33
Начало
i=1; S=0
нет
i<Nexp
да
Генерация случайного вектора
Ӯ(i)(Y1,…,Yl):
l
W(Ӯ(i))=∑Yk
k=1
да
нет
W(Ӯ(i))<lmin
нет
Построение подграфа Ğ
с числом ребер, равным W(Ӯ(i))
ξ(Ӯ(i))=0
Вычисление ξ(Ӯ(i))
W(Ӯ(i))>lmax
да
ξ(Ӯ(i))=1
S=S+ξ(Ӯ(i))
i++
Рˆсв(xa,xb)=S/Nexp
Конец
Рис. 13. Снижение временных затрат на проведение
некоторых экспериментов
34
Покажем, как можно количественно оценить выигрыш от
данного метода ускорения. При этом ограничимся случаем, когда
вероятность существования всех ребер одинакова и равна p .
В алгоритме на рис. 13 случайный вектор Y (i ) генерируется
N exp раз. Однако процедуры построения подграфа и вычисления
связности вершин в подграфе повторяются N ′ раз. Таким образом,
поскольку временные затраты на генерацию вектора по сравнению с
временными затратами на процедуры построения подграфа и
вычисления связности вершин в подграфе пренебрежительно малы,
то время моделирования по сравнению с алгоритмом на рис. 8
сократится в N exp N ′ раз.
N ′ − случайная величина, следовательно, при большом
количестве экспериментов
N ′ = M [ N ′]
и выигрыш равен
N exp
M [ N ′]
.
Для вычисления математического ожидания M [ N ′] введем в
( )
рассмотрение функционал φ Y (i ) :
( )
φ Y
(i )
( )
1, если w Y (i ) ∈ [ lmin , lmax ]
=
0, если иначе

N exp
( )
N ′ = ∑φ Y ( )
i =1
i
35
( )
N exp
( )
M [ N ′] =
M φ Y (i )  =
N exp ⋅ M φ Y (i )  =
∑




i =1
{
( ) }
N ⋅ ∑ Pr {w (Y ( ) ) =
=
1} =
N ⋅ Pr lmin ≤ w Y (i ) ≤ lmax =
=
lmax
i
exp
lmin
lmax
N exp ∑ Cli p i (1 − p )
=⋅
l −i
lmin
Cli – число способов выбрать i единиц на длине l , (1 − p )
l −i
–
вероятность того, что на остальных позициях будет 0.
Выигрыш:
N exp
=
N′
1
lmax
∑ C p (1 − p )
i
l
i
l −i
.
(16)
lmin
Моделирование было ускорено именно за счет того, что до
моделирования была проанализирована структура графа и
определены значения lmin и lmax .
Из формулы (16) следует, что выигрыш при вероятностях
существования ребер p = 0 и p = 1 равен бесконечности. Это
объясняется тем, что при l < lmin и l > lmax процедуры построения
подграфа и вычисления связности вершин в подграфе не
выполняются.
Рассмотренный подход к ускорению имитационного
моделирования может быть использован не только при оценке
вероятностных характеристик случайных графов, но и при
моделировании других систем, в частности при моделировании
системы, в которой используется помехоустойчивое кодирование, в
36
ряде случаев можно исключить этап работы декодера за счет
привлечения информации о lmin .
2.2.2 Уменьшение дисперсии оценки. Метод расслоенной
выборки
Предыдущий способ ускорения моделирования заключался не
в уменьшении количества экспериментов, а в уменьшении
трудоемкости тех экспериментов, результат которых заранее
известен. Основной причиной для увеличения числа опытов является
большая дисперсия получаемой оценки. Рассматриваемый далее
метод ускорения заключается в том, что оценка строится таким
образом, что дисперсия оценки понижается и ту же самую точность
можно обеспечить за счет меньшего числа экспериментов (или при
фиксированном числе экспериментов увеличить точность оценки).
Метод носит название «метод расслоенной выборки» [6].
Рассмотрим его применительно к задаче нахождения вероятности
существования пути между заданной парой вершин в случайном
графе.

Пусть задан случайный граф G ( X , Y , P ) и требуется
определить Pсв ( xa , xb ) вероятность связности двух вершин xa и xb .
Для упрощения изложения будем полагать, что вероятность
существования всех ребер одинакова и равна p .
Пусть также Y − число ребер в случайном графе равно l .
Разобьем общее число экспериментов N exp на l групп ( l слоев) и в
каждой группе будем проводить по N j экспериментов так, чтобы
выполнялось условие:
37
l
∑N
j =1
j
= N exp .
Будем полагать, что в j -ой группе в ходе эксперимента в
случайном графе будет присутствовать ровно j ребер. Обозначим
Pr {путь xa , xb j ребер} = Pсв ( xa , xb j ) .
Для каждой группы получим свою оценку вероятности
связности двух вершин:
∑ ξ (Y ( ) )
Nj
i

Pсв ( xa , xb j ) =
Нижний индекс
( j)
j
i =1
Nj
.
(17)
говорит о том, что случайный вектор Y j
содержит ровно j единиц.
Покажем теперь, как можно найти оценку вероятности
связности вершин, используя оценки для каждой из групп.
Пусть Π j − вероятность того, что в графе будет ровно j ребер.
Если вероятность существования любого ребра равна p , то
=
Π j Cl j p j (1 − p )
l− j
.
Тогда вероятность связности двух вершин может быть
вычислена по следующей формуле:

=
Pсв ( xa , xb )
l

∑P (x , x j)⋅ Π .
j =1
св
a
b
j
(18)
Здесь индекс ( j ) указывает на то, что рассматриваются графы
в которых присутствуют ровно j ребер.
38
На основе формул (17) и (18) можно получить конечный
результат для оценки вероятности связности двух вершин.
Алгоритм моделирования в j -ом слое представлен на
рис. 14.
Теперь осталось определить неизвестные значения N j . Для
этого сформулируем следующую оптимизационную задачу.
Пусть общее число экспериментов
N exp
зафиксировано.
Требуется задать множество {N1 , N 2 ,, N l } таким образом, чтобы
дисперсия оценки была минимальной.

 D  Pсв ( xa , xb ) → min



l

N j N=
const
 ∑=
exp
 j =1

1, l
N j ≥ 0, j =

Целевая функция будет выглядеть следующим образом:

 l 

D  Pсв ( xa , xb ) D  ∑ P=
=
св ( xa , xb j ) ⋅ Π j 
 j =1

l

= ∑ D  Pсв ( xa , xb j ) ⋅ Π 2j .
(19)
j =1
Применив к (19) формулу (12) получим

D  Pсв ( xa , xb )=
l
∑Π
j =1
2
j
⋅
(
Pсв ( xa , xb j ) 1 − Pсв ( xa , xb j )
Nj
)=
(20)
= f ( N 1 , N 2 ,, N l ) .
39
Начало
i=1; Sj=0
нет
i<Nj
да
Генерация случайного вектора Ӯj(i),
в котором j единиц расположены
случайным образом
W(Ӯj(i))=j
Построение подграфа Ğ
с числом ребер, равным W(Ӯj(i))
Вычисление ξ(Ӯj(i)):
1, если xa и xb связны
0, если xa и xb несвязны
ξ(Ӯj(i))=
{
Sj=Sj+ξ(Ӯj(i))
i++
Рˆ св(xa,xb|j)=Sj/Nj
Конец
Рис. 14. Алгоритм имитационного моделирования в j-ом слое
40
Описанная выше оптимизационная задача обладает
следующими свойствами:
1. Нелинейная задача, так как целевая функция нелинейная.
2. Имеется одно ограничение типа равенства
l
∑N
j =1
j
− N exp =
0.
3. Имеется l ограничений типа неравенств
1, l.
N j ≥ 0, j =
4. Задача дискретная, поскольку N j являются дискретными
величинами.
Однако, учитывая специфику задачи ( N exp – большое число), можно
рассматривать задачу, как непрерывную и полученное решение
округлять до ближайшего целого значения. Ограничения типа
неравенств можно временно исключить из рассмотрения. Тогда для
ее решения можно применить метод неопределенных множителей
Лагранжа [7] и полученное этим методом решение проверить на
выполнение ограничений типа неравенств. Для этого введем в
рассмотрение следующую функцию:

l


j =1

ϕ ( N1 , N 2 ,,=
N l , λ ) f ( N1 , N 2 ,, N l ) + λ  ∑ N j − N exp  ,
Где λ – неопределенный множитель Лагранжа.
Возьмем частную производную по
j -ой переменной и
приравняем ее к нулю.
d (ϕ )
d (N j )
(
)
Π 2j Pсв ( xa , xb j ) 1 − Pсв ( xa , xb j )
=
+ λ ⋅ 1 0.
N 2j
41
Отсюда
Nj =
(
Π j ⋅ Pсв ( xa , xb j ) 1 − Pсв ( xa , xb j )
λ
).
Далее с учетом ограничения находим значение неопределенного
множителя λ :
l
l
∑N
j =1
j
= N exp ⇒ λ =
∑Π
j =1
j
(
⋅ Pсв ( xa , xb j ) 1 − Pсв ( xa , xb j )
)
N exp
.
Таким образом, находим неизвестные N j :
=
N j N exp ⋅
(
Π j ⋅ Pсв ( xa , xb j ) 1 − Pсв ( xa , xb j )
l
(
)
∑ Π k ⋅ Pсв ( xa , xb k ) 1 − Pсв ( xa , xb k )
k =1
)
.
(21)
Из полученного выражения (21) следует, что N j ≥ 0 , т.е.
ограничения типа неравенств выполняются.
В формулу (21) для выбора оптимальных значений N j
входят значения Pсв ( xa , xb j ) , которые в общем случае неизвестны и
их оценки будут получены только в результате эксперимента.
Так как заранее известно, что
0, если j < lmin
Pсв ( xa , xb j ) = 
,
1, если j > lmax
то N j = 0 , для j < lmin или j > lmax .
Для определения подоптимальных значений N j зададим
неизвестные значения Pсв ( xa , xb j ) равными 0,5 (верхняя оценка).
42
Тогда
(22)
N j =Π j ⋅ N exp .
Вычисленные
по
формуле
(22)
значения
Nj
будут
неоптимальными (т.е. дисперсия оценок при использовании таких
значений будет больше, чем для случая известных Pсв ( xa , xb j ) .
Однако такой подход не требует знания Pсв ( xa , xb j ) .
Подведем общий итог рассмотрения метода расслоенной
выборки применительно к задаче нахождения вероятности
существования пути между парой вершин в случайном графе.
Обозначим дисперсию оценки вероятности существования
пути между парой вершин в случайном графе, полученную
неускоренным методом моделирования, за D1 . Дисперсию оценки,
полученную по методу расслоенной выборки при подоптимальных
значениях элементов множества {N1 , N 2 ,, N l } , обозначим за D2 .
Путем подстановки значений
получить
оптимальные
{N 1 , N 2 ,, N l } .
Pсв ( xa , xb j ) в формулу (21) можно
значения
элементов
множества
Обозначим дисперсию оценки, полученной путем
моделирования с оптимальными параметрами, за D3 . Можно
доказать, что D1 > D2 > D3 (в данной работе доказательство не
приводится).
Таким образом, рассмотренный метод расслоенной выборки
позволяет при том же числе экспериментов получить оценку с
большей точностью даже при отсутствии дополнительной
информации (о lmin и lmax ).
43
Заключение
В учебном пособии был рассмотрен метод оценки надежности
вычислительных сетей и других технических систем с
использованием случайных графов. Были описаны два подхода –
численный расчет и имитационное моделирование. Для численного
расчета был описан переборный алгоритм и ряд достаточно простых
способов сокращения перебора. Для дальнейшего самостоятельного
изучения могут быть рекомендованы работы, в которых
предлагаются способы численного расчета с использование так
называемых двоичных решающих диаграмм [8], которые позволяют
в ряде случаев уменьшить число операций при вычислении
вероятностных характеристик случайных графов. При рассмотрении
имитационного моделирования были рассмотрены два способа
ускорения моделирования. Для самостоятельного изучения может
быть рекомендована книга [9], в которой рассмотрены и другие
способы ускорения имитационного моделирования.
44
Литература
1. Строгонов А.В., Жаднов В.В., Полесский С.Н. Обзор
программных комплексов по расчету надежности сложных
технических систем // Компоненты и технологии. — 2007. —
№ 5. — С. 183-190.
2. Харари Ф. Теория графов / Пер.с англ. и предисл. В. П.
Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал
УРСС, 2003. - 296 с.
3. Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С.
336.
4. Математические схемы и алгоритмы моделирования
инфокоммуникационных систем: учеб. пособие / Кутузов
О.И., Татарникова Т.М. СПб.: ГУАП, 2013. – 148 с.
5. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее
инженерные приложения. Учеб. пособие для вузов.— 2-е
изд., стер.— М.: Высш. шк., 2000.
6. Шеннон Р. Имитационное моделирование систем - искусство
и наука. М.: Мир, 1978. - 424с.
7. Ильин В. А., Позняк Э. Г. Основы математического анализа:
в 2-х ч. (Курс высшей математики и математической физики).
Часть I: 7-е изд. — М.: Физматлит, 2005. — 648 с.
8. Randal E. Bryant. Graph-Based Algorithms for Boolean Function
Manipulation (1986), IEEE Transactions on Computers Vol. 35
pp 677–691, 1986.
9. Xinyu Zang, Hairong Sun, Kishor S. Trivedi. A BDD-Based
Algorithm for Reliability Graph Analysis, 2000.
45
Учебное издание
Гильмутдинов Марат Равилевич
Марковская Наталья Владимировна
Тюрликов Андрей Михайлович
ИСПОЛЬЗОВАНИЕ СЛУЧАЙНЫХ ГРАФОВ
ДЛЯ ОЦЕНКИ НАДЕЖНОСТИ
ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
Учебное пособие
Публикуется в авторской редакции.
Отпечатано с оригинал-макета автора
Подписано в печать 12.12.2014. Формат бумаги 60×841/16.
Бумага офсетная. Усл. печ. л. 2,73. Тираж 100 экз. Заказ № 653.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
ДЛЯ ЗАМЕТОК
ДЛЯ ЗАМЕТОК
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 514 Кб
Теги
gilmytdinov
1/--страниц
Пожаловаться на содержимое документа