Оцінювання трудомісткості алгоритмів. Марковська модель

Главная » Каталог статей » Статьи на украинском » Системотехніка оптоелектронних та лазерних систем » Оцінювання трудомісткості алгоритмів. Марковська модель

Найбільш просту модель можна одержати, якщо прийняти припущення про відсутність післядії у обчислювальному процесі, коли наступний стан обчислювального процесу залежить тільки від поточного стану та не залежить від попередніх станів. В такому випадку обчислювальний процес стає марковським процесом, що визначається множиною притаманних йому станів {S0, …, SH+1}, матрицею імовірностей переходів

S0 S1 SH+1

clip_image001clip_image002 S0 p0,0 p0,1 p0,H+1

S1 p1,0 p1,1 p1, H+1

Р = [pij] = … …………………………….

SH+1 pH+1,1 pH+1,2 … pH+1, H+1

та розподілом імовірностей (а0, …, аH+1) станів S0, …, SH+1 у момент ча­су 0. Елементи pij матриці Р визначають імовірності переходу процесу з станів Si у стани Sj, тобто імовірності того, що процес, що знаходиться у стані Si, у наступний момент часу буде знаходиться у стані Sj. Матриця Р — стохастична матриця, суми елементів рядків якої

Н+1

å pij=1. (1)

j=0

Імовірності аj визначають перший можливий стан St0 процесу.

Будемо вважати, що обчислювальний процес розвивається таким чином.

Процес починається з стану S0, тобто програма починає виконуватись з етапу обчислення. Етап введення — виведення може бути ініційований тільки процесором, тобто може слідувати тільки за етапом обчислення. Це одночасно означає, що після кожного етапу введення — виведення відбувається етап обчислення. В такому випадку імовірності початкових станів

0, а1, а0, …, аH+1) = (1, 0, 0, …, 0) (2)

та матриця імовірностей переходів

S0 S1 S2 SH SH+1

clip_image003clip_image004 S0 0 p0,1 p0,2 p0,H p0,H+1

S1 1 0 0 0 0

S2 1 0 0 … 0 0

Р = [pij] = … …………………………………………… (3)

SH 1 0 0 … 0 0

SH+1 0 0 0 … 0 1

З стану обчислення S0 процес з відповідною імовірністю може перейти у стани S1, … SH, етапи, що представляють звертання до файлів F1, …, FH, або у поглинаючий стан SH+1. З станів S1, …SH процес з імовірністю 1 повертається у стан обчислення S0. Досягнувши поглинаючого стану SH+1, процес з імовірністю 1 назавжди залишається в ньому. Порядок зміни станів наочно проявляється на графі марковського ланцюга (рис.1). Переходи між станами S0, … SH+1 представляються на графі дугами, на яких позначені імовірності переходів, відмінні від 1.

Значення імовірностей [p0,1, …, p0,H+1] зумовлюють хід обчислю­вального процесу та залежать від параметрів трудомісткості алгоритму. Ці значення обчислюються таким чином. Трудомісткість алгоритму визначає, зокрема, середнє число N1, …, NH звертань до файлів F1, …, FH. Отже, середнє число переходів з стану S0 у стани S1, …, SH має бути (N1+ … + NH). Один раз процес переходить з стану S0 у поглинаючий стан SH+1. Таким чином, обчислювальний процес повинен виходити з стану S0 у середньому

H

N = å Nh+1 (4)

h=1

разів, тобто у процесі реалізації алгоритму етапи обчислення зустрічаються у середньому N разів. Значення p0,h визначає частку переходів у стан Sh по відношенню до всіляких переходів з стану S0 у стани S1, … SH+1.

Ця частка дорівнює у середньому Nh/N, де Nh — середнє число переходів у стан Sh. Отже,

p0,h = Nh/ N (clip_image006); p0,H+1 = 1/ N. (5)

Кiлькiсть роботи, що виконується на кожному з етапів, характеризується параметрами q1, …, qH алгоритму. Значення q визна­чає середню кiлькiсть процесорних операцій, що виконуються за одну реалізацію алгоритму, та значення q1, …, qH — середню трудомісткість етапів, відповідних станам S1, … SH. Середня трудомісткість етапу обчислення

