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

* Работа поддержана грантами РФФИ 09-01-00032, 07-07-00022 и грантом АВЦП Рособразования 2.1.1/3235

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