В математике массив Костаса (названный в честь Джона П. Костаса) можно рассматривать геометрически как набор из 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:
0 | 1 | 0 | 0 |
1 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 0 | 0 | 1 |
Существуют точки с координатами: (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}
Полная база данных массивов для всех размерностей, которые были тщательно проверены, доступна здесь (недоступная ссылка)
Массив Уэлча-Костаса, или просто массив Уэлча (Велча), является массивом Костаса, полученным с использованием метода, разработанного Ллойдом Р. Уэлчем (англ. Lloyd R. Welch). Массив Уэлча-Костаса строится путём взятия первообразного корня g простого числа p и определением массива A, где , если , в противном случае 0. Результатом является массив Костаса размера p − 1.
3 является первообразным корнем по модулю 5.
Поэтому [3 4 2 1] является перестановкой Костаса. Это дискретно экспоненциальный массив Уэлча (Велча). Транспонированный массив является дискретно логарифмическим массивом Уэлча.
Число массивов Уэлча-Костаса, которые существуют для данного размера, зависит от функции Эйлера.
Метод Лемпеля-Голомба использует примитивные элементы α и β из конечного поля GF(q) и аналогично определяется , если , иначе 0. Результатом является массив Костаса размера q − 2. Если α + β = 1, то первая строка и столбец удаляются для формирования другого массива Костаса размера q − 3: неизвестно, есть ли такие пары примитивных элементов для каждой степени q.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .