., Stm, що змінюються в моменти часу to, t1, ..., tm, причому і заключний стан процесу
Марковська модель обчислювальних процесів
Найбільш просту модель можна отримати, якщо прийняти допущення про відсутність наслідки в обчислювальному процесі, означаючому, що наступний стан обчислювального процесу залежить тільки від поточного стану і не залежить від попередніх станів. У такому випадку обчислювальний процес стає марковским процесом, обумовленим безліччю властивих йому станів матрицею ймовірностей переходів
В
і розподілом ймовірностей (a0, ..., aH +1) станів S0, ..., SH +1 в момент часу 0.
Елементи Pij матриці P визначають ймовірності переходу процесу зі стану Si в стан Sj, тобто ймовірності того, що процес, що перебуває в стані Si в наступний момент часу буде перебувати в стані Sj. Матриця P - стохастична матриця, построкові суми елементів якої
.
Ймовірності ai визначають перше можливе стан St0 процесу. Будемо вважати, що обчислювальний процес розвивається таким чином. Процес починається з стану S0, тобто програма починає виконуватися з етапу рахунку. Етап введення-виведення може бути ініційований тільки процесором, тобто може слідувати тільки за етапом рахунку. Це одночасно означає, що після кожного етапу введення-виведення слід етап рахунку. У такому випадку ймовірності початкових станів (a0, a1, a2, ..., aH +1) = (1,0,0, ..., 0) і матриця ймовірностей переходів
В
Зі стану рахунку S0 процес з відповідною ймовірністю може перейти в стани S1, ..., SH, що представляють собою етапи звернення до файлів F1, ..., FH, або в поглинаючий стан SH +1. З станів S1, ..., SH процес з імовірністю 1 повертається в стан рахунку S0. Досягнувши поглинаючого стану SH +1 процес з імовірністю 1, назавжди залишається в ньому. Порядок зміни станів можна представити на графі марковського ланцюга. Переходи між станами S0, ..., SH +1 представляються на графі дугами, на яких позначені ймовірності переходів, відмінні від 1. br/>
Значення ймовірностей P01, ..., P0, H +1 зумовлюють хід обчислювального процесу і залежать від параметрів трудомісткості алгоритму. Ці значення обчислюються наступним чином. Трудомісткість алгоритму визначає, зокрема, середнє число N1 ... NH звернень до файлів F1, ... FH. Отже, середнє число переходів зі стану S0 у стан S1 ... SH має бути (N1 + ... + NH). Один раз процес переходить зі стану S0 в поглинаючий стан SH +1. Таким чином, обчислювальний процес повинен виходити зі стану S0 в середньому раз, тобто в процесі реалізації алгоритму етапи рахунки зустрічаються в середньому N разів. Значення P0h визначає частку переходів у стан Sh по відношенню до всіляких переходах зі стану S0 в стани S1 ... SH +1. p> Ця частка дорівнює в середньому Nh/N, де Nh - середня кількість переходів у стан Sh. Отже:
P0, h = Nh/N, h = 1,2 ... H, H +1 = 1/N.
Кількість робо...
