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

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

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

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

I = ´V (3.6)

С помощью уравнений (2.1) и (3.5) это выражение можно представить в виде

´(N₁+N₂) log₂(h₁+h₂) , (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

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

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

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

GCD(A, B, GCD) , для которого h₁=N₁=2; h₂=N₂=3.

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

´(N₁+N₂) log₂(h₁+h₂) = 2/2 * 3/3 *5* log₂(5) = 11.6

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

Таблица 5

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

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

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