Введение
Набор отметок на двумерной квадратной сетке, таких что расстояние между любыми двумя парами отметок различно.
В математике массив Костаса можно рассматривать геометрически как набор из n точек, каждая из которых расположена в центре квадрата в n×n квадратной сетке, при этом каждая строка или столбец содержит только одну точку, и все n(n–1)/2 векторов смещения между каждой парой точек различны. Это приводит к идеальной автокорреляционной функции типа "кнопка", что делает массивы полезными в таких приложениях, как сонар и радар. Массивы Костаса можно рассматривать как двухмерные аналоги одномерной конструкции линейки Голомба, и, помимо математического интереса, имеют схожие применения в планировании экспериментов и радиолокационной инженерии с фазированной антенной решеткой. Массивы Костаса названы в честь Джона П. Костаса, который впервые описал их в техническом отчете 1965 года. Независимо от него, Эдгар Гилберт также опубликовал работы на эту тему в том же году, представив логарифмический метод Уэлча для построения массивов Костаса. Общее перечисление массивов Костаса остается открытой проблемой в информатике, а поиск алгоритма, решающего ее за полиномиальное время, является актуальным направлением исследований.
In mathematics, a Costas array can be regarded geometrically as a set of n points, each at the center of a square in an n×n square tiling such that each row or column contains only one point, and all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct. This results in an ideal "thumbtack" auto ambiguity function, making the arrays useful in applications such as sonar and radar. Costas arrays can be regarded as two dimensional cousins of the one dimensional Golomb ruler construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array radar engineering. Costas arrays are named after John P. Costas, who first wrote about them in a 1965 technical report. Independently, Edgar Gilbert also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays. The general enumeration of Costas arrays is an open problem in computer science and finding an algorithm that can solve it in polynomial time is an open research question.
Лемпель Голомб
Конструкция Лемпеля — Голомба выбирает α и β как примитивные элементы конечного поля GF(q) и аналогичным образом определяет , в противном случае 0. Результатом является массив Костаса размера q − 2. Если α + β = 1, то первую строку и столбец можно удалить, чтобы сформировать другой массив Костаса размера q − 3: такая пара примитивных элементов существует для каждой простой степени q > 2.
Расширения Тейлора, Лемпеля и Голомба
Создание новых массивов Костаса путем добавления или вычитания одной или двух строк/столбцов, содержащих 1 или пару единиц в углу, было опубликовано в статье, посвященной методам генерации, а также в основополагающей работе Голомба и Тейлора 1984 года. Более сложные методы генерации новых массивов Костаса путем удаления строк и столбцов из существующих массивов Костаса, сгенерированных генераторами Уэлча, Лемпеля или Голомба, были опубликованы в 1992 году. Верхней границы для порядка, при котором эти генераторы производят массивы Костаса, не существует.
Другие методы
Два метода, позволившие найти массивы Костаса порядка до 52, используя более сложные методы добавления или удаления строк и столбцов, были опубликованы в 2004 и 2007 годах.
Варианты
Массивы Костаса на гексагональной решетке известны как сотовые массивы. Доказано, что существует лишь конечное число таких массивов, которые должны содержать нечетное количество элементов, расположенных в форме гексагона. На данный момент известно 12 таких массивов (с учетом симметрии), и предполагается, что это их общее количество.