О Некоторых Труднорешаемых Задачах Помехоустойчивого Анализа Структурированных Данных

Abstract

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