Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В результате разведки в 3-м парастрофическом срезе на удалении M=70 найдена первая интересная область — обобщенная симметрия с координатами (1,16), в которой в ходе разведки найдено 5 2-КФных двушек (повторных). В проект (http://gerasim.boinc.ru) добавлены 400 тыс. WU'шек для подробного исследования данной области на удалениях M \in {50, 60, 70, 80}.
Подскажите, в чём может быть дело. Имеется современный компьютер с 4 ядерным процессором Intel Core i3-9100F и внешней видеокартой NVidia GeForce GTX 1650
Система - 64 разрядный Windows 10
Из распределённых вычислений - подключен только проект Gerasim@Home причём в 3 потока.
Видеокарта для вычислений не используется.
Так вот, при таком современном компьютере и при факте, что используется только 3 потока из 4, постоянно тормозит Яндекс.Браузер при открытии вкладок и переключении между вкладками. Google Chrome тоже тормозит в этих же местах, но меньше и реже.
Также при запуске виснет (не запускается) игра World of Tanks
А как только остановить Gerasim@Home - так всё сразу начинает работать идеально, и Яндекс.Браузер не тормозит больше и World of Tanks мгновенно стартует.
В чём может быть дело?
Может сейчас новое счётное приложение как-то не правильно приоритет выставляет?
Сколько RAM в системе? Тормоза при открытии вкладок обычно связаны с долгим обращением в диску. Жесткий диск HDD или SSD?
И я бы вообще не рекомендовал запускать BOINC при запуске игр, они обычно очень сильно завязаны на количество ядер процессора, и если какие-то из них полностью заняты (в данном случае задачами BOINC), остальные будут постоянно ожидать эти медленные потоки.
Память - 16 гигабайт.
Диск SSD
Цитата: SETI_Home_v8 от 09.07.2020, 09:48Цитата: Yura12 от 09.07.2020, 08:00Память - 16 гигабайт.
Диск SSD
А я бы вот вообще Боинк на ссд не ипользовал, мне кажется что ссд быстрее изнашивается...
Ну, я не могу сказать, что BOINC уж прям так яростно использует диск (если, конечно, не включить все флаги логгирования).
Цитата: Yura12 от 09.07.2020, 08:00Память - 16 гигабайт.
Диск SSD
Должно быть более, чем достаточно (ну, если в браузере не открыто пару сотен вкладок одновременно).
Я бы Вам порекомендовал открыть монитор ресурсов и посмотреть, кто и что использует активно.
Просто приложения Герасима, они маленькие и не такие ресурсоемкие. Я слабо верю, чтобы они настолько систему вешали.
Если бы у Вас бежали VirtualBox задачи - тогда да, а так я даже затрудняюсь что-либо сказать.
О подсчете числа X-образных заполнений диагоналей ДЛК
Сколько существует различных заполнений диагоналей ДЛК порядка N с фиксированной первой диагональю (для определенности 0, 1, ..., N, хотя порядок значений не важен)? У меня стойкое ощущение амнезии: код готовый есть, а вот результирующих цифр не нашел (ни в OEIS'е, ни в своих заметках). То ли они остались на утерянном старом форуме, то ли притаились и лежат где-то в укромном месте... Одним словом, расчет был выполнен повторно, в результате чего получился следующий числовой ряд:
1, 0, 0, 4, 4, 80, 80, 4752, 4752, 440192, 440192, 59245120, 59245120, 10930514688, 10930514688
Расчет значений a(N) до N<=13 особых вычислительных затрат не требует — на их подсчет уходит несколько секунд вычислительного времени максимум. Подсчет числа заполнений для a(14) и a(15) потребовал 1,5 часа для каждого при организации вычислений в 1 поток на Core i7 4770 (при необходимости можно сделать и быстрее). Значения a(16) и a(17) в настоящее время считаются, по моим прикидкам на их определение потребуется около 100 часов в тех же условиях, ждем...
Несложно показать, что по определению число X-образных заполнений диагоналей с фиксированной главной диагональю равно сумме кратностей линеек СКФ соответствующей размерности. Например, для N=4 у нас имеется 2 линейки с лексикографически минимальными X-образными заполнениями
0 . . 1
. 1 0 .
. 3 2 .
2 . . 3
и
0 . . 1
. 1 3 .
. 0 2 .
2 . . 3
Их кратности равны 2 и 2, а общее число X-образных диагональных заполнений с фиксированной главной диагональю a(4) = 2 + 2 = 4. Аналогично, для N=6 существует 3 линейки СКФ с кратностями 16, 48 и 16, а a(6) = 16 + 48 + 16 = 80.
Несложно убедиться в том, что число X-образных заполнений диагоналей без фиксации главной диагонали в N! раз больше, чем с фиксацией, и образует следующий числовой ряд:
1, 0, 0, 96, 480, 57600, 403200, 191600640, 1724405760, 1597368729600, 17571056025600, 28378507272192000, 368920594538496000, 952903592436341145600, 14293553886545117184000
Полученные числовые ряды в OEIS не представлены, что необходимо исправить в самое ближайшее время 
PPS. Похоже на то, что для всех n>=1 a(2*n) = a(2*n+1).
О числе линеек СКФ для ДЛК порядка 11
В результате построения всех X-образных диагональных заполнений для ДЛК порядка 11 и применения к ним всех возможных комбинаций M-преобразований установлено, что они образуют 67 различных классов эквивалентности (т.е. член a(11) последовательности https://oeis.org/draft/A309283 в OEIS равен 67). На его определение потребовалось 2,5 часа вычислительного времени Core i7 4770 в 1 поток.
Очень похоже на то, что, как и для X-образных диагональных заполнений с фиксированной главной диагональю, для последовательности A309283 a(2*t) = a(2*t+1) для всех t>0.
Определения числа линеек для ДЛК порядков N>=12 на одной машине проблематично, однако для этого в перспективе можно использовать грид...
Эмпирически было замечено, что в последовательностях
* число X-образных заполнений диагоналей в ДЛК с фиксированной главной диагональю (см. https://vk.com/wall162891802_1291),
* число классов эквивалентности X-образных заполнений диагоналей в ДЛК (см. https://vk.com/wall162891802_1292)
для известных значений выполняется соотношение a(2*t) = a(2*t+1) для всех t>0. Покажем теоретически, что данное соотношение справедливо для ВСЕХ t. Рассмотрим квадрат порядка N=2*t. В нем главная диагональ фиксирована и для определенности заполнена значениями 0, 1, ..., 2*t-1 (всего 2*t значений). Побочная диагональ заполняется значениями из множества U1 = {0, 1, ..., 2*t-1} мощностью |U1|=2*t всеми возможными способами, причем для каждого из N=2*t элементов побочной диагонали запрещено использовать ровно два значения из U1: одно из них уже использовано в строке на главной диагонали, второе — в столбце на главной диагонали.
Теперь рассмотрим случай размерности N=2*t+1. В нем главная диагональ заполнена значениями 0, 1, ..., 2*t (всего 2*t+1 значений), а в побочной диагонали зафиксирован один элемент (центральный), тот самый, в котором диагонали пересекаются в центре квадрата. Заполнить значениями всеми возможными способами необходимо оставшиеся N-1 = 2*t элементов (количество заполняемых элементов совпадает!). Возможные значения, которые можно поставить в незаполненные клетки побочной диагонали, образуют множество U2 = {0, 1, ..., t-1, t+1, ..., 2*t} мощностью |U2|=2*t (мощности множеств U1 и U2 совпадают!). На каждый из незаполненных элементов диагонали так же накладывается два запрета, чтобы не получилось дублирования значения в строках и столбцах со значениями с главной диагонали (число ограничений совпадает).
Таким образом, задачи заполнения диагоналей для порядков 2*t и 2*t+1 эквивалентны: необходимо заполнить 2*t клеток значениями множества мощностью 2*t без повторений, причем на каждую клетку есть два запрета на использование значений, отличается лишь состав элементов множеств U1 и U2, что на число заполнений не влияет. Соответственно, число заполнений совпадает. А раз совпадает число заполнений, то и число классов эквивалентности для них тоже будет совпадать с учетом того, что любые комбинации M-преобразования оставляют центральный элемент квадрата на месте, местами меняются лишь окружающие его элементы диагоналей.
О числе классов эквивалентности перестановок из N элементов с одинаковой структурой мультимножества длин циклов
Напомню, что через структуры мультимножеств длин циклов описываются обобщенные симметрии (автоморфизмы) в ДЛК. Рассмотрим, как происходит их построение на примере перестановки
P = [9 3 8 4 7 2 5 1 6 0].
Циклы получаются следующим образом:
P[0]=9, P[9]=0 — цикл длины 2;
P[1]=3, P[3]=4, P[4]=7, P[7]=1 — цикл длины 4;
P[2]=8, P[8]=6, P[6]=5, P[5]=2 — цикл длины 4.
Соответствующее перестановке P мультимножество длины циклов L(P) = {2,4,4}.
Для размерности N=10, как было показано whitefox'ом, существует 42 различных мультимножества: {1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,2}, ..., {10}. А для других размерностей? Можно организовать небольшой вычислительный эксперимент и определить, что и было проделано для размерностей N<=12, результаты приведены ниже.
N=1
---
1: {1}
N=2
---
1: {1,1}
2: {2}
N=3
---
1: {1,1,1}
2: {1,2}
3: {3}
N=4
---
1: {1,1,1,1}
2: {1,1,2}
3: {1,3}
4: {2,2}
5: {4}
N=5
---
1: {1,1,1,1,1}
2: {1,1,1,2}
3: {1,1,3}
4: {1,2,2}
5: {1,4}
6: {2,3}
7: {5}
N=6
---
1: {1,1,1,1,1,1}
2: {1,1,1,1,2}
3: {1,1,1,3}
4: {1,1,2,2}
5: {1,1,4}
6: {1,2,3}
7: {1,5}
8: {2,2,2}
9: {2,4}
10: {3,3}
11: {6}
N=7
---
1: {1,1,1,1,1,1,1}
2: {1,1,1,1,1,2}
3: {1,1,1,1,3}
4: {1,1,1,2,2}
5: {1,1,1,4}
6: {1,1,2,3}
7: {1,1,5}
8: {1,2,2,2}
9: {1,2,4}
10: {1,3,3}
11: {1,6}
12: {2,2,3}
13: {2,5}
14: {3,4}
15: {7}
N=8
---
1: {1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,2}
3: {1,1,1,1,1,3}
4: {1,1,1,1,2,2}
5: {1,1,1,1,4}
6: {1,1,1,2,3}
7: {1,1,1,5}
8: {1,1,2,2,2}
9: {1,1,2,4}
10: {1,1,3,3}
11: {1,1,6}
12: {1,2,2,3}
13: {1,2,5}
14: {1,3,4}
15: {1,7}
16: {2,2,2,2}
17: {2,2,4}
18: {2,3,3}
19: {2,6}
20: {3,5}
21: {4,4}
22: {8}
N=9
---
1: {1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,3}
4: {1,1,1,1,1,2,2}
5: {1,1,1,1,1,4}
6: {1,1,1,1,2,3}
7: {1,1,1,1,5}
8: {1,1,1,2,2,2}
9: {1,1,1,2,4}
10: {1,1,1,3,3}
11: {1,1,1,6}
12: {1,1,2,2,3}
13: {1,1,2,5}
14: {1,1,3,4}
15: {1,1,7}
16: {1,2,2,2,2}
17: {1,2,2,4}
18: {1,2,3,3}
19: {1,2,6}
20: {1,3,5}
21: {1,4,4}
22: {1,8}
23: {2,2,2,3}
24: {2,2,5}
25: {2,3,4}
26: {2,7}
27: {3,3,3}
28: {3,6}
29: {4,5}
30: {9}
N=10
---
1: {1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,4}
6: {1,1,1,1,1,2,3}
7: {1,1,1,1,1,5}
8: {1,1,1,1,2,2,2}
9: {1,1,1,1,2,4}
10: {1,1,1,1,3,3}
11: {1,1,1,1,6}
12: {1,1,1,2,2,3}
13: {1,1,1,2,5}
14: {1,1,1,3,4}
15: {1,1,1,7}
16: {1,1,2,2,2,2}
17: {1,1,2,2,4}
18: {1,1,2,3,3}
19: {1,1,2,6}
20: {1,1,3,5}
21: {1,1,4,4}
22: {1,1,8}
23: {1,2,2,2,3}
24: {1,2,2,5}
25: {1,2,3,4}
26: {1,2,7}
27: {1,3,3,3}
28: {1,3,6}
29: {1,4,5}
30: {1,9}
31: {2,2,2,2,2}
32: {2,2,2,4}
33: {2,2,3,3}
34: {2,2,6}
35: {2,3,5}
36: {2,4,4}
37: {2,8}
38: {3,3,4}
39: {3,7}
40: {4,6}
41: {5,5}
42: {10}
N=11
---
1: {1,1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,1,4}
6: {1,1,1,1,1,1,2,3}
7: {1,1,1,1,1,1,5}
8: {1,1,1,1,1,2,2,2}
9: {1,1,1,1,1,2,4}
10: {1,1,1,1,1,3,3}
11: {1,1,1,1,1,6}
12: {1,1,1,1,2,2,3}
13: {1,1,1,1,2,5}
14: {1,1,1,1,3,4}
15: {1,1,1,1,7}
16: {1,1,1,2,2,2,2}
17: {1,1,1,2,2,4}
18: {1,1,1,2,3,3}
19: {1,1,1,2,6}
20: {1,1,1,3,5}
21: {1,1,1,4,4}
22: {1,1,1,8}
23: {1,1,2,2,2,3}
24: {1,1,2,2,5}
25: {1,1,2,3,4}
26: {1,1,2,7}
27: {1,1,3,3,3}
28: {1,1,3,6}
29: {1,1,4,5}
30: {1,1,9}
31: {1,2,2,2,2,2}
32: {1,2,2,2,4}
33: {1,2,2,3,3}
34: {1,2,2,6}
35: {1,2,3,5}
36: {1,2,4,4}
37: {1,2,8}
38: {1,3,3,4}
39: {1,3,7}
40: {1,4,6}
41: {1,5,5}
42: {1,10}
43: {2,2,2,2,3}
44: {2,2,2,5}
45: {2,2,3,4}
46: {2,2,7}
47: {2,3,3,3}
48: {2,3,6}
49: {2,4,5}
50: {2,9}
51: {3,3,5}
52: {3,4,4}
53: {3,8}
54: {4,7}
55: {5,6}
56: {11}
N=12
---
1: {1,1,1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,1,1,4}
6: {1,1,1,1,1,1,1,2,3}
7: {1,1,1,1,1,1,1,5}
8: {1,1,1,1,1,1,2,2,2}
9: {1,1,1,1,1,1,2,4}
10: {1,1,1,1,1,1,3,3}
11: {1,1,1,1,1,1,6}
12: {1,1,1,1,1,2,2,3}
13: {1,1,1,1,1,2,5}
14: {1,1,1,1,1,3,4}
15: {1,1,1,1,1,7}
16: {1,1,1,1,2,2,2,2}
17: {1,1,1,1,2,2,4}
18: {1,1,1,1,2,3,3}
19: {1,1,1,1,2,6}
20: {1,1,1,1,3,5}
21: {1,1,1,1,4,4}
22: {1,1,1,1,8}
23: {1,1,1,2,2,2,3}
24: {1,1,1,2,2,5}
25: {1,1,1,2,3,4}
26: {1,1,1,2,7}
27: {1,1,1,3,3,3}
28: {1,1,1,3,6}
29: {1,1,1,4,5}
30: {1,1,1,9}
31: {1,1,2,2,2,2,2}
32: {1,1,2,2,2,4}
33: {1,1,2,2,3,3}
34: {1,1,2,2,6}
35: {1,1,2,3,5}
36: {1,1,2,4,4}
37: {1,1,2,8}
38: {1,1,3,3,4}
39: {1,1,3,7}
40: {1,1,4,6}
41: {1,1,5,5}
42: {1,1,10}
43: {1,2,2,2,2,3}
44: {1,2,2,2,5}
45: {1,2,2,3,4}
46: {1,2,2,7}
47: {1,2,3,3,3}
48: {1,2,3,6}
49: {1,2,4,5}
50: {1,2,9}
51: {1,3,3,5}
52: {1,3,4,4}
53: {1,3,8}
54: {1,4,7}
55: {1,5,6}
56: {1,11}
57: {2,2,2,2,2,2}
58: {2,2,2,2,4}
59: {2,2,2,3,3}
60: {2,2,2,6}
61: {2,2,3,5}
62: {2,2,4,4}
63: {2,2,8}
64: {2,3,3,4}
65: {2,3,7}
66: {2,4,6}
67: {2,5,5}
68: {2,10}
69: {3,3,3,3}
70: {3,3,6}
71: {3,4,5}
72: {3,9}
73: {4,4,4}
74: {4,8}
75: {5,7}
76: {6,6}
77: {12}
Число различных по структуре мультимножества длины циклов классов эквивалентности перестановок из N элементов образует следующий числовой ряд:
1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77
Он уже представлен в OEIS (см. https://oeis.org/A000041) и представляет собой т.н. разбиения числа (см. https://ru.wikipedia.org/wiki/Разбиение_числа) — число способов представления целого положительного числа N в виде суммы целых положительных слагаемых b(1) + b(2) + b(3) + ... + b(m) = N, причем b(i) <= b(i+1).
Вот так в математике все связано: от латинских квадратов к перестановкам, от них — к циклам в их составе, а от мультимножеств длин циклов — к разбиениям числа на слагаемые!