Введение
1 Квадратичные модели поиска похожих элементов 10
2 Задачи поиска подмножества векторов 27
2.1 Постановки задач 27
2.2 Несуществование схемы FPTAS для общего случая . 31
2.3 Геометрические основы алгоритмов 32
2.4 Алгоритмы решения задач 36
2.4.1 Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности . 37
2.4.2 Точный псевдополиномиальный алгоритм 40
2.4.3 Схема FPTAS для специального случая 42
2.5 Заключение к главе 49
3 Задачи поиска подпоследовательности векторов 50
3.1 Постановки задач 50
3.2 Алгоритмы решения задач 54
3.2.1 Вспомогательная задача и точный полиномиальный алгоритм её решения 54
3.2.2 2-приближённый полиномиальный алгоритм . 63
3.2.3 Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач 65
3.3 Заключение к главе 67
Заключение 68
Литература
