Міністерствоосвіти і науки, молоді та спорту України
Тернопільськийнаціональний технічний університет ім. І.Пулюя
Кафедракомп’ютернихсистем та мереж
Звіт
долабораторної роботи №4
натему Оцінка трудомісткості алгоритму
з дисципліни Комп’ютернісистеми
Виконав:
Студент групи СІ 22
НикорчукВолодимир
Перевірив:
Хомів БогданАрсенович
Тернопіль2011
Частина1.Засвоєння засобів аналізу трудомісткостіобчислювальних алгоритмів
Короткітеоретичні відомості:
Задача, щопідлягає вирішенню на ПК, може бути охарактеризована кількістю даних,складністю алгоритму та його трудомісткістю. Під трудомісткістю алгоритмурозуміється кількість обчислювальної роботи, необхідної для його реалізації.Трудомісткість характеризує витрати часу для реалізації алгоритму на деякійсукупності технічних засобів. Звичайно, трудомісткість оцінюється кількістюпроцесорних операцій та операцій введення-виведення. В загальному випадку,трудомісткість алгоритму є випадковою величиною, що залежить від вхідних даних.Тому, трудомісткість алгоритму може бути визначена тільки наближено, в термінахтеорії ймовірностей: математичним сподіванням, дисперсією і т. д.
Трудомісткістьалгоритму в першому наближенні може бути охарактеризована набором параметрів:
ϴ- середня кількість процесорних операцій, необхідних для однієї реалізаціїалгоритму;
N1,N2 ,…NH – середнякількість запитів до файлів за один прогін програми;
L1,L2 ,…LH-середнякількість інформації, що передається за одне звернення до файлів F1,F2 ,…FH.
При необхідностінабір параметрів, що характеризують трудомісткістю алгоритму може бутидоповнений. Вхідна інформація для розрахунку трудомісткості алгоритму може бутиодержана з блок-схеми алгоритму.
Для розрахункутрудомісткості алгоритму необхідно знати ймовірності переходів з логічнихвершин при одиничному значенні логічної умови. Якщо відповідну ймовірністьвизначити через p,тоді ймовірність виходу з логічної вершини при нульовому логічному значенніумови, що перевіряється буде дорівнювати l-p. Для подальших розрахунків схему алгоритму раціонально зображати в вигляді графаалгоритму. Для цього пропонується перенумерувати всі оператори схеми алгоритму.У логічних операторів замість логічних умов «1» і «0» будемо записувативідповідну даному виходу ймовірність. Ймовірність виходу з операторної вершинидорівнює 1. Граф алгоритму можна істотно спростити, якщо трудомісткістьвиконання логічних вершин незначна в порівнянні з трудомісткістю виконанняоператорних вершин. Тоді стани, що відповідають логічними вершинами, можназлити з станами, що випереджають відповідні операторні вершини.
Хід роботи:
1. Побудоваблок-схеми за логічною схемою алгоритмів.
Поч. X1↑1А/> ВX2↑2С X3↑3/> ЕX4↑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.
Таблиця 2n0= 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+1n4 n5= 4 n6= 0.2n5 n6= 0.8 n7= 0.2 n0+1n6 n7= 1
6. Знаходженнясередньої кількості процесорних операцій за допомогою програмиMicrosoft Excelпоказанана рис.4.
/>
Рисунок 4
7. Знаходженнякількості звернень до файлів та довжин за допомогою програми MicrosoftExcel зображенона рис.5.
/>
Рисунок 5
Частина2.Компіляція програми
Операційнасистема Linuxмаєбагато вбудованих компіляторів, практично під кожну мову програмування високогорівня. Два найбільш поширені компілятори – це gccтаg++для мов програмування С та С++ відповідно. В даній лабораторній роботі явикористовував компілятор g++,з допомогою якого скомпілював програму, що обчислює числа Фібоначчі. Цяпрограма складається з двох файлів lab.cppта fib.h.Перший містить головну функцію програми і слугує для вводу виводу чисел. Другийпроводить математичні операції з числами. Результат виконання програми об’єднуєтьсяі записується в один об’єктний файл lab1.Щоб зібрати всі файли в один, потрібно використати ключ –о, наприклад: g++lab.cppfib.h–o lab1.Виконуємоотриманий файл за допомогою команди ./lab1.
Нижче наведенолістинг програми та скріншот, який показує результат виконання.
Лістинг 2.1 lab.cpp
#include
#include«fib.h»
usingnamespace std;
intmain()
{
longn;
cout>n;
cout
return0;
}
Лістинг 2.2 fib.h
longfibonacci ( long n)
{
if( n == 0)
{
return0;
}
elseif ( n == 1 )
{
return1;
}
Elsereturn fibonacci( n -1) + fibonacci(n-2);}
Висновок
На данійлабораторній роботі я засвоїв засоби аналізу трудомісткості обчислювальногоалгоритму, а також навчився компілювати програми в консольному режимі Linux.