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


Итерация параметров методов


Будем считать, что интерфейс содержит методы add, delete и createRoot. У метода add имеются два параметра: вершина, к которой нужно добавить ребенка, и добавляемая вершина. Метод требует, чтобы вершина, к которой добавляется ребенок, существовала. У метода delete имеется один параметр - удаляемая вершина. Можно выделить две разновидности метода: метод удаляет только листовые вершины, метод удаляет все поддерево, корнем которого является заданная вершина. Метод createRoot создает корневую вершину; вершину можно создать, если дерево пусто.

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

Легко видеть, что итерация вершин дерева в качестве параметров методов описывает недетерминированный автомат. На показано обобщенное состояние {0, 1, 1} и два соответствующих ему дерева, которые различаются порядком вершин. В этом обобщенном состоянии переход, соответствующий вызову метода add(C, D) , может переводить автомат как в обобщенное состояние {0, 1, 1, 1} так и в обобщенное состояние {0, 0, 1, 2} в зависимости от дерева, соответствующего исходному обобщенному состоянию.

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

Таким образом, имеем следующие переходы:

  • add(i, A) ;
  • delete(i) ;
  • createRoot(A) ,

где i - элемент мультимножества обобщенного состояния, А - добавляемая вершина.

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

Однако переходы по методу delete по-прежнему оказываются недетерминированными. В примере, показанном на , в состоянии {0, 0, 1, 2} результирующее состояние при удалении вершины без детей зависит от того, сколько было детей у родителя.


Начало  Назад  Вперед