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

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

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

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

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

V = N log₂  (2.2)

где N = N₁ + N₂ -длина реализации; а  = ₁ + ₂ - ее словарь.

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

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

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

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

V^* = (N₁^* + N₂^*) log₂(₁^* ₊ ₂^*) (2.3)

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

N₁^* = ₁^* ; N₂^* = ₂^*

что дает нам

V^* = (₁^* ₊ ₂^*) log₂(₁^* ₊ ₂^*)

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

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

V^* = (2₊ ₂^*) log₂( 2₊ ₂^*) , (2.4)

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

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

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

Паскаль: V =N * log₂  = 61* log₂ 18 = 254.4 бита.

СИ: V =N * log₂  = 55* log₂ 18 = 224.8 бита.

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

V^* = (2 +₂^*) log₂( 2 + ₂^*) = (2+3) log₂(2+3) = 11,6 бита

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

6. Понятие уровня программы. Вывод уравнения уровня. Интеллектуальное содержание программы. Несовершенства в программах.

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

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

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

(3.1)

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

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

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

V^* = LV (3.2)

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

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

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

Вывод уравнения уровня программы

Нередко требуется определить уровень программы непосредственно из ее реализации не зная ее потенциального объема V^* и не ссылаясь на возможное обращение к ней в виде вызова процедуры Это можно сделать рассмотрев отдельно влияние операторов и операндов на уровень программы Разумно предположить что чем больше число уникальных операторов используемых в реализации тем ниже ее уровень Но наименьшее возможное число уникальных операторов равно двум и эти два оператора суть символ функции и оператор присваивания или группировки те ₁^*= 2 С другой стороны увеличение числа уникальных операторов беспредельно поскольку на него нет ограничений ни в каком языке в котором разрешено определение новых вложенных процедур подпрограмм или переходов к помеченным участкам Отсюда получаем следующее соотношение операторов: L  (33)

Операнды же не дают однозначного минимума по всем возможным алгоритмам поэтому к ним требуется иной подход В этом случае достаточно заметить что всякое повторение имени операнда является указанием на более низкий уровень реализации Этот эффект можно измерить взяв отношение числа простых операндов к общему числу операндов

L  (34)

Объединяя уравнения (33) и (34), заметим что коэффициент пропорциональности являющийся константой должен равняться единице, поскольку в случае потенциального языка ₁=₁^* ₂=N₂ и L=1. Тогда приходим к уравнению уровня программы

(35)

в котором символ ^ указывает на то что уровень определяемый этим выражением служит аппроксимацией уравнения (31) На самом деле его можно было бы взять в качестве альтернативного определения уровня программы

Возвращаясь к примерам программ для алгоритма Евклида, определим их уровень и его оценку для представлений на Паскале и СИ.

Паскаль: L = V^* / V =11.6 / 254.4 = 0.0456; = 2*₂ /(₁* N₂) = 2*6/(12*21) =0.0476

СИ: L = V^* / V =11.6 / 224.8 = 0.0516; = 2*₂ /(₁* N₂) = 2*6/(11*18) =0.0606 .

Определение интеллектуального содержания программ

Соотношения для объема и уровня программы рассмотренные ранее приводят к интересному выводу Если произведение объема на уровень любого алгоритма действительно не изменяется при выражении его на различных языках то это свойство можно считать фундаментальным И хотя интуитивно ясно что в машинном коде требуется большая степень детализации для того чтобы «сказать то же» что и на языке Паскаль пока еще отсутствует способ позволяющий измерить «сколько» же было сказано в каждом случае Но если постулировать что любые две эквивалентные программы в самом деле «говорят одно и то же» мы сможем ответить на вопрос «сколько?»

Меру того сколько было сказано в программе логичнее было бы назвать информационным содержанием программы но теория информации Шеннона раньше других завладела смыслом этого термина правда для указания лишь объема сообщения без учета его уровня

Поэтому «информационое содержание» программы мы заменим понятием интеллектуального содержания и определим как

I = V (36)

С помощью уравнений (21) и (35) это выражение можно представить в виде

(N₁+N₂) log₂(₁+₂) , (37)

где все члены в правой части доступны непосредственному измерению, исходя из любого выражения алгоритма Интеллектуальное содержание вычисленное с помощью уравнения (3.6) приближенно равно потенциальному объему V^* полученному из уравнения (34). Следовательно поскольку V^* не зависит от языка на котором выражен алгоритм интеллектуальное содержание также не должно от него зависеть 

Эту инвариантность можно продемонстрировать оценив интеллектуальное содержание программ, реализующих алгоритм Евклида на разных языках Выше мы рассмотрели метрики алгоритма Евклида, реализованного на Паскале и СИ (приведены в таблицах 2 и 3). Для этих программ значения интеллектуального содержания будут равны:

