Форум программистов, компьютерный форум, киберфорум
Programma_Boinc
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  

2-ТРАНСВЕРСАЛИ В ПАРАХ ОРТОГОНАЛЬНЫХ ДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ.

Запись от Programma_Boinc размещена 03.12.2024 в 12:14
Показов 1747 Комментарии 1

2-ТРАНСВЕРСАЛИ В ПАРАХ ОРТОГОНАЛЬНЫХ ДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ.

УДК 681.3 Э.И. Ватутин evatutin@rambler.com
Юго-Западный государственный университет, Курск

В работе предложено понятие 2-трансверсалей (диагональных и общего вида) в парах ОЛК/ОДЛК, показана их связь с задачей построения троек взаимно ортогональных ЛК/ДЛК и приведено краткое описание их свойств.

Латинские квадраты (ЛК) и диагональные латинские квадраты (ДЛК) представляют собой достаточно известные типы комбинаторных объектов, исследованию которых посвящено достаточно большое количество научных публикаций. Одной из наиболее известных открытых математических проблем является попытка построения тройки взаимно ортогональных ЛК/ДЛК (ВОЛК/ВОДЛК) порядка 10 N = либо доказательство ее несуществования.

Для построения ортогональных соквадратов (ОЛК/ОДЛК) к заданному квадрату наиболее эффективным является метод Эйлера-Паркера, базирующийся на построении множества трансверсалей, и последующем поиске покрытия из N попарно не пересекающихся трансверсалей (диагональных трансверсалей при поиске ОДЛК и трансверсалей общего вида при поиске ОЛК).
Введем в рассмотрение понятие 2-трансверсалей, определенных в парах ОЛК/ОДЛК. Так 2-трансверсалью в паре ОЛК/ОДЛК A и B будем называть такую трансверсаль, которая одновременно является трансверсалью как в квадрате A, так и в квадрате B.
Аналогично, диагональной 2-трансверсалью в паре ОДЛК будем называть такую диагональную трансверсаль, которая одновременно является диагональной трансверсалью в обоих ДЛК пары.

Несложно показать, что необходимым и достаточным условием существования третьего квадрата C, ортогонального обоим квадратам A и B пары, является наличие N попарно не пересекающихся 2-трансверсалей. Следовательно, при поиске тройки ВОЛК/ВОДЛК имеет смысл сконцентрироваться на целенаправленном построении пар ОЛК/ОДЛК с большим числом 2-трансверсалей, для чего необходимо исследование их свойств. Пример пары ОДЛК порядка 9 и диагональной 2-трансверсали приведен на рисунке.

00 11 22 33 44 55 66 77 88
82 53 36 08 27 60 41 15 74
46 04 17 20 65 78 52 83 31
35 87 58 61 13 24 70 06 42
28 45 64 12 76 81 37 50 03
14 68 73 47 80 32 05 21 56
57 26 01 75 38 43 84 62 10
71 30 85 54 02 16 23 48 67
63 72 40 86 51 07 18 34 25

Рис. Пример пары ОДЛК порядка 9 и диагональной 2-трансверсали [1 0 3 2 4 6 5 8 7] (выделена жирным). Также указанная пара ОДЛК имеет еще 3 диагональных 2-трансверсали: [2 6 7 0 4 1 8 3 5], [3 5 1 8 4 7 0 2 6] и [5 3 8 1 4 0 7 6 2]

С использованием построенных ранее коллекций ОДЛК можно посчитать следующие числовые ряды для 2-трансверсалей:

• минимальное число 2-трансверсалей в парах ОДЛК – 1, 0, 0, 4, 10, 0, 2, 2,2, 2, 2, 2 (диагонали ДЛК по определению являются трансверсалями, поэтому для всех порядков N, для которых существуют ОДЛК, ( )2a N ³ );
• максимальное число 2-трансверсалей в парах ОДЛК – 1, 0, 0, 4, 10, 0, 28,96, 648, ()1028a³, ( )11
1782a³, ()12 108a³;
• мощность спектра числа 2-трансверсалей в парах ОДЛК – 1, 0, 0, 1, 1, 0, 3,7, 66, ()10 17a³, ( )11 35a³, () 12 42a³; и для диагональных 2-трансверсалей:
• минимальное число диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 (вероятно далее с ростом размерности N ряд будет состоять из нулевых значений);
• максимальное число диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 0, 0, 0, 14, 32, 140, ()10 8a³ , ( )11 320a³, () 12 38a³, () 13 992a³;
• мощность спектра числа диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 1, 1, 0, 3, 4, 53, () 106a³ , ( ) 11 37a³, ()12 11a³, () 13 14a³.

Все посчитанные числовые ряды не представлены в OEIS и планируются к добавлению в состав энциклопедии.
Для порядка 11 N = ДЛК в составе рекордных пар ОДЛК являются либо циклическими, либо DSODLS/ESODLS (либо одновременно); для порядка 12 N =– по-видимому, диагонализированными составными квадратами вида 34´ с максимально возможным для данной размерности числом трансверсалей, равным 198 144 (см. числовые ряды A287644 и A344105 в OEIS).

Для порядка 10 N =рекордным числом общих 2-трансверсалей (как диагональных, так и общего вида) обладают ДЛК, являющиеся SODLS/ESODLS с относительно небольшим числом трансверсалей (124/932 и 128/932 соответственно при известных максимальных значениях 890/5504), что делает актуальной задачу бестрансверсального поиска ESODLS с использованием схем отображения ячеек CMS [1].

В перспективе при необходимости введенное определение 2-трансверсалей может быть расширено на 3-трансверсали в тройках ВОЛК/ВОДЛК, 4-трансверсали в четверках ВОЛК/ВОДЛК и т.д.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Vatutin E.I., Zaikin O.S., Manzuk M.O., Nikitina N.N. Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-And-Conquer // Communications in Computer and Information Science. 2021. Vol. 1510. pp. 498–512. DOI: 10.1007/978-3-030-92864-3_38.
https://boinc.ru
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 1
Комментарии
  1. Старый комментарий
    Зачем писать капслоком? Двенадцать лет что ли?
    Запись от barabar размещена 03.12.2024 в 13:47 barabar вне форума
 
Новые блоги и статьи
Контейнеризация React приложений с Docker
Reangularity 03.04.2025
Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .
Свой попап в SwiftUI
mobDevWorks 03.04.2025
SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .
Антипаттерны микросервисной архитектуры
ArchitectMsa 03.04.2025
Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .
std::mutex в C++: Советы и примеры использования
bytestream 03.04.2025
std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
Метод с двумя буферами (или double buffering) или ping-pong buffering
Hrethgir 02.04.2025
Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .
На любовном киберфронте
Alexander-7 01.04.2025
Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
Как работает Node.js изнутри
run.dev 29.03.2025
Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
Моки в Python: Mock Object Library
py-thonny 29.03.2025
Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
JavaScript: Управление памятью и улучшение производительности
run.dev 29.03.2025
В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер