Реклама:

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

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

Программная сложность модулей. Программные модули являются наиболее простыми компонентами в КП, поэтому наиболее доступны для количественного анализа сложности. Исследования сложности программных модулей развиваются по двум направлениям 165, 86, 37] и позволяют оценить основные характеристики, от которых она зависит. Первое направление (структурное) базируется на исследовании внутренней структуры модулей и на обобщении их характеристик с целью получения значений сложности. При ^том наибольшее внимание уделяется анализу маршрутов исполнения программ И объему тестов, необходимых для проверки структуры программных модулей при тестировании.

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

Структурная сложность программ определяется числом взаимодействующих компонент, числом связей между компонентами и сложностью их взаимодействия. При функционировании программы разнообразие ее поведения и разнообразие связей входных и результирующих данных 6 значительной степени определяются набором путей-маршрутов, по которым исполняется программа. Установлено [86], что сложность программного модуля зависит не столько от размера программы (числа команд), сколько оТ числа отдельных путей ее исполнения, существующих в программе. Все маршруты возможной обработки данных должны быть проверены при создании программы и. тем самым определяют сложность ее тестирования,


⇐ Предыдущая страница| |Следующая страница ⇒