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

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

Елементи теорії графів алгоритмів

Трудомісткість алгоритму — кiлькiсть обчислювальної роботи, що потрібна для реалізації алгоритму. Трудомісткість алгоритму інакше називають складністю обчислень [1]. Оцінюється трудомісткість алгоритму кiлькiстю операцій, що виконуються з метою обробки, введення та виведення інформації у процесі розв‘язку задачі. Кожній реалізації алгоритму притаманний елемент випадковості, пов’язаний з тим, що початкові дані являють собою у загальному випадку випадкову вибірку з множини початкових даних, до якої застосовується алгоритм. Тому повна характеристика трудомісткості передбачає опис кiлькості операцій, що виконуються за одну реалізацію алгоритму, над випадковими величинами.

До моделей обчислювальних процесів висувають наступні вимоги [1].

1. Модель забезпечує можливість визначати порядок породження алгоритмом запитів на кожен з видів обслуговування — обчислення та введення-виведення інформації, що зберігається у кожному з файлів.

2. Модель забезпечує можливість визначати трудомісткість обслуговування запитів — кiлькiсть операцій, яку повинен виконати процесор при обслуговуванні запиту на обчислення, та кiлькiсть символів інформації, що вводиться та виводиться.

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

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

Стосовно до задач аналізу трудомісткості оператори алгоритму будемо підрозділяти на функціональні, переходу та введення-виведення. Функціональний оператор задає перетворення на множині даних, тобто задає деяку сукупність обчислювальних операцій. Оператор переходу задає порядок обчислення значень предикатів та правило вибору одного з можливих шляхів розвитку обчислювального процесу, відповідного поточним значенням даних, відношення між якими представляються предикатами. Оператор введення-виведення задає звертання до визначеного файла з метою передачі деякої кiлькості інформації. Функціональні оператори та оператори переходу задають сукупності обчислювальних операцій над даними та відносяться до одного класу операторів, що називаються основними операторами [1].

Сукупність операторів та зв’язків між ними найбільш наочно представляється графом алгоритму, який будується як композицiя вершин, відповідних операторам алгоритму, та дуг, що відображають зв’язки між операторами. Виділяють вершини: початкові, кінцеві, операторні. Початкова вершина не має жодного входу та має тільки один вихід. Така вершина визначає початок алгоритму. Кінцева вершина має не менше одного входу та жодного виходу; вона визначає кiнець алгоритму. Операторна вершина відповідає основному операторові або операторові введення-виведення. Вершина, що представляє функціональний оператор або оператор введення-виведення, може мати будь-яке не менше одиниці число входів та тільки один вихід. Вершина, що представляє оператор переходу, може мати будь-яке не менше одиниці число входів та не менше двох виходів. В будь-якій ситуації оператор переходу визначає один та тільки один вихід з вершини, що його представляє.

Граф алгоритму є коректним, якщо виконуються наступні умови: 1) існує тільки одна початкова та тільки одна кінцева вершина; 2) для кожної вершини окрім початкової існує у всякому разі один шлях, що веде у цю вершину з початкової; 3) з кожної вершини окрім кінцевої існує у всякому разі один шлях, що веде з цієї вершини у кінцеву; 4) вихід з будь-якої вершини повинен вести тільки до однієї вершини графу; 5) при будь-яких значеннях логiчних умов існує шлях з початкової вершини у кінцеву, причому будь-якому фіксованому набору значень умов відповідає тільки один такий шлях.

Приклад графу алгоритму приведений на рис.1. Умовимося вершини графу позначати номерами 0, 1, .. К: 0 відповідає початковій вершині графу; К — кінцевій вершині; 1, .. К-1 ідентифікують оператори алгоритму. В програмуванні графи алгоритмів зображаються з використанням набору фігур, що позначають тип оператора, та називаються схемами алгоритмів (програм).

Граф виявляє структуру алгоритму, визначаючи множину операторів V= {V1, …, VK-1} та дуг D= {(i, j)}, clip_image002 та clip_image004, що пов’язують оператори.

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

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

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

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

K

å pij=1, (clip_image002[1]). (1)

j=1

Значення pij визначаються імовірностями значень предикатів, що залежать від розподілу значень даних, відношення між якими задаються предикатами. Іншими словами, імовірності pij залежать від імовірностей виконання умови, що перевіряється оператором i з метою вибору шляху переходу. Наприклад, нехай оператор 2 (рис. 1) породжує перехід до оператора 3 при від’ємному значенні деякої змінної Х та до оператора 4 при додатньому значенні Х. Якщо відомо, що величина Х рівномірно розподілена у діапазоні (- 1, +3), то з імовірністю 0, 25 її знак від‘ємний та з імовірністю 0, 75 — додатній. Внаслідок цього перехід до оператора 3 відбувається з імовірністю p2,3=0,25 та перехід до оператора 4 — з імовірністю p2,4=0,75. Нехай далі оператор 7, що замикає цикл, породжує перехід до оператора 1 у дев’яти випадках, а у одному випадку перехід відбувається у кiнець алгоритму (цикл, що починається від оператора 1 та що закінчується оператором 7, виконується 10 разів). Тоді імовірності переходів p7,1=0,9 та p7,K=0,1. Якщо за оператором i обов’язково виконується оператор j,то pij=1.

Нехай n1, … nK-1 — середнє число звертань до операторів V1, …,VК-1 за один прогін алгоритму. В такому випадку характеристики трудомісткості можуть бути обчислені таким чином: середнє число операцій, що виконуються при одному прогоні алгоритму,

q = å niki, (2)

Vi Î S0

середнє число звертань до файла Fh

Nh = å ni, (clip_image006[1]), (3)

Vi Î Sh

середня кiлькiсть інформації, що пеpедається при одному звертанні до файла Fh,

q h = (1/Nh) å nili (clip_image006[2]). (4)

Vi Î Sh

В (2) — (4) підсумовування виконується по всіх вершинах, що відносяться до класу основних операторів S0 або класу операторів введення-виведення Sh, що звертаються до файла Fh.

Таким чином, для оцінювання трудомісткості алгоритму необхідно визначити середнє число звертань n1, …, nK-1 до операторів.

Сітьовий підхід використовується у тих випадках, коли кiлькiсть обчислень при розрахунку трудомісткості алгоритмів треба скоротити. Окрім того, цей метод дозволяє визначити середню, мінімальну та максимальну трудомісткість.

Cуть сітьового підходу полягає у виділенні шляхів на графі алгоритму, відповідних мінімальній, середній та максимальній трудомісткості послідовності операторів. Ці шляхи можуть бути виділені тільки на графах, що не містять циклів. З цього приводу методика сітьового підходу починається з аналізу трудомісткості алгоритмів, що не містять цикли. Потім розглядається спосіб виключення циклів з графу алгоритму шляхом заміни їх операторами з еквівалентною трудомісткістю. Цей спосіб дозволяє поширити сітьовий підхід на будь-які алгоритми, у тому числі такі, що містять будь-яку кiлькiсть циклів.

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

2.1. Алгоритми без циклів

Алгоритм будемо представляти у вигляді графу, що складається з k операторних вершин та має єдину кінцеву вершину з номером K=k+1; дуги графу відзначені імовірностями переходів pij. Кожній вершині графу поставлено у відповідність середнє значення трудомісткості ki або lj. З врахуванням (2) — (4) задача оцінювання трудомісткості алгоритму зводиться до визначення середнього числа n1, …, nk звертань до операторів за один прогін алгоритму за умови, що трудомісткість всіх операторів kj однакова та дорівнює 1.

