RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика» // Архив

Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2015, том 4, выпуск 3, страницы 95–108 (Mi vyurv8)

Дискретная математика и математическая кибернетика

Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@home

О. С. Заикин, С. Е. Кочемазов

Институт динамики систем и теории управления им. В.М. Матросова СО РАН (Иркутск, Российская Федерация)

Аннотация: В статье рассматривается подход к решению задач поиска систем ортогональных латинских квадратов, основанный на сведении этих задач к проблеме булевой выполнимости. Была построена соответствующая кодировка для задачи поиска пар ортогональных диагональных латинских квадратов порядка 10. С помощью построенной кодировки в проекте добровольных распределенных вычислений SAT@home были найдены 17 новых пар. На основе 17 найденных пар, а также 3 ранее известных пар, были построены псевдотройки диагональных латинских квадратов порядка 10. Построение псевдотроек было осуществлено на вычислительном кластере, для этого была сделана параллельная реализация алгоритма генерации диагональных латинских квадратов порядка 10.

Ключевые слова: латинские квадраты, добровольные распределенные вычисления, задача о булевой выполнимости, проект SAT@home.

УДК: 519.1, 004.832.25

Поступила в редакцию: 27.03.2015

DOI: 10.14529/cmse150308



Реферативные базы данных:


© МИАН, 2024