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

Марковский метод

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

Пример расчета основных параметров

¨
реализации алгоритмов на ЭВМ

Рассчитаем основные параметры реализации на ЭВМ алгоритма двумя методами: сетевым и марковским. Граф-схема исходного алгоритма представлена на рис. 1.6, где V0 и Vk обозначают соответственно начальную и конечную вершины графа, Vai - вершины, соответствующие операторам счета, а Vjbi - вершины, соответствующие операторам обращения к файлам ().

Пусть операторы счета Vai, число которых равно m0 =8 (), характеризуются следующими показателями количества операций qVi:

 

Vai                
qVi,опер                

Операторы обращения к файлам Vjbi (где j - номер файла, к которому осуществляется обращение) задаются средним количеством информации li, передаваемой при выполнении данного оператора:

Vjbi                
li, байт                

Число операторов ввода-вывода при обращении к каждому из трех файлов (F =3) для данного алгоритма равно: m1 =3 (вершины V1b1, V1b2, V1b7); m2 =3 (вершины V2b3, V2b6, V2b8); m3 =2 (вершины V3b4, V3b5).

Области изменения параметров ветвления алгоритма Xi примем следующие:

X1=(-2;2); X2=(-3;4); X3=(1;6);

а области изменения параметров циклов (максимальное значение счетчиков Ii) Ki примем равными

К1=25, К2=50, К3=15.

При этом счетчики циклов Ii в начале реализации алгоритма устанавливаются в единицу, т.е. I1= I2= I3=1.

Марковский метод

Чтобы уменьшить размерность системы линейных уравнений для определения вероятности выполнения операторов, осуществим объединение последовательных операторов алгоритма. В результате такого преобразования образуется укрупненная граф-схема алгоритма. В один общий оператор могут входить только те вершины ГСА, которые при любых условиях выполнения алгоритма реализуются последовательно. На рис. 1.7 представлена укрупненная ГСА исходного алгоритма, на которой через Аi обозначены операторные вершины.

В операторные вершины укрупненной ГСА вошли следующие вершины, соответствующие операторам счета и операторам обращения к файлам исходного алгоритма:

А0 =(V0) A1 =(Va1) A2 =(V1b1)

A3 =(Va2, V1b2) A4 =(Va3, V2b3) A5 =(Va4)

A6 =(Va5, V3b4) A7 =(Va6, V3b5) A8 =(Va7, V2b6)

A9 =(V1b7) A10 =(Va8, V2b8)

По параметрам Ii и Xi определим вероятности переходов из одного оператора в другой.

Параметр Х1 изменяется в пределах от -2 до +2. Переход из вершины А2 в А3 произойдет при значениях Х1 больших нуля (с вероятностью 2/5=0,4), а в вершину А4 - при значениях Х1 меньших или равных нулю (с вероятностью 3/5=0,6). Аналогично определяются вероятности перехода из вершины А6 в А5 (p65=0,83) и А10 (p6 10=0,17).

 
 

Из вершины А4 осуществляется переход сразу в три вершины А6, А7 и А8. Согласно параметру Х3=(1;6), вероятность перехода из А4 в А6 равна 0,5. Следовательно с вероятностью 0,5 осуществится переход либо в вершину А7, либо А8. Исходя из заданного условия I1<K1 и параметра K1=25, цикл должен выполнятся 24 раза. Следовательно, в 24/25 (0,96) случаях осуществиться переход в вершину А8, а в 1/25 (0,04) случаях - в вершину А7. Таким образом, p47=0,5´0,04=0,02 и p48=0,5´0,96=0,48.

Остальные полученные вероятности переходов следующие: p8 10=0,02, p89=0,98, p10 1=0,93, p10 k=0,07.

Используя рассчитанные вероятности переходов, составим таблицу вероятности переходов.

Таблица 1.4

Таблица вероятностей переходов

  А1 А2 А3 А4 А5 А6 А7 А8 А9 А10 Ак
А1 -----   ----- ----- ----- ----- ----- ----- ----- ----- -----
А2 ----- ----- 0,4 0,6 ----- ----- ----- ----- ----- ----- -----
А3 ----- ----- ----- ----- ----- ----- ----- ----- -----   -----
А4 ----- ----- ----- ----- ----- 0,5 0,02 0,48 ----- ----- -----
А5 ----- ----- -----   ----- ----- ----- ----- ----- ----- -----
А6 ----- ----- ----- ----- 0,83 ----- ----- ----- ----- 0,17 -----
А7 ----- ----- ----- ----- ----- ----- ----- ----- -----   -----
А8 ----- ----- ----- ----- ----- ----- ----- ----- 0,98 0,02 -----
А9 -----   ----- ----- ----- ----- ----- ----- ----- ----- -----
А10 0,93 ----- ----- ----- ----- ----- ----- ----- ----- ----- 0,07

Для определения трудоемкости алгоритма и средней трудоемкости этапа счета рассчитаем среднее число пребывания марковского процесса в невозвратных состояниях, решая систему линейных уравнений. Система уравнений строится по столбцам таблицы вероятности переходов.

0,93n10 - n1= -1 n1=14,3

n1 + n9 - n2=0 n2=27,64

0,4n2 - n3=0 n3=11,056

0,6n2 + n5 - n4=0 n4=28,35

Þ
0,83n6 - n5=0 n5=11,765

0,5n4 - n6=0 n6=14,175

0,02n4 - n7=0 n7=0,567

0,48n4 - n8=0 n8=13,608

0,98n8 - n9=0 n9=13,336

n3 + 0,17n6 + n7 + 0,02n8 - n10=0 n10=14,304

Среднее число процессорных операций при одном прогоне алгоритма равно , где S0 – множество вершин Vai.

Аi Vai qVi, опер ni qVi*ni, опер
      14,3  
      11,056 1105,6
      28,35 1417,5
      11,765 352,95
      14,175 850,5
      0,567 22,68
      13,608 2721,6
      14,304 500,64

q=7114,47 операций

Среднее число обращений к файлам равно:

G1=n2+n3+n9=52,032;

G2=n4+n8+n10=56,262;

G3=n6+n7=14,742.

Среднее количество информации, передаваемое при одном обращении к файлам, рассчитывается так:

L1=(n2l1+n3l2+n9l7)/G1=686,854 байт;

L2=(n4l3+n8l6+n10l8)/G2=648,694 байт;

L3=(n6l4+n7l5)/G3=965,385 байт.

Средняя трудоемкость этапа счета qa определяется следующим образом:

N=n1+ n3+ n4+ n5+ n6+ n7+ n8+ n10=108,125;

qa=q/N=7114,47/108,125=65,7986 операций.

 


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


<== предыдущая страница | следующая страница ==>
Пути решения проблемы информатизации общества| Сетевой метод

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