Архив задач олимпиады по математике и криптографии

Диагностика неисправоности

Имеется устройство, преобразующее 3-х битовые комбинации в двоичные символы. Известно, что сейчас устройство или работает правильно (режим ПР), или имеет неисправность одного из 3-х типов (Н1, Н2 и Н3). В таблице указано, какие символы в зависимости от входа устройство выдает при правильной работе, а также при возможных неисправностях. 

вход

ПР

Н1

Н2

Н3

000

0

1

0

0

001

1

1

1

0

010

1

0

0

0

011

1

0

1

1

100

1

1

1

1

101

0

0

0

1

110

1

1

0

1

111

0

1

0

1
Какое наименьшее количество 3-битовых комбинаций (среди которых обязательно должна быть 111) следует подать на вход, чтобы, проанализировав выходные значения, суметь однозначно определить тип неисправности или же убедиться, что устройство работает правильно? Выпишите все (с точностью до перестановки) такие наборы 3-битовых входов.

  • Решение

    • Решение

    Если, например, подать на вход 000, то на выходе мы получим 0, если устройство работает правильно или имеет неисправность типа Н2 или Н3, либо 1, если имеется неисправность Н1. Значит, вход 000 позволяет различить, скажем, неисправности Н1 и Н3, но не позволяет отличить ПР от Н2. Составим таблицу, где для каждого входа укажем, какие пары режимов этот вход различить может (символ 1), а какие – нет (символ 0). 

    вход

    ПР и Н1

    ПР и Н2

    ПР и Н3

     Н1 и Н2

    Н1 и Н3

    Н2 и Н3

    000

    1

    0

    0

    1

    1

    0

    001

    0

    0

    1

    0

    1

    1

    010

    1

    1

    1

    0

    0

    0

    011

    1

    0

    0

    1

    1

    0

    100

    0

    0

    0

    0

    0

    0

    101

    0

    0

    1

    0

    1

    1

    110

    0

    1

    0

    1

    0

    1

    111

    1

    0

    1

    1

    0

    1
    Чтобы определить режим работы устройства, нужно подать на вход такие комбинации, что им соответствующие строки покрывают единицами все столбцы (то есть в каждом столбце есть хотя бы одна единица, стоящая в одной из этих строк). Сразу можно заметить, что входных комбинаций потребуется по крайней мере 3, так как никакие 2 строки не покрывают все столбцы. Вход 111 покрывает 4 столбца. Непокрытыми остаются столбец ПР и Н2 (покрывается входами 010 и 110) и столбец Н1 и Н3 (покрывается входами 000, 001, 011, 101). Таким образом, имеем 8 наборов, по 3 входные комбинации в каждом: 111-{010,110}-{000, 001, 011, 101}.
  • Ответ

    • Ответ

    Минимальное количество входных комбинаций равно 3. Всего 8 наборов: 111-{010,110}-{000, 001, 011, 101}