ТЕСТ

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

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

	f1	f2		fj		fm
е 1
es

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

2. Задается цель логич. анализа таблицы. Для этого фиксируется нек-рое подмножество пар (i, j), номеров столбцов. В частности, если множество Fразбито на классы, то тогда и только тогда, когда f_i и f_j принадлежат одному классу, Подмножество можно интерпретировать как отношение или как нек-рое свойство.
Имеется два специальных случая: 1) j= 2, . . ., ти f₁ - выделенная функция (этот случай связан с задачей о проверке), 2) относится к задаче о диагностике (полного различения).
Цель логич. анализа можно сформулировать следующим образом: указать процедуру, к-рая для любых iи j таких, что позволяла бы отличить образ f_i от образа f_j. Если соответствует разбиению Fна классы, то задача эквивалентна задаче об отнесении произвольно заданной функции f из Fсоответствующему классу. Ниже в основном говорится об этой задаче. Сформулированный вопрос решается тривиально, если полностью известна таблица и все известно о функции f. В реальных задачах получение информации о функции f возможно, но при определенных затратах. Кроме того, для обширного класса задач вся таблица либо не известна, либо настолько велика, что мы не в состоянии с ней оперировать. Поэтому ограничиваются ее нек-рым фрагментом - т. н. представительной выборкой, и задачу ставят в эвристич. варианте.

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

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


В случае безусловных экспериментов обычно под тестом Тпонимают такую совокупность вопросов что для любых (i, j) из найдется и (условие распознавания Для многозначных (и не всюду определенных) таблиц вместо предиката можно использовать другие предикаты.
В случае условных экспериментов тестом Тявляется ориентированное дерево, получающееся из условного эксперимента Эпутем удаления всех концевых ребер и позволяющее распознать свойство Так, в данном выше примере для диагностич. задачи {е ₁, е₂, е₃}будет безусловным тестом; эксперименты Э ₂ и Э ₃ порождают условные тесты Т ₂ и Т ₃,а эксперимент Э ₁ не приводит к условному тесту.
Для любого множество Т ₀={е ₁, . .., e_s}является безусловным тестом (тривиальным Т.). Если таблица имеет большие размеры, тривиальный Т. приводит к очень трудоемкой процедуре логич. анализа. Поэтому возникает вопрос о построении более простых Т. Для этого уточняется понятие сложности l(Т)теста Т. Ниже приведены нек-рые варианты определения сложности для безусловных Т:
l₁ (Т)=r, здесь l₁ (Т)характеризует лкратность