ТЕСТЫ

— одно из важнейших понятий теории распознавания образов. Первоначально их рассматривали в связи с использованием логических методов при поиске неисправностей в электр. схемах. Рассмотрим таблицу, содержащую s строк и столбцов

Данная таблица заполнена символами 0 и 1 так, что ее столбцы попарно различны. Строки этой таблицы можно рассматривать как признаки а столбцы — как образы, характеризуемые функциями тогда и только тогда, когда признак для образа выполнен). Пусть некоторое подмножество пар номеров столбцов. Множество Т признаков , наз. Т. относительно , если для любой пары существует признак , такой, что . Очевидно, что мн-во, содержащее все признаки является Т. (тривиальным Т.). Однако могут существовать и другие Т. Важным типом Т. являются тупиковые Т., т. е. такие Т., которые при удалении любого из признаков превращаются в мн-ва, не являющиеся Т. Среди тупиковых Т. находятся т. н. минимальные Т., т. е. такие, которые содержат наименьшее число признаков. Совершенно очевидно, что процедура опознания, вообще говоря, становится проще, если использовать минимальные Т. Поэтому важным вопросом в теории Т. являются методы построения минимальных Т. Приведем алгоритм построения всех тупиковых Т. Для этого рассматриваем символы как булевы переменные. Далее для каждой пары из находим все признаки на которых отличается от Все полученные символы соединяем знаком а затем берем логич. произведение этих выражений. Потом раскрываем скобки и упрощаем по правилам булевой алгебры. Каждое из произведений дает один из тупиковых Т.

Для таблицы и мн-ва получаем Имеем 5 тупиковых Т. которых два минимальны. Однако эти методы, если они не учитывают «дополнительной» информации, значительно трудоемки.

Среди диагностических задач, связанных с построением Т., отметим два особенно важных типа задач. 1) 9) - содержит все пары . В этом случае Т. наз. диагностическим. Диагностический Т. позволяет отличать каждый образ от каждого. содержит все пары , где — фиксированное число. В этом случае Т. наз. проверяющим. Проверяющий Т. позволяет отличить данный образ Д от всех остальных. Понятие Т. можно обобщить на случай таблиц, заполненных символами и тех, которые могут содержать также и пустые клетки. Т. появляются во многих диагностических задачах.

1. Поиск не иравностей в электрических схемах. Пусть схема (контактная схема или схема из функциональных элементов) имеет входов и один выход и реализует булеву функцию Предположим, что в результате воздействия источника неисправностей она переходит в схемы которые реализуют соответственно булевы ф-ции при этом допустимо, что т. е. две неисправности функционально неразличимы. Пусть система ф-ций, характеризующая все попарно различимые классы неисправностей, и пусть Получаем таблицу из столбцов и строк. Для того, чтобы ответить на вопрос, исправна ли схема или в каком состоянии она находится, необходимо, очевидно, через испытуемую схему «прогнать» наборы и найти значения схемы на выходе и после этого либо сравнить полученный «столбец» с первым столбцом, либо узнать, с каким из столбцов он совпадает. Время для этой процедуры зависит от числа наборов s. Очевидно, что это время уменьшается, если рассматривать не мн-во всех наборов, а какой-либо из тупиковых Т.

2. Диагностические задачи в области медицины. При изучении определенных классов заболеваний появляется таблица, строки которой соответствуют симптомам, а столбцы — видам заболеваний. Очевидно, что если признаки проявляются дискретным образом (например, в показаниях т-ры, кровяного давления и т. п.), то получаем таблицу вышеуказанного типа, причем, если набор признаков достаточно богат, то все столбцы попарно различны. Здесь иптересны две задачи: а) установить, здоров ли данный субъект, исходя из набора возможных признаков заболеваний, б) установить конкретный диагноз. Для решения этих задач полезны Т., поскольку они позволяют быстрее и более обозримо указать решение.

3. Распознавание геометрических образов. Пусть на прямоугольном дискретном табло возмоншо появление двух символов - 0 и 1, каждый из которых может иметь несколько реализаций, отличающихся друг от друга своими размерами и положением. Требуется, задавая «вопросы» о состоянии некоторых конкретных ячеек табло (заштрихована клетка или нет), узнать, какой из символов записан на табло. Перенумеруем все клетки табло символами и для каждого образа 0 и 1 выпишем «столбцы», указывающие, какие клетки в данном образе заштрихованы (1) и какие нет (0). Для решения задачи в качестве мн-ва возьмем такие пары номеров столбцов, что пробегает все номера образа 0, а все номера образа 1. Тупиковые Т., очевидно, позволяют достаточно экономно опознавать образ.

4. Другие задачи. К построению Т. сводятся некоторые игровые задачи, например, игра в «Морской бой», задача о построении миним. дизъюнктивных нормальных форм, задача о поиске неисправностей в автоматах и т. п. Т. позволяют проанализировать логич. связи между признаками и ввести меру важности признаков. Например, можно считать, что важность признака определяют как отношение числа тупиковых Т., в которое данный признак входит, к числу всех тупиковых Т. Установление меры важности признаков полезно в решении прикладных диагностических задач и используется в диагностических задачах геологии, экономики, медицины и т. п. Лит.: Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем. «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Дмитриев А. Н., Журавлев Ю. И., Кренделев Ф. П. О математических принципах классификации предметов и явлений. «Дискретный анализ», 1966, в. 7.

С. В. Яблонский.