Аннотация:
Рассматриваются достаточно компактные представления недоопределённых данных, позволяющие полностью восстановить исходные данные (а не только их доопределения). Их построение основано на введённых и изученных в данной работе специальных матрицах, названных селективными. Они обобщают широко применяемые в информатике дизъюнктивные матрицы. Исследованы свойства селективных матриц и получены оценки длины представления данных в функции от некоторых параметров. Рассмотрены сложностные вопросы, связанные с построением представлений.
Ключевые слова:недоопределённые данные, сжатие, двоичное представление, базис системы множеств, длина представления, дизъюнктивная матрица, дизъюнктивный код, свободное от покрытий семейство, полиномиальный алгоритм.
Полный текст:
PDF файл (627 kB)