Объем программы.

Важной характеристикой программы является ее размер. При переводе алгоритма с одного языка на другой размер программы будет меняться. Изучение этих изменений количественными методами требует, чтобы размер был измеримой величиной.

Кроме того, метрическая характеристика размера должна быть применима к широкому кругу языков без потери общности и объективности и, следовательно, не должна зависеть от набора символов, требуемых для представления алгоритма, то есть символов, практически используемых для записи операторов или имен операндов.

Решение этой проблемы связано с тем, что можно определить абсолютный минимум длины представления самого длинного оператора или имени операнда. Минимальная длина зависит только от числа элементов в словаре h. В общем случае log2 h есть минимальная длина (в битах) всей программы. Под битом здесь понимается логическая единица информации – символ, оператор, операнд – то, чем оперирует программист при создании программы.

Соответствующая метрическая характеристика размера любой реализации какого-либо алгоритма, называемая объемом V, может быть определена как

V = N log2 h (2.2)

где N = N1 + N2 -длина реализации; а h = h1 + h2 - ее словарь.

Очевидно, что если данный алгоритм переводится с одного языка на другой, то его объем меняется. Например, при переводе алгоритма с Паскаля в машинный код какой-либо конкретной машины его объем увеличится. С другой стороны, выражение алгоритма на более развитом языке, нежели тот, на котором он исходно написан, приведет к уменьшению его объема. Последняя возможность чрезвычайно важна и заслуживает специального рассмотрения.

Потенциальный объем V*

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

Обозначив соответствующие программные параметры возможно кратчайшей или наиболее сжатой формы алгоритма звездочками, из уравнения (2.1) получим, что минимальный (или потенциальный ) объем равен

V* = (N1* + N2*) log2(h1* + h2*) (2.3)

Но в минимальной форме ни операторы, ни операнды не требуют повторений, поэтому

N1* = h1* ; N2* = h2*

что дает нам

V* = (h1* + h2*) log2(h1* + h2*)

Кроме того, известно минимально возможное число операторов h1* для любого алгоритма. Каждый алгоритм должен включать один оператор для имени функции или процедуры и один в качестве символа присваивания или группировки, т.е. минимальное значение h1*=2.

Уравнение теперь примет вид:

V* = (2+ h2*) log2( 2+ h2*) , (2.4)

где h2* должно представлять собой число различных входных и выходных параметров.

Из уравнения (3.4) следует, что потенциальный объем V* любого алгоритма не должен зависеть от языка, на котором он может быть выражен. Если h2* расценивается как число единых по смыслу (неизбыточных) операндов, то V* оказывается наиболее полезной мерой содержания алгоритма.

Вернемся к примеру программы для алгоритма Евклида и определим его объем для программ на Паскале и СИ.

Паскаль: V =N * log2 h = 61* log2 18 = 254.4 бита.

СИ: V =N * log2 h = 55* log2 18 = 224.8 бита.

 

Чтобы найти потенциальный объем, нам нужно подсчитать число требуемых входных и выходных параметров. В данном случае это А, В и GCD, так что h2*=3. Следовательно, потенциальный объем:

V* = (2 +h2*) log2( 2 + h2*) = (2+3) log2(2+3) = 11,6 бита

Как уже упоминалось выше, при переводе алгоритма с одного языка на другой его потенциальный объем V* не меняется, но действительный объем V увеличивается или уменьшается в зависимости от развитости рассматриваемых языков. Однако легко заметить, что не может быть гладкого перехода от выражения на потенциальном языке, для которого V = V* , к любому менее развитому языку, для которого V > V*. Такой резкий переход обусловлен тем, что для потенциального языка N*= h* , в то время как для всех других языков применяется уравнение длины и N > h.

 

Лекция 3. Уровень программ. Интеллектуальное содержание программы.

1. Уровень программы.

Понятие уровня программы известно с тех пор, как первые «языки высокого уровня» получили свое название. Однако, прежде чем это понятие сможет применяться в науке, оно должно быть выражено количественно или приведено к измеримому виду, так как в противном случае невозможно определить изменения уровня разных выражений какого либо алгоритма.

Прежде, чем вводить метрическую характеристику уровня программы, необходимо заметить, что уровень языка и уровень программы являются разными понятиями, хотя и тесно связанными. Функциональное соотношение между ними и способы измерения уровня языка будут рассмотрены позднее. Сейчас ограничимся измерением уровня отдельных программ. Ранее выведенные выражения для определения объема V программы и потенциального объема V* подсказывают простой метод количественного выражения данного понятия. Если записать уровень L программы, являющейся реализацией какого либо алгоритма, как

; (3.1)

то лишь наиболее сжатое выражение , какое только возможно для алгоритма, будет иметь уровень, равный единице.

Более объемные реализации будут иметь меньшие значения уровня, так что L£1.

Перестроив выражение (3.1) и выделив независящий от реализации член получим

V* = L´V (3.2)

при увеличении объема уровень программы уменьшается, и наоборот.

Обычно легче написать вызов процедуры, чем саму процедуру. С этой точки зрения проще всего было бы использовать потенциальный язык (L = 1). Однако из самого определения потенциального языка следует, что любая процедура, которая когда либо могла бы понадобиться, в нем уже присутствует. Так как число таких процедур бесконечно, процесс простого ознакомления с их списком тоже бесконечен. Поэтому реализация и использование потенциальных языков невозможны для выполнения реальных заданий.

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

 








Дата добавления: 2015-08-26; просмотров: 2786;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.