В математике массив Костаса (названный в честь Джона П. Костаса) можно рассматривать геометрически как набор из n точек, лежащих в клетках шахматной доски размерности n × n таким образом, чтобы каждая строка или столбец содержали только одну точку и все n(n − 1)/2 вектора смещений между каждой парой точек были различны. С помощью этого массива можно создать идеальную кнопкообразную функцию неопределённости (то есть функцию, которая бесконечна в точке (0,0) и принимает значение ноль в других точках), что делает применение массивов Костаса полезным для таких приложений, как гидро- и радиолокация.
Массив Костаса может быть представлен в цифровом виде как массив из n × n чисел, где каждой точке ставится в соответствие 1, а в случае отсутствия точки в массив записывается 0. Если интерпретировать их как двоичные матрицы, эти массивы чисел имеют свойство: каждая строка и столбец имеет только одну точку на нем, поэтому они также являются матрицами перестановок. Таким образом, массивы Костаса для любого n являются подмножеством матриц перестановок порядка n.
Массивы Костаса можно рассматривать как двумерные аналоги одномерных линеек Голомба. Они представляют математический интерес, применяются в разработках радиолокационной техники на фазированных решётках.
Все массивы Костаса вплоть до размера 27 × 27 известны . Существует два способа получения массивов Костаса, работающих с рядом простых чисел и степенью простых чисел. Они известны как методы Уэлча (Велча (Lloyd R. Welch)) и Лемпеля-Голомба, и возникли в математике из теории конечных полей.
Пока неизвестны все массивы Костаса для всех размеров. В настоящее время самые маленькие размеры, для которых массивы неизвестны — 32 × 32 и 33 × 33.
Определение массивов
Массивы, как правило, описываются как ряд индексов, указывающих столбцы для каждой строки. С учетом того, что в любом столбце имеется только одна точка, массив можно представить как одномерный. Например, массив Костаса порядка N = 4:
0100100000100001
Существуют точки с координатами: (1,2), (2,1), (3,3), (4,4)
x-координата увеличивается линейно, мы можем записать это кратко как последовательность y-координат. Тогда позиция в наборе будет x-координатой. Вышеописанный массив может быть закодирован последовательностью {2,1,3,4}. Это позволяет легко обращаться с массивами порядка N.
Известные массивы
N = 1 {1}
N = 2 {1,2} {2,1}
N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}
N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}
N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}
N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}
Полная база данных массивов для всех размерностей, которые были тщательно проверены, доступна здесь
Построение
Уэлч (Велч) Массив Уэлча-Костаса, или просто массив Уэлча (Велча), является массивом Костаса, полученным с использованием метода, разработанного Ллойдом Р. Уэлчем (). Массив Уэлча-Костаса строится путём взятия первообразного корня g простого числа p и определением массива A, где , если , в противном случае 0. Результатом является массив Костаса размера p − 1.
Пример
3 является первообразным корнем по модулю 5.
Поэтому [3 4 2 1] является перестановкой Костаса. Это дискретно экспоненциальный массив Уэлча (Велча). Транспонированный массив является дискретно логарифмическим массивом Уэлча.
Число массивов Уэлча-Костаса, которые существуют для данного размера, зависит от функции Эйлера.
Лемпель-Голомб Метод Лемпеля-Голомба использует примитивные элементы α и β из конечного поля GF(q) и аналогично определяется , если , иначе 0. Результатом является массив Костаса размера q − 2. Если α + β = 1, то первая строка и столбец удаляются для формирования другого массива Костаса размера q − 3: неизвестно, есть ли такие пары примитивных элементов для каждой степени q.
См. также Перестановка Диэдрическая группа
Литература
Ссылки
On-Line Encyclopedia of Integer Sequences: : Number of Costas arrays of order n, counting rotations and flips as distinct. : Number of inequivalent Costas arrays of order n under dihedral group.
Категория:Комбинаторика