7. Найти минимальное число точек контроля, обеспечивающих поиск неисправностей в системе с точностью до блока.

Граф является упорядоченным.

По данному графу, представляющему систему, построим матрицу смежности:

	1	2	3	4	5	6	7	8
1				1		1
2				1	1
3				1		1
4							1	1
5							1
6							1	1
7
8

С=

Матрица C, также как и граф, является упорядоченной. Строим по матрице смежности матрицу достижимости графа:

	1	2	3	4	5	6	7	8
1	1			1		1	1	1
2		1		1	1		1	1
3			1	1		1	1	1
4				1			1	1
5					1		1
6						1	1	1
7							1
8								1

D =

По матрице достижимости определим все возможные проверки, учитывая, что входными узлами являются элементы 1, 2, 3 а точками контроля – выходы элементов 7 и 8:

(1, 7); (1, 8); (2, 7); (2, 8); (3, 7); (3, 8)

Построим матрицу проверок по матрице достижимости (строка b(i,j) матрицы B получается побитовым умножением строки i на столбец j в матрице достижимости):

	1	2	3	4	5	6	7	8
b(1,7)	1	0	0	1	0	1	1	0
b(1,8)	1	0	0	1	0	1	0	1
b(2,7)	0	1	0	1	1	0	1	0
b(2,8)	0	1	0	1	0	0	0	1
b(3,7)	0	0	1	1	0	1	1	0
b(3,8)	0	0	1	1	0	1	0	1

B=

Судя по матрице проверок, неразличимых дефектов на данном множестве контрольных точек нет.

8. Построить последовательную и комбинационную программы поиска одиночных дефектов в системе.

Исходная матрица проверок :

	1	2	3	4	5	6	7	8
b(1,7)	1	0	0	1	0	1	1	0
b(1,8)	1	0	0	1	0	1	0	1
b(2,7)	0	1	0	1	1	0	1	0
b(2,8)	0	1	0	1	0	0	0	1
b(3,7)	0	0	1	1	0	1	1	0
b(3,8)	0	0	1	1	0	1	0	1

B =

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

	1	2	3	4	5	6	7	8
b(1,7)	1	0	0	1	0	1	1	0
b(1,8)	1	0	0	1	0	1	0	1
b(2,7)	0	1	0	1	1	0	1	0
b(2,8)	0	1	0	1	0	0	0	1
b(3,7)	0	0	1	1	0	1	1	0
b(3,8)	0	0	1	1	0	1	0	1

B^*=

Построим последовательную процедуру поиска одиночных дефектов.

За исходную матрицу проверок возьмем матрицу B^*. В качестве первой выберем проверку, которая разбивает все множество возможных дефектов на примерно равные подмножества. В данном случае это проверка b(2,8).

1)Если результат проверки b(2,7) равен 1, то получим матрицу:

	1	3	6	8
b(1,7)	1	0	1	0
b(1,8)	1	0	1	1
b(2,8)	0	0	0	1
b(3,7)	0	1	1	0
b(3,8)	0	1	1	1

B₁^(2,1)=

1.1)Если результат проверки b(3,7) равен 1, то получим матрицу:

	1	8
b(1,7)	1	0
b(1,8)	1	1
b(2,8)	0	1
b(3,8)	0	1

B₁^(3,7)=

1.1.1)Следующая проверка b(1,7). Если результат этой проверки равен 1, то неисправен блок 8, иначе неисправен блок 1.

1.2)Если результат проверки b(3,7)равен 0, то получим матрицу:

	3	6
b(1,7)	0	1
b(1,8)	0	1
b(2,8)	1	1
b(3,8)	1	1

B₀^(3,7)=

1.2.1)Следующая проверка b(1,8). Если результат этой проверки равен 1, то неисправен блок 3, иначе неисправен блок 6.

2)Если результат проверки b(2,7) равен 0, то получим матрицу:

	2	4	5	7
b(1,7)	0	1	0	1
b(1,8)	0	1	0	0
b(2,8)	1	1	0	0
b(3,7)	0	1	0	1
b(3,8)	0	1	0	0

B₀^(2,7)=

2.1)Если результат проверки b(2,8) равен 1, то то получим матрицу:

	5	7
b(1,7)	0	1
b(3,7)	0	1
b(3,8)	0	0

B₁^(2,8)=

2.1.1)Следующая проверка b(1,7). Если результат этой проверки равен 1, то неисправен блок 5, иначе неисправен блок 7.

2.2) Если результат проверки b(2,8) равен 0, то получим матрицу:

	2	4
b(3,7)	0	1
b(3,8)	0	1

B₀^(2,8)=

14)Следующая проверка b(3,8). Если ее результат равен 1, то неисправен блок 2, иначе неисправен блок 4.