Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Вимірювання властивостей алгоритмів
Лабораторна робота №5.
Оцінювання якості розробки програм на основі метрик Холстеда.
Вимірювання властивостей алгоритмів.
Якщо задана реалізація алгоритму на деякій мові можна ідентифікувати всі операнди, визначені як змінні або константи, що використовуються в цій реалізації. Аналогічно можна ідентифікувати всі оператори, визначені як символи або комбінації символів, що впливають на значення або на порядок операндів. Виходячи з ідентифікації операторів і операндів, можна визначити ряд вимірних категорій, обов'язково присутніх у будь-якій версії будь-якого алгоритму. Вони визначаються метриками, за допомогою яких можуть бути отримані основні характеристики якості програм.
До складу вимірних властивостей будь-якого подання алгоритму (або програми) можуть бути включені наступні метричні характеристики:
- число простих (унікальних) операторів, що з’являються в даній реалізації;
- число простих (унікальних) операндів, що з’являються в даній реалізації;
- загальне число всіх операторів, що з’являються в даній реалізації;
- загальне число всіх операндів, що з’являються в даній реалізації;
- число входжень j оператора, де j=1,2,3,… ;
- число входжень j оператора, де j=1,2,3,… ;
Відштовхуючись від цих основних метричних характеристик для програми, зручно визначити:
словник 
та довжину 
реалізації програми.
Відповідно до даних визначеннями повинні виконуватися наступні три співвідношення:
Розглянемо приклад обчислення введених метрик для програми, що реалізує широко відомий алгоритм Евкліда знаходження найбільшого загального дільника (НЗД) двох цілих чисел. Можливі варіанти програми на мовах Паскаль і С наведені в таблиці 1.
Таблиця 1
| Програма на Паскалі | Програма на С |
| Function GCD (a,b: integer): integer; Label L1, L2; Var G, R: integer; Begin If (a=0) then L1: begin GCD:= b; return end; If (b=0) then Begin GCD:= a; return end; L2: G:= a/b; R:= a - b*G; If (R=0) GOTO L1; a:=b; b:=R; GOTO L2; End. | Int gcd (int a, int b) { int G; int R; if (!a) return (b); if(!b) return (a); while(1) { G = a/b; R = a – b*G; If (R) { a = b; b = R; } else return (b); } } |
Результати підрахунку числа типів операторів і операндів і їх загальної кількості зведені в таблицю 2 для програми на Паскалі і в таблицю 3 для програми на С. При підрахунку використовувалися наступні міркування.
Щодо класифікації операторів інтуїтивно зрозуміло, що символи:
:= знак присвоєння;
= знакрівності (або знак присвоювання у програмі на С);
-- знак віднімання;
/ знак ділення;
* знак множення
відповідають їх звичайному визначенню.
Пара, що складається з дужок відкриванння і закривання (), {} класифікується як один оператор групи. Оскільки пара слів, Begin... End виконує таку ж функцію групування, вона класифікується як такий же самий оператор. Мітки L1 і L2 - не змінні і не константи, тому вони не є операндами. Отже, вони повинні бути операторами або їх складовими частинами. Комбінація GO TO імітки L1 визначає хід виконання програми шляхом задання для неї лічильника або вказівника коду; ця комбінація класифікується як один оператор. Мітка, що не використовується трактується всього лише як коментар, тому її присутність в програмі не обов’язкова. Обмежувач; (крапка з комою) також визначає хід виконання програми (простим просуванням лічильника), що дозволяє класифікувати точку з комою як оператор. По тій ж причині всі керуючі структури, наприклад IF, IF... THEN... ELSE, DO... WHILE, класифікуються як оператори. Показник виклику функції або оператор процедури також є операторами. Крім того, можливість задання помічених ділянок та введення нових функцій усувають будь-які обмеження на зростання величини h 1 (числа типів операторів), які в іншому випадку могли б бути накладені набором команд машини або розробкою мови.
| Оператор | I | F1i | Операнд | J | F2j |
| ; | GCD | ||||
| := | G | ||||
| = | R | ||||
| () або begin end | A | ||||
| If | B | ||||
| / | |||||
| * | |||||
| - | |||||
| GOTO L1 | |||||
| GOTO L2 | |||||
| Function GCD | |||||
| Return |
Таблиця 2
Відповідно, вимірні метрики програми на Паскалі будуть дорівнювати:
η1 = 12; N1 = 40; η2 = 6; N2 = 21; η = 18; N = N1 + N2 = 61; 
58,53
Таблиця 3
| Оператор | I | F1i | Операнд | J | F2j |
| ; | GCD | ||||
| = | G | ||||
| , | R | ||||
| () або {} | A | ||||
| If | B | ||||
| / | |||||
| * | |||||
| - | |||||
| ! | |||||
| Int GCD | |||||
| Return |
Відповідно, вимірні метрики програми на С будуть рівні:
η1 = 11; N1 = 37; η2 = 6; N2 = 18; η = 17; N = N1 + N2 = 55; 53,56
Date: 2015-07-11; view: 321; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |