Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Измеримые свойства алгоритмов.

Читайте также:
  1. II.Транспортные характеристики грузов. Свойства.
  2. Q.3. Магнитные свойства кристаллов.
  3. VBA. Циклический алгоритм, понятие, основные элементы. Виды циклических алгоритмов.
  4. а) наименьшая частица вещества, которая сохраняет его химические свойства.
  5. Алгоритм. Основные способы описания алгоритмов.
  6. Алгоритм. Способы его описания. Виды алгоритмов.
  7. Алгоритмы и их свойства
  8. Алканы. Строение, свойства, получение и применение
  9. Альдегиды. Способы получения и химические свойства.Изомерия.
  10. Аминокислотный состав белков. Строение, стереохимия, физико-химические свойства и классификация протеиногенных аминокислот.

Если задана реализация алгоритма на языке программирования, можно идентифицировать все операнды, определенные как переменные или константы, используемые в этой реализации. Аналогично можно идентифицировать все операторы, определенные как символы или комбинации символов, влияющие на значение или на порядок операндов.

Исходя из идентификации операторов и операндов, можно определить ряд измеримых категорий, обязательно присутствующих в любой версии любого алгоритма. Они определяются метриками, с помощью которых могут быть получены основные характеристики качества программ.

В состав измеримых свойств любого представления алгоритма (или программы) могут быть включены следующие метрические характеристики:

 

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 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Методические указания по выполнению контрольной работы по дисциплине| КУЛЬТУРА РЕЧИ

lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав