4551
правка
Задача о кратчайшем векторе: различия между версиями
Материал из WEGA
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 17:30, 26 марта 2022
, 26 марта 2022→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <math>\mathcal{L} (\mathbf{b}_1, ..., \mathbf{b}_n) = \Bigg\{ \sum_{i = 1}^n x_i \mathbf{b}_i : x_1, ..., x_n \in \mathbb{Z} \Bigg\}</math> из n линейно независимых векторов | ''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <math>\mathcal{L} (\mathbf{b}_1, ..., \mathbf{b}_n) = \Bigg\{ \sum_{i = 1}^n x_i \mathbf{b}_i : x_1, ..., x_n \in \mathbb{Z} \Bigg\}</math> из n линейно независимых векторов <math>\mathbf{b}_1, ..., \mathbf{b}_n \in \mathbb{R}^m</math> в m-мерном евклидовом пространстве. Для удобства вычислений векторы решетки <math>\mathbf{b}_1, ..., \mathbf{b}_n</math> часто предполагаются целыми (или рациональными), так что решетка может быть представлена целочисленной матрицей <math>\mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_n] \in \mathbb{R}^{m \times n}</math> (называемой ''базисом'') с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в L(B) удобно представить в виде Bx, где x – целочисленный вектор. Целые числа m и n называются размерностью и рангом решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность. | ||
