4551
правка
Задача о кратчайшем векторе: различия между версиями
Материал из WEGA
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 19:17, 26 марта 2022
, 26 марта 2022→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
'''Определение 2 (Задача о ближайшем векторе, <math>CVP_\gamma</math>)'''. Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка t. Требуется найти вектор решетки <math>\mathbf{Bx}</math> (где x | '''Определение 2 (Задача о ближайшем векторе, <math>CVP_\gamma</math>)'''. Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка <math>\mathbf{t}</math>. Требуется найти вектор решетки <math>\mathbf{Bx}</math> (где <math>\mathbf{x} \in \mathbb{Z}^n</math>), такой, что <math>\parallel \mathbf{Bx - t} \parallel \le \gamma \cdot \parallel \mathbf{By - t} \parallel </math> для любого <math>\mathbf{y} \in \mathbb{Z}^n</math>. | ||
Решетки веками исследовались математиками на эквивалентном языке квадратичных форм; они являются основным объектом изучения в геометрии чисел – направлении, предложенном Минковским в качестве связующего звена между геометрией и теорией чисел. Математическое введение в решетки см. в работе [3]. В [6, 12] дается введение в решетки с акцентом на вычислительные и алгоритмические вопросы. | Решетки веками исследовались математиками на эквивалентном языке квадратичных форм; они являются основным объектом изучения в ''геометрии чисел'' – направлении, предложенном Минковским в качестве связующего звена между геометрией и теорией чисел. Математическое введение в решетки см. в работе [3]. В [6, 12] дается введение в решетки с акцентом на вычислительные и алгоритмические вопросы. | ||
== Основные результаты == | == Основные результаты == | ||
