О. А. Кутненко, А. В. Плясунов, “NP-трудность некоторой задачи цензурирования данных”, Дискретн. анализ и исслед. опер., 2021, том 28, выпуск 2,страницы 60

NP-трудность некоторой задачи цензурирования данных

О. А. Кутненко^ab, А. В. Плясунов^ab

^a Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
^b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Доказана NP-трудность рассматриваемой в работе постановки задачи цензурирования данных. К решению такой задачи сводится одна из проблем анализа данных. В качестве количественной оценки компактности образа используется функция конкурентного сходства (FRiS-функция), с помощью которой оценивается локальное сходство объектов со своими ближайшими соседями. Ил. 1, библиогр. 23.

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

УДК: 519.87+519.854

Статья поступила: 10.06.2020
Переработанный вариант: 22.12.2020
Принята к публикации: 24.12.2020

DOI: 10.33048/daio.2021.28.692