Розглянемо методику обчислень значень n1, …, nk для алгоритму, що не містить цикли. Для застосування сітьового підходу до оцінювання трудомісткості цього алгоритму вершини графу мають бути пронумеровані за порядком їх слідування, тобто так, щоб будь-яка вершина мала номер, більший будь-якого номера попередніх їй вершин. Нумерація проводиться таким чином. Початковій вершині присвоюється номер 0. Черговий номер i=1, 2 … присвоюється вершині, у яку входять дуги від вже пронумерованих вершин з номерами, меншими i. При цьому будь-яким двом вершинам повинні відповідати різні номери. Такий порядок нумерації є результативним для будь-якого графу без циклів. Причому кінцева вершина графу буде мати максимальний номер К. Приклад коректної нумерації вершин графу приведений на рис. 2.

Оскільки граф не містить циклів, то при прогоні алгоритму вершина 1 буде виконана точно один раз, тобто n1=1. Середнє число попадань обчислювального процесу у вершину визначається виразом

K

ni = å pjinj (clip_image008), (5)

j=1

де pji — імовірність переходу з вершини j у вершину i.

При встановленому порядку нумерації вершин на момент обчислення ni значення n1, …, ni-1 вже визначені. Тому обчислення значення ni зводиться до підсумовування добутків, причому оскільки pji=0 для всіх j³i, то підсумовування слід проводити тільки для j < i.

2.2. Приклад оцінювання середньої трудомісткості алгоритму без циклів

Визначимо середнє число звертань n1, …, nk до операторів алгоритму, зображеного на рис. 2.

Застосувавши (5), отримаємо значення ni, які зведені у табл. 1

Таблиця 1

n1=1 n6=p3,6n3+p2,6n2+p4,6n4=0,36
n2=p1,2n1=1 n7=p4,7n4=0,54
n3=p2,3n2=0,2 n8=p5,8n5+p6,8n6=0,44
n4=p2,4n2=0,6 n9=p8,9n8+p7,9n7=0,98
n5=p3,5n3=0,1 n10=p5,10n5+p9,10n9=1

Алгоритми, що містять цикли

Розглянемо випадок алгоритму, що містить цикли (рис. 3). Безпосереднє застосування описаної методики до таких алгоритмів неможливе та для обчислення значень n1, …, nk необхідно виключити цикли, замінюючи їх операторами з еквівалентною трудомісткістю.

clip_image010

Рис. 3.

Для спрощення опису методу приймемо, що алгоритм складається з однотипних операторів, наприклад, тільки основних операторів. Розділимо цикли по рангах. До рангу 1 (r=1) відносяться цикли, які не містять усередині себе жодного циклу, до рангу 2 (r=2) — цикли, усередині яких є цикли рангу не вище 1, і т.ін. Наприклад, алгоритм, зображений на рис. 3, містить два цикли С1 та С2 рангу 1 та один цикл С3 рангу 2. Сукупність операторів, що входить у цикл, та дуг, що пов’язують їх, за вийнятком дуги, що замикає цикл, називають тілом циклу. Тіло циклу рангу 1 (r=1) є графом без циклів. Застосовуючи до цього графу вищеописану методику, можна визначити значення ni для кожного з операторів, приналежних тілу циклу, та, отже, трудомісткість тіла циклу С дорівнює

kTC = å kjnj. (6)

Vj Î С

Тут підсумовування проводиться по всіх вершинах Vj, що містяться у циклі С.

Нехай відомо середнє число повторень циклу nC, рівне числу виконань тіла циклу при одному прогоні алгоритму. Якщо імовірність переходу по дузі, що замикає цикл, дорівнює pkl, то

nC=1+pklnC, (7)

звідки

nC=1/(1-pkl). (8)

В такому випадку середня трудомісткість циклу

kC=nC å kjni = nC * kTC, (9)

Vi Î С

та цикл С можна замінити оператором з трудомісткістю kC.

Застосовуючи вказану процедуру заміни циклів операторами до всіх циклів рангу 1, потім до циклів рангу 2 і т.ін., врешті-решт прийдемо до графу без циклів, трудомісткість якого знаходиться вищеописаним способом.

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

Визначимо трудомісткість алгоритму, заданого графом, зображеним на рис. 3.

