Читайте также:
|
|
Если задана реализация алгоритма на языке программирования, можно идентифицировать все операнды, определенные как переменные или константы, используемые в этой реализации. Аналогично можно идентифицировать все операторы, определенные как символы или комбинации символов, влияющие на значение или на порядок операндов.
Исходя из идентификации операторов и операндов, можно определить ряд измеримых категорий, обязательно присутствующих в любой версии любого алгоритма. Они определяются метриками, с помощью которых могут быть получены основные характеристики качества программ.
В состав измеримых свойств любого представления алгоритма (или программы) могут быть включены следующие метрические характеристики:
h1 - число простых (уникальных) операторов, появляющихся в данной реализации;
h2 - число простых (уникальных) операндов, появляющихся в данной реализации;
N1 - общее число всех операторов, появляющихся в данной реализации;
N2 - общее число всех операндов, появляющихся в данной реализации;
f1j - число вхождений j-го оператора, где j = 1,2,3... h1;
f2j - число вхождений j-го операнда, где j = 1,2,3... h2.
Словарь программы h h = h1 + h2 Длина реализации программы NN = N1 + N2 |
Рассмотрим пример вычисления введенных метрик для программы, реализующей алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух целых чисел. Возможные варианты программы на языках Паскаль и Си приведены в таблице 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, классифицируются как операторы.
Указатель вызова функции или оператор процедуры также являются операторами.
Таблица 2 (для программы на Паскале)
Оператор | I | F1i | Операнд | J | F2j |
; | GCD | ||||
:= | G | ||||
= | R | ||||
() или begin end | A | ||||
If | B | ||||
/ | |||||
* | |||||
- | |||||
GOTO L1 | |||||
GOTO L2 | |||||
Function GCD | |||||
Return | |||||
Измеряемые метрики программы на Паскале будут равны
число простых (уникальных) операторов | η1 = 12 |
число простых (уникальных) операндов | η2 = 6 |
общее число всех операторов | N1 = 40 |
общее число всех операндов | N2 = 21 |
словарь программы h | h = h 1 + h 2 = 18 |
длина реализации программы N | N = N1 + N2 = 61 |
уравнение оценки длины программы h1 log2h1 + h2 log2h2 | 12* log212 + 6* log26 =12* 3,584963 + 6* 2,584963 = 58,52933 (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,56352 ( 53,56)
Литература:
1. Метрология и электрорадиоизмерения в телекоммуникационных системах: Учеб. Для вузов/ В.И. Нефедов, А.С. Сигов, В.К. Битюков, и др. Под ред. В.И. Нефедова и А.С. Сигова. – 3-е изд., перераб. И доп. – М.:Высш. шк., 2005. – 599 с.:ил.
2. Метрология и электрорадиоизмерения в телекоммуникационных системах. Учебное пособие/ Под общей редакцией Б.Н. Тихонова. – 2-е изд., стереотип. – М.: Горячая линия-Телеком, 2012. – 360, с.: ил.
3. Ресурсы Интернета library.tuit.uz.
Дата добавления: 2015-05-05; просмотров: 12 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Методические указания по выполнению контрольной работы по дисциплине | | | КУЛЬТУРА РЕЧИ |