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

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

Запись от Programma_Boinc размещена 03.12.2024 в 12:14
Показов 1759 Комментарии 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 вне форума
 
Новые блоги и статьи
Async/await в TypeScript
run.dev 06.04.2025
Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .
Многопоточность в C#: Синхронизация потоков
UnmanagedCoder 06.04.2025
Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .
TypeScript: Классы и конструкторы
run.dev 06.04.2025
TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .
Многопоточное программирование: Rust против C++
golander 06.04.2025
C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .
std::vector в C++: от основ к оптимизации производительности
NullReferenced 05.04.2025
Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .
Реляционная модель и правила Кодда: фундамент современных баз данных
Codd 05.04.2025
Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .
Асинхронные операции в Django с Celery
py-thonny 05.04.2025
Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .
Использование кэшей CPU: Максимальная производительность в Go
golander 05.04.2025
Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .
Создаем Telegram бот на TypeScript с grammY
run.dev 05.04.2025
Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .
Паттерны распределённых транзакций в Event-Driven микросервисах
ArchitectMsa 05.04.2025
Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер