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

Ключевые слова: поиск подмножеств векторов, помехоустойчивое обнаружение повторяющегося фрагмента, кластерный анализ, дискретная оптимизация, NP-трудная задача, алгоритмы с гарантированными оценками точности.

ACM Classification Keywords: F.2. Analysis of Algorithms and Problem Complexity, G.1.6. Optimization, G2. Discrete Mathematics, I.5.3. Pattern Recognition: Clustering.

Link:

О НЕКОТОРЫХ ТРУДНОРЕШАЕМЫХ ЗАДАЧАХ ПОМЕХОУСТОЙЧИВОГО АНАЛИЗА СТРУКТУРИРОВАННЫХ ДАННЫХ1

Александр Кельманов

http://foibg.com/ibs_isc/ibs-08/ibs-08-p06.pdf