Мета роботи. Лабораторна робота №1 Оцінка трудомісткості алгоритму

Тема

ЛАБОРАТОРНА РОБОТА №1 Оцінка трудомісткості алгоритму

Лабораторних робіт

Загальні вимоги до оформлення звітів з

Захист роботи

Порядок виконання роботи

Тривалість роботи

ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ

ВСТУП

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

У результаті вивчення дисципліни студент повинен:

знати – визначення та характеристики інформаційних систем, як об’єкту моделювання, що таке трудомісткість алгоритму, швидкодія ЕОМ, продуктивність ЕОМ, номінальна та комплексна продуктивність і що собою являють системи оперативної обробки;

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

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

Кожна лабораторна робота триває 4-6 годин.

1 Підготовка до виконання роботи (попереднє ознайомлення з методичними вказівками до лабораторної роботи та опрацювання теоретичного матеріалу і рекомендованою літературою).

2 Отримання допуску до виконання роботи (знати відповіді на контрольні запитання).

3 Виконання типового навчального завдання.

4 Захист роботи.

Захист лабораторної роботи полягає у:

– контролі досягнення студентом мети роботи;

– контролі наявності знань у студента.

Звіт з лабораторної роботи оформляється згідно з нормативними вимогами ІФНТУНГ. Звіт повинен включати:

1 Титульний аркуш.

2 Мету та завдання до лабораторної роботи.

3 Результати виконаної роботи.

4 Висновки.

5 Перелік посилань на джерела.

6 Додатки (при необхідності).

Оцінка трудомісткості алгоритму.

Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів.

Теоретичні відомості:

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

Трудомісткість алгоритму в першому наближенні може бути охарактеризована набором параметрів:

Θ - середня кількість процесорних операцій, необхідних для однієї реалізації алгоритму; Ni, N₂,...,N_H - середня кількість запитів до файлів за один прогін програми; L_i, L₂,...,L_H - середня кількість інформації, що передається за одне звернення до файлів Fi, F₂,...,F_h.

При необхідності набір параметрів, що характеризують трудомісткість алгоритму може бути доповнений. Вхідна інформація для розрахунку трудомісткості алгоритму може бути одержана з блок-схеми алгоритму (рис. 1.1).

Для розрахунку трудомісткості алгоритму необхідно знати імовірності переходів з логічних вершин при одиничному значенні логічної умови. Якщо відповідну імовірність визначити через p, тоді імовірність виходу з логічної вершини при нульовому логічному значенні умови, що перевіряється буде рівна 1 - p.

Рисунок 1. 1 – Блок-схема алгоритму

.

Для подальших розрахунків схему алгоритму раціонально зображати в вигляді графа алгоритму. Для цього пропонується перенумерувати всі оператори схеми алгоритму. У логічних операторів замість логічних умов '1' і '0' будемо записувати відповідну даному виходу імовірність. Імовірність виходу з операторної вершини рівна 1. Отриманий таким чином граф алгоритму зображений на рис. 1.2.

Граф алгоритму можна істотно спростити, якщо трудомісткість виконання логічних вершин незначна в порівнянні з трудомісткістю виконання операторних вершин. Тоді стани, що відповідають логічним вершинам, можна злити з станами, що випереджають відповідні операторні вершини. В нашому прикладі можна злити стан (1.2), (3.4), (7.8), (10.11).

Рисунок 1. 2 - Граф алгоритму

Після перенумерації отримаємо мінімізований граф алгоритму (рис. 1.3). При достатньому досвіді до нього можна було прийти відразу від блок-схеми (рис.1.1). Позначимо через п₁, n₂,...,n_k-1 - середнє число запитів до операторів V₁, V₂,...,V_k-1, відповідно. Кожен з операторів V_і(i=1,2,...,k-1) буде характеризуватись наступним набором чисел:

• k_i - середня кількість процесорних операцій, що виконуються в операторі V_і

• m_іj - середня кількість запитів до файлу F_j(j=1,2,...,h) з оператора V_і

l_іj - середня кількість інформації, що передається при одному запиті до файлу F_j(j=1,2,...,H) з оператора V_і.

Рисунок 1. 3. – Мінімізований граф алгоритму

Тоді для оцінки трудомісткість можна використати наступні формули:

(1.1)

(1.2)

(1.3)

де Θ - середнє число процесорних операцій, що виконуються при одному виконанні алгоритму; N_j- середнє число запитів до файлу F_j(j=1,2,...,H) при одному виконанні алгоритму; l_j - середня кількість інформації, що передається при одному запиті до файлу F_j(j=l,2,.,H) при одному виконанні програми.

Для визначення середнього числа запитів n_i до оператора V_i(i=1,2,...,k-1) звичайно робляться наступні допущення:

- імовірність виконання оператора V_i після оператора V_j рівна P_ij і є постійною величиною;

- імовірність P_ij залежить тільки від оператора V_i;

- .

При виконанні вищезазначених допущень обчислювальний процес стає Марківським процесом з станами S₁,S₂,...,S_k. При цьому оператори V₁,V₂,...,V_k-1 відповідають станам S₁,S₂,...,S_k-1. Стан S_k відповідає кінцевій вершині граф алгоритму. Стани S₁,S₂,...,S_k-1 називаються незворотними, бо процес, неодмінно, з них виходить.

Сучасна теорія алгоритмів налічує декілька способів оцінки трудомісткості алгоритмів.

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

Для визначення середнього числа процесорних операцій, що виконуються за один прогін програми необхідно подати граф алгоритму у вигляді стохастичної матриці P. Для рис.1.3 вона прийме вигляд:

Таблиця 1. 1- Стани стохастичної матриці

Елементами матриці P є імовірності переходу з стану і в стан j, що наведені на графі алгоритму. З стохастичної матриці слідує, наприклад, що в стані S₄ процес може виявитися при переході з S₁ з імовірністю 0.5 або при переході з стану S₃ з імовірністю 1.

Якщо відомі середні числа запитів до вершин V₁ і V₃, то число запитів до вершини V₄ буде рівним: n₄ = p₁₄ n₁ + p₃₄ n₃ = 0.9n₁ + n₃.

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

(1.4)

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

n₁ = 1n₀ = 1*1 = 1;

n₂ = 0.5n₁ = 0.5*1 = 0.5;

n₃ = 0.4n₂ + 0.25n₅ = 0.2 + 0.25n₅;

n₄ = 0.5n₁ + n₃ = 0.5 + n₃;

n₅ = 0.6n₂ + n₄ = 0.3 + n₄;

n₆ = 0.75n₅;

n₇ = n₆ + 0.8n₇.

Вирішуючи систему рівнянь, отримаємо:

n₁ = 1; n₂ = 0.5; n₃ = 0.533; n₄ = 1.033;

n₅ = 1.333; n₆ = 1; n₇ = 5.

Для перевірки правильності вирішення системи лінійних рівнянь можна використати тотожність:

при (1.5)

В наведеному прикладі це виконується так: n_k = 0.2 * n₇ = 0.2 * 5 = 1.

Даний спосіб є універсальним (в випадку Марківського процесу), але вимагає великих затрат часу при значних розмірах стохастичної матриці.

Мережевий підхід до оцінки трудомісткості алгоритмів

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

Використовуючи формулу (1.4) для рис. 1.4 можемо записати:

n₀ = 1;

п₁ = 1 * n₀ = 1;

n₂ = 0.5 * п₁ = 0.5;

n_4’ = 0.5 * n₁ = 0.5;

n_5’ = n_4’ + 0.6n₂ = 0.5 + 0.6 * 0.2 = 0.8;

n_3’ = 0.4n₂ + 0.25n_5’ = 0.4 * 0.5 + 0.25 * 0.8 =0.4;

n₆ =n_3’ + 0.75n_5’ = 0.4 + 0.75 * 0.8 = 1;

n_7’ = 1 * n₆ =1.

Рисунок 1. 4 - Граф алгоритму буз циклів

В зв'язку з відсутністю циклів систему легко розв’язати. Витрати часу на аналіз можуть бути додатково знижені, якщо ввести ефективну нумерацію станів графа алгоритму. Остання полягає в тому, що номер вершини повинен бути таким, щоб дуги що входять в цю вершину починалися в вершинах з меншими номерами. Якщо після такої нумерації рівняння записувати в порядку зростання номерів вершин, то вони будуть відразу вирішуватися, бо невідомі з меншими номерами вже будуть обчислені. В наведеному прикладі нумерація вершин не відповідає визначеній вимозі, але рівняння записувалися в порядку їхнього розв’язку. За наявності в графі алгоритму циклів, їх слід замінити операторами з еквівалентною трудомісткістю. Якщо в графі алгоритму є вкладені в цикл цикли, тоді, перш за все слід замінити еквівалентними операторами внутрішні цикли, а після цього переходити до заміни зовнішніх циклів. Розрахунок трудомісткості алгоритму виконується по наведеній вище методиці.

Визначимо через р_с імовірність замикання циклу, тобто імовірність переходу по дузі з кінця циклу в його початок. Тоді в відповідності з виразом (1.4) можна записати:

n_c = 1 + p_cn_c, , (1.6)

де п_с - середнє число повторень циклу.

З виразу (1.6) одержимо:

(1.7)

Тоді середнє число процесорних операцій циклу буде рівне:

k_c = п_ск_тс,

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

Приклад 1

В алгоритмі на рис.1.3 є два цикли. Перший містить оператори V₃,V₄,V₅, а другий складається тільки з оператора V₇. Перший цикл ускладнюється входами в середину циклу з операторів V₁ та V₂.

Для позбавлення від входів в цикл не через початок циклу V₃ обчислимо елементарні перетворення графа алгоритму. Еквівалентний граф після очевидних перетворень зображений на рис. 1.5.

З рис.1.5 слідує, що оператори V₄ та V₅, що використовувались для входу в тіло циклу не через його початок, винесені окремо під номерами 4' й 5'. Кількість повторень циклів з виразу (1.7) рівна:

де n_c1, n_c2 - число повторень першого та другого циклів. Граф алгоритму без циклів наведений на рис. 1.4.

Рисунок 1. 5- Еквівалентний граф алгоритму

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

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

Приклад 2

Оцінимо мінімальне і максимальне число процесорних операцій для графа алгоритму, зображеного на рис. 1.4. Для спрощення приймемо, що всі оператори мають трудомісткість, рівну 1000 процесорних операцій. Через Ai і Bi будемо визначати, відповідно, мінімальне і максимальне число процесорних операцій, що буде мати місце в момент виходу процесу з і-ї вершини графа.

A₀ = 0;

A₁ = min(A₀) + 1000 = 1000;

A₂ = min(A₁) + 1000 = 2000;

A_4’ = min(A₁) + 1000 = 2000;

A_5’ = min(A₂,A_4’) + 1000 = 3000;

A_3’ = min(A₂,A_5’) + 1000 = 3000;

A₆ = min(A₃,A_5’) + 1000 = 4000;

A₇ = min(A₆) + 1000 = 5000;

B₀ = 0;

B₁ = max(B₀) + 1000 = 1000;

B₂ = max(B₁) + 1000 = 2000;

B_4’ = max(B₁) + 1000 = 2000;

B_5’ = max(B₂,B_4’) + 1000 = 3000;

B_3’ = max(B₂,B_5’) + 1000 = 4000;

B₆ = max(B₃,B_5’) + 1000 = 5000;

B₇= max(B₆) + 1000 = 6000.

Завдання для виконання:

1 Перед виконанням роботи ознайомитись з теоретичними відомостями.

2 В відповідності до отриманого номеру варіанту вибрати логічну схему алгоритму (ЛСА) - таблиця 1.1. Згідно з ЛСА зобразити графічну схему алгоритму.

3 З таблиці 1.2 вибираються імовірності переходів при одиничних логічних умовах, відповідно до варіанту

4 З таблиці 1.3 знаходяться кількість процесорних операцій в операторах алгоритму.

5 З таблиці 1.4 по останній цифрі варіанту вибираються кількість запитів і довжина запису в кілобайтах у разі звертання до файлів F₁, F₂, F₃.

6 Зображається блок-схема алгоритму, граф алгоритму і мінімальний граф алгоритму.

7 Визначається трудомісткість алгоритму засобами теорії марківських ланцюгів.

8 Визначається середня трудомісткість алгоритму з допомогою мережевого підходу.

9 Обчислюється мінімальна і максимальна трудомісткість алгоритму.

Контрольні питання:

1. Що таке трудомісткість алгоритму?

2. Як визначається трудомісткість алгоритму і з якою метою обчислюється ця величина?

3. Чому трудомісткість алгоритму є, як правило, випадковою величиною?

4. Які параметри можуть бути використані для характеристики трудомісткості алгоритму?

5. Як виконати ефективну нумерацію станів в графі алгоритму для мереженого аналізу?

6. Що таке стохастична матриця?

7. Як визначити імовірності виходу з логічної вершини?

8. Що таке марківський процес?

9. Доведіть правильність формули (1.4).

10. Доведіть правильність тотожності (1.5).

11. Доведіть правильність виразу (1.6).

12. Чи існує різниця в оцінці середньої трудомісткості при використанні теорії марківських ланцюгів та мережевого підходу? Якщо так, то пояснити її.

Література

1. Основы теории вычислительных систем / Под ред. С.А. Майорова. - М.: Высшая школа, 1978. - 408 стр.

Таблиця 1. 1- Логічні схеми алгоритмів

Варіант	Логічна схема алгоритму
	Поч. Ax1­^1Bx2­^2C¯^3x3­^3D¯^2E¯^4Mx4­^4K¯^1 Кін.
	Поч. Ax2­^2Bx3­^3 C x1­^1D¯^3E¯^1¯^4M¯^2x4­^4K Кін.
	Поч. Ax2­^2B¯^3¯^2Cx3­^3¯^1Dx1­^1Ex4­^4M K¯^4 Кін.
	Поч. A¯^2¯^1Bx1­^1Cx2­^2Dx4­^4¯^3Ex3­^3M¯^4K Кін.
	Поч. ↓^1Ax1↑^1Bx2↑^2Ex3↑^3C↓^2↓^3Mx4↑^4D↓^4K Кін.
	Поч. A¯^4Bx2­^2Cx3­^3D¯^2¯^3Ex4­^4Mx1­^1K¯^1 Кін.
	Поч. Ax2↑^2Cx4↑^4Dx3↑^3E↓^2↓^3↓^1↓^4Kx1↑^1M B Кін.
	Поч. Аx1↑^1Вx2↑^2M↓^2↓^3↓^4Сx4↑^4Еx3↑^3K↓^1D Кін.
	Поч. x1↑^1A↓^1↓^2Bx2↑^2C↓^4Dx3↑^3Е↓^3Mx4↑^4 К Кін.
	Поч. x1↑^1A↓^4↓^2Bx2↑^2Cx3↑^3E↓^3Dx4↑^4K↓^1M Кін.
	Поч. ↓^3Ax1↑^1Bx2↑^2C↓^2D↓^1Ex3↑^3Kx4↑^4M↓^4 Кін.
	Поч. x4↑^4Ax1↑^1B↓^2Cx2↑^2D↓^1Ex3↑^3K↓^4M↓^3 Кін.
	Поч. Ax1↑^1Bx2↑^2C↓^2↓^1D↓^3↓^4E Kx4↑^4Mx3↑^3 Кін.
	Поч. Ax1↑^1Bx2↑^2C↓^2D↓^3Ex3↑^3↓^1Kx4↑^4M↓^4 Кін.
	Поч. ↓^2↓^4Ax1↑^1B↓^1Cx2↑^2DEx3↑^3K↓^3Mx4↑^4 Кін.
	Поч. ↓^1Ax1↑^1B↓^4↓^2Cx2↑^2Dx4↑^4E Kx3↑^3M↓^3 Кін.
	Поч. ↓^1Ax1↑^1Bx3↑^3C↓^3Dx4↑^4E↓^2Kx2↑^2M↓^4 Кін.
	Поч. ↓^4Ax4↑^4Bx1↑^1C↓^1Dx3↑^3Ex2↑^2K↓^2M↓^3 Кін.
	Поч. x1↑^1A↓^3Bx2↑^2Cx4↑^4D↓^2↓^4Ex3↑^3K M↓^1 Кін.
	Поч. ↓^4Ax1↑^1B↓^1C↓^2↓^3D Ex2↑^2Kx3↑^3Mx4↑^4 Кін.
	Поч. x1↑^1A↓^3Bx2↑^2Cx4↑^4D↓^4E↓^2K↓^1Mx3↑^3 Кін.
	Поч. x2↑^2A↓^3Bx1↑^1C↓^2Dx4↑^4E↓^1↓^4K Mx3↑^3 Кін.
	Поч. x1↑^1Ax2↑^2B↓^2↓^1Cx4↑^4D↓^3Ex3↑^3K M↓^4 Кін.
	Поч. x1↑^1A↓^2B↓^1Cx2↑^2D↓^3Ex3↑^3↓^4Mx4↑^4 К Кін.
	Поч. x3↑^3Ax2↑^2↓^1Bx1↑^1C↓^2↓^3D↓^4Ex4↑^4M K Кін.

Примітки до таблиці 1.1: В ЛСА символам Поч. та Кін. відповідають початковий і кінцевий оператори алгоритму. Символи A, B, C, D, E, K, M визначають функціональні оператори алгоритму. Символи x₁, x₂, x₃, x₄ визначають логічні умови. Якщо логічна умова рівна одиниці, тоді виконується наступний оператор в ЛСА. Якщо логічна умова рівно нулю, тоді здійснюється перехід по стрілці з відповідним індексом. У логічної умови стрілка направлена вверх. Наприклад, V. У місця переходу стрілка направлена вниз - ΝΛ (Для схеми алгоритму, зображеної на рис.1 ЛСА має вигляд:

Таблиця 1. 2- Імовірності переходу (по Х= 1)

Таблиця 1. 3- Кількість процесорних операцій в операторах (в тисячах)

Таблиця 1. 4- Кількість звернень до файлів та довжина

Примітки до таблиці 1.4: Кількість звернень до файлів - чисельник; довжина запису в кілобайтах - знаменник

Дата добавления: 2015-05-24