Страница публикации

Оценка числа трансверсалей для диагональных латинских квадратов малого порядка

Авторы: Ватутин Э.И., Заикин О.С., Кочемазов С.Е., Валяев С.Ю., Титов В.С.

Журнал: Телекоммуникации

Том:

Номер: 1

Год: 2018

Отчётный год: 2018

Издательство:

Местоположение издательства:

URL:

Аннотация: В статье рассмотрена возможность применения современных телекоммуникационных средств для решения задач комбинаторики с использованием концепции добровольных распределенных вычислений на платформе BOINC. Приведено подробное описание задачи построения трансверсалей и диагональных трансверсалей для диагональных латинских квадратов (ДЛК), показано, что с их использованием возможно эффективное построение ортогонального ДЛК для заданного исходного ДЛК. Аналитическая оценка минимального и максимального числа трансверсалей в зависимости от порядка квадрата N неизвестна, поэтому для определения искомых комбинаторных характеристик необходим вычислительный эксперимент. Минимальное и максимальное число трансверсалей для латинских квадратов малого порядка известно, в то время как аналогичные оценки для диагональных латинских квадратов и диагональных трансверсалей неизвестны. Авторами были разработаны программные реализации высокоэффективного генератора ДЛК и алгоритма построения числа трансверсалей путем перебора в глубину с возвратами, с использованием которых искомые характеристики были определены для N < 8. Для случая N = 8 с использованием проекта добровольных распределенных вычислений был организован соответствующий вычислительный эксперимент, который позволил определить искомые значения комбинаторных характеристик. Найденные целочисленные последовательности являются новыми и не представлены в энциклопедии OEIS.

Индексируется WOS: 0

Индексируется Scopus: 0

Индексируется РИНЦ: 1

Публикация в печати: 0

Добавил в систему: