Cтраница 1
Стековый алгоритм является читающим. [1]
Любой детерминированный стековый алгоритм моделируется итеративным алгоритмом, работающим с таблицам прямого доступа и временной сложности О ( п), где п - число всех возможных разных векторов значений переменных, встречающихся в результате выполнения программы. [2]
Этот алгоритм значительно менее эффективен, чем простой стековый алгоритм маркировки, поскольку каждый список должен проходиться не один раз, а два. [3]
Кроме того, область, отводимая под стек, должна быть очень большой, если мы хотим иметь уверенность в том, что сбор мусора всегда сможет быть выполнен без переполнения стека ( см. упр. В итоге оказывается, что стековый алгоритм маркировки не вполне удовлетворителен, хотя концептуально он весьма прост. [4]
В силу леммы 9.3 достаточно ограничиться распознаванием свойств на элементарных 1-окрестностях. Решение поставленной задачи получаем с помощью модификации процедуры ПОИСК, описанной в теореме 9.3. Стековый алгоритм ПОИСК осуществляет последовательный целенаправленный полный перебор методом поиска в глубину всех возможных вариантов выбора регуляторов в элементах ограниченной области. В стеке запоминается пройденный путь вместе с соответствующим выбором регуляторов. Y в последнем подбирается наименьший регулятор такой, что dl и d2, а также d2 и dl согласованы относительно представляющего свойства. Если такого регулятора нет, то, применяя стек, выполняется возврат в dlt в котором выбирается следующий регулятор, согласованный с уже пройденными элементами. [5]
В силу леммы 9.3 достаточно ограничиться распознаванием свойств на элементарных 1-окрестностях. Решение поставленной задачи получается применением к дереву процедуры ПОИСК. Стековый алгоритм ПОИСК осуществляет последовательный целенаправленный перебор типа поиска в глубину всех возможных вариантов выбора регуляторов в вершинах дерева. [6]