В работе рассматриваются конечные двузначные системы проверок (информационные системы), широко используемые в различных приложениях, связанных с решением задач распознавания образов, диагностики неисправностей, дискретной оптимизации. Для произвольной конечной двузначной системы проверок, не содержащей проверок (атрибутов), тождественно равных константе, изучается поведение глобальной функции Шеннона — неулучшаемой верхней оценки минимальной глубины деревьев решений, решающих задачи над данной системой проверок, в зависимости от числа проверок, входящих в описание задачи. В работе рассматривается глобальный подход к исследованию деревьев решений, при котором в деревьях решений допускается использование произвольных проверок из данной системы.

двузначные системы проверок, деревья решений, функции Шеннона

Математические вопросы и теория численных методов