Основы Кибернетики, Алгоритмы решения задач/Задачи на тесты

Материал из eSyr's wiki.

Содержание 1 По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты 1.1 Определения 1.2 Построение всех тупиковых тестов по заданной таблице 1.2.1 Теория 1.2.2 Пример 1.3 Построение всех тупиковых тестов по схеме и списку её неисправностей 1.3.1 Идея решения 1.3.2 Пример

[править] По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты

[править] Определения

Ненадежная схема — пара (Σ, И), где Σ - собственно схема, а И — источник неисправностей, а соответствующее ей множество схем Σ₁, …, Σ_s вместе с теми функциями ƒ₁, …, ƒ_s, которые они реализуют.

Рассмотрим матрицу M, M ∈ B^{p, s}, где M<i, j> = ƒ_j(α_i), считая, что i-й строке (j-му столбцу) этой таблицы соответствует набор α_i (соответственно функция ƒ_j и состояние Σ_j).

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

Рассмотрим отделимую по столбцам матрицу M^ (здесь и далее — M с крышкой), состоящую из различных столбцов матрицы M. Тогда M^ — таблица контроля (Σ, И). Далее, не ограничивая общности рассуждений будем полагать M^ ≡ M.

Пусть помимо таблицы контроля M для модели (Σ, И) задана цель контроля, т.е. указано множество N, состоящее из тех неупорядоченных пар различных чисел отрезка [1, s], для которых пары состояний (столбцов матрицы M) с соответствующими номерами необходимо отличать друг от друга.

Если N состоит из всех возможных пар указанного вида, то целью контроля является диагностика схемы, а если N = {(1,2),...(1,t)}, то - проверка схемы.

Множество строк матрицы M с номерами из T, T ⊆ [1, p], называется тестом для (M, N), если для любой пары (i, j) из N существует t, t ∈ T, такое, что M<t, i> ≠ M<t, j>. Мощность теста называется его длиной.

Тест, который перестает быть тестом при удалении любой своей строки, называется тупиковым.

Тест, имеющий минимальную мощность, называется минимальным.

Если целью контроля является диагностика схемы (проверка исправности схемы), то тест называется диагностическим (проверяющим).

[править] Построение всех тупиковых тестов по заданной таблице

[править] Теория

Пусть M, M ∈ B^p,s, - отделимая по столбцам матрица, а N - связанная с ней цель контроля. Сопоставим i-й строке матрицы M переменную y_i, а каждому набору β, β ∈ B^p, значений этих переменных (y₁,...,y_p) - множество строк матрицы M с номерами из множества I = I(β) ⊆ [1, p], где i ∈ I(β) тогда и только тогда, когда β<i> = 1. Рассмотрим ФАЛ F(y), для которой F(β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I(β) образуют тест для (M,N). Эта ФАЛ называется функцией теста для (M,N).

Сопоставим паре (M,N) матрицу M‘ из множества B^p,S, S = |N|, столбцы которой пронумерованы парами из N, а столбец с номером (i, j) получается в результате поразрядного сложения по модулю 2 столбцов с номерами i и j матрицы M. При этом строки матрицы M с номерами из множества T, T ⊆ [1, p] образуют тест (тупиковый тест, минимальный тест) тогда и только тогда, когда строки матрицы M‘ с номерами из T образуют покрытие (тупиковое покрытие, покрытие минимальной длины) матрицы M‘.

Лемма: Функция теста ƒ(y₁,...,y_p) для отделимой по столбцам матрицы M, M ∈ B^p,s, и цели контроля N может быть задана с помощью КНФ ƒ(y₁,...,y_p) = ∧_{(i, j)∈N}( ∨_{1 ≤ t ≤ p, M<t, i>≠M<t, j>} y_t)

Следствие: Каждая элементарная конъюнкция вида y_t1⋅⋅⋅y_tr сокращенной ДНФ функции ƒ(y₁,...,y_p), получающаяся из указанной в лемме КНФ в результате раскрытия скобок и приведения подобных, соответствует тупиковому тесту, связанному с множеством T = {t₁,...,t_r} и обратно.

[править] Пример

Построить все тупиковые диагностические тесты для матрицы M:

0	1	0
0	1	1
1	0	1
1	1	0

Решение:

1. Построим матрицу M‘ столбцы которой равны поразрядной сумме по модулю 2 пар столбцов матрицы M, номера которых соответствуют цели контроля N = {(1,2), (1,3), (2,3)}:

1	0	1
1	1	0
1	0	1
0	1	1

2. Построим теперь функцию покрытия матрицы M‘:

ƒ(y₁,y₂,y₃,y₄) = (y₁ ∨ y₂ ∨ y₃) ⋅ (y₂ ∨ y₄) ⋅ (y₁ ∨ y₃ ∨ y₄) = y₁y₂ ∨ y₁y₄ ∨ y₂y₃ ∨ y₂y₄ ∨ y₃y₄

3. Следовательно, тупиковыми диагностическими тестами матрицы M являются множества её строк с номерами {1,2}, {1,4}, {2,3}, {2,4}, {3,4}.

В случае проверяющих тестов на шаге 1 N = {(1, 2), (1, 3)} и матрица M‘ принимает вид

1	0
1	1
1	0
0	1

ƒ(y₁,y₂,y₃,y₄) = (y₁ ∨ y₂ ∨ y₃) ⋅ (y₂ ∨ y₄) = y₁y₄ ∨ y₂ ∨ y₃y₄

Таким образом, тупиковыми проверяющими тестами матрицы M являются множества её строк с номерами {1,4}, {2}, {3,4}.

[править] Построение всех тупиковых тестов по схеме и списку её неисправностей

[править] Идея решения

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

[править] Пример

Построить все тупиковые диагностические тесты для схемы, реализующей ФАЛ ƒ(x₁x₂x₃) = (0010 1101), на входах которой может происходить одна из следующих неисправнотей:

1. Инвертирование x₂
2. Перестановка x₁ и x₃
3. Подстановка константы 1 вместо x₁ и x₂

Решение:

Построим таблицу значений для функции ƒ, а так же для функций ƒ₁,ƒ₂,ƒ₃, описывающих функционирование в случае неисправностей 1, 2, 3 соответственно.

• ƒ₁(x₁x₂x₃) = ƒ(x₁x₂x₃)
• ƒ₂(x₁x₂x₃) = ƒ(x₃x₂x₁)
• ƒ₃(x₁x₂x₃) = ƒ(11x₃)

x1x2x3	ƒ(x1x2x3)	ƒ(x1x2x3)	ƒ(x3x2x1)	ƒ(11x3)
000	0	1	0	0
001	0	0	1	1
010	1	0	1	0
011	0	0	0	1
100	1	0	0	0
101	1	1	1	1
110	0	1	0	0
111	1	1	1	1

Перепишем эту таблицу в виде таблицы контроля (матрицы M):

0		0	1	0	0
1		0	0	1	1
2		1	0	1	0
3		0	0	0	1
4		1	0	0	0
5		1	1	1	1
6		0	1	0	0
7		1	1	1	1

Нумерация строк нарочно начинается с 0, чтобы двоичное представление номеров строк соответствовало наборам, которым эти строки соответствуют.

Заметим, что строки 5 и 7 состоят только из 1, т.е. на наборах (101) и (111) все 4 состояния неотличимы. Таким образом можно из матрицы контроля можно эти строки выкинуть. Кроме того, строки 0 и 6 совпадают, так что можно оставить только одну из них. Получается таблица M₁:

0		0	1	0	0
1		0	0	1	1
2		1	0	1	0
3		0	0	0	1
4		1	0	0	0

Итак, задача свелась к предыдущей. Осталось только на последнем шаге вернуться от номеров строк к наборам. При предложенной нумерации нужно всего лишь номера строк перевести в двоичное представление и в ответ записать не номера строк а сами наборы, например {(000), (010), (011)}, ...