Просмотр кода страницы Gerasim@Home

{{много внутренних ссылок|дата=2023-02-25}}
{{Карточка программы для добровольных вычислений
 | platform = [[BOINC]]
 | name = Gerasim@Home
 | program_download_traffic = 2 МБ
 | download_traffic = 1 КБ
 | upload_traffic = 150 КБ
 | hdd_usage = 2 МБ
 | ram_usage = 10 МБ
 | graphics = нет
 | time = до 6 часов
 | deadline = 11 дней
 | gpu_usage = нет
|screenshot=Gerasim.gif}}

'''Gerasim@Home''' — российский проект [[Добровольные вычисления|добровольных распределенных вычислений]] на платформе [[BOINC]]. Проект стартовал в тестовом режиме в феврале 2008 года<ref name="boincstats">[http://boincstats.boincstats.com/stats/project_graph.php?pr=gerasim BOINCstats | Gerasim@Home — Credit overview<!-- Заголовок добавлен ботом -->]{{Недоступная ссылка|date=2018-05|bot=InternetArchiveBot }}</ref>. Отличительной особенностью серверной части проекта, разработанной С. Ю. Валяевым, является использование [[Операционная система|операционной системы]] [[Windows Server 2008]] и связки [[Microsoft SQL Server]] с [[ASP.NET]], в то время как стандартный набор приложений от разработчиков BOINC требует использования операционной системы [[Linux]] или [[Unix]]. По состоянию на 23 июля 2015 года в проекте приняли участие 1999 пользователей (890 компьютеров) из 62 стран, обеспечивая производительность 1—5 [[тера-|тера]][[флопс]]. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в [[Интернет]], установив на него программу [[BOINC Manager]].

== История проекта ==
Проект стартовал в тестовом режиме в феврале 2008 года<ref name="boincstats" />, используя в качестве тестового расчетного модуля программу gsm для поиска простых чисел.

В июне 2010 года на [http://www.swsu.ru/structura/up/fivt/kvt/index.php кафедре вычислительной техники] [[Юго-Западный государственный университет|Юго-Западного государственного университета]] было разработано расчетное приложение separator, целью которого является построение [[Разбиение графа|разбиений]] параллельных [[Граф-схема алгоритма|граф-схем алгоритмов]] [[Логическое управление|логического управления]], получаемых различными [[Эвристический алгоритм|эвристическими методами]], с целью сравнения качества получаемых решений и выработки рекомендаций о границах целесообразности применения методов. Первая часть расчетов была завершена в сентябре 2011 г.

В январе 2013 года был начат эксперимент<ref>{{cite web|url=http://forum.gerasim.boinc.ru/default.aspx?g=posts&m=609#post609|title=Separator progress - Page 2 - Science - Forum Gerasim@home|accessdate=2013-01-30|archiveurl=https://www.webcitation.org/6EB0NgdPg?url=http://forum.gerasim.boinc.ru/default.aspx?g=posts#post609|archivedate=2013-02-04|deadurl=yes}}</ref> по исследованию возможностей применения жадной стратегии синтеза разбиения с ограничением на выбор вершин из смежной окрестности текущего блока<ref name="adjbar" />.

В марте 2014 года начата новая серия экспериментов, целью которой является апробация применения эвристических методов применительно к решению известных задач [[Теория графов|теории графов]] на примере задачи поиска [[Задача о кратчайшем пути|кратчайшего пути в графе]] и для поиска разбиений<ref name="march14">[http://forum.boinc.ru/default.aspx?g=posts&m=63861#post63861 О проекте Gerasim@home — Page 48 — Gerasim@home — Форум Boinc.ru<!-- Заголовок добавлен ботом -->]{{Недоступная ссылка|date=2019-11|bot=InternetArchiveBot }}</ref>.

В июне 2014 года стартовала серия экспериментов с целью исследования возможности использования {{нп1|Случайный перебор|случайного перебора|en|Random search}}<ref name=autogenerated1>{{Cite web |url=http://evatutin.narod.ru/evatutin_separations_31_rand.pdf |title=Ватутин Э. И., Колясников Д. В., Мартынов И. А., Титов В. С. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. Барнаул: Барнаул, 2014. С. 115—125. |access-date=2014-08-13 |archive-date=2014-08-14 |archive-url=https://web.archive.org/web/20140814014158/http://evatutin.narod.ru/evatutin_separations_31_rand.pdf |deadlink=no }}</ref><ref name=rs2>{{Cite web |url=http://evatutin.narod.ru/evatutin_separations_32_rs.pdf |title=Ватутин Э. И., Колясников Д. В., Титов В. С. Анализ результатов применения метода случайного перебора в задаче поиска разбиений граф-схем параллельных алгоритмов // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 102—110. |access-date=2015-03-01 |archive-date=2015-04-02 |archive-url=https://web.archive.org/web/20150402120629/http://evatutin.narod.ru/evatutin_separations_32_rs.pdf |deadlink=no }}</ref> с фиксированным числом итераций при построении разбиений.

В феврале 2015 года запущено продолжение серии экспериментов, целью которых является апробация применения эвристических методов применительно к решению задачи поиска [[Задача о кратчайшем пути|кратчайшего пути в графе]] с использованием возвратной стратегии<ref name="sam">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_deadlocks.pdf |title=Ватутин Э. И., Мартынов И. А., Титов В. С. Способ обхода тупиков при решении задач дискретной оптимизации с ограничениями // Перспективные информационные технологии (ПИТ-2014). Самара: изд-во Самарского научного центра РАН. С. 313—317. |access-date=2015-02-16 |archive-date=2015-02-16 |archive-url=https://web.archive.org/web/20150216221654/http://evatutin.narod.ru/evatutin_grth_pathfind_deadlocks.pdf |deadlink=no }}</ref>, а также методов [[Алгоритм имитации отжига|имитации отжига]]<ref name="sa">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_sa.pdf |title=Ватутин Э. И., Титов В. С. Параметрическая оптимизация алгоритма имитации отжига на примере решения задачи поиска кратчайшего пути в графе // Вестник Череповецкого государственного университета. № 6 (67). 2015. С. 13-16. |access-date=2015-11-28 |archive-date=2015-12-08 |archive-url=https://web.archive.org/web/20151208071944/http://evatutin.narod.ru/evatutin_grth_pathfind_sa.pdf |deadlink=no }}</ref>, [[Поиск в глубину|перебора с ограничением глубины]]<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=72355#post72355 |title=О проекте Gerasim@home — Page 63 — Gerasim@home — Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2015-02-16 |archiveurl=https://web.archive.org/web/20150216215524/http://forum.boinc.ru/default.aspx?g=posts&m=72355#post72355 |archivedate=2015-02-16 |deadlink=yes }}</ref><ref name="ldfs">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_ldfs.pdf |title=Ватутин Э. И., Мартынов И. А., Титов В. С. Анализ результатов использования метода перебора с ограничением глубины в задаче поиска кратчайшего пути в графе // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (МППОС’15). Барнаул, 2015. С. 120—128. |access-date=2015-08-04 |archive-date=2015-12-08 |archive-url=https://web.archive.org/web/20151208063151/http://evatutin.narod.ru/evatutin_grth_pathfind_ldfs.pdf |deadlink=no }}</ref>, различных вариаций [[Муравьиный алгоритм|муравьиного алгоритма]]<ref name="ac" /><ref name="ac2" />, [[Генетический алгоритм|генетического алгоритма]]<ref name="genetics" /> и алгоритма [[Алгоритм пчелиной колонии|пчелиной колонии]]<ref name="bc">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_bc.pdf |title=Ватутин Э. И., Титов В. С. Особенности метаоптимизации алгоритма пчелиной колонии в задаче поиска кратчайшего пути в графе при наличии ограничений на плотность графа // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. № 2 (19). 2016. С. 52-65. |access-date=2016-08-07 |archive-date=2016-08-20 |archive-url=https://web.archive.org/web/20160820123733/http://evatutin.narod.ru/evatutin_grth_pathfind_bc.pdf |deadlink=no }}</ref>.

В июне 2016 года запущен вычислительный эксперимент, целью которого является подсчет числа диагональных [[Латинский квадрат|латинских квадратов]] порядка 9 ({{OEIS|A274171}} и {{OEIS|A274806}})<ref>{{Cite web |url=http://gerasim.boinc.ru/news/news.aspx?id=69 |title=Project News<!-- Заголовок добавлен ботом --> |access-date=2016-06-25 |archive-date=2016-07-17 |archive-url=https://web.archive.org/web/20160717183913/http://gerasim.boinc.ru/news/news.aspx?id=69 |deadlink=no }}</ref>.

В октябре 2016 в проекте был начат эксперимент, направленный на исследование эффективности методов [[Случайное блуждание|случайных блужданий]]<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=84764#post84764 |title=О проекте Gerasim@home — Page 94 — Gerasim@home — Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2016-11-22 |archiveurl=https://web.archive.org/web/20161122223120/http://forum.boinc.ru/default.aspx?g=posts&m=84764#post84764 |archivedate=2016-11-22 |deadlink=yes }}</ref> и [[Метод роя частиц|роя частиц]]<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=85080#post85080 |title=О проекте Gerasim@home — Page 96 — Gerasim@home — Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2016-11-22 |archiveurl=https://web.archive.org/web/20161122222509/http://forum.boinc.ru/default.aspx?g=posts&m=85080#post85080 |archivedate=2016-11-22 |deadlink=yes }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_pso.pdf |title=Ватутин Э.И., Титов В.С. Исследование особенностей применения метода роя частиц в задачах дискретной оптимизации // Вестник компьютерных и информационных технологий. № 5 (167). 2018. С. 26–34. DOI: 0.14489/vkit.2018.05.pp.026–034. |access-date=2018-06-04 |archive-date=2019-07-15 |archive-url=https://web.archive.org/web/20190715065817/http://evatutin.narod.ru/evatutin_grth_pathfind_pso.pdf |deadlink=no }}</ref> в задаче поиска кратчайшего пути в графе.

[[Файл:Gerasim@Home_First_ODLS_10.png|thumb|Первая пара ортогональных диагональных латинских квадратов порядка 10, найденная в проекте]]

В начале 2017 года в проекте был организован эксперимент, направленный на определение значений ряда комбинаторных характеристик диагональных латинских квадратов и их ортогональных пар ([[Греко-латинский квадрат|греко-латинских квадратов]]) порядка 8<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=85954#post85954 |title=О проекте Gerasim@home - Page 98 - Gerasim@home - Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2017-03-14 |archiveurl=https://web.archive.org/web/20170315174124/http://forum.boinc.ru/default.aspx?g=posts&m=85954#post85954 |archivedate=2017-03-15 |deadlink=yes }}</ref>. В марте 2017 стартовал эксперимент по получению случайных пар ортогональных диагональных латинских квадратов порядка 10 с целью формирования списка их уникальных канонических форм<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=86752#post86752 |title=Поиск КФ ОДЛК в проекте Gerasim@home - Gerasim@home - Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2017-03-14 |archiveurl=https://web.archive.org/web/20170315085514/http://forum.boinc.ru/default.aspx?g=posts&m=86752#post86752 |archivedate=2017-03-15 |deadlink=yes }}</ref>. С 3 по 16 июня 2017 года в проекта осуществлялся подсчет числа симметричных диагональных латинских квадратов порядка 10<ref  name="sdls10">{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=88056#post88056 |title=О проекте Gerasim@home - Page 103 - Gerasim@home - Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2017-06-16 |archiveurl=https://web.archive.org/web/20170620204207/http://forum.boinc.ru/default.aspx?g=posts&m=88056#post88056 |archivedate=2017-06-20 |deadlink=yes }}</ref>. 23 октября 2017 года в проекта запущен эксперимент, направленный на анализ симметричных в одной плоскости квадратов при построении пар ортогональных диагональных латинских квадратов<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=89528#post89528 |title=О проекте Gerasim@home - Page 106 - Gerasim@home - Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2017-10-29 |archiveurl=https://web.archive.org/web/20171030040755/http://forum.boinc.ru/default.aspx?g=posts&m=89528#post89528 |archivedate=2017-10-30 |deadlink=yes }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_ls_dls_symm_v2.pdf |title=Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Титов В.С. Исследование свойств симметричных диагональных латинских квадратов. Работа над ошибками // Интеллектуальные и информационные системы (Интеллект – 2017). Тула, 2017. С. 30–36. |access-date=2017-12-04 |archive-date=2017-12-05 |archive-url=https://web.archive.org/web/20171205042042/http://evatutin.narod.ru/evatutin_co_ls_dls_symm_v2.pdf |deadlink=no }}</ref>.

В декабре 2018 года в проекте был начат эксперимент по изучению эффективности эвристических методов в задаче [[Раскраска графов|раскраски графов]] общего вида<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=91833#post91833 |title=О проекте Gerasim@home - Page 117 - Gerasim@home - Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2018-12-20 |archiveurl=https://web.archive.org/web/20181220230547/http://forum.boinc.ru/default.aspx?g=posts&m=91833#post91833 |archivedate=2018-12-20 |deadlink=yes }}</ref>.

С 2022 года расчеты, связанные с исследованием свойств диагональных латинских квадратов, перенесены в проект добровольных распределенных вычислений [[RakeSearch]]<ref>{{Cite web |url=https://rake.boincfast.ru/rakesearch/ |title=RakeSearch<!-- Заголовок добавлен ботом --> |access-date=2023-07-05 |archive-date=2023-07-05 |archive-url=https://web.archive.org/web/20230705211431/https://rake.boincfast.ru/rakesearch/ |url-status=live }}</ref>.

== Приложение separator ==
[[Файл:logic.control.algorithm.separation.png|thumb|Пример разбиения параллельной [[граф-схема алгоритма|граф-схемы алгоритма]] логического управления. Разными цветами отмечены вершины, попадающие в различные блоки разбиения]]

Необходимость в отыскании разбиения, (суб)оптимального по ряду [[Показатель качества|показателей качества]], возникает при проектировании [[Система логического управления|систем логического управления]], используемых для осуществления логического управления различными дискретными системами (цифровыми схемами, [[ЧПУ|станками с ЧПУ]], роботизированными сборочными линиями и т. д.). При проектировании подобных систем возникает ряд [[Комбинаторика|комбинаторных]] многокритериальных [[Оптимизация (математика)|оптимизационных]] задач на дискретных структурах ([[Граф (математика)|графах]]), к которым и относится задача синтеза разбиения заданной граф-схемы алгоритма управления<ref>Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4</ref><ref>Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5</ref><ref>Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. [[Саарбрюккен|Saarbrucken]]: [[VDM Publishing|Lambert Academic Publishing]], 2011 г. 292 с. ISBN 978-3-8433-1728-3</ref>, в соответствии с которым должна работать разрабатываемая система логического управления. Отыскание точного решения (глобального оптимума) в большинстве практических случаев невозможно из-за того, что поставленная задача принадлежит к [[Класс NP|классу NP]], поэтому на практике обычно ограничиваются применением эвристических методов, дающих решения неплохого качества за приемлемое время.

Качество найденного решения оценивается как степень минимизации частных показателей качества, к которым относятся:
* число блоков разбиения <math>H</math> — совпадает с числом контроллеров в составе системы логического управления, напрямую влияет на аппаратную сложность системы системы логического управления, её энергопотребление и массогабаритные характеристики;
* степени дублирования сигналов логических условий <math>\gamma_X</math> и микроопераций <math>\gamma_Y</math> — определяют оптимальность распределения вершин граф-схемы алгоритма по блокам разбиения, влияют на число дорожек, связывающих контроллеры на [[Печатная плата|печатной плате]] или в составе [[Интегральная схема|интегральной микросхемы]] (в зависимости от выбранного способа реализации системы логического управления);
* сложность сети межблочных связей <math>\alpha</math> — определяет необходимое число микрокоманд передачи управления между контроллерами, влияет на глубины некоторых очередей в составе коммуникационной подсистемы контроллера;
* интенсивность межблочных взаимодействий <math>\delta</math> — определяет среднее число передач управления за время выполнения заданного управляющего алгоритма (межконтроллерный [[сетевой трафик|трафик]] передачи управления), влияет на быстродействие системы управления в целом.
Интегральная оценка качества разбиения <math>J</math> рассчитывается как [[Весовая функция|взвешенная сумма]] нормированных значений частных показателей качества.

При практической реализации системы логического управления приходится учитывать ограничения технологического характера, к которым в первую очередь относятся:
* число ножек на корпусе микросхемы для приема сигналов логических условий <math>X_{max}</math> и выдачи сигналов микроопераций <math>Y_{max}</math>;
* объём памяти микрокоманд <math>W_{max}</math> в составе контроллера.
Ограничение <math>Y_{max}</math> не является критическим и может быть исключено из рассмотрения путём дублирования контроллеров, имеющих одинаковые входы и выполняющих однотипные микропрограммы. С целью упрощения внутренней структуры контроллера накладывается дополнительное структурное ограничение на невозможность размещения параллельных вершин в составе одного блока разбиения (контроллера).

В качестве эвристических методов поиска разбиений в вычислительных экспериментах принимали участие:
* метод С. И. Баранова<ref>Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.</ref> и его модификации<ref name="adjbar">{{Cite web |url=http://evatutin.narod.ru/evatutin_separations_26_adjbar.pdf |title=Ватутин Э. И., Леонов М. Е. Использование смежной окрестности при жадном последовательном формировании блоков разбиения граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. 2013. Т. 56. № 6. С. 30-35. |access-date=2013-10-12 |archive-date=2013-10-14 |archive-url=https://web.archive.org/web/20131014045522/http://evatutin.narod.ru/evatutin_separations_26_adjbar.pdf |deadlink=no }}</ref> — используют [[Жадный алгоритм|жадную стратегию]] последовательного формирования блоков разбиения;
* метод параллельно-последовательной декомпозиции<ref>Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62.</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_separations_07_psm.pdf |title=Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917. |access-date=2012-05-13 |archive-date=2014-03-29 |archive-url=https://web.archive.org/web/20140329185833/http://evatutin.narod.ru/evatutin_separations_07_psm.pdf |deadlink=no }}</ref> — использует ряд эквивалентных преобразований (разрыв циклов, объединение линейных участков граф-схемы алгоритма, классификация отношений между вершинами граф-схемы, построение множества сечений граф-схемы, построение блоков разбиения на основании анализа таблиц включений);
* {{нп1|метод случайного перебора||en|Random search}}<ref name=autogenerated1 /><ref name=rs2 /> с заданным числом итераций.

[[Файл:gerasim@home params space.png|thumb|Исследуемое пространство параметров и номера вычислительных экспериментов]]

Методы характеризуются существенно различной трудоемкостью реализации, [[Вычислительная сложность|временной и емкостной сложностью]] алгоритмов преобразований и качеством получаемых решений при различных значениях технологических ограничений. При проведении сравнения качества методов необходимо исследование различных областей пространства параметров <math>\left( X_{max}, W_{max}, N \right)</math>, где <math>N</math> — число вершин в составе граф-схем алгоритмов, что является вычислительно сложной задачей. В процессе расчетов были проанализированы отдельные срезы пространства параметров, на основании чего было выявлено существенно различное поведение методов синтеза разбиений по мере усиления или ослабления значений технологических ограничений.

[[Файл:gerasim@home ll exp4 b gamma.png|thumb|Средние значения показателей качества при различных значениях координат пространства параметров, полученные в одном из экспериментов]]
[[Файл:gerasim@home ll exp4 b rho.png|thumb|Вероятности получения минимального значения выбранного показателя качества методом С. И. Баранова при различных значениях координат пространства параметров, полученные в одном из экспериментов]]
[[Файл:Gerasim@home pm.png|thumb|Карты предпочтительного использования последовательных эвристических методов при синтезе разбиений в плоскости параметров <math>(X_{max}; N)</math>]]

Для каждой точки выбранного среза пространства параметров осуществляется построение выборки параллельных алгоритмов логического управления с псевдослучайной структурой, построение их разбиений указанным методом и оценка качества, что требует от нескольких минут (малые значения <math>N</math>) до нескольких часов (большие значения <math>N</math>) вычислительного времени. Полученные выборки числовых значений объёмом около 200 КБ каждая передаются на сервер проекта и ожидают последующей обработки. Общий объём полученных данных (без учёта избыточности) составил 235 ГБ, а вычислительные затраты — 51,6 [[экса-|экза]][[флоп]] (818 ГГц-лет). По сравнению с реализацией на двухъядерном процессоре Core 2 Duo с частотой 1,86 ГГц выигрыш во времени, полученный за счет параллельной обработки с использованием [[грид]], составил 155 раз. Постобработка полученных результатов<ref>[http://evatutin.livejournal.com/21767.html evatutin — Расчеты и постобработка завершены!<!-- Заголовок добавлен ботом -->]</ref><ref>[http://evatutin.livejournal.com/56013.html evatutin — Постобработка результатов анализа смежной жадной стратегии завершена!<!-- Заголовок добавлен ботом -->]</ref> заняла около суток вычислительного времени и заключалась в расчете средних значений параметров качества <math>\gamma_x</math> и вероятностей <math>\rho_x</math> получения разбиения с минимальным значением выбранного показателя качества, в результате чего были получены искомые двумерные карты общим объёмом 96 МБ, которые можно использовать для подробного анализа поведения методов в различных областях пространства параметров.

== Приложение spstarter ==
В марте 2014 года стартовала<ref name="march14" /> очередная серия вычислительных экспериментов, отличительной особенностью которой является поддержка одновременного выполнения нескольких экспериментов. С целью тестирования методов решения дискретных оптимизационных задач был реализован соответствующий расчетный модуль, статически подключаемый к приложению spstarter.exe. Помимо приложения separator, вошедшего в состав нового расчетного модуля, реализована возможность анализа качества решений тестовой задачи нахождения кратчайшего пути в графе с использованием ряда подходов ([[алгоритм Дейкстры]], жадный алгоритм, случайный перебор, взвешенный случайный перебор<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_wr.pdf |title=Ватутин Э. И., Дремов Е. Н., Мартынов И. А., Титов В. С. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. № 10 (137). Вып. 9. 2014. c. 59-64. |access-date=2014-07-22 |archive-date=2014-07-29 |archive-url=https://web.archive.org/web/20140729225620/http://evatutin.narod.ru/evatutin_grth_pathfind_wr.pdf |deadlink=no }}</ref>, их модификации с поддержкой комбинаторных возвратов<ref name="sam" />, вариации [[Муравьиный алгоритм|алгоритма муравьиной колонии]]<ref name="ac">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_ac.pdf |title=Ватутин Э. И., Титов В. С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 111—120. |access-date=2015-03-01 |archive-date=2015-04-02 |archive-url=https://web.archive.org/web/20150402124414/http://evatutin.narod.ru/evatutin_grth_pathfind_ac.pdf |deadlink=no }}</ref><ref name="ac2">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_ac2.pdf |title=Ватутин Э. И., Титов В. С. Об одном подходе к использованию алгоритма муравьиной колонии при решении задач дискретной комбинаторной оптимизации // Интеллектуальные и информационные системы (Интеллект 2015). Тула, 2015. С. 8-13. |access-date=2015-12-11 |archive-date=2016-03-05 |archive-url=https://web.archive.org/web/20160305015810/http://evatutin.narod.ru/evatutin_grth_pathfind_ac2.pdf |deadlink=no }}</ref>, [[Алгоритм имитации отжига|метод имитации отжига]], [[Поиск в глубину|перебор с ограничением глубины или числа рассматриваемых ветвей дерева]], [[генетический алгоритм]]<ref name="genetics">{{Cite web |url=http://evatutin.narod.ru/evatutin_grth_pathfind_ga.pdf |title=Ватутин Э. И., Титов В. С. Исследование особенностей применения генетического алгоритма в задаче поиска кратчайшего пути в графе при наличии ограничений на плотность графа // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (МППОС — 2016). Барнаул: изд-во Алтайского государственного университета, 2016. С. 152—159. |access-date=2016-06-25 |archive-date=2016-06-16 |archive-url=https://web.archive.org/web/20160616005115/http://evatutin.narod.ru/evatutin_grth_pathfind_ga.pdf |deadlink=no }}</ref>, [[алгоритм пчелиной колонии]]<ref name="bc" />, метод [[Случайное блуждание|случайных блужданий]] и вариации [[Метод роя частиц|метода роя частиц]]) с целью выявления их сильных и слабых сторон. Наилучшие результаты были в рассматриваемой задаче были продемонстрированы методом муравьиной колонии и генетическим алгоритмом<ref>{{Cite web |url=http://ceur-ws.org/Vol-1973/paper09.pdf |title=Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Sequential Formation of the Decision in the Graph Shortest Path Problem // CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 67–76. |access-date=2017-10-29 |archive-date=2017-10-30 |archive-url=https://web.archive.org/web/20171030003417/http://ceur-ws.org/Vol-1973/paper09.pdf |deadlink=no }}</ref><ref>Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Limited Depth-First Search Techniques in the Graph Shortest Path Problem // Open Engineering. Vol. 7. Iss. 1. 2017. pp. 428—434. DOI: 10.1515/eng-2017-0041.</ref>,<ref>{{Cite web |url=https://jpit.az/uploads/article/az/2020_1/COMPARISON_OF_DECISIONS_QUALITY_OF_HEURISTIC_METHODS_BASED_ON_MODIFYING_OPERATIONS_IN_THE_GRAPH_SHORTEST_PATH_PROBLEM.pdf |title=Vatutin E., Panishchev V., Gvozdeva S., Titov V. Comparison of Decisions Quality of Heuristic Methods Based on Modifying Operations in the Graph Shortest Path Problem // Problems of Information Technology. No. 1. 2020. pp. 3–15. DOI: 10.25045/jpit.v11.i1.01. |access-date=2020-01-16 |archive-date=2020-01-16 |archive-url=https://web.archive.org/web/20200116143949/https://jpit.az/uploads/article/az/2020_1/COMPARISON_OF_DECISIONS_QUALITY_OF_HEURISTIC_METHODS_BASED_ON_MODIFYING_OPERATIONS_IN_THE_GRAPH_SHORTEST_PATH_PROBLEM.pdf |deadlink=no }}</ref>.

== Определение асимптотического поведения комбинаторных характеристик комбинаторных структур на базе диагональных латинских квадратов ==
Асимптотическое поведение числа диагональных латинских квадратов (ДЛК) с ростом их размерности N до выполненных в проекте расчетов было неизвестно. В результате разработки высокоэффективного расчетного модуля, который использует ряд приемов алгоритмической и высокоуровневой [[Оптимизация (информатика)|оптимизации]]<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_01_ls_g_rs_wrs_ac.pdf |title=Ватутин Э. И., Журавлев А. Д., Заикин О. С., Титов В. С. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 18-30. |access-date=2016-11-22 |archive-date=2016-03-30 |archive-url=https://web.archive.org/web/20160330030358/http://evatutin.narod.ru/evatutin_co_01_ls_g_rs_wrs_ac.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_ls_dls_1_8_eng.pdf |title=Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzuk M.O., Kochemazov S.E., Titov V.S. Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares // Distributed computing and grid-technologies in science and education (GRID’16): book of abstracts of the 7th international conference. Dubna: JINR, 2016. p. 114—115. |access-date=2016-11-22 |archive-date=2017-09-21 |archive-url=https://web.archive.org/web/20170921172143/http://evatutin.narod.ru/evatutin_co_ls_dls_1_8_eng.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_ls_dls_1_8.pdf |title=Ватутин Э. И., Заикин О. С., Журавлев А. Д., Манзюк М. О., Кочемазов С. Е., Титов В. С. О влиянии порядка заполнения ячеек на темп генерации диагональных латинских квадратов // Информационно-измерительные диагностирующие и управляющие системы (Диагностика — 2016). Курск: изд-во ЮЗГУ, 2016. С. 33-39. |access-date=2016-11-22 |archive-date=2016-11-22 |archive-url=https://web.archive.org/web/20161122222932/http://evatutin.narod.ru/evatutin_co_ls_dls_1_8.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_ls_dls_9.pdf |title=Ватутин Э. И., Титов В. С., Заикин О. С., Кочемазов С. Е., Валяев С. Ю., Журавлев А. Д., Манзюк М. О. Использование грид-систем для подсчета комбинаторных объектов на примере диагональных латинских квадратов порядка 9 // Информационные технологии и математическое моделирование систем 2016. М.: изд-во Центра информационных технологий в проектировании РАН, 2016. С. 154—157. |access-date=2016-11-22 |archive-date=2016-11-22 |archive-url=https://web.archive.org/web/20161122222713/http://evatutin.narod.ru/evatutin_co_ls_dls_9.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_ls_S_0_and_1.pdf |title=Ватутин Э. И., Журавлев А. Д., Заикин О. С., Титов В. С. Учёт алгоритмических особенностей задачи при генерации диагональных латинских квадратов // Известия ЮЗГУ. 2016. № 2 (65). C. 46-59. |access-date=2016-11-22 |archive-date=2017-09-21 |archive-url=https://web.archive.org/web/20170921173351/http://evatutin.narod.ru/evatutin_co_ls_S_0_and_1.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://ceur-ws.org/Vol-1787/486-490-paper-84.pdf |title=Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzyuk M.O., Kochemazov S.E., Titov V.S. Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares // CEUR Workshop proceedings. Selected Papers of the 7th International Conference Distributed Computing and Grid-technologies in Science and Education. 2017. Vol. 1787. pp. 486–490. urn:nbn:de:0074-1787-5. |access-date=2017-02-02 |archive-date=2017-02-02 |archive-url=https://web.archive.org/web/20170202234922/http://ceur-ws.org/Vol-1787/486-490-paper-84.pdf |deadlink=no }}</ref>, удалось достичь темпа генерации в 6,6 млн. ДЛК/с, что позволило определить число ДЛК до N<10 ({{OEIS|A274171}} и {{OEIS|A274806}}). Для этого потребовалось 3 месяца расчетов на грид с реальной производительностью 2—5 TFLOP/s<ref>{{Cite web |url=http://forum.boinc.ru/default.aspx?g=posts&m=84754#post84754 |title=О проекте Gerasim@home — Page 94 — Gerasim@home — Форум Boinc.ru<!-- Заголовок добавлен ботом --> |accessdate=2016-11-22 |archiveurl=https://web.archive.org/web/20161122221240/http://forum.boinc.ru/default.aspx?g=posts&m=84754#post84754 |archivedate=2016-11-22 |deadlink=yes }}</ref> и 3 месяца расчетов на вычислительном кластере «Академик В. М. Матросов» [[Сибирское отделение Российской академии наук|СО РАН]] с целью проверки и подтверждения полученного результата<ref>{{Cite web |url=https://link.springer.com/chapter/10.1007%2F978-3-319-67035-5_9 |title=Vatutin E.I., Kochemazov S.E., Zaikin O.S. Applying volunteer and parallel computing for enumerating diagonal Latin squares of order 9 // Proc. of The Eleventh International Conference on Parallel Computational Technologies, Vol. 753 of Communications in Computer and Information Science, Springer, 2017, pp. 114–129. DOI: 10.1007/978-3-319-67035-5_9. |access-date=2017-10-09 |archive-date=2017-10-09 |archive-url=https://web.archive.org/web/20171009195430/https://link.springer.com/chapter/10.1007%2F978-3-319-67035-5_9 |deadlink=no }}</ref>.

С использованием аналогичных алгоритмических принципов был осуществлен подсчет числа симметричных диагональных латинских квадратов порядка N<11<ref name="sdls10" /> и определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка N<9<ref>{{Cite web |url=http://ceur-ws.org/Vol-1973/paper01.pdf |title=Vatutin E.I., Kochemazov S.E., Zaikin O.S., Valyaev S.Yu. Enumerating the Transversals for Diagonal Latin Squares of Small Order // CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6–14. |access-date=2017-10-29 |archive-date=2017-10-30 |archive-url=https://web.archive.org/web/20171030040801/http://ceur-ws.org/Vol-1973/paper01.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_trans_enum.pdf |title=Ватутин Э.И., Заикин О.С., Кочемазов С.Е., Валяев С.Ю., Титов В.С. Оценка числа трансверсалей для диагональных латинских квадратов // Телекоммуникации. 2018. № 1. С. 12–21. |access-date=2018-02-06 |archive-date=2018-02-07 |archive-url=https://web.archive.org/web/20180207005424/http://evatutin.narod.ru/evatutin_co_dls_trans_enum.pdf |deadlink=no }}</ref><ref>Vatutin E.I., Zaikin O.S., Kochemazov S.E., Valyaev S.Y. Using Volunteer Computing to Study Some Features of Diagonal Latin Squares // Open Engineering. Vol. 7. Iss. 1. 2017. pp. 453—460. DOI: 10.1515/eng-2017-0052.</ref>.

Кроме определения комбинаторных характеристик, в проекте производится поиск и коллекционирование канонических форм ортогональных диагональных латинских квадратов порядка 10 с целью классификации образуемых ими комбинаторных структур (графов на множестве бинарного отношения ортогональности)<ref name="comb_structs" /> и попыткой отыскания тройки попарно-ортогональных диагональных латинских квадратов, что является открытой математической проблемой. Наиболее эффективно поиск ортогональных квадратов общего вида осуществляется с использованием [[трансверсаль|трансверсалей]] путем сведения исходной задачи к [[:en:Exact cover|задаче о точном покрытии]] с последующем её решением с использованием [[:en:Dancing Links|алгоритма танцующих связей]] в рамках [[Метод Эйлера — Паркера|метода Эйлера-Паркера]]<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_dlx_reduct.pdf |title=Ватутин Э.И., Белышев А.Д., Кочемазов С.Е., Заикин О.С., Никитина Н.Н., Манзюк М.О. О полиномиальном сведении задач на базе латинских квадратов к задаче о точном покрытии // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание – 2019). Курск: изд-во ЮЗГУ, 2019. С. 62–64. |access-date=2019-05-28 |archive-date=2019-05-28 |archive-url=https://web.archive.org/web/20190528124833/http://evatutin.narod.ru/evatutin_co_dls_dlx_reduct.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://ceur-ws.org/Vol-2638/paper26.pdf |title=Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on diagonal Latin squares to the exact cover problem // CEUR Workshop Proceedings. Proceedings of the Second International Conference Information, Computation, and Control Systems for Distributed Environments (ICCS-DE 2020). Vol. 2638. Technical University of Aachen, Germany, 2020. |access-date=2020-07-17 |archive-date=2020-07-18 |archive-url=https://web.archive.org/web/20200718153012/http://ceur-ws.org/Vol-2638/paper26.pdf |deadlink=no }}</ref>. По состоянию на июль 2020 г. коллекция включает более 10 млн канонических форм ОДЛК порядка 10, найденных в проекте.

== Научные достижения ==
* получены границы областей применимости методов синтеза разбиений: область слабых ограничений для метода С. И. Баранова, область сильных ограничений для метода параллельно-последовательной декомпозиции (качественное преимущество);
* получены отношения степени оптимизации каждого из выбранных показателей качества к известному для него условному оптимуму, для каждого из методов показан проигрыш в процентах (количественное превосходство);
* получены границы областей нечувствительности, в которых ослабление ограничений не влияет на повышение качества решений, область нечувствительности имеет различную ширину для различных эвристических методов;
* сформулированы рекомендации для разработчиков аппаратной части мультиконтроллеров, структура логического мультиконтроллера с большим числом простых контроллеров является предпочтительной; показана диктуемая практикой необходимость работы в области сильных ограничений;
* произведен подсчет числа диагональных латинских квадратов порядка N<10 ({{OEIS|A274171}} и {{OEIS|A274806}});
* произведен подсчет числа горизонтально симметричных диагональных латинских квадратов порядка N<11 ({{OEIS|A287649}} и {{OEIS|A292516}});
* произведен подсчет числа дважды симметричных диагональных латинских квадратов порядка N<10 ({{OEIS|A287650}} и {{OEIS|A292517}});
* произведен подсчет числа симметричных в одной плоскости диагональных латинских квадратов порядка N<9 ({{OEIS|A296060}} и {{OEIS|A296061}});
* произведен подсчет числа редуцированных (первая строка квадратов упорядочена, например, по возрастанию) пар ортогональных диагональных латинских квадратов порядка N<8 ({{OEIS|A287651}});
* произведен подсчет максимально возможного числа диагональных латинских квадратов, ортогональных одному диагональному латинскому квадрату порядка N<9 ({{OEIS|A287695}});
* произведен подсчет числа и анализ свойств главных классов диагональных латинских квадратов порядка N<9 ({{OEIS|A287764}}, {{OEIS|A299783}}, {{OEIS|A299784}}, {{OEIS|A299785}} и {{OEIS|A299787}})<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_cfs_cnt.pdf |title=Vatutin E., Belyshev A., Kochemazov S., Zaikin O., Nikitina N. Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing // Supercomputing Days Russia 2018. M.: Moscow State University, 2018. pp. 933–942. |access-date=2018-12-21 |archive-date=2018-12-21 |archive-url=https://web.archive.org/web/20181221134648/http://evatutin.narod.ru/evatutin_co_dls_cfs_cnt.pdf |deadlink=no }}</ref><ref>{{Cite web |url=https://link.springer.com/chapter/10.1007%2F978-3-030-05807-4_49 |title=Vatutin E., Belyshev A., Kochemazov S., Zaikin O., Nikitina N. Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing // Communications in Computer and Information Science. Vol. 965. Springer, 2018. pp. 578–586. DOI: 10.1007/978-3-030-05807-4_49. |access-date=2019-01-05 |archive-date=2019-01-05 |archive-url=https://web.archive.org/web/20190105201344/https://link.springer.com/chapter/10.1007%2F978-3-030-05807-4_49 |deadlink=no }}</ref>;
* произведен подсчет числа центрально симметричных диагональных латинских квадратов порядка N<10 ({{OEIS|A293777}} и {{OEIS|A293778}})<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_centr_symm.pdf |title=Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Манзюк М.О., Никитина Н.Н., Титов В.С. О свойствах центральной симметрии диагональных латинских квадратов // Высокопроизводительные вычислительные системы и технологии. № 1 (8). 2018. С. 74–78. |access-date=2018-11-13 |archive-date=2018-11-14 |archive-url=https://web.archive.org/web/20181114060425/http://evatutin.narod.ru/evatutin_co_dls_centr_symm.pdf |deadlink=no }}</ref><ref>{{Cite web |url=https://jpit.az/uploads/article/az/2019_2/CENTRAL_SYMMETRY_PROPERTIES_FOR_DIAGONAL_LATIN_SQUARES.pdf |title=Vatutin E.I., Kochemazov S.E., Zaikin O.S., Manzuk M.O., Nikitina N.N., Titov V.S. Central Symmetry Properties for Diagonal Latin Squares // Problems of Information Technology. No. 2. 2019. pp. 3-8. DOI: 10.25045/jpit.v10.i2.01. |access-date=2019-10-15 |archive-date=2019-10-15 |archive-url=https://web.archive.org/web/20191015114655/https://jpit.az/uploads/article/az/2019_2/CENTRAL_SYMMETRY_PROPERTIES_FOR_DIAGONAL_LATIN_SQUARES.pdf |deadlink=no }}</ref>;
* произведено определение минимального и максимального числа [[Трансверсаль|трансверсалей]] в диагональных латинских квадратах порядка N<9 ({{OEIS|A287644}}, {{OEIS|A287645}}, {{OEIS|A287647}} и {{OEIS|A287648}});
* произведен подсчет числа пандиагональных латинских квадратов порядка N с фиксированной первой строкой ({{OEIS|A123565}});
* произведен подсчет числа ортогональных (ODLS), самоортогональных (SODLS), дважды самоортогональных (DSODLS) и расширенных самоортогональных (ESODLS) диагональных латинских квадратов порядка 1—10, а также нормализованных квадратов для того же типа ортогональности и их главных классов ({{OEIS|A330391}}}, {{OEIS|A329685}}, {{OEIS|A333366}}, {{OEIS|A309210}})<ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_sodls_and_dsodls_1_to_10.pdf |title=Ватутин Э.И., Белышев А.Д. Определение числа самоортогональных (SODLS) и дважды самоортогональных диагональных латинских квадратов (DSODLS) порядков 1–10 // Высокопроизводительные вычислительные системы и технологии. Т. 4. № 1. 2020. С. 58–63. |access-date=2020-07-19 |archive-date=2020-07-19 |archive-url=https://web.archive.org/web/20200719140649/http://evatutin.narod.ru/evatutin_sodls_and_dsodls_1_to_10.pdf |deadlink=no }}</ref>;
* произведена классификация комбинаторных структур, возникающих из диагональных латинских квадратов порядка 1—10 на множестве бинарного отношения ортогональности<ref name="comb_structs">{{Cite web |url=http://ceur-ws.org/Vol-2267/282-287-paper-53.pdf |title=Vatutin E.I., Titov V.S., Zaikin O.S., Kochemazov S.E., Manzuk M.O., Nikitina N.N. Orthogonality-based classification of diagonal Latin squares of order 10 // CEUR Workshop Proceedings. Vol. 2267. Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018). Dubna, JINR, 2018. pp. 282–287. |access-date=2019-01-05 |archive-date=2019-01-05 |archive-url=https://web.archive.org/web/20190105201713/http://ceur-ws.org/Vol-2267/282-287-paper-53.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_comb_structs.pdf |title=Ватутин Э.И., Титов В.С., Заикин О.С., Кочемазов С.Е., Манзюк М.О. Анализ комбинаторных структур на множестве отношения ортогональности диагональных латинских квадратов порядка 10 // Информационные технологии и математическое моделирование систем 2017. М.: ЦИТП РАН, 2017. С. 167–170. |access-date=2018-02-16 |archive-date=2018-02-16 |archive-url=https://web.archive.org/web/20180216143843/http://evatutin.narod.ru/evatutin_co_dls_comb_structs.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://evatutin.narod.ru/evatutin_co_dls_comb_structs_v2_abstr.pdf |title=Vatutin E.I., Titov V.S., Zaikin O.S., Kochemazov S.E., Manzyuk M.O., Nikitina N.N. Orthogonality-based classification of diagonal Latin squares of order 10 // Distributed computing and grid-technologies in science and education (GRID’18): book of abstracts of the 8th international conference. Dubna: JINR, 2018. pp. 94–95. |access-date=2018-11-13 |archive-date=2018-11-13 |archive-url=https://web.archive.org/web/20181113170229/http://evatutin.narod.ru/evatutin_co_dls_comb_structs_v2_abstr.pdf |deadlink=no }}</ref>;
* показано, что рекордная характеристика ортогональности 274<ref>{{Cite web |url=http://discretemath.upc.edu/jmda16/wp-content/uploads/2015/09/JMDA2016_paper_65.pdf |title=Zaikin O., Zhuravlev A., Kochemazov S., Vatutin E. On the Construction of Triples of Diagonal Latin Squares of Order 10 // Electronic Notes in Discrete Mathematics. Vol. 54C. 2016. pp. 307–312. DOI: 10.1016/j.endm.2016.09.053. |accessdate=2019-05-28 |archiveurl=https://web.archive.org/web/20161122222402/http://discretemath.upc.edu/jmda16/wp-content/uploads/2015/09/JMDA2016_paper_65.pdf |archivedate=2016-11-22 |deadlink=yes }}</ref> для псевдотройки попарно-ортогональных диагональных латинских квадратов порядка 10, найденная в ходе анализа плоскостной симметрии в ДЛК, не может быть улучшена как в данном классе симметрий, так и в классе чистых обобщенных симметрий и их окрестностей.

[[Файл:ODLS10-comb-structs.png|right|thumb|Комбинаторные структуры из диагональных латинских квадратов порядка 10 на множестве бинарного отношения ортогональности: a — «пустышка» (ДЛК без ОДЛК), b — пара ОДЛК (1:1), c — линия-3 («двушка», 1:2), d — «трешка» (1:3), e — четверка (1:4), f — пятерка (1:5), g — шестерка (1:6), h — семерка (1:7), i — восьмерка (1:8), j — ромб-3, k — ромб-4, l — цикл-4, m — «рыба», n — линия-4, o — линия-5, p — летательный аппарат, q — Дедал-10, r — крест, s — дерево, t — Дедал-8, u — Венера, v — ромб-5, w — десятка (1:10), x — робот, y — скат]]

[[Файл:dls10_oc274_record.png|right|thumb|Псевдотройка попарно-ортогональных диагональных латинских квадратов порядка 10 с рекордной характеристикой ортогональности 274. Образующий её квадрат B является строчно-инверсным и горизонтально-симметричным.]]

== См. также ==
* [[BOINC]]
* [[Добровольные вычисления]]
* [[Разбиение графа]]
* [[Граф-схема алгоритма]]
* [[Комбинаторная оптимизация]]
* [[Латинский квадрат]]
* [[Греко-латинский квадрат]]
* [[OEIS]]

== Примечания ==
{{Примечания|2}}

== Ссылки ==
* [http://gerasim.boinc.ru Официальный сайт проекта]
* [https://twitter.com/Gerasim_home Твиттер проекта]
* [http://evatutin.narod.ru/evatutin_separations_21_gerasim1.pdf Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2012). Курск: изд-во ЮЗГУ, 2012. С. 138—140.]
* [http://evatutin.narod.ru/evatutin_separations_22_gerasim2.pdf Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм] // [[Известия ЮЗГУ]]. № 3 (42). [[Курск]]: изд-во ЮЗГУ, 2012. С. 66—74.
* {{youtube|9DDi56_P7OY|Пленарный доклад «Использование грид-вычислений на платформе BOINC для построения разбиений параллельных алгоритмов логического управления» (Курск, 2012)}}
* [http://evatutin.narod.ru/evatutin_separations_23_gerasim3.pdf Ватутин Э. И., Титов В. С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов] // [https://web.archive.org/web/20180110210039/http://paco2012.ipu.ru/ Параллельные вычисления и задачи управления (PACO’12)]. М.: ИПУ РАН, 2012.
* [http://evatutin.narod.ru/evatutin_separations_28_spo.pdf Ватутин Э. И., Титов В. С. Структурно-параметрическая оптимизация систем логического управления с использованием добровольных распределенных вычислений] // [[Известия ЮЗГУ]]. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». № 2. Ч. 1. С. 12-17. ISSN 22231536.
* {{youtube|oNrlh0XYwHM|Ватутин Э.И. Сравнение эвристических методов синтеза разбиений граф-схем параллельных алгоритмов с использованием добровольных распределенных вычислений на платформе BOINC // BOINC:FAST'13. Петрозаводск, 2013.}}
* [http://evatutin.livejournal.com/65305.html Научно-популярное описание задачи построения разбиений]
* [http://evatutin.livejournal.com/80019.html Ватутин Э. И., Валяев С. Ю. Расчетный модуль для построения разбиений параллельных алгоритмов логического управления с использованием добровольных распределенных вычислений // Свидетельство о государственной регистрации программы для ЭВМ № 2013618013 от 28.08.13.]
* [http://evatutin.narod.ru/evatutin_separations_29_grid14.pdf Vatutin E.I., Titov V.S. Voluntary distributed computing for solving discrete combinatorial optimization problems using Gerasim@home project // Distributed computing and grid-technologies in science and education: book of abstracts of the 6th international conference. Dubna: JINR, 2014. PP. 60-61.] ISBN 978-5-9530-0387-2.
* [http://evatutin.livejournal.com/86955.html Ватутин Э. И., Валяев С. Ю., Дремов Е. Н., Мартынов И. А., Титов В. С. Расчетный модуль для тестирования комбинаторных оптимизационных алгоритмов в задаче поиска кратчайшего пути в графе с использованием добровольных распределенных вычислений // Свидетельство о государственной регистрации программы для ЭВМ № 2014619797 от 22.09.14.]
* [http://evatutin.narod.ru/evatutin_separations_33_gerasim4.pdf Ватутин Э. И., Титов В. С. Анализ областей качественного превосходства последовательных эвристических методов синтеза разбиений при проектировании логических мультиконтроллеров // Известия высших учебных заведений. Приборостроение. 2015. Т. 58. № 2. С. 115—122. DOI: 10.17586/0021-3454-2015-58-2-115-122.]
* [http://evatutin.narod.ru/gerasim/index.html Результаты вычислительных экспериментов в графическом виде]
* {{youtube|AY5GsIWfgow|Пленарный доклад «Решение задач дискретной комбинаторной оптимизации с использованием грид-систем на добровольной основе» (Курск, 2015)}}
* [http://ceur-ws.org/Vol-1502/paper5.pdf Vatutin E.I., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing // CEUR Workshop Proceedings. Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2015). Vol. 1502. Technical University of Aachen, Germany, 2015. P. 37-51. urn: nbn: de:0074-1502-3.]
* [http://evatutin.narod.ru/evatutin_separations_37_gerasim7_rs.pdf Ватутин Э. И., Валяев С. Ю., Титов В. С. Анализ результатов применения метода случайного перебора при построении разбиений граф-схем параллельных алгоритмов в зависимости от размерности задачи и силы ограничений // Перспективные информационные технологии (ПИТ 2016). Самара: изд-во Самарского научного центра РАН, 2016. С. 481—486.]
* [http://evatutin.narod.ru/evatutin_co_ls_enum_all.pdf Подсчет числа диагональных латинских квадратов с использованием добровольных распределенных вычислений]
* [http://evatutin.narod.ru/img/evatutin_science_total_08_2017.png Результаты проекта в графической форме (по состоянию на август 2017)]
* [http://evatutin.narod.ru/evatutin_ls_all_structs_n1to8_rus.pdf Перечень различных комбинаторных структур из ДЛК порядка 1-8]
* [http://evatutin.narod.ru/evatutin_ls_all_structs_rus.pdf Перечень различных комбинаторных структур из ДЛК порядка 10, найденных в проекте]
* [http://evatutin.narod.ru/evatutin_co_dls_bachelors_cnt.pdf Ватутин Э. И., Кочемазов С. Е., Заикин О. С., Цитерров И. И. Оценка вероятности нахождения ортогональных диагональных латинских квадратов среди диагональных латинских квадратов общего вида // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2018). Курск: изд-во ЮЗГУ, 2018. С. 72-74.]

Обсуждение проекта в форумах:
* [https://web.archive.org/web/20170521043108/http://forum.boinc.ru/default.aspx?g=topics&f=74 boinc.ru]
* [http://distributed.org.ua/forum/index.php?showtopic=1041 distributed.org.ua]

{{Добровольные вычисления}}

[[Категория:Проекты добровольных вычислений]]
[[Категория:Теория логического управления]]
[[Категория:Комбинаторная оптимизация]]
[[Категория:Латинские квадраты]]