Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@home
Автор: Заикин Олег Сергеевич, Кочемазов Степан Евгеньевич
Рубрика: Дискретная математика и математическая кибернетика
Статья в выпуске: 3 т.4, 2015 года.
Бесплатный доступ
В статье рассматривается подход к решению задач поиска систем ортогональных латинских квадратов, основанный на сведении этих задач к проблеме булевой выполнимости. Была построена соответствующая кодировка для задачи поиска пар ортогональных диагональных латинских квадратов порядка 10. С помощью построенной кодировки в проекте добровольных распределенных вычислений SAT@home были найдены 17 новых пар. На основе 17 найденных пар, а также 3 ранее известных пар, были построены псевдотройки диагональных латинских квадратов порядка 10. Построение псевдотроек было осуществлено на вычислительном кластере, для этого была сделана параллельная реализация алгоритма генерации диагональных латинских квадратов порядка 10.
Латинские квадраты, добровольные распределенные вычисления, задача о булевой выполнимости, проект sat@home
Короткий адрес: https://sciup.org/147160574
IDR: 147160574 | DOI: 10.14529/cmse150308
Список литературы Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@home
- Тужилин, М.Э. Об истории исследований латинских квадратов/М.Э. Тужилин//Обозрение прикладной и промышленной математики. -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. DOI: DOI: 10.1201/9781420010541
- 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. DOI: DOI: 10.1109/grid.2004.14
- Ивашко, Е.Е. Использование 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/a51decrypt (дата обращения 30.11.2014).
- Een, N. An Extensible SAT-solver/N. Een, N. Sorensson//Lecture notes in computer science. -2003. -Vol. 2919. -P. 502-518. DOI: DOI: 10.1007/978-3-540-24605-3_37
- Egan, J. Enumeration of MOLS of small order/Egan J., Wanless I.M.//Cornell University Library. arXiv:1406.3681v2 .
- Гришагин, В.А. Параллельное программирование на основе MPI/В.А. Гришагин, А.Н. Свистунов. -Изд-во ННГУ им. Н.И. Лобачевского. -2005. -93 с.
