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

Олег Сергеевич Заикин, Степан Евгеньевич Кочемазов

Аннотация


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

Ключевые слова


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

Полный текст:

PDF

Литература


Тужилин М.Э. Об истории исследований латинских квадратов / М.Э. Тужилин // Обозрение прикладной и промышленной математики. — 2012. — Т. 19, Вып. 2. — С. 226–227.

Colbourn C.J. Handbook of Combinatorial Designs. Second Edition / C.J. Colbourn, J.H. Dinitz. — Chapman&Hall, — 2006. — 984 p.

Biere A. Handbook of Satisfiability / A. Biere, V. Heule, H. van Maaren, T. Walsh (eds.). — IOS Press. — 2009.

Семенов А.А. Применение алгоритмов решения проблемы булевой выполнимости (SAT) к комбинаторным задачам / А.А. Семенов, О.С. Заикин, И.В. Отпущенников, С.Е. Кочемазов // Труды XII Всероссийского совещания по проблемам управления. — Изд-во ИПУ РАН. — 2014. — С. 7361–7374.

Семенов А.А. Технологии решения многомерных задач логического поиска / А.А. Семенов, Д.В. Беспалов // Вестник Томского государственного университета. —2005. — № 14. — С. 61–73.

Zhang H. Combinatorial Designs by SAT Solvers / H. Zhang. — In: Biere A., Heule V., van Maaren H., Walsh T. (eds.) Handbook of Satisfiability. — IOS Press. — 2009. P. 533–568.

Gomes C. Completing quasigroups or Latin squares: A structured graph coloring problem / C. Gomes, D. Shmoys // Proceedings of the Computational Symposium on Graph Coloring and Generalizations. — 2002. — P. 22–39.

Brown J.W. Completion of the spectrum of orthogonal diagonal Latin squares / J.W. Brown, F. Cherry, L. Most, M. Most, E.T. Parker, W.D. Wallis // Lecture notes in pure and applied mathematics. — 1992. — Vol. 139. — P. 43–49.

Заикин О.С. Опыт организации добровольных вычислений на примере проектов OPTIMA@home и SAT@home / О.С. Заикин, М.А. Посыпкин, А.А. Семенов, Н.П. Храпов // Вестник Нижегородского университета им. Н.И. Лобачевского. — 2012. — № 5-2. — С. 340–347.

Заикин О.С. Процедуры построения декомпозиционных множеств для распределен-ного решения SAT-задач в проекте добровольных вычислений SAT@home / О.С. Заикин, А.А. Семенов, М.А. Посыпкин // Управление большими системами. — М.: ИПУ РАН. — Вып. 43. — 2013. — С. 138–156.

SAT@home: проект добровольных распределенных вычислений для решения круп-номасштабных SAT-задач. URL: http://sat.isa.ru/pdsat/ (дата обращения 20.03.2015).

Anderson D.P. BOINC: A System for Public-Resource Computing and Storage / D.P. Anderson // In: Buyya, R. (ed.) GRID, IEEE Computer Society. — 2004 — P. 4–10.

Ивашко Е.Е. Использование BOINC-грид в вычислительноемких научных исследо-ваниях / Е.Е. Ивашко, Н.Н. Никитина // Вестник Новосибирского государственного университета. Серия: Информационные технологии. — 2013. — Т. 11, № 1. — С. 53–57.

Ватутин Э.И. Использование добровольных распределенных вычислений на плат-форме BOINC для анализа качества разбиений граф-схем параллельных алгоритмов / Э.И. Ватутин, В.С. Титов // Труды шестой международной конференции «Параллельные вычисления и задачи управления» PACO'2012. — Институт проблем управления им. В.А. Трапезникова РАН, Москва. — 2012. — С. 37–54.

Гринберг Я.Р. Алгоритм кластеризации элементов сетей передачи данных / Я.Р. Гринберг, И.И. Курочкин, А.В. Корх // Информационные технологии и вычисли-тельные системы. — 2012. — № 3. — С. 18–30.

Заикин О.С. Применение метода Монте-Карло к прогнозированию времени парал-лельного решения проблемы булевой выполнимости / О.С. Заикин, А.А. Семенов // Вычислительные методы и программирование: новые вычислительные технологии. — 2014. — Т. 15, № 1. — С. 22–35.

Rainbow-таблицы для шифра A5/1. URL: http://opensource.srlabs.de/projects/a51-decrypt (дата обращения 30.11.2014).

Een N. An Extensible SAT-solver / N. Een, N. Sorensson // Lecture notes in computer science. — 2003. — Vol. 2919. — P. 502–518.

Egan J. Enumeration of MOLS of small order / Egan J., Wanless I.M. // arXiv:1406.3681v2 [math.CO].

Гришагин В.А. Параллельное программирование на основе MPI / В.А. Гришагин, А.Н. Свистунов. — Изд-во ННГУ им. Н.И. Лобачевского. — 2005. — 93 с.




DOI: http://dx.doi.org/10.14529/cmse150308