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

Для забезпечення необхідної точності розв‘язку деяких задач аналізу обчислювальних систем необхідні відомості про дисперсію трудомісткості алгоритму. По визначенню дисперсією (розсіюванням) дискретної випадкової величини називають математичне чекання квадрата відхилення випадкової величини від її математичного чекання [3]

clip_image002, (1)

де x — дискретна випадкова величина; M(x) — математичне чекання величини x.

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

Середнім квадратичним відхиленням випадкової величини x називають квадратний корінь з дисперсії, тобто:

clip_image004. (2)

Процедура визначення дисперсії трудомісткості складна. В даній роботі розглядається формальна сторона цього питання [1].

Для обчислення дисперсії алгоритм представляється як марковський ланцюг з матрицею імовірностей переходів [2]

clip_image005clip_image007

Тут K — кiлькiсть операторів алгоритму та елементи визначають імовірності переходу з станів clip_image009 у стани clip_image011. Наприклад, алгоритм рис.1 відповідає матриці імовірностей переходів:

clip_image013

clip_image015

Рис. 1

Трудомісткість операторів представимо вектор-стовпцем:

clip_image017.

Для визначення дисперсії необхідно обчислити квадратну матрицю

clip_image019, (3)

де

clip_image021

— одинична матриця; clip_image023- поелементна різниця матриць clip_image025 та clip_image027, що представляє собою матрицю K-го порядку:

clip_image029.

Обертанням матриці clip_image023[1] формується матриця clip_image031, елементи clip_image033 якої мають зміст середнього числа попадань процесу у стани з номерами clip_image035, якщо процес починається зі станів з номерами clip_image009[1].

Таким чином, якщо алгоритм починає виконуватись від оператора з номером i=1, то кiлькiсть звертань до операторів clip_image037 задається першим рядком clip_image039 матриці clip_image031[1]. Помноживши матрицю clip_image031[2] на вектор-стовпець clip_image041, отримаємо вектор-стовпець

clip_image043, (4)

елементи якого визначають середню трудомісткість алгоритму, ініційованого від операторів clip_image045 відповідно.

Значення дисперсії можна визначити наступним матричним виразом:

clip_image047 (5)

Тут clip_image049- діагональна матриця,

clip_image051,

що одержується з елементів вектора L; clip_image053- вектор-стовпці виду

clip_image055,

clip_image057,

що визначаються шляхом зведення у квадрат елементів векторів L та clip_image059.

Елементи вектор-стовпця

clip_image061

визначають дисперсію часу виконання програми, що починається від операторів з номерами clip_image045[1] відповідно. Якщо алгоритм виконується завжди з першого оператора, то дисперсія задається першим елементом D1 вектора D.

2. Приклад оцінювання дисперсії трудомісткості алгоритму

Нехай потрібно обчислити дисперсію трудомісткості алгоритму (рис.2).

Трудомісткість операторів складає clip_image063 та clip_image065 операцій.

Згідно з графом (рис. 2) будуємо матрицю імовірностей переходів:

clip_image067.

Обчислюємо матрицю N:

clip_image069.

clip_image071

Рис. 2 Граф алгоритму

Визначаємо вектор середньої трудомісткості алгоритму:

clip_image073.

Перший елемент clip_image075 вектора визначає середню трудомісткість алгоритму, ініційованого від оператора 1, елемент clip_image077- трудомісткість алгоритму, ініційованого від оператора 2, і т.ін.

Застосовуючи (5), знаходимо

clip_image079

Cередньоквадратичне відхилення трудомісткості алгоритму, ініційованого від першого оператора, становить clip_image081.

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