А. О. Савинский, “Сложность восстановления матриц рейтингов рекомендательных систем”, Интеллектуальные системы. Теория и приложения, 2015, том 19, выпуск 3,страницы 5

Часть 1. Общие проблемы теории интеллектуальных систем

Сложность восстановления матриц рейтингов рекомендательных систем

А. О. Савинский

Аннотация: В работе строится математическая модель рекомендательных систем. Приводятся оценки числа типов пользователей в матрице пользователей. Доказывается NP-трудность задач поиска представителя и перечисления матриц пользователей в общем случае и приводится полиномиальный алгоритм поиска представителя матриц пользователей в случае, когда число типов пользователей равно двум.

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