Построение безусловных тестов

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

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

Рассмотрим на том же примере синтез безусловных тестов и оценим стоимость тестирования.

При синтезе безусловного теста с безусловной остановкой критерием оптимального теста является его минимальная длина (минимальное количество элементарных проверок) при минимальной стоимости самих проверок. Учитывать при этом вероятности отдельных состояний объекта нет смысла.

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

Следуя этому критерию, в качестве первой должна быть взята проверка, содержащая 5 или 6 единиц (т.к. всего состояний 11). Таких проверок 5: p₆, p₇, p₉, p₁₁ и p₁₂. Очевидно должна быть выбрана самая дешевая из них, т.е. p₆. Она разделит все множество состояний на две группы: 1:(S₁, S₄, S₅, S₈, S₁₀) и 0: (S₂, S₃, S₆, S₇, S₉,S₁₁).

Следующая проверка должна разделять каждую из этих групп тоже на примерно равные части. Для наглядности перепишем таблицу состояний, сгруппировав все состояния в указанные две группы и вычеркнув проверку p₆. Получим табл. 3.3. Поскольку первая группа содержит 5 состояний, а вторая 6, то, очевидно наилучшими будут проверки содержащие по три единицы в каждой группе или в первой группе две единицы, а во второй три.

Таблица 3.4

Таблица состояний после первого шага.

Из табл. 3.3 видно, что таких проверок 4: p₇, p₉, p₁₁ и p₁₂. Очевидно надо выбрать проверку p₇ как самую дешевую. По ее результатам разделим каждую группу на две подгруппы и, в соответствии с этим перепишем таблицу состояний (см. Табл. 3.4).

Таблица 3.4.

Таблица состояний после второго шага.

Теперь все состояния оказались разделенными на 4 подгруппы, три из которых содержат по 3 состояния, а четвертая – два. Очевидно, что третья проверка должна каждую из этих подгрупп делить на две части. Этому условию отвечают проверки: p₁, p₂, p₁₁. Выбираем самую дешевую – p₁ и, в соответствии с ее результатами переписываем таблицу состояний (см. табл. 3.5).

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

Таблица 3.5

Таблица состояний после третьего шага.

\подгруппах. Это проверки: p₂, p₄, p₅, p₉, p₁₀ и p₁₂. Выбираем самую дешевую – p₂. Она разделяет (S₁,S₁₀) и (S₂,S₆). Неразделенной остается лишь подгруппа (S₃,S₉). Ее разделяют проверки p₄, p₁₀, p₁₁, p₁₂. Выбираем в качестве последней проверки самую дешевую из них – p₄. Итак, тест построен, он содержит пять проверок: p₆, p₇, p₁, p₂ и p₄.

Опознавателями диагностируемых состояний являются результаты этих проверок. Они сведены в таблицу 3.6.

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

Таблица 3.6.

Опознаватели диагностируемых состояний.

Поскольку тест в нашем случае на одну проверку длиннее, чем минимально необходимо (для получения 11 различных двоичных комбинаций минимально необходимо 4 двоичных разряда), то имеет смысл проверить, не окажется ли дешевле тест, получаемый с помощью самых дешёвых проверок, даже если он окажется ещё длиннее. Поэтому попробуем составить тест из самых дешёвых проверок p₁, p₂, p₃, p₄ , …

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

Таблица 3.7

Разбиение таблицы состояний после первого шага (проверка p₁).

Таблица 3.8

Разбиение таблицы состояний после второго шага (проверка p₂).

Таблица 3.9

Разбиение таблицы состояний после третьего шага (проверка p₃)

Таблица 3.10.

Разбиение таблицы состояний после четвертого шага

(проверка p₄).

Таблица 3.11

Разбиение таблицы состояний после пятого шага (проверка p₅)

Таким образом, и в этом случае мы получили тест длинной в 5 проверок, но поскольку это самые дешевые проверки, то и стоимость тестирования будет ниже, чем в предыдущем случае:

С=Сp₁+ Сp₂+ Сp₃+ Сp₄+ Сp₅=22+25+27+31+35=140

Очевидно, что из любого безусловного теста с безусловной остановкой может быть получен безусловный тест с условной остановкой. Но чтобы подсчитать его эффективность надо учитывать вероятности отдельных состояний, которые не принимались в расчет при построении безусловных тестов с безусловной остановкой. Поэтому полученные из них тесты с условной остановкой не будут самыми эффективными. Тем не менее выигрыш в стоимости тестирования мы и в этом случае должны получить.

Действительно для первого из построенных тестов средняя стоимость тестирования составит

C_ср=(Cp₆+Cp₇+Cp₁)×(p₈+p₅+p₄+p₇+p₁₁)+(Cp₆+Cp₇+Cp₁+Cp₂)×(p₁+p₁₀+p₂+p₆)+(Cp₆+Cp₇+Cp₁+Cp₂+Cp₄)×(p₃+p₉);

C_ср=(38+43+22)×(0.0238+0.0406+0.0045+0.0031+0.0012)+(38+43+
+22+25)×(0.7713+0.0857+0.0061+0.0018)+(38+43+22+25+31)×

(0.058+0.0026)=103×0.0732+128×0.8649+159×0.0606=7.54+110.7+

+7.76=126

А для второго теста

C_ср=(Cp₁+Cp₂+Cp₃)×(p₇+p₈)+(Cp₁+Cp₂+Cp₃+Cp₄)×(p₃+p₄+p₁₁)+(Cp₁+Cp₂+Cp₃+Cp₄+Cp₅)×(p₁+p₉+p₂+p₅+p₆+p₁₀)=(22+25+27)×(0.0045+0.0031)+(22+25+27+31)×(0.0580+0.0406+0.0012)+(22+25+27+31+35)×(0.7713+0.0026+0.0857+0.0238+0.0061+0.0018)=74×0.0071+105×0.0998+140×0.8913=0.525+10.48+124.78=135.8

Отсюда видно, что хотя стоимость тестирования для первого теста с безусловной остановкой выше, чем для второго (соответственно 159 и 140), но у построенных из них тестов с условной остановкой соотношение средних стоимостей тестирования будет обратной (126 и 135.8), хотя ни тот, ни другой не будут наиболее эффективными, т.к. при их построении не учитывались вероятности диагностируемых состояний объекта.

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