q0= q/ N, (6)

де N — середнє число етапів обчислення, що визначається (4).

Трудомісткість кожного етапу будемо розглядати як випадкову величину Jh з математичним чеканням Jh, clip_image008; закон розподілу випадкових величин J0,… Jh будемо зумовлювати особливо.

Таким чином, під моделлю обчислювального процесу будемо розуміти марковський ланцюг з (Н+2) станами, початковим станом S0 та матрицею імовірностей переходів (3). Реалізація обчислювального процесу — випадкова послідовність станів S0,St1, St2, …, StM, порядок зміни яких визначається у стохастичному смислі матрицею імовірностей переходів. З станами S0, …, SH пов’язана певна кiлькiсть роботи, що характеризується значеннями випадкових величин J0,… Jh відповідно. Діаграма обчислювального процесу, породжуваного марковською моделлю, зображена на рис. 2. Значення Jji визначає трудомісткість відповідного етапу та представляє собою j — е значення випадкової величини Ji, математичне чекання якої qі. В даному випадку стан S3 є поглинаючим: досягнувши його, процес припиняється.

Приклад марковської моделі обчислювального процесу

Побудуємо марковську модель обчислювального процесу, породжуваного алгоритмом, трудомісткість якого характеризується наступними параметрами: q = 100 млн операцій; N1 = 19 звертань до файла F1; N2 = 180 звертань до файла F2; q1 = 2000 байтів; q2 = 500 байтів за звертання до файла.

Згідно з (4) середнє число етапів обчислення при одному прогоні алгоритму N = N1 +N2 +1 = 200. Імовірності переходу процесу з стану обчислення S0 у стани S1, S2 та S3 визначаються (5) та дорівнюють відповідно: p0,1 = N1 /N = 19 /200 = 0,095; p0,2 = N2 /N = 180/200 = 0,9; p0,3= N3/N = 1/N = 0,005.

Підставляючи ці значення у (3), одержуємо наступну матрицю імовірностей переходів:

clip_image009clip_image010 S0 S1 S2 S3

S0 0 0,095 0,9 0,005

S1 1 0 0 0

Р = S2 1 0 0 0

S3 0 0 0 1

З матриці видно, що з імовірністю 0,095 за етапом обчислення відбудеться звертання до файла F1, з імовірністю 0,9 — звертання до файла F2 та з імовірністю 0,005 обчислювальний процес припиниться.

Середня трудомісткість етапу обчислення згідно з (6) становить q0= q/ N= 0,5 млн. операцій.

Оцінювання трудомісткості алгоритмів методами теорії марковських ланцюгів

На рис. 3 представлений граф алгоритму, де показано множину операторів V = {V1, …, Vk-1} та дуг D = {(i, j)}, clip_image012 таclip_image014, що пов’язують оператори.

Для оцінювання трудомісткості алгоритму необхідно:

1. Розбити множину операторів на класи: основних операторів S0 = { Va1, … , Vamo} , Vak Î V, операторів введення-виведення Sh = { Vb1, … , Vbmh }, clip_image006[1] (кожен з цих операторів задає звертання до одного й того ж файла Fh).

2. Для кожного основного оператора Va необхідно визначити се­ред­ню кiлькiсть операцій ka, що складають оператор, та для кожного оператора введення-виведення Vb — середню кiлькiсть інформації lb, що пеpедається при виконанні оператора.

3. Переходи між операторами Vi та Vj слід розглядати як випад­кові події та характеризувати їх імовірностями рi,j, тобто кожна дуга (i, j) графу алгоритму має бути відзначена імовірністю переходу рi,j, з якою перехід з вершини Vi виконується cаме по цій дузі, тобто до вершини Vj. Імовірності переходів повинні відповідати умові:

К

å рi,j = 1, (clip_image012[1]) (7)

j = 1

