Полная версия

Главная arrow Информатика arrow Введение в курс метрической теории и метрологии программ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ПРОГРАММНАЯ СЛОЖНОСТЬ ЗАДАЧ (объемные характеристики программ)

2.1. Длина программы (алгоритмическая сложность решаемой задачи)

На основании исследований количественных характеристик текстов в лингвистике относительно давно установлен ряд эмпирических закономерностей. Одна из них, так называемый закон Ципфа [6], является зависимостью между частотой появления тех или иных слов в тексте (выбранных из словаря текста) и их рангом. В конце 70-х гг. XX века аналогичные результаты были получены М. Холстедом [4] при изучении текстов программ, написанных на различных алгоритмических языках. Им было найдено соотношение, связывающее общее количество слов в программах с величиной их словарей. Как оказалось, эти закономерности могут быть получены и осмыслены теоретически на основе представлений алгоритмической теории сложности, основные результаты которой приведены выше.

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

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

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

Известно, что энтропия Н имеет максимум, когда все pt равны; в нашем случае

(Здесь л- обозначает не число букв алфавита, как в п. 1.2, а величину словаря программы.)

Поэтому

В этом выражении, относящемся к произвольной последовательности, Nus, вообще говоря, независимы. Однако в случае программы это не так. Действительно, N не может быть меньше 5, так как каждое имя из словаря должно появиться в тексте программы хотя бы один раз. Значит, наименьшее значение Я будет s log s. Следовательно, справедливо равенство

Поскольку тексты программ, как отмечено выше, всегда максимально сжаты, то из условия экстремума АН найдем соотношение между N

us:

откуда следует, что

Это и есть соотношение М. Холстеда между длиной программы (количество слов) и величиной ее словаря, полученное на основе алгоритмической теории сложности.

Так как вторая производная

отрицательна при всех значениях в, то условие максимума АН выполнено.

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

называемую объемом программы и выражаемую в битах.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>