Паскаль: I = V = 0.0476 * 254.4 = 12.11;

СИ: I = V = 0.0606 * 224.8 = 13.62;

Теперь рассмотрим существенно отличный от этих двух вариант реализации алгоритма поиска наибольшего общего делителя (НОД), основанный на выборе значений НОД из заранее подготовленной таблицы значений. Пусть в качестве операнда «TABLE» в программу включен массив из 1000 строк и 1000 столбцов содержащий заранее вычисленные значения НОД Тогда алгоритм вычисления сводится к выбору значения НОД из двумерного массива по индексам, равным аргументам функции НОД и может быть представлен в виде:

TABLE 0,1,.........................

0,1,.........................

..............................

GCD := TABLE [A,B]

Подсчет частот для алгоритма вычисления НОД в виде «просмотра таблицы» представлен в табл. 4.

Таблица 4

J	Оператор	f1,j	J	Операнд	f2,j
1		1 000 001	1	TABLE	1 000 001
2		1	2	A	1
3	:=	1	3	B	1
4	[ ]	1	4	CGD	1
1=4		N1=1 000 004	2=4		N2=1 000 004

Соответственно, значение интеллектуального содержания такой программы будет равно

(N₁+N₂) log₂(₁+₂) = 2/4 * 4/1000004 *2*1000004* log₂(8) = 4*3 =12

В потенциальном языке этот алгоритм будет записан в виде одного оператора

GCD(A, B, GCD)  для которого ₁=N₁=2 ₂=N₂=3

И значение интеллектуального содержания программы на потенциальном языке будет

(N₁+N₂) log₂(₁+₂) = 2/2 * 3/3 *5* log₂(5) = 11.6

В табл. 5 указаны данные для всех четырех версий алгоритма Евклида а также вычисленное с помощью уравнения (37) интеллектуальное содержание I .

Таблица 5

Язык	1	2	N1	N	I
Паскаль	10	6	21	52	12.11
СИ	9	6	21	52	13.62
Потенциальный	2	3	3	5	11.6
Просмотр таблицы	4	4	1 000 004	2 000 0088	12

Как и следовало ожидать с уменьшением уровня используемого в реализации алгоритма пропорционально возрастает требуемый объем поэтому интеллектуальное содержание колеблется в пределах приблизительно 10% от его среднего значения { }

Поскольку данное свойство остается неизменным при изменении языка и лишь усиливается с увеличением сложности задачи оно определяет не зависящую от языка меру содержания внутренне присущего программе.

Пока параметры I и V* используются только как вспомогательные величины они являются весьма полезными метрическими характеристиками которые задают меру того «сколько» было сказано но ничего не говорят о важности сказанного То есть программные параметры показывают насколько хорошо написана программа но не определяют нужно ли было вообще ее писать

7. Работа в программировании. Уравнение работы. Расчет времени программирования.

Работа в программировании

Если мы ограничим понятие работы в программировании умственной деятельностью затрачиваемой на превращение заранее разработанного алгоритма в реализацию на языке которым исполнитель свободно владеет то метрические характеристики и понятия введенные выше дадут нам возможность проникнуть в суть процесса программирования и образуют исходную систему для его количественной оценки Простое соотношение между этими метрическими характеристиками и работой выполняемой программистом может быть получено с помощью шести шагов описанных ниже в общих чертах

Вывод уравнения работы

1. Как и ранее допустим что любая реализация какого­­-либо алгоритма заключается в N­-кратном выборе из словаря состоящего из  элементов

2. Предположим далее что каждый выбор из словаря  неслучаен Исследования методов сортировки показали что за исключением хеширования самым быстрым способом поиска в упорядоченном списке является двоичный поиск при котором список многократно делится пополам до тех пор пока не будет найден нужный элемент Полученное в результате число сравнений равно двоичному логарифму числа элементов в списке Следовательно эффективный процесс эквивалентный двоичному поиску  требует log₂ сравнений для нахождения элемента

3. На основании шагов 1 и 2 можно заключить что программа порождается выполнением N  log₂ мысленных сравнений

4. Поскольку объем программы V определяется как

V = N log₂ (41)

из шага 3 следует что он равен числу мысленных сравнений затрачиваемых на порождение программы

5. Каждое мысленное сравнение содержит ряд элементарных мысленных различений число которых является мерой сложности задачи Из предыдущих результатов вытекает что именно уровень программы L является величиной обратной ее сложности

