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

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

¨

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

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

Пусть операторы счета V_ai, число которых равно m₀ =8 (), характеризуются следующими показателями количества операций q^V_i:

Vai
q^Vi,опер

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

V^jbi
li, байт

Число операторов ввода-вывода при обращении к каждому из трех файлов (F =3) для данного алгоритма равно: m₁ =3 (вершины V¹_b1, V¹_b2, V¹_b7); m₂ =3 (вершины V²_b3, V²_b6, V²_b8); m₃ =2 (вершины V³_b4, V³_b5).

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

X₁=(-2;2); X₂=(-3;4); X₃=(1;6);

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

К₁=25, К₂=50, К₃=15.

При этом счетчики циклов I_i в начале реализации алгоритма устанавливаются в единицу, т.е. I₁= I₂= I₃=1.

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

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

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

А₀ =(V₀) A₁ =(V_a1) A₂ =(V¹_b1)

A₃ =(V_a2, V¹_b2) A₄ =(V_a3, V²_b3) A₅ =(V_a4)

A₆ =(V_a5, V³_b4) A₇ =(V_a6, V³_b5) A₈ =(V_a7, V²_b6)

A₉ =(V¹_b7) A₁₀ =(V_a8, V²_b8)

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

Параметр Х₁ изменяется в пределах от -2 до +2. Переход из вершины А₂ в А₃ произойдет при значениях Х₁ больших нуля (с вероятностью 2/5=0,4), а в вершину А₄ - при значениях Х₁ меньших или равных нулю (с вероятностью 3/5=0,6). Аналогично определяются вероятности перехода из вершины А₆ в А₅ (p₆₅=0,83) и А₁₀ (p_{6 10}=0,17).

Из вершины А₄ осуществляется переход сразу в три вершины А₆, А₇ и А₈. Согласно параметру Х₃=(1;6), вероятность перехода из А₄ в А₆ равна 0,5. Следовательно с вероятностью 0,5 осуществится переход либо в вершину А₇, либо А₈. Исходя из заданного условия I₁<K₁ и параметра K₁=25, цикл должен выполнятся 24 раза. Следовательно, в 24/25 (0,96) случаях осуществиться переход в вершину А₈, а в 1/25 (0,04) случаях - в вершину А₇. Таким образом, p₄₇=0,5´0,04=0,02 и p₄₈=0,5´0,96=0,48.

Остальные полученные вероятности переходов следующие: p_{8 10}=0,02, p₈₉=0,98, p_{10 1}=0,93, p_{10 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,93n₁₀ - n₁= -1 n₁=14,3

n₁ + n₉ - n₂=0 n₂=27,64

0,4n₂ - n₃=0 n₃=11,056

0,6n₂ + n₅ - n₄=0 n₄=28,35

Þ

0,83n₆ - n₅=0 n₅=11,765

0,5n₄ - n₆=0 n₆=14,175

0,02n₄ - n₇=0 n₇=0,567

0,48n₄ - n₈=0 n₈=13,608

0,98n₈ - n₉=0 n₉=13,336

n₃ + 0,17n₆ + n₇ + 0,02n₈ - n₁₀=0 n₁₀=14,304

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

Аi	Vai	q^Vi, опер	ni	q^Vi*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 операций

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

G₁=n₂+n₃+n₉=52,032;

G₂=n₄+n₈+n₁₀=56,262;

G₃=n₆+n₇=14,742.

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

L₁=(n₂l₁+n₃l₂+n₉l₇)/G₁=686,854 байт;

L₂=(n₄l₃+n₈l₆+n₁₀l₈)/G₂=648,694 байт;

L₃=(n₆l₄+n₇l₅)/G₃=965,385 байт.

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

N=n₁+ n₃+ n₄+ n₅+ n₆+ n₇+ n₈+ n₁₀=108,125;

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

Дата добавления: 2015-10-31