Тестирование софта - статьи


         

отсутствуют такие стимулы, что из


отсутствуют такие стимулы, что из некоторой группы состояний переходы по этому стимулу ведут в состояния нескольких разных групп). При этом иногда можно считать, что различия между состояниями в рамках одной группы гораздо меньше, чем между состояниями различных групп, и поэтому прежде всего важно протестировать поведение системы относительно разных групп ее состояний. В имеющейся литературе универсальные покрывающие слова практически не упоминаются, в отличии от слов де Бройна. Некоторое количество работ посвящено аналогу универсальных покрывающих слов глубины 0 (т.е. покрывающих все состояния) для неориентированных графов под именем универсальных обходящих последовательностей (universal traversal sequences, введены Куком, S. A. Cook, в конце 70-х годов прошлого века). Фокусом внимания этих работ является не собственно построение таких последовательностей, а одна из проблем теории сложности алгоритмов — как соотносятся классы сложности P-log-SPACE детерминированных алгоритмов, требующих полиномиально-логарифмической памяти, и NP-log-SPACE недетерминированных алгоритмов с такими же требованиями к памяти. Дело в том, что задача построения пути между двумя произольными вершинами графа является примером NP-log-SPACE задачи, а универсальная обходящая последовательность дает детерминированный алгоритм решения для нее. Тем самым верхние и нижние границы длины универсальных обходящих последовательностей задают правила преобразования сложности NP-log-SPACE алгоритма для решения некоторой задачи в сложность P-log-SPACE алгоритма для нее же. В первой известной автору статье [33], в которой появилось понятие универсальной обходящей последовательности, было показано, что для любых m, k ? 1 существует универсальная обходящая последовательность для m-регулярных неориентированных графов с k вершинами длины O(m2k3log k), а при m = 2 даже O(k3). Для ориентированного случая, который нас интересует, все обстоит несколько сложнее — длина универсальных покрывающих слов как минимум экспоненциальна в зависимости от k.

Содержание  Назад  Вперед