МІНІСТЕРСТВО освіти и науки, молоді та спорту України
Тернопільський національний технічний університет ім. І.Пулюя
Кафедра комп'ютерних систем та мереж
Звіт
до лабораторної роботи № 4
на тему Оцінка трудомісткості алгоритму
з дісціпліні Комп'ютерні системи
Виконала:
Студент групи СІ 22
Нікорчук Володимир
Перевірів:
Хомів Богдан Арсенович
Тернопіль 2011
Частина 1 . Засвоєння засобів аналізу трудомісткості обчислювальних алгорітмів
Короткі теоретичні Відомості:
Завдання, Що підлягає вірішенню на ПК, Може буті охарактеризована кількістю даніх, складністю алгоритму та Його трудомісткістю. Під трудомісткістю алгоритму розуміється кількість обчіслювальної роботи, необхідної для Його реалізації. Трудомісткість характеризує витрати годині для реалізації алгоритму на деякій сукупності технічних засобів. Звичайний, трудомісткість оцінюється кількістю процесорніх операцій та операцій введення-виведення. У загально випадка, трудомісткість алгоритму є Випадкове завбільшки, Що поклади від вхідніх даніх. Того, трудомісткість алгоритму Може буті визначена Тільки набліжено, в термінах Теорії ймовірностей: математичне сподіванням, дісперсією и т. д.
Трудомісткість алгоритму в Першому набліженні Може буті охарактеризована набором параметрів:
О? - Середня кількість процесорніх операцій, необхідніх для однієї реалізації алгоритму;
N 1 , N 2 , ... N H - середня кількість Запитів до файлів за один прогін прогрів;
L 1 , L 2 , ... L H - середня кількість інформації, Що передається за Одне звернення до файлів F 1 , F 2 , ... F H .
При необхідності набор параметрів, Що характеризують трудомісткістю алгоритму Може буті ДОПОВНЕННЯ. Вхідна ІНФОРМАЦІЯ для розрахунку трудомісткості алгоритму Може буті одержані з блок-схеми алгоритму.
Для розрахунку трудомісткості алгоритму необхідно знати ймовірності переходів з логічніх вершин при одінічному значенні логічної умів. ЯКЩО відповідну ймовірність візначіті через p, тоді ймовірність виходе з логічної вершини при Нульовий логічному значенні Умова, Що перевіряється буде дорівнюваті lp . Для подалі розрахунків схему алгоритму раціонально зображаті в вігляді графа алгоритмом. Для цього пропонується перенумеруваті ВСІ оператори схеми алгоритму. У логічніх Операторів Замість логічніх умів В«1В» и В«0В» будемо запісуваті відповідну даного виходе ймовірність. Ймовірність виходе з операторної вершини дорівнює 1. Граф алгоритму можна істотно спростіті, ЯКЩО трудомісткість виконан логічніх вершин незначна в порівнянні з трудомісткістю виконан операторних вершин. Тоді стани, Що відповідають логічнімі вершинами, можна злить з станами, Що віпереджають відповідні операторні вершини.
Хід роботи:
1. Побудова Блок-схема за логічною схемою алгорітмів.
Поч. X 1 ↑ 1 А В X 2 ↑ 2 З X 3 ↑ 3 Е X 4 ↑ 4 До М Кін.
Блок-схема даного алгоритму зображена на рис.1.
Малюнок 1
2. Побудова графа даного алгоритму з отріманої Вище блок-схеми, Що показано на рис.2.
Малюнок 2
3. Мінімізація графа даного алгоритму, Що показано на рис. 3.
Малюнок 3
4. Подання графа у вігляді стохастічної матріці зображено в табліці1.
алгоритм граф трудомісткість excel
Табліця1
S1
S2
S3
S4
S5
S6
S7
Sk
S0
0.8
0.2
S1
1
S2
0.2
0.8
S3
0.3
0.7
S4
1
S5
0.8
0.2
S6
1
S7
1
5. Розв `язання системи алгебраїчніх рівнянь, Рішення якіх Дає Середнє число Запитів до Операторів, Що показано в табліці 2.
Таблиця 2
n0 =
1
n0 =
1
n1 =
0.8n0 ​​
n1 =
0.8
n2 =
1n1 +0.2 n2 +0.8 n5
n2 =
5
n3 =
0.8n2
n3 =
4
n4 =
0.3n3
n4 =
1.2
n5 =
0.7n3 +1 n4
n5 =
4 ...
