Текущая версия |
Ваш текст |
Строка 1: |
Строка 1: |
- | == По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты == | + | == From Ebaums Inc to MurkLoar. == |
- | | + | We at EbaumsWorld consider you as disgrace of human race. |
- | === Определения ===
| + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
- | | + | Dig yourself a grave - you will need it. |
- | '''Ненадежная схема''' — пара (Σ, И), где Σ - собственно схема, а И — источник неисправностей, а соответствующее ей множество схем Σ<sub>1</sub>, …, Σ<sub>s</sub> вместе с теми функциями ƒ<sub>1</sub>, …, ƒ<sub>s</sub>, которые они реализуют.
| + | |
- | | + | |
- | Рассмотрим матрицу ''M'', ''M'' ∈ ''B''<sup>p, s</sup>, где ''M''<i, j> = ƒ<sub>j</sub>(α<sub>i</sub>), считая, что ''i''-й строке (''j''-му столбцу) этой таблицы соответствует набор α<sub>i</sub> (соответственно функция ƒ<sub>j</sub> и состояние Σ<sub>j</sub>).
| + | |
- | | + | |
- | Матрица, состоящая из различных столбцов (строк) называется '''отделимой по столбцам''' (соответственно '''по строкам''').
| + | |
- | | + | |
- | Рассмотрим отделимую по столбцам матрицу ''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''<sup>p,s</sup>, - отделимая по столбцам матрица, а ''N'' - связанная с ней цель контроля. Сопоставим ''i''-й строке матрицы ''M'' переменную ''y''<sub>i</sub>, а каждому набору β, β ∈ ''B''<sup>p</sup>, значений этих переменных (''y''<sub>1</sub>,...,''y''<sub>p</sub>) - множество строк матрицы ''M'' с номерами из множества ''I'' = ''I''(β) ⊆ [1, p], где ''i'' ∈ ''I''(β) тогда и только тогда, когда β<''i''> = 1. Рассмотрим ФАЛ ''F''(''y''), для которой ''F''(β) = 1 тогда и только тогда, когда система строк матрицы ''M'' с номерами из ''I''(β) образуют тест для (''M'',''N''). Эта ФАЛ называется ''функцией теста'' для (''M'',''N'').
| + | |
- | | + | |
- | Сопоставим паре (''M'',''N'') матрицу ''M''‘ из множества ''B''<sup>p,S</sup>, ''S'' = |''N''|, столбцы которой пронумерованы парами из ''N'', а столбец с номером (i, j) получается в результате поразрядного сложения по модулю 2 столбцов с номерами ''i'' и ''j'' матрицы ''M''. При этом строки матрицы ''M'' с номерами из множества ''T'', ''T'' ⊆ [1, p] образуют тест (тупиковый тест, минимальный тест) тогда и только тогда, когда строки матрицы ''M''‘ с номерами из ''T'' образуют покрытие (тупиковое покрытие, покрытие минимальной длины) матрицы ''M''‘.
| + | |
- | | + | |
- | '''Лемма:''' Функция теста ƒ(''y''<sub>1</sub>,...,''y''<sub>p</sub>) для отделимой по столбцам матрицы ''M'', ''M'' ∈ ''B''<sup>p,s</sup>, и цели контроля ''N'' может быть задана с помощью КНФ ƒ(''y''<sub>1</sub>,...,''y''<sub>p</sub>) = ∧<sub>(i, j)∈''N''</sub>( ∨<sub>1 ≤ ''t'' ≤ ''p'', ''M''<t, i>≠''M''<t, j></sub> ''y''<sub>t</sub>)
| + | |
- | | + | |
- | '''Следствие:''' Каждая элементарная конъюнкция вида ''y''<sub>t<sub>1</sub></sub>⋅⋅⋅''y''<sub>t<sub>r</sub></sub> сокращенной ДНФ функции ƒ(''y''<sub>1</sub>,...,''y''<sub>p</sub>), получающаяся из указанной в лемме КНФ в результате раскрытия скобок и приведения подобных, соответствует тупиковому тесту, связанному с множеством ''T'' = {t<sub>1</sub>,...,t<sub>r</sub>} и обратно.
| + | |
- | | + | |
- | ==== Пример ====
| + | |
- | | + | |
- | Построить все тупиковые диагностические тесты для матрицы ''M'':
| + | |
- | {|border="0"
| + | |
- | |0
| + | |
- | |1
| + | |
- | |0
| + | |
- | |-
| + | |
- | |0
| + | |
- | |1
| + | |
- | |1
| + | |
- | |-
| + | |
- | |1
| + | |
- | |0
| + | |
- | |1
| + | |
- | |-
| + | |
- | |1
| + | |
- | |1
| + | |
- | |0
| + | |
- | |-
| + | |
- | |}
| + | |
- | | + | |
- | '''Решение:'''
| + | |
- | | + | |
- | 1. Построим матрицу ''M''‘ столбцы которой равны поразрядной сумме по модулю 2 пар столбцов матрицы ''M'', номера которых соответствуют цели контроля ''N'' = {(1,2), (1,3), (2,3)}:
| + | |
- | {|border="0"
| + | |
- | |1
| + | |
- | |0
| + | |
- | |1
| + | |
- | |-
| + | |
- | |1
| + | |
- | |1
| + | |
- | |0
| + | |
- | |-
| + | |
- | |1
| + | |
- | |0
| + | |
- | |1
| + | |
- | |-
| + | |
- | |0
| + | |
- | |1
| + | |
- | |1
| + | |
- | |-
| + | |
- | |}
| + | |
- | | + | |
- | 2. Построим теперь функцию покрытия матрицы ''M''‘:
| + | |
- | | + | |
- | ƒ(''y''<sub>1</sub>,''y''<sub>2</sub>,''y''<sub>3</sub>,''y''<sub>4</sub>) = (''y''<sub>1</sub> ∨ ''y''<sub>2</sub> ∨ ''y''<sub>3</sub>) ⋅ (''y''<sub>2</sub> ∨ ''y''<sub>4</sub>) ⋅ (''y''<sub>1</sub> ∨ ''y''<sub>3</sub> ∨ ''y''<sub>4</sub>) = ''y''<sub>1</sub>''y''<sub>2</sub> ∨ ''y''<sub>1</sub>''y''<sub>4</sub> ∨ ''y''<sub>2</sub>''y''<sub>3</sub> ∨ ''y''<sub>2</sub>''y''<sub>4</sub> ∨ ''y''<sub>3</sub>''y''<sub>4</sub>
| + | |
- | | + | |
- | 3. Следовательно, тупиковыми диагностическими тестами матрицы ''M'' являются множества её строк с номерами {1,2}, {1,4}, {2,3}, {2,4}, {3,4}.
| + | |
- | | + | |
- | В случае проверяющих тестов на шаге 1 ''N'' = {(1, 2), (1, 3)} и матрица ''M''‘ принимает вид
| + | |
- | {|border="0"
| + | |
- | |1
| + | |
- | |0
| + | |
- | |-
| + | |
- | |1
| + | |
- | |1
| + | |
- | |-
| + | |
- | |1
| + | |
- | |0
| + | |
- | |-
| + | |
- | |0
| + | |
- | |1
| + | |
- | |-
| + | |
- | |}
| + | |
- | | + | |
- | ƒ(''y''<sub>1</sub>,''y''<sub>2</sub>,''y''<sub>3</sub>,''y''<sub>4</sub>) = (''y''<sub>1</sub> ∨ ''y''<sub>2</sub> ∨ ''y''<sub>3</sub>) ⋅ (''y''<sub>2</sub> ∨ ''y''<sub>4</sub>) = ''y''<sub>1</sub>''y''<sub>4</sub> ∨ ''y''<sub>2</sub> ∨ ''y''<sub>3</sub>''y''<sub>4</sub>
| + | |
- | | + | |
- | Таким образом, тупиковыми проверяющими тестами матрицы ''M'' являются множества её строк с номерами {1,4}, {2}, {3,4}.
| + | |
- | | + | |
- | === Построение всех тупиковых тестов по схеме и списку её неисправностей ===
| + | |
- | | + | |
- | ==== Идея решения ====
| + | |
- | | + | |
- | Идея заключается в том, чтобы по функции, реализуемой схемой, и списку неисправностей построить таблицу контроля. В этом случае задача сведется к предыдущей.
| + | |
- | | + | |
- | ==== Пример ====
| + | |
- | | + | |
- | Построить все тупиковые диагностические тесты для схемы, реализующей ФАЛ ƒ(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = (0010 1101), на входах которой может происходить одна из следующих неисправнотей:
| + | |
- | # Инвертирование ''x''<sub>2</sub>
| + | |
- | # Перестановка ''x''<sub>1</sub> и ''x''<sub>3</sub>
| + | |
- | # Подстановка константы 1 вместо ''x''<sub>1</sub> и ''x''<sub>2</sub>
| + | |
- | | + | |
- | '''Решение:'''
| + | |
- | | + | |
- | Построим таблицу значений для функции ƒ, а так же для функций ƒ<sub>1</sub>,ƒ<sub>2</sub>,ƒ<sub>3</sub>, описывающих функционирование в случае неисправностей 1, 2, 3 соответственно.
| + | |
- | * ƒ<sub>1</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = ƒ(''x''<sub>1</sub><span style="text-decoration:overline;">''x''<sub>2</sub></span>''x''<sub>3</sub>)
| + | |
- | * ƒ<sub>2</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = ƒ(''x''<sub>3</sub>''x''<sub>2</sub>''x''<sub>1</sub>)
| + | |
- | * ƒ<sub>3</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = ƒ(11''x''<sub>3</sub>)
| + | |
- | | + | |
- | {|border="1" cellspacing="0"
| + | |
- | |''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>
| + | |
- | |ƒ(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>)
| + | |
- | |ƒ(''x''<sub>1</sub><span style="text-decoration:overline;">''x''<sub>2</sub></span>''x''<sub>3</sub>)
| + | |
- | |ƒ(''x''<sub>3</sub>''x''<sub>2</sub>''x''<sub>1</sub>)
| + | |
- | |ƒ(11''x''<sub>3</sub>)
| + | |
- | |-
| + | |
- | |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''):
| + | |
- | | + | |
- | {|border="0"
| + | |
- | |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''<sub>1</sub>:
| + | |
- | | + | |
- | {|border="0"
| + | |
- | |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)}, ...
| + | |
- | | + | |
- | <!-- Задача из моего варианта первой контрольной. У меня столбец для ƒ<sub>1</sub> в к/р построен неверно, поэтому, уж извините, без ответа. Здесь я этот столбец исправил. -->
| + | |
- | | + | |
- | {{Курс Основы Кибернетики}}
| + | |