Припустимо, що трудомісткість всіх операторів однакова та дорівнює 1, тобто kj=1. Середнє число повторень циклів С1, С2 та С3 визначається з імовірностей переходів, вказаних на рис. 3 за формулою (6) наступними значеннями: nC1=5, nC2=20 та nC3=10.

Виділимо тіла циклів С1 та С2 рангу 1. Їх структура зображена на рис. 4, а, б. Застосовуючи вищеописану методику до цих графів, визначаємо середню трудомісткість kC1 та kC2 виконання тіл цих циклів (табл 2).

Таблиця 2

Цикл С1 Цикл С2
n3=1 n7=1
n4=p3,4n3=1 n8=p7,8n7=0,2
n5=p4,5n4=0,5 n9=p8,9n8=0,2
n6=p4,6n4+p5,6n5=1 n10=p7,10n7=0,8
n11=p9,11n9+p10,11n10=1

6 11

kTC1= å kini=3,5; kTC2= å kini=3,2.

i=3 i=7

Середня трудомісткість циклів С1 та С2 обчислюється множенням отриманих значень на середнє число повторень цих циклів (9): kC1=17,5 та kC2=64 операцій.

Замінюючи у графі (див. рис. 3) цикли С1 та С2 операторами С1 та С2 з трудомісткістю kC1 та kC2, отримаємо граф, вигляд якого показаний на рис.4, в. Тіло циклу С3 має вигляд, зображений на рис. 4, г. Трудомісткість тіла циклу С3 визначається таким чином (табл. 3)

Таблиця 3

n2=1 nC2=p2,C2n2=0,6
nC1=p2,C1n2=0,4 n12=pC1,12nC1+pC2,12nC2=1

0

kTC3= å kjnj=1+17,5*0,4+64*0,6+1=47,4.

VjÎC3

З врахуванням числа nC3 повторень циклу трудомісткість циклу складе kC3=474 операції.

Замінивши цикл С3 оператором С3 з трудомісткістю kC3, отримаємо граф, що має вигляд, показаний на рис. 4, д. Трудомісткість алгоритму, що представляється цим графом, q=k1+kС3+k13=1+474+1=476 операцій.

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

Розглянемо методику обчислення мінімальної та максимальної трудомісткості алгоритмів. Спочатку будемо розглядати алгоритми без циклів, вершини графів яких нумерують за порядком їх слідування, як це було описано раніше.

Мінімально можливе та максимально можливе значення трудомісткості на момент закінчення виконання оператора Vi позначимо відповідно через Аi та Вi. Маємо А0=0 та В0=0. Тоді для інших вершин з номерами clip_image012

Ai = min (Aj)+ki min; (10)

(j,i)ÎD

Bi = max (Bj)+ki max, (11)

(j,i)ÎD

де (j, i) — дуга, що виходить з вершини j та входить у вершину i; D — множина дуг графу програми; мінімальне min(Aj) та максимальне max(Bj) значення визначаються по відношенню до всіх вершин j, з яких виходять дуги, що входять у вершину i; значення kimin та kimax характеризують мінімальну та максимальну трудомісткість оператора Vi.

Для кінцевої вершини К графу обчислюються значення

AK = min (Aj), (12)

(j,K)ÎD

BK = max (Bj), (13)

(j,K)ÎD

що характеризують мінімальну та максимальну трудомісткість алгоритму.

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

Визначимо мінімальну та максимальну трудомісткість алгоритму, що зображений на рис. 2.

Приймемо, що трудомісткість кожного оператора постійна та дорівнює 1. Нумерація вершин на графі (рис. 2) відповідає розглянутому вище правилу.

Послідовно застосовуючи (10), (11), отримаємо наступні значення (табл. 4).

Таблиця 4

A0=0 B0=0
A1=min(A0)+1=1 B1=max(B0)+1=1
A2=min(A1)+1=2 B2=max(B1)+1=2
A3=min(A2)+1=3 B3=max(B2)+1=3
A4=min(A2)+1=3 B4=max(B2)+1=3
A5=min(A3)+1=4 B5=max(B3)+1=4
A6=min(A2,A3,A4)+1=3 B6=max(B2,B3,B4)+1=4
A7=min(A4)+1=4 B7=max(B4)+1=4
A8=min(A5,A6)+1=4 B8=max(B5,B6)+1=5
A9=min(A7,A8)+1=5 B9=max(B7,B8)+1=6
A10=min(A5,A9)+1=5 B10=max(B5,B9)+1=7
AK=min(A10)+1=5 BK=max(B10)+1=7

Таким чином, мінімальна трудомісткість алгоритму АK дорівнює 5, а максимальна ВK — 7 операціям.

Алгоритми, що містять цикли

Мінімальна та максимальна трудомісткість алгоритмів, що містять цикли, знаходиться по аналогії з методом визначення середньої трудомісткості алгоритмів з циклами. При цьому виділяються цикли рангу 1. Знаходиться мінімальна А та максимальна В трудомісткість тіла циклу. Мінімальна та максимальна трудомісткість циклу визначається значеннями Anmin та Bnmax, де nmin та nmax — мінімальне та максимальне число повторень циклу. Потім цикл замінюється оператором з трудомісткістю

kmin=Anmin, (14)

kmax=Bnmax, (15)

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

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

Визначимо мінімальну та максимальну трудомісткість алгоритму, граф якого зображений на рис. 3. Трудомісткість всіх операторів постійна та дорівнює 1 (kj=1). Мінімальне та максимальне число повторень циклів С1 та С2 представляються такими парами значень: n1= (3;7); n2= (15; 25). Число повторень циклу С3 постійне та дорівнює 10.

Виділяємо тіла циклів С1 та С2, структура яких представлена графами рис. 4а, б. Мінімальна та максимальна трудомісткість цих частин алгоритму визначається так:

1) для графу рис. 4, а (табл. 5)

Таблиця 5

A0=0 B0=0
A3=min(A0)+1=1 B3=max(B0)+1=1
A4=min(A3)+1=2 B4=max(B3)+1=2
A5=min(A4)+1=3 B5=max(B4)+1=3
A6=min(A4,A5)+1=3 B6=max(B4,B5)+1=4
AC1=3 BC1=4

2) для графу рис. 4, б (табл. 6)

Таблиця 6

A0=0 B0=0
A7=min(A0)+1=1 B7=max(B0)+1=1
A8=min(A7)+1=2 B8=max(B7)+1=2
A9=min(A8)+1=3 B9=max(B8)+1=3
A10=min(A7)+1=2 B10=max(B7)+1=2
A11=min(A9,A10)+1=3 B11=(B9,B10)+1=4
AC2=3 BC2=4

Трудомісткість циклів С1 та С2 представляється наступними мінімальними та максимальними значеннями:

kC1 min=AC1n1 min=9; kC2 min=AC2n2 min=45;
kC1max=BC1n1max=28; KC2max=BC2n2max=100.

Замінивши у графі на рис. 3 цикли С1 та С2 еквівалентними їм операторами С1 та С2, отримаємо граф рис. 4,в. Тіло циклу С3 має структуру, зображену на рис. 4, г. Мінімальна та максимальна трудомісткість тіла циклу представлена у табл. 7.

Таблиця 7

A0=0 B0=0
A2=min(A0)+1=1 B2=max(B0)+1=1
AC1=min(A2)+k C1min=10 B C1=max(B2)+k C1max=29
AC2=min(A2)+k C2min=46 B C2=max(B2)+k C2max=101
A12=min(A C1,A C2)+1=11 B12=max(B C1,B C2)+1=102
AC3=11 B C3=102

Замінивши цикл С3 еквівалентним оператором С3, одержуємо граф (рис. 4, д), мінімальна та максимальна трудомісткість якого

AK=kmin+kC3 min+k13 min=112;

BK=k1max+kC3 max+k13 max=1022.

Середня трудомісткість цього алгоритму, вирахована раніше (п.2.4), складала 476 операцій.

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