Припустимо, що імовірності переходів рkj постійні та після виконання оператора Vk(clip_image017) перехід до наступного оператора визначається тільки розподілом імовірностей рkj, тобто не залежить від ходу обчислювального процесу у минулому — до переходу до оператора Vk. При вказаних допущеннях процес виконання алгоритму є марковським процесом з К станів S1, …, SК, відповідних перебуванню процесу у вершинах V1, …, VК графу алгоритму. Стани S1, …, SК-1 — незворотні (процес після якогось числа кроків обов’язково покидає їх), стан SК — поглинаючий (досягнувши його, процес припиняється).

Початковим є стан Si, визначений дугою (0, i), що виходить з початкової вершини графа. Для спрощення позначень умовимося, що i=1, тобто початковий стан — стан S1. Порядок зміни станів визначається графом алгоритму, дуги якого відзначені імовірностями переходів рij. Відзначений граф алгоритму можна розглядати як граф марковського ланцюга.

Середнє число n1, …, nK-1 перебувань марковського процесу у незворотних станах S1, …, SК-1 визначається коренями системи лінійних алгебраїчних рівнянь

К-1

nі = d+ å рnj (clip_image019), (8)

j = 1

де d- символ Кронекера (dіj =1 при i = j та dіj = 0 при i ¹ j).

Рівняння (8) будуються виходячи з наступних міркувань. Значення ni буде дорівнювати у всякому разі одиниці, що відзначено символом d. В інших випадках процес попадає у стан Si тільки з інших станів clip_image021 з імовірностями рji. Якщо процес знаходився у стані j nj разів та рji ¹ 0, то процес з цього стану попадає у стан i в середньому рjinj разів. Підсумовуванням значень рjinj по всіх j знаходиться число попадань процесу у стан i з всіх інших станів j.

Значення n1, …, nK-1 визначаються розв‘язком системи лінійних алгебраїчних рівнянь (8), канонічний запис якого має вигляд

1,1 — 1) n1 + р2,1 n2 + … + рК-1,1 nK-1 = -1;

р1,2 n1 + (р2,2 -1) n2 +… + рК-1,2 nK-1 = 0;

………………………………………………….…. (9)

р1,К-1 n1 2,К-1 n2 + … +( рК-1,К-1 -1) nK-1 =0.

В результаті можна визначити трудомісткість алгоритму у вигляді середнього числа операцій при одному прогоні алгоритму таким чином:

q = å nі ki, (10)

Vi ÎS0

де ki — кiлькiсть операцій, породжуваних кожним оператором.

Розглянутий спосіб визначення трудомісткості алгоритмів є універсальним, дозволяючи одержувати оцінки для алгоритмів з будь-якою структурою, простий з точки зору програмування, але вимагає розв‘язку системи лінійних алгебраїчних рівнянь звичайно високого порядку.

Приклад оцінювання трудомісткості алгоритму

Нехай вимагається визначити трудомісткість алгоритму, заданого графом (рис. 3).

Для простоти приймемо, що всі оператори алгоритму — основні (оператори введення-виведення відсутні) та кiлькiсть операцій ki, породжуваних кожним з операторів, постійна та дорівнює 1.

На основі графу (рис. 3) та формули (9) будуємо систему з семи лінійних алгебраїчних рівнянь:

— n1 +0,9 n7 = -1;

n1 - n2 = 0;

0,25 n2 - n3 = 0;

0,75 n2 - n4 = 0;

0,5 n3 + 0,2 n4 — n5 = 0;

0,8 n4 — n6 = 0;

0,5 n3 + n5 +n6 - n7 = 0.

Розв‘язуючи систему, визначаємо середнє число попадань об­числю­вального процесу у стани S1, … ,S7: n1 = 10; n2 = 10; n3 = 2,5; n4 = 7,5; n5 = 2,75; n6 = 6,00; n7 = 10.

Підставляючи отримані значення у (10), одержуємо оцінку трудомісткості алгоритму:

7

q = å nі ki = 10 + 10 + … + 6,0 + 10 = 49,75 операцій.

Один комментарий к “Оцінювання трудомісткості алгоритмів. Марковська модель”

  1. XXX Says:

    :roll:



Оставьте комментарий к статье