Jump to content

Массив Костаса

В математике массив Костаса можно рассматривать геометрически как набор из n точек, каждая из которых находится в центре квадрата в квадратной n × n, мозаике размера так что каждая строка или столбец содержит только одну точку, а все n ( n - 1)/2 смещения вектора между каждой парой точек различны. В результате получается идеальная функция автоматической неоднозначности «кнопка» , что делает массивы полезными в таких приложениях, как гидролокаторы и радары . Массивы Костаса можно рассматривать как двумерные родственники конструкции одномерной линейки Голомба , и, помимо того, что они представляют математический интерес, они имеют аналогичные приложения в экспериментальном проектировании и с фазированной решеткой радиолокационной технике .

Массивы Костаса названы в честь Джона П. Костаса , который впервые написал о них в техническом отчете 1965 года. Независимо о них в том же году написал Эдгар Гилберт , опубликовав то, что сейчас известно как логарифмический метод Уэлча построения массивов Костаса. [1] Общее перечисление массивов Костаса является открытой проблемой в информатике, и поиск алгоритма, который может решить ее за полиномиальное время, является открытым исследовательским вопросом.

Числовое представление [ править ]

Массив Костаса может быть представлен численно как массив чисел n × n , где каждая запись равна либо 1 для точки, либо 0 для отсутствия точки. При интерпретации как двоичные матрицы эти массивы чисел обладают тем свойством, что, поскольку каждая строка и столбец имеют ограничение на наличие только одной точки, они, следовательно, также являются матрицами перестановок . Таким образом, массивы Костаса для любого заданного n являются подмножеством матриц перестановок порядка n .

Массивы обычно описываются как серия индексов, определяющих столбец для любой строки. Поскольку дано, что любой столбец имеет только одну точку, можно представить массив одномерно. Например, ниже приведен действительный массив Костаса порядка N = 4:

или просто

В координатах стоят точки: (1,2), (2,1), (3,3), (4,4).

Поскольку координата x увеличивается линейно, мы можем сокращенно записать это как набор всех координат y . Тогда позиция в наборе будет координатой x . Обратите внимание: {2,1,3,4} будет описывать вышеупомянутый массив. Это определяет перестановку. упрощает передачу массивов для заданного порядка N. Это

Известные массивы [ править ]

Количество массивов Костаса известно для порядков с 1 по 29. [2] (последовательность A008404 в OEIS ):

Заказ Число
1 1
2 2
3 4
4 12
5 40
6 116
7 200
8 444
9 760
10 2160
11 4368
12 7852
13 12828
14 17252
15 19612
16 21104
17 18276
18 15096
19 10240
20 6464
21 3536
22 2052
23 872
24 200
25 88
26 56
27 204
28 712
29 164

Вот некоторые известные массивы:Н = 1{1}

Н = 2{1,2} {2,1}

Н = 3{1,3,2} {2,1,3} {2,3,1} {3,1,2}

Н = 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}

Н = 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}

Н = 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}

Перечисление известных массивов Костаса порядка 200, [3] заказать 500 [4] и заказать 1030 [5] доступны. Хотя эти списки и базы данных этих массивов Костаса, вероятно, почти полны, могут существовать другие массивы Костаса с порядками выше 29, которых нет в этих списках.

Конструкции [ править ]

Уэлч [ править ]

Массив Уэлча-Костаса , или просто массив Уэлча, представляет собой массив Костаса, созданный с использованием следующего метода, впервые обнаруженного Эдгаром Гилбертом в 1965 году и переоткрытого в 1982 году Ллойдом Р. Уэлчем .Массив Уэлча – Костаса строится путем взятия примитивного корня g простого числа p и определения массива A по формуле если , в противном случае 0. Результатом является массив Костаса размера p - 1.

Пример:

3 — примитивный элемент по модулю 5.

3 1 = 3 ≡ 3 (по модулю 5)
3 2 = 9 ≡ 4 (по модулю 5)
3 3 = 27 ≡ 2 (по модулю 5)
3 4 = 81 ≡ 1 (по модулю 5)

Следовательно, [3 4 2 1] является перестановкой Костаса. Точнее, это экспоненциальный массив Уэлча. Транспонирование массива представляет собой логарифмический массив Уэлча.

Количество массивов Уэлча – Костаса, существующих для данного размера, зависит от функции totient .

Лемпель-Голомб [ править ]

Конструкция Лемпеля–Голомба рассматривает α и β как примитивные элементы конечного поля GF( q ) и аналогичным образом определяет если , в противном случае 0. Результатом является массив Костаса размера q - 2. Если α + β = 1, то первая строка и столбец могут быть удалены, чтобы сформировать другой массив Костаса размера q - 3: такая пара примитивных элементов существует для каждая степень простого числа q>2 .

Тейлора, Лемпеля Расширения и Голомба

Генерация новых массивов Костаса путем добавления или вычитания одной или двух строк/столбцов с единицей или парой единиц в углу была опубликована в статье, посвященной методам генерации. [6] и в знаковой статье Голомба и Тейлора 1984 года. [7]

Более сложные методы создания новых массивов Костаса путем удаления строк и столбцов существующих массивов Костаса, созданных генераторами Уэлча, Лемпеля или Голомба, были опубликованы в 1992 году. [8] Не существует верхнего предела порядка, в котором эти генераторы будут создавать массивы Костаса.

Другие методы [ править ]

Два метода, позволяющие найти массивы Костаса до 52-го порядка с использованием более сложных методов добавления или удаления строк и столбцов, были опубликованы в 2004 году. [9] и 2007. [10]

Варианты [ править ]

Массивы Костаса на шестиугольной решетке известны как сотовые массивы . Показано, что существует лишь конечное число таких массивов, которые должны иметь нечетное число элементов, расположенных в форме шестиугольника. В настоящее время известно 12 таких массивов (с точностью до симметрии), что предположительно соответствует их общему числу. [11]

См. также [ править ]

Примечания [ править ]

  1. ^ Костас (1965) ; Гилберт (1965) ; Независимое открытие массивов Костаса , Аарон Стерлинг, 9 октября 2011 г.
  2. ^ Борода (2006) ; Дракакис и др. (2008) ; Дракакис, Иорио и Рикард (2011) ; Дракакис и др. (2011)
  3. ^ Борода (2006) .
  4. ^ Борода (2008) .
  5. ^ Борода (2017) ; Бирд, Джеймс К., Файлы для загрузки: Costas Arrays , получено 20 апреля 2020 г.
  6. ^ Голомб (1984) .
  7. ^ Голомб и Тейлор (1984) .
  8. ^ Голомб (1992) .
  9. ^ Рикард (2004) .
  10. ^ Бирд и др. (2007) .
  11. ^ Блэкберн, Саймон Р.; Пануи, Анастасия; Патерсон, Маура Б.; Стинсон, Дуглас Р. (10 декабря 2010 г.). «Сотовые массивы» . Электронный журнал комбинаторики . 17 : 172 р. дои : 10.37236/444 . ISSN   1077-8926 .

Ссылки [ править ]

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2670fd7608b05c437a91a55cd05c63b8__1702248420
URL1:https://arc.ask3.ru/arc/aa/26/b8/2670fd7608b05c437a91a55cd05c63b8.html
Заголовок, (Title) документа по адресу, URL1:
Costas array - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)