ти, виконуваної на кожному з етапів, характеризується параметрами q1, ..., qH алгоритму. Значення q визначає середня кількість процесорних операцій, виконуваних за одну реалізацію алгоритму, і значення q1, ..., qH - середню трудомісткість етапів, відповідних станам S1 ... SH. Середня трудомісткість етапу рахунки
q0 = q/N,
де N-середнє число етапів рахунки.
Трудомісткість кожного етапу будемо розглядати як випадкову величину uh з математичним очікуванням qH, h = 0,1, ..., H.
Таким чином, під моделлю обчислювального процесу будемо розуміти марковскую ланцюг з (H +2) станами, початковим станом S0 і матрицею ймовірностей переходів. Реалізація обчислювального процесу - випадкова послідовність станів S0, St1, St2, ..., Stm, порядок зміни яких визначається в імовірнісному сенсі матрицею ймовірностей переходів. З станами S0 ... SH пов'язано певну кількість роботи, що характеризується значеннями випадкових величин u0 ... uH відповідно. Діаграма обчислювального процесу, породжуваного марковській моделлю має вигляд:
Значення uij визначає трудомісткість відповідного етапу і являє собою j-е значення випадкової величини ui, математичне очікування якої qi. У даному випадку стан S3 є поглинаючим: досягнувши його, процес припиняється. p> Розглянемо приклад. Нехай заданий алгоритм, трудомісткість якого характеризується наступними параметрами:
q = 100 млн. операцій;
N1 = 19 звернень до файлу F1;
N2 = 180 звернень до файлу F2;
q1 = 2000 байтів;
q2 = 500 байтів за звернення до файлу.
Побудуємо марковскую модель обчислювального процесу, породжуваного цим алгоритмом. Середнє число етапів рахунки за однієї прогоні алгоритму N = N1 + N2 +1 = 200. Ймовірності переходу процесу зі стану рахунку S0 в стани S1, S2 і S3 рівні відповідно:
P01 = N1/N = 19/200 = 0,095
P02 = N2/N = 180/200 = 0,9
P03 = 1/N = 1/200 = 0,005
Підставляючи ці значення, отримуємо наступну матрицю ймовірностей переходів:
В
З матриці видно, що з імовірністю 0,095 за етапом рахунки відбудеться звертання до файлу F1, з імовірністю 0,9 - F2, і з 0,005 - обчислювальний процес припиниться. Середня трудомісткість етапу рахунки q0 = q/N = 100/200 = 0,5 млн. операцій. p align="center"> Оцінка трудомісткості алгоритмів методами теорії марковських ланцюгів
Оператори алгоритму будемо поділяти на функціональні, переходу і введення-виведення. Функціональний оператор задає перетворення на множині даних, тобто задає деяку сукупність обчислювальних про Пераціму. Оператор переходу задає порядок обчислення значень предикатів і правило вибору одного з можливих шляхів розвитку обчислювального процесу, відповідного поточним значення даних, відносини між якими представляються предикатами. Оператор вводу-виводу задає звернення до певного файлу з метою передачі деякої кілько...
