Длина программы

С использованием рассмотренных программных параметров можно получить уравнение для оценки количественного соотношения между длиной программыN и словарем h. Это уравнение на первый взгляд может показаться несколько неожиданным. Однако тщательный анализ доказывает его правомерность, кроме этого его правильность подтверждается экспериментально.

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

h £ N,

что определяет нижнюю границу для N, выраженную черезh.

Найдем верхнюю границу для N. Разобьем строку длины N на подстроки длины h. Разделенная таким образом программа для ЭВМ оказывается состоящей из N/h операторов длины h каждый. Теперь если мы потребуем, чтобы строка не содержала двух одинаковых подстрок длины h, то появится искомая верхняя граница.

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

Число возможных комбинаций из h элементов взятых по h за раз, хорошо известно из школьного курса математики и составляет

N £ h^h+1

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

N £ h´h₁^h1´h₂^h2

Верхняя граница для этого неравенства должна включать не только упорядоченное множество из N элементов, представляющих исследуемую программу, но и его всевозможные подмножества. Семейство всевозможных подмножеств из N элементов содержит 2^N элементов. Следовательно, мы можем приравнять число возможных комбинаций из операторов и операндов (равное числу подстрок N/h) числу подмножеств из N элементов и выразить длину реализации алгоритма через его словарь. Из уравнения

2^N = h₁^h1´h₂^h2

получаем

N = log₂ (h₁^h1´h₂^h2)

или

N = log₂ h₁^h1 + log₂ h₂^h2

Это дает нам уравнение оценки длины

h₁ log₂h₁ + h₂ log₂h₂ (2.1)

В этом выражении символ N снабдили Ù для того, чтобы отличать вычисленную (теоретическую) оценку длины от значения N полученного в результате непосредственного измерения (опытной длины). Эта оценка соответствует основным концепциям теории информации, по которым частота использования операторов и операндов в программе пропорциональна двоичному логарифму количества их типов. Выражение (2.1) представляет собой идеализированную аппроксимацию измеренной длины N=N₁+N₂ , справедливую для программ, не содержащих несовершенств (стилистических ошибок). Экспериментальные исследования ряда авторов на представительной группе программ показали, что для стилистически корректных программ отклонения в оценке их теоретической длины от опытной не превышают (10-15)% .