Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: evatutin от 01.07.2021, 09:52Цитата: AenBleidd от 30.06.2021, 17:47@drmos, сейчас лето, время отпусков. Может люди на пляжу пузо греют и не читают форумов
Не знаю, кто где и что греет, у нас сессия и защиты, что отнимает все свободное время. Чуть позже отвечу более развернуто...
Эх, ну я думал, что хоть у вас отпуск человеческий уже начался, а то я в последний раз в отпуске был полтора года назад, еще до пандемии 
Рад вернуть в проект свой i7. Похоже, проблема была со стороны провайдера - они там на своей стороне какой-то рубильничек передёрнули и всё неожиданно заработало. Поднагрузим 5900Х. Как он там поживает?
Кстати, из-за того что удалял/добавлял проект заново, теперь в списке компьютеров машина висит в количестве двух штук - ID 46841 и ID 56875. Можно ли их как-то объединить или теперь только остаётся удалить старый как неактивный? В других проектах вроде есть опция 'merge hosts'.
Опции 'merge hosts' у Герасима нетути. Компьютер можно только удалить. Вот Ваши компики:
https://gerasim.boinc.ru/users/showUserHosts.aspx?userid=4071
Нажмите "Delete inactive hosts". Если за компиком не числятся результаты, и его кредиты начислены участнику, команде и стране, Герасим разрешит его удалить.
*****
Поднагрузим 5900Х. Как он там поживает?
При наличии заданий у приложения Graph coloring, процессор на 85% загружен выдачей заданий и приёмом посчитанных результатов.
Остальные 15% заняты обработкой полученных результатов и начислением кредитов участникам, командам и странам.
При этом, число обработанных результатов сильно отстаёт от числа сообщённых. Соответственно, очередь на обработку результатов - растёт и растёт. Сейчас мне приходится регулярно запрещать выдачу новых заданий, чтобы Герасим хоть что-то обработал.
Задержка в обработке - из-за низкой скорости записи на диск: RAID-0: 2x Тошиба 1 TB.
Головки шмурыгают, аж в прихожей слышно. 
*****
Ошибки в Validator и file_deleter - исправил.
Всем привет и хорошего настроения.
p.s.
Сейчас у Герасима уже несколько часов нет заданий, но обработка полученных результатов продолжается. И может продолжаться ещё несколько суток.
Загрузка процессора 5-10%.
Эксперимент по исследованию значений быстровычислимых числовых характеристик для ДЛК порядка 12 завершен (подпроект ODLS BS). В результате получены следующие нижние и верхние ограничения:
11888 <= Число трансверсалей <= 198144
1200 <= Число диагональных трансверсалей <= 28496
0 <= Число интеркалятов <= 188
Эксперимент с максимальным числом ОДЛК все еще продолжается ввиду того, что для него была выбрана неудобная для BOINC грид схема :(. В перспективе аналогичные эксперименты следует организовать по другому, чем мы и займемся по мере наличия свободного времени...
Все найденные границы были добавлены в соответствующие ряды в OEIS.
Под моим руководством была защищена выпускная квалификационная работа бакалавра на тему "Программа для поиска псевдотроек диагональных латинских квадратов 10 порядка" (автор работы — Владислав Мальков). Когда-то давно на форуме я упоминал, что кроме известной рекордной псевдотройки с ХО=100+100+74=274, в которой две пары ДЛК полностью ортогональны, а третья ортогональная в 74 ячейках (см. статью https://www.sciencedirect.com/science/article/abs/pii/S1571065316301470?via%3Dihub), можно попытаться построить псевдотройки других типов. Вот эта задача и была поставлена перед студентом...
В итоге им было сделано следующее: полным перебором отталкиваясь от заданных начальных заполнений производилось построение 3 ДЛК, далее для каждой из 3 пар производилось вычисление ХО и находилась суммарная ХО. К сожалению и вопреки моим пожеланиям программа была реализована на Python'е (который, согласно некоторым источникам, ссылки на которые я давать не буду, "является языком более высокого уровня по сравнению в Delphi или C++" (c) :), что сказалось на эффективности перебора. Поиск работал несколько десятков часов в 10 потоков. В результате был получен целый ряд певдотроек с ХО в диапазоне 200-229, в том числе 3 псевдотройки с рекордной (на данный момент и для данного типа псевдотроек) ХО:
Квадрат A:
7 3 1 8 4 2 5 9 0 6
0 6 5 3 1 8 9 7 2 4
4 2 8 0 7 6 1 3 9 5
8 4 6 9 2 7 0 5 1 3
9 8 7 1 5 4 3 2 6 0
2 0 3 6 8 1 7 4 5 9
3 9 2 5 6 0 4 1 8 7
6 1 9 7 3 5 2 0 4 8
5 7 4 2 0 9 6 8 3 1
1 5 0 4 9 3 8 6 7 2
Квадрат B:
2 9 4 5 7 3 1 8 0 6
1 4 2 7 0 8 6 3 5 9
5 7 3 2 6 4 0 9 1 8
9 2 1 0 4 7 3 6 8 5
3 6 5 8 9 1 4 0 2 7
7 0 8 1 2 6 5 4 9 3
6 1 9 4 5 2 8 7 3 0
8 3 7 9 1 0 2 5 6 4
4 8 0 6 3 5 9 1 7 2
0 5 6 3 8 9 7 2 4 1
Квадрат C:
4 9 2 8 1 6 5 7 3 0
8 7 4 0 3 1 2 5 6 9
9 4 6 1 8 3 7 2 0 5
7 6 9 5 0 2 4 1 8 3
0 8 1 6 2 7 3 9 5 4
3 2 0 4 5 9 6 8 7 1
5 1 3 9 7 8 0 6 4 2
2 5 8 7 4 0 1 3 9 6
6 3 5 2 9 4 8 0 1 7
1 0 7 3 6 5 9 4 2 8
ХО(A,B) = 80
ХО(A,C) = 78
ХО(B,C) = 71
ХО = 80+78+71 = 229
В перспективе дальнейших исследований можно попытаться усилить найденное значение и поискать псевдотройки еще одного типа, в которых одна пара ДЛК полностью ортогональна, а другие две ортогональны частично. На данный момент найденный рекорд для таких псевдотроек (см. статью https://cyberleninka.ru/article/n/the-search-for-systems-of-diagonal-latin-squares-using-the-sat-home-project, хотя ее авторы об этом и не пишут составляет 254.
Не так давно были посчитаны 4 спектра для числовых характеристик ДЛК порядка 1-7 (см. https://vk.com/wall162891802_1678). Для их вычисления все ДЛК были перечислены полным перебором, для каждого производился расчет соответствующей числовой характеристики, результирующее множество значений образовало соответствующий спектр. Для следующей по порядку размерности N=8 можно проделать серию аналогичных вычислительных экспериментов с той лишь разницей, что соответствующих ДЛК уже довольно много, и вместо их перечисления в лоб будем получать СКФ с использованием разработанного ранее генератора СКФ на базе X-образных заполнений и ESODLS-схем (напомню, что в рамках главного класса все квадраты обладают одним и тем же значением числовой характеристики и достаточно проанализировать один из квадратов главного класса (в данном случае — СКФ), что приблизительно на 3 порядка снижает необходимые затраты вычислительного времени). Соответствующие вычислительные эксперименты заняли не более 24 мин в 1 поток на Core i7 4770, получены следующие результаты.
1. Спектр трансверсалей: в числовом ряду https://oeis.org/A344105 a(8)=73, спектр образован значениями {8, 12, 16, 20, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 132, 136, 138, 140, 142, 144, 156, 160, 168, 176, 180, 192, 224, 256, 320, 384}.
2. Спектр диагональных трансверсалей: в числовом ряду https://oeis.org/A345370 a(8)=47, спектр образован значениями {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 36, 38, 40, 42, 44, 48, 52, 56, 64, 72, 88, 96, 120}.
3. Спектр интеркалятов: в числовом ряду https://oeis.org/A345760 (если его не удалят, сейчас в OEIS идет дискуссия по этому поводу) a(8)=61, спектр образован значениями {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 56, 60, 64, 68, 72, 80, 88, 112}.
4. Спектр ОДЛК: в числовом ряду https://oeis.org/A345761 (если его не удалят по аналогичной рассмотренной выше причине) a(8)=31, спектр образован значениями {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 20, 22, 24, 28, 40, 45, 48, 50, 108, 116, 128, 131, 824}.
Точные значения членов a(9) соответствующих числовых рядов могут быть получены и для размерности N=9, однако для этого потребуется вычислительный эксперимент на грид, незначительно более простой по необходимым затратам вычислительного времени по сравнению с выполненным недавно экспериментом по построению полного списка КФ ОДЛК порядка 9 и расчету соответствующих экстремальных значений быстровычислимых числовых характеристик. Спектр ОДЛК может быть построен проще...
Спектр числа ОДЛК к одному ДЛК порядка 9
Возьмем имеющийся у нас список КФ ОДЛК порядка 9 (см. http://evatutin.narod.ru/evatutin_odls_9.zip), построим для каждой КФ все возможные ОДЛК, посчитаем их количество и получим множество из 98 различных значений. На выполнение данной процедуры требуется около 20 с вычислительного времени процессора Core i7 4770 в 1 поток (напомню, что сам список мы считали двумя проектами (Gerasim@Home и RakeSearch) около 3 месяцев). Добавим к этому списку любую пустышку, например, вот эту
0 1 2 3 4 5 6 7 8
2 3 1 7 8 6 0 5 4
3 7 8 5 2 1 4 6 0
8 2 0 4 5 3 7 1 6
4 5 3 1 6 8 2 0 7
6 8 4 2 0 7 5 3 1
5 6 7 8 3 0 1 4 2
7 0 5 6 1 4 8 2 3
1 4 6 0 7 2 3 8 5
у которой по определению 0 ОДЛК и получим спектр для числа ОДЛК к одному ДЛК из 99 различных значений: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 54, 55, 56, 58, 59, 60, 61, 64, 66, 67, 68, 69, 70, 71, 72, 74, 76, 78, 80, 82, 86, 88, 92, 96, 99, 100, 104, 106, 111, 112, 120, 128, 138, 144, 147, 188, 190, 194, 196, 204, 220, 308, 310, 329, 360, 516, 560, 576, 580, 614}. Таким образом, в ряду https://oeis.org/draft/A345761 a(9)=99.
Спектр числа ОДЛК к одному ДЛК порядка 10
Для порядка N=10 нам уже довольно давно известны ДЛК, обладающие {0, 1, 2, 3, 4, 5, 6, 7, 8, 10} ОДЛК, о чем упомянуто даже в вики (см. https://ru.wikipedia.org/wiki/Метод_Эйлера_—_Паркера). Список образуемых ими комбинаторных структур доступен онлайн: http://evatutin.narod.ru/evatutin_ls_all_structs_rus.pdf . Исчерпывающий список КФ ОДЛК порядка N=10 построить не представляется возможным, т.к. он слишком велик, поэтому на данный момент можно утверждать, что в ряду https://oeis.org/draft/A345761 a(10)>=10. Хотя, с большой долей вероятности, a(10)=10, т.к. наши продолжительные поиски ДЛК с другим числом ОДЛК не выявили и маловероятно, что они существуют в принципе.
Кроме поиска латинских квадратов планируется ли применение найденных квадратов на практике? Может, уже кем-то написаны статьи о практическом применении результатов именно данного эксперимента?
Например, в этой статье говорится, что их используют “в комбинаторике, алгебре (изучение латинских квадратов тесно связано с изучением квазигрупп), теории кодов, статистике и многих других областях”.
Аппроксимация спектра ОДЛК для ДЛК порядка 11
Возьмем список КФ ОДЛК порядка 11 (см. https://disk.yandex.ru/d/N5q5wsPeeCSVPg), полученный нами недавно в эксперименте по исследованию быстровычислимых характеристик ОДЛК, и организуем для него эксперимент по построению спектра ОДЛК, в результате чего получим спектр из 35 значений, на что потребовалось 64 часа работы Core i7 4770 в 1 поток. Добавляя к нему любую пустышку, например, вот эту
0 1 2 3 4 5 6 7 8 9 10
1 2 0 4 5 10 8 9 3 7 6
5 8 3 7 2 4 9 10 0 6 1
4 10 7 1 6 8 2 3 9 0 5
10 0 5 8 7 6 1 4 2 3 9
6 7 8 10 0 9 4 2 1 5 3
9 6 10 0 8 3 5 1 7 4 2
7 4 9 6 10 1 3 8 5 2 0
8 3 4 2 9 0 10 5 6 1 7
3 5 6 9 1 2 7 0 4 10 8
2 9 1 5 3 7 0 6 10 8 4
получим аппроксимацию спектра ОДЛК для ДЛК порядка 11, состоящего из 36 элементов: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 21, 28, 32, 33, 34, 35, 36, 37, 38, 47, 127, 18530, 19139, 24593, 26914, 30198, 32462}. На основании полученного спектра можно сказать, что в числовом ряду https://oeis.org/draft/A345761 a(11)>=36. Не исключено, что существуют ДЛК с отличным от перечисленного выше в спектре числом ОДЛК, которые можно попробовать поискать в перспективе...