Geum.ru

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

Вид материалаТесты

Содержание


D; б) если на матрице D
Подобный материал:
МЕТОД СОЗДАНИЯ МНОЖЕСТВА МИНИМАЛЬНЫХ ТЕСТОВ НА БУЛЕВОЙ ДИАГНОСТИЧЕСКОЙ МАТРИЦЕ ПРИ МАЛЫХ ЗАТРАТАХ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ И ВРЕМЕНИ

Ю.А. Бродская

Россия, Саратов

Потребность в множестве минимальных тестов для диагностирования на заданной булевой матрице возникает, если тесты в таком множестве различаются используемыми ресурсами и их затратами. Уменьшение затрат вычислительных ресурсов при построении минимальных тестов позволяет увеличивать размерность булевой диагностической матрицы («матрицы D»). Здесь m и n – мощности множеств: состояний объекта («СО») и элементарных проверок («ЭП»), соответственно. Известны различные методы создания множеств минимальных тестов [1-4]. В методе, согласно [2], выполняется построение на матрице различий всех тупиковых тестов матрицы D, из которых выбираются тесты с минимальной длиной. Мощность множества всех тупиковых тестов (и, соответственно, количество операций при выборке минимальных тестов) растет экспоненциально с ростом количества ЭП.

Метод, согласно [3], отличается от метода по [2] тем, что минимальные тесты, формируются как кратчайшие покрытия матрицы различий с использованием метода наискорейшего спуска (в общем случае, приближенные). С помощью «метода комбинаторного поиска», реализующего целенаправленный эффективный перебор вариантов покрытий, находятся точные кратчайшие покрытия. В методе, согласно [4], выполняются операции: 1) построение небулевой матрицы различий с размерностью ; 2) вычисление длины минимального теста с помощью эвристического алгоритма; 3) определение на матрицах D и : а) ЭП, для каждой из которых существует хотя бы одна пара СО, различаемых значениями этой ЭП, и только ей; б) ЭП и множеств ЭП мощностью , не принадлежащих тестам с длиной ; 4) определение на матрице D множеств мощностью , не содержащих ЭП и множеств ЭП, выявленных в п/п. 3 «б»; 5) определение на матрице D: а) множеств ЭП, полученных в п.4 и не являющихся тестами; б) того факта, что разность множеств, согласно п.4 и п/п. 5 «а» - есть множество тупиковых тестов длины , следовательно, и множество минимальных тестов. Метод, предлагаемый в докладе, есть усовершенствованный метод из [4], выполняемый при меньших затратах вычислительных ресурсов и времени. Этот метод отличаетсяот метода в [4] тем, что: а) небулева матрица различий не формируется, а задачи, выполняемые на ней в [4], выполняются на матрице D; б) если на матрице D определены ЭП по п/п. 3 «а» вышеприведенного описания метода из [4], то матрица D разбивается на подматрицы, в каждой из которых содержатся СО с одинаковыми значениями множества найденных ЭП; в) для каждой подматрицы выполняются операции по п.2, п/п. 3 «б», п.4, п.5 того же описания.

Множество минимальных тестов матрицы D создается как множество различных, минимальных по мощности объединений минимальных тестов из всех подматриц матрицы D.

Список литературы

1. Соловьев Н.А. Тесты (теория, построение, применение). - Новосибирск: Наука, 1978. – 189 с.

2. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем. // Труды математического института им. В.А.Стеклова, 1958, Т 51. – С. 271-360.

3. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, Гл. ред. физ.-мат. Лит-ры, 1981. – 416 с.

4. Бродская Ю.А. Формирование кратчайших покрытий небулевых матриц при решении задач диагностики// Мат. Шестой междунар. Конф. «Автоматизация проектирования дискретных систем». – Т.1. – Мн.: ОИПИ НАН Беларуси, 2007. – С. 138-145.