Тест

в кибернетике - одно из важнейших средств логич. Анализа информации. Аппарат Т. Первоначально был использован в задаче контроля работы электрич. Схем. Позже на основе Т. Были разработаны эффективные алгоритмы распознавания образов. Тестовый подход успешно применяется во многих областях математики. Основные задачи с Т. Могут быть сформулированы следующим образом. 1. Дана прямоугольная таблица, содержащая s строк и тстолбцов. Строки характеризуются вопросами (признаками) е 1, . ., es из нек-рого множества Е, столбцы - объектами (образами) f1,..., fm из множества F. f1 f2 fj fm е 1 es В клетке, лежащей на пересечении 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 (Т)характеризует лкратность.