Математическая энциклопедия - тест

в кибернетике одно из важнейших средств логич. анализа информации. Аппарат Т. первоначально был использован в задаче контроля работы электрич. схем. Позже на основе Т. были разработаны эффективные алгоритмы распознавания образов. Тестовый подход успешно применяется во многих областях математики. Основные задачи с Т. могут быть сформулированы следующим образом.

1. Дана прямоугольная таблица, содержащая s строк и тстолбцов. Строки характеризуются вопросами (признаками) е 1, . . ., es из нек-рого множества Е, столбцы объектами (образами) f1,..., fm из множества F.

В клетке, лежащей на пересечении i-й строки и j-го столбца, находится ответ fj(ei) (значение i-го признака для j-го образа), принадлежащий нек-рому множеству G. Таким образом, поскольку при можно рассматривать j-й столбец как столбец, задающий функцию fj(x). Естественно считать, что столбцы таблицы попарно различны. Так как природа множеств Еи Gсущественного значения не имеет, то в дальнейшем предполагается Е={0, 1, . . ., s-1} и G={0, 1, . . ., k-1}. В нек-рых случаях на множествах Еи G задается частичный порядок Иногда столбцам приписываются вероятности p1, . . ., р т

2. Задается цель логич. анализа таблицы. Для этого фиксируется нек-рое подмножество пар (i, j), номеров столбцов. В частности, если множество Fразбито на классы, то тогда и только тогда, когда fi и fj принадлежат одному классу, Подмножество можно интерпретировать как отношение или как нек-рое свойство.

Имеется два специальных случая: 1) j= 2, . . ., ти f1 выделенная функция (этот случай связан с задачей о проверке), 2) относится к задаче о диагностике (полного различения).

Цель логич. анализа можно сформулировать следующим образом: указать процедуру, к-рая для любых iи j таких, что позволяла бы отличить образ fi от образа fj. Если соответствует разбиению Fна классы, то задача эквивалентна задаче об отнесении произвольно заданной функции f из Fсоответствующему классу. Ниже в основном говорится об этой задаче. Сформулированный вопрос решается тривиально, если полностью известна таблица и все известно о функции f. В реальных задачах получение информации о функции f возможно, но при определенных затратах. Кроме того, для обширного класса задач вся таблица либо не известна, либо настолько велика, что мы не в состоянии с ней оперировать. Поэтому ограничиваются ее нек-рым фрагментом т. н. представительной выборкой, и задачу ставят в эвристич. варианте.

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

Система Твопросов и необходимая для нее информация (ответы), позволяющая распознать свойство наз. тестом исходной таблицы.

В случае безусловных экспериментов обычно под тестом Тпонимают такую совокупность вопросов что для любых (i, j) из найдется и (условие распознавания Для многозначных (и не всюду определенных) таблиц вместо предиката можно использовать другие предикаты.

В случае условных экспериментов тестом Тявляется ориентированное дерево, получающееся из условного эксперимента Эпутем удаления всех концевых ребер и позволяющее распознать свойство Так, в данном выше примере для диагностич. задачи {е 1, е2, е3}будет безусловным тестом; эксперименты Э 2 и Э 3 порождают условные тесты Т 2 и Т 3,а эксперимент Э 1 не приводит к условному тесту.

Для любого множество Т 0={е 1, . .., es}является безусловным тестом (тривиальным Т.). Если таблица имеет большие размеры, тривиальный Т. приводит к очень трудоемкой процедуре логич. анализа. Поэтому возникает вопрос о построении более простых Т. Для этого уточняется понятие сложности l(Т)теста Т. Ниже приведены нек-рые варианты определения сложности для безусловных Т:

l1 (Т)=r, здесь l1 (Т)характеризует лкратность

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985