АЛГОРИТМ АНАЛИЗА МАССИВА В ПРОГРАММЕ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОЛЬНЫХ ПРОВЕРОК
В данной статье анализируется два способа анализа алгоритмов программного обеспечения. Первый из них основан на использовании механизма цепи рекурсии (chain recurrences). Данный способ потенциально может существенно упростить задачу анализа в случае возможности представления программы в виде базовой рекурсии (base recurrence), которая позволяет представить выражение под циклом в виде, из которого можно получить значение выражения на i-ой итерации за O(1). Так как в настоящее время эта задача не решена, то метод анализа программ, основанный на цепях рекурсии может быть применен только в ограниченном количестве программ (стоит сказать, что количество таких программ велико), где нет сложных циклов и выражений под ними. Второй способ - это алгоритмический способ анализа. В статье приведена группа алгоритмов, с помощью которой можно выполнять проверку соотношений больше/меньше на произвольном массиве в программе. В качестве апробации был использован алгоритм сортировки вставкой. Приведенная группа алгоритмов проверки состоит из алгоритма определения путей в программе (при этом подразумевается, что пути строятся из расчета, что обратные ребра графа управления (control flow graph) входят в каждый путь только один раз), алгоритма анализа исследуемого соотношения в программе. Последний алгоритм предполагает предварительную обработку данных, которая не рассматривается в статье, но является достаточно простой, а также выполнения проверки соотношения на всей длине массива, без учета его составных частей. Алгоритм проверки может быть модифицирован (основная его часть будет сохранена) для проверки других видов соотношений.