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

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

Перейти к: навигация, поиск

Содержание

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

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

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

Рассмотрим матрицу M, MBp, s, где M<i, j> = ƒji), считая, что 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, tT, такое, что M<t, i> ≠ M<t, j>. Мощность теста называется его длиной.

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

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

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

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

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

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

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

Лемма: Функция теста ƒ(y1,...,yp) для отделимой по столбцам матрицы M, MBp,s, и цели контроля N может быть задана с помощью КНФ ƒ(y1,...,yp) = ∧(i, j)∈N( ∨1 ≤ tp, M<t, i>≠M<t, j> yt)

Следствие: Каждая элементарная конъюнкция вида yt1⋅⋅⋅ytr сокращенной ДНФ функции ƒ(y1,...,yp), получающаяся из указанной в лемме КНФ в результате раскрытия скобок и приведения подобных, соответствует тупиковому тесту, связанному с множеством T = {t1,...,tr} и обратно.

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

Построить все тупиковые диагностические тесты для матрицы 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‘:

ƒ(y1,y2,y3,y4) = (y1y2y3) ⋅ (y2y4) ⋅ (y1y3y4) = y1y2y1y4y2y3y2y4y3y4

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

ƒ(y1,y2,y3,y4) = (y1y2y3) ⋅ (y2y4) = y1y4y2y3y4

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

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

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

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

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

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

  1. Инвертирование x2
  2. Перестановка x1 и x3
  3. Подстановка константы 1 вместо x1 и x2

Решение:

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

  • ƒ1(x1x2x3) = ƒ(x1x2x3)
  • ƒ2(x1x2x3) = ƒ(x3x2x1)
  • ƒ3(x1x2x3) = ƒ(11x3)
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 совпадают, так что можно оставить только одну из них. Получается таблица M1:

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)}, ...



Основы Кибернетики


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

пт пт пт пт пт
Февраль
09 16 26
Март
02 09 16 23 30
Апрель
06 13 20 27
Май
04 11 18 25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Личные инструменты
Разделы