6. Так как объем V равен числу мысленных сравнений а величина обратная уровню программы те 1/L, есть среднее число элементарных мысленных различений входящих в каждое мысленное сравнение общее число элементарных мысленных различений Е требуемых для порождения программы должно задаваться выражением

Е = (42)

Можно выявить более глубокий смысл уравнения работы если вспомнить уравнение (31)

L =

и подставить его в уравнение (42)

E = (43)

Уравнение (43) показывает что мысленная работа по реализации любого алгоритма с данным потенциальным объемом в каждом языке пропорциональна квадрату объема программы Как будет детально показано далее из уравнения (43) следует что так как «квадрат суммы больше суммы двух квадратов» правильное разбиение на модули может уменьшить работу по программированию реализаций разбитых на отдельные части Теперь перейдем от подсчета элементарных мысленных различений к измерению времени

Расчет времени, необходимого для программирования.

Рассмотрим понятие введенное психологом Джоном Страудом в работе «Тонкая структура психологического времени» ДжСтрауд определил «момент» как время требуемое человеческому мозгу для выполнения наиболее элементарного различения Он обнаружил что в течение времени бодрствования человек воспринимает эти «моменты» со скоростью «от пяти до двадцати раз» в секунду Следует отметить что в диапазон приведенных Страудом цифр попадает и число кадров в секунду превращающее кинофильм из последовательности отдельных снимков в непрерывное изображение Обозначая через S число страудовских «моментов» в секунду мы можем записать

5  S  20 в сек

В дальнейшем S называется числом Страуда Естественно что любой человек занимающийся реализацией алгоритма может в зависимости от степени своей сосредото-ченности отвлечь какую-то часть мысленных различений на посторонние предметы Пользуясь терминологией вычислительной техники можно сказать что если он находится «в режиме разделения времени» S представляет собой лишь верхнюю границу С другой стороны если программист выполняет эквивалент машинной операции «запретить все прерывания» и сосредоточивает внимание на программировании то применимо действительное значение S

Для того чтобы перевести в единицы времени уравнение (42) имеющее размерность двоичных разрядов или различений разделим обе его части на число различений в единицу времени В результате получим

T^ = = = (44)

Символ ^ здесь указывает на то что с помощью этого уравнения вычисляется приближенное а не наблюдаемое время программированияУравнение (44) можно выразить через основные параметры если подставить в него вместо V правую часть уравнения (21) а вместо L - правую часть уравнения (35)

T = (45)

При этом естественно =2

В предыдущем выводе подразумевалось что все программы совершенны т е не имеют несовершенств Хотя это допущение более или менее обосновано для опубли-кованных программ оно необязательно Поэтому откажемся от него по крайней мере в первом приближении подставив вместоN в уравнение (45) Если при этом задается уравнением длины приходим к выражению

(46)

где за исключением числа Страуда S все параметры в правой части доступны непосред-ственному измерению для любой реализации алгоритма

8. Уровень языка программирования. Прогнозирование числа ошибок в программах.

Уровень языка.

Материал, изложенный в лекции 3, выявил полезное соотношение между уровнем программы L и ее объемом V. Для любого алгоритма, который переводится с одного языка на другой, с увеличением объема уровень уменьшается в той же пропорции. В результате произведение L на V равняется потенциальному объему V^* данного алгоритма. С другой стороны, если язык реализации остается одним и тем же, а разрешено менять сам алгоритм, имеется другое, но похожее соотношение. В этом случае с увеличением потенциального объема V^* уровень программы L уменьшится в том же отношении. Следовательно, произведение L на V^* остается неизменным для любого языка. Это произведение, называемое уровнем языка, обозначается через  и записывается в виде:

 = LV^* (4.7)

Изменения уровня от языка к языку

Следует ожидатьчто чем более универсальным будет язык общего назначения тем больше проявиться способов его использования для данной цели Поскольку многие из этих способов находятся на различных уровнях  с ростом среднего значения увеличатся и отклонения от него Кроме этой гипотезы вводится еще одна более существенная согласно которой среднее значение полученное на ряде программ свидетельствует о количественном росте при увеличении развитости языка Для проверки второй гипотезы необходимо иметь интуитивно упорядоченный список языков Так, принято считать что Фортран выше языка ассемблера ПЛ-1 выше Фортрана а английский язык еще выше чем ПЛ-1 Результаты, полученные рядом исследователей, рассматривавших реализации одной группы алгоритмов на различных языках, включая английский, сведены в табл.6.

Таблица 6

Язык		Отклонения
Английский	216	0,74
ПЛ-1	1,53	0,92
Алгол	1,21	0,74
Фортран	1,14	0,81
Ассемблер	0,88	0,42