Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Сетевой метод

Читайте также:
  1. I. 2.3. Табличный симплекс-метод.
  2. I. 3.2. Двойственный симплекс-метод.
  3. I. Передача параметров запроса методом GET.
  4. II. Методика работы
  5. II. Методика работы.
  6. II. Методика работы.
  7. II. Методика работы.

Чтобы рассчитать сетевым методом основные параметры алгоритма, необходимо на укрупненной ГСА выделить циклы. Для исходного алгоритма, взятого в примере, выделяются три цикла (рис. 1.8).

 
 

Сначала рассчитывают вложенные циклы, поэтому рассмотрим первый цикл - цикл С1 (см. рис. 1.9).

Определим вероятность выхода из цикла Рвых и вероятность зацикливания Рц. Вероятность выхода из цикла будет равна сумме всех выходов (т.к. выход не единственный).

Рвых=0,48+0,02+0,5´0,17=0,585 Þ Рц=1 - Рвых=0,415.

Таким образом, среднее число повторений цикла С1 равняется

nC1=1/Pвых=1,71.

 

Найдем трудоемкость тела цикла: qtC1=åniqVi, где значение qVi - это трудоемкость вершины Vai, соответствующей оператору счета, входящей в i-ю операторную вершину укрупненной ГСА.

n4=1 qV4=50

n6=0,5 qV6=60 => qtC1=50+30+12,45=92,45 операций

n5=0,83* n6=0,415 qV5=30

Таким образом средняя трудоемкость цикла С1 равна

qC1= qtC1´nC1=158,09 операций.

 
 

Для определения минимальной и максимальной трудоемкости цикла С1 необходимо определить минимальный и максимальный пути прохождения по циклу.

Максимальная qmaxС1 и минимальная qminС1 трудоемкость цикла определяется как сумма трудоемкостей всех вершин, составляющих соответственно максимальный и минимальный пути цикла, умноженной на среднее число повторений цикла nC1

qminС1=50´1,71=85,5 операций;

qmaxС1=(50+60+30+50+60) ´1,71=427,5 операций.

 

Цикл С2. После расчета вложенных циклов они представляются на графе других циклов в виде вершины, в данном случае цикл С1 представляется вершиной С1 (рис. 1.10).

В цикле С2 кроме вероятности выхода из цикла необходимо определить вероятности выхода из цикла С1. Так как сумма вероятностей выходов из С1 равна 1, то, например, рC1 8=0,48/(0,17+0,02+0,48)=0,72. Аналогично определяются и остальные вероятности.

Рвых=0,4+0,6´(0,25+0,03)+0,6´0,72´0,02=0,577;

Рц=0,423;

Среднее число повторений цикла С2 равняется

nC2=1/Pвых=1,73.

Трудоемкость тела цикла определяется как

n2=1 qV2=0

nC1=0,6 qVC1=158,09 => qtC2=181,254 операций,

n8=0,72´ nC1=0,432 qV8=200

n9=0,98´ n8=0,423 qV9=0

а средняя трудоемкость цикла С2 равна

 
 

qC2= qtC2´ nC2=313,57 операций.

Минимальный путь для цикла С2 будет состоять из одной вершины.

Так как в вершине А2 отсутствует оператор счета, то минимальная трудоемкость цикла С2 равно нулю qminС2=0 операций.

Максимальный путь равен полному прохождению цикла, и максимальная трудоемкость цикла С2 равна

qmaxС2=(0+427,5+200+0+0+427,5+200) ´1,73=2171,15 операций.

Цикл С3. Для цикла С3 (рис. 1.11), как и для цикла С2, нужно рассчитать вероятности выхода из цикла С2. Рассуждения аналогичные, но вероятности берутся те, которые уже рассчитывали для С2.

Например: рC2 10=(0,02+0,25)/(0,4+0,03+0,25+0,02)=0,39

Рвых=0,07;

Рц=0,93;

nC3=14,29.

Трудоемкость тела цикла равна

n1=1 qV1=10

nC2=1 qVC2=313,57

n3=0,57´ nC2=0,57 qV3=100 => qtC3=417,17 операций;

n7=0,04´ nC2=0,04 qV7=40

n10= n3+n7+0,39´ nC2=1 qV10=35

а средняя трудоемкость цикла С3 и всего алгоритма определяется как

qC3= qср= qtC3´ nC3= 5961,36 операций.

Для цикла С3 характерно ветвление алгоритма - в вершину А10 идут три дуги. Чтобы рассчитать минимальную и максимальную трудоемкости этого цикла, необходимо вычислить минимальные и максимальные пути соответственно.

Расчет минимальной трудоемкости.

qmin0=0

qmin1=10

qminС2=0+10=10

qmin3=100+10=110

qmin7=40+10=50

qmin10=35+min(qmin3,qminC2,qmin7)=45

qmink=qmin=45´14,29=643,05 операций.

Расчет максимальной трудоемкости.

qmax0=0

qmax1=10

qmaxС2=2171,15+10=2181,15

qmax3=100+2181,15=2281,15

qmax7=40+2181,15=2221,15

qmax10=35+max(qmax3,qmaxC2,qmax7)=35+2281,15=2316,15

qmaxк=qmax=2316,15´14,29=33097,78 операций.

 

Таким образом, полученные значения трудоемкостей для цикла С3 и определяют минимальную, среднюю и максимальную трудоемкости всего алгоритма, рассчитанные сетевым методом:

qmin =643,05 операций;

qср =5961,36 операций;

qmax =33097,78 операций.


Дата добавления: 2015-10-31; просмотров: 78 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Марковский метод| Теоретичні відомості

mybiblioteka.su - 2015-2024 год. (0.01 сек.)