Форум

Пожалуйста or Регистрация для создания сообщений и тем.

Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...

PreviousPage 161 of 161

Возьмем и посмотрим на пример ДЛК

3 4 8 1 10 0 5 9 2 6 7
8 10 6 7 5 1 9 3 4 0 2
2 1 0 3 4 5 6 7 10 8 9
1 5 3 6 0 2 10 4 7 9 8
10 6 9 2 7 8 3 5 1 4 0
7 2 5 10 6 9 4 8 0 1 3
5 3 10 0 2 4 8 6 9 7 1
4 0 2 5 9 3 7 1 8 10 6
9 7 1 4 8 6 2 0 5 3 10
0 8 4 9 3 7 1 10 6 2 5
6 9 7 8 1 10 0 2 3 5 4

Он очень похож на горизонтально симметричный ДЛК (см. рисунок во вложении, там нагляднее, т.к. некоторые симметричные пары значений выделены). На самом деле данный квадрат симметричным в горизонтальной плоскости быть не может как минимум потому, что его порядок N=11, а плоскостная симметрия существует только для квадратов четных порядков, да и не все пары значений при отражении от вертикальной прямой, проходящей через центр квадрата, в сумме дают N-1 = 10. Существование подобных квадратов в очередной подтверждает выдвинутый ранее тезис о том, что "полная" симметрия может не существовать, а в частичном виде очень даже. При этом ранее также неоднократно было замечено, что свойства частично симметричных ДЛК с большим числом симметрично заполненных ячеек M интересны и очень близки к свойствам полностью симметричных ДЛК.

Для формирования подобных квадратов с частичной плоскостной симметрией был разработан специальный генератор с рядом особенностей (аналогичные генераторы для четных порядков N отличаются деталями реализации). Данный генератор позволяет формировать выборки произвольного объема из частично симметричных ДЛК произвольного порядка N с произвольно заданным числом симметрично расположенных ячеек M. Пример работы генератора для N=11 и M=80 приведен ниже:

4 0 2 7 5 1 9 3 8 10 6
6 3 8 9 0 4 10 1 2 7 5
1 8 0 6 3 2 7 4 10 5 9
7 2 6 1 10 0 5 9 4 8 3
8 6 10 5 9 3 1 7 0 4 2
9 1 7 0 4 5 6 10 3 2 8
10 5 1 3 8 7 2 0 6 9 4
3 10 4 2 6 9 0 8 5 1 7
5 9 3 4 2 10 8 6 7 0 1
2 4 9 10 7 8 3 5 1 6 0
0 7 5 8 1 6 4 2 9 3 10

0 1 2 3 4 5 6 7 8 9 10
5 10 4 1 8 2 3 9 6 0 7
8 3 9 4 7 0 5 6 1 10 2
6 7 10 8 1 3 9 2 4 5 0
9 5 3 6 2 4 8 10 0 7 1
1 2 0 10 5 6 7 4 3 8 9
10 6 8 5 9 7 1 0 2 4 3
2 0 1 7 3 9 4 5 10 6 8
4 9 5 2 0 8 10 3 7 1 6
7 4 6 0 10 1 2 8 9 3 5
3 8 7 9 6 10 0 1 5 2 4

0 1 2 3 4 5 6 7 8 9 10
5 10 4 1 8 2 3 9 6 0 7
8 3 9 4 7 0 5 6 1 10 2
6 7 10 8 1 3 9 2 4 5 0
9 5 0 6 2 4 8 10 3 7 1
1 2 3 10 5 6 7 4 0 8 9
10 6 8 5 9 7 1 0 2 4 3
2 0 1 7 3 9 4 5 10 6 8
4 9 5 2 0 8 10 3 7 1 6
7 4 6 0 10 1 2 8 9 3 5
3 8 7 9 6 10 0 1 5 2 4

0 1 2 3 4 5 6 7 8 9 10
5 10 4 1 8 2 3 9 6 0 7
8 3 9 4 7 0 5 6 1 10 2
6 7 10 8 1 3 9 2 4 5 0
9 5 6 0 2 4 8 10 3 7 1
1 2 3 10 5 6 7 4 0 8 9
10 6 8 5 9 7 1 0 2 4 3
2 0 1 7 3 9 4 5 10 6 8
4 9 5 2 0 8 10 3 7 1 6
7 4 0 6 10 1 2 8 9 3 5
3 8 7 9 6 10 0 1 5 2 4

0 1 2 3 4 5 6 7 8 9 10
1 2 4 7 0 3 10 6 5 8 9
7 5 8 9 10 6 0 1 2 4 3
4 6 9 10 3 8 7 0 1 2 5
9 7 10 2 5 1 4 8 0 3 6
3 10 6 4 8 7 2 5 9 0 1
6 3 5 0 1 2 9 10 4 7 8
8 0 1 6 9 4 5 3 7 10 2
10 4 3 8 2 0 1 9 6 5 7
2 9 7 5 6 10 8 4 3 1 0
5 8 0 1 7 9 3 2 10 6 4

0 1 2 3 4 5 6 7 8 9 10
5 2 0 6 1 7 9 3 10 8 4
8 0 4 7 3 6 1 9 5 10 2
1 10 8 5 6 3 7 4 2 0 9
2 5 9 10 7 4 3 1 0 6 8
3 6 5 0 2 9 8 10 4 1 7
9 4 7 1 0 8 10 6 3 2 5
10 3 6 2 5 1 4 8 9 7 0
7 8 1 9 10 2 0 5 6 4 3
4 7 10 8 9 0 5 2 1 3 6
6 9 3 4 8 10 2 0 7 5 1

0 1 2 3 4 5 6 7 8 9 10
1 10 6 8 3 2 7 5 4 0 9
4 8 9 10 7 3 5 0 1 2 6
10 4 3 2 5 9 1 8 7 6 0
6 3 8 5 1 0 9 10 2 7 4
8 5 4 9 10 7 0 3 6 1 2
9 7 10 0 2 6 8 4 5 3 1
7 0 1 4 8 10 2 6 9 5 3
2 9 5 6 0 4 10 1 3 8 7
5 6 0 7 9 1 3 2 10 4 8
3 2 7 1 6 8 4 9 0 10 5

0 1 2 3 4 5 6 7 8 9 10
6 7 0 1 8 2 3 9 10 5 4
9 10 5 8 3 6 4 2 7 0 1
2 3 4 10 5 9 7 0 6 1 8
5 0 9 6 2 3 8 4 1 10 7
1 8 3 7 10 4 0 5 9 6 2
7 6 10 2 1 8 9 3 0 4 5
10 4 8 9 6 7 5 1 2 3 0
8 5 6 4 0 1 2 10 3 7 9
4 2 7 0 9 10 1 6 5 8 3
3 9 1 5 7 0 10 8 4 2 6

0 1 2 3 4 5 6 7 8 9 10
8 10 3 1 2 7 4 9 5 0 6
5 4 9 10 7 2 8 0 1 6 3
4 3 1 2 0 6 10 8 9 5 7
7 5 6 0 8 1 2 10 4 3 9
10 8 7 9 5 4 3 1 6 2 0
6 2 0 5 9 10 1 3 7 8 4
1 0 8 7 3 9 5 6 10 4 2
2 7 5 6 1 0 9 4 3 10 8
9 6 4 8 10 3 0 5 2 7 1
3 9 10 4 6 8 7 2 0 1 5

0 1 2 3 4 5 6 7 8 9 10
10 7 8 4 9 2 1 5 6 3 0
5 10 9 8 3 6 7 2 1 0 4
3 8 10 5 6 9 2 4 0 1 7
8 5 3 10 1 4 9 0 7 6 2
4 9 1 7 0 8 3 6 2 10 5
1 2 0 6 5 7 4 3 10 8 9
7 4 6 0 2 3 8 10 9 5 1
6 0 7 2 10 1 5 9 3 4 8
9 6 4 1 7 0 10 8 5 2 3
2 3 5 9 8 10 0 1 4 7 6

А раз у нас есть новый интересный генератор, то следующим шагом стоит посмотреть на свойства формируемых им ДЛК...

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array
hoarfrost и Шмяка отреагировали на эту запись.
hoarfrostШмяка
Цитата: Yura12 от 16.11.2022, 20:17

А нельзя как-то организоваться в Вашем институте, чтобы привлечь к этому делу студентов, пишущих курсовые / дипломные, может даже аспирантов, чтобы они оказывали бы помощь, взяли на себя хоть часть работы, чтобы дело пошло быстрее?

Мечты...

PS. Рассмотренная выше задача с генератором частично-плоскостно-симметричных ДЛК примерно год назад была поставлена одному моему студенту (бакалавру). Он сделал ее кусками, которые ничего нового не дали (известные куски спектров малых порядков, пристрелочные запуски), а потом устроился работать и пропал, как это обычно и бывает. Он же пытался делать приложение под Linux, о чем меня здесь постоянно просят и о чем я помню. Оно даже по-UpperCase-ило строки, до более серьезного кода мы не добрались. Видимо опять делать мне, а я один все не успеваю... И это еще при том, что студент толковый и от меня получал вполне заслуженные пятерки, таких последнее время немного. Перспектив для улучшения ситуации в обозримой перспективе я не вижу, причины в общем-то понятны нам внизу и непонятны руководству нашей системы образования наверху. Компетенциями, профстандартами, инновациями, стартапами и онлайн-образованием ситуацию не улучшить, а именно этим нас убеждают заниматься и это отнимает кучу времени, которого всегда мало и которое можно было бы потратить с большей пользой

Array
DrMOS отреагировал на эту запись.
DrMOS

Обработка спектра числа трансверсалей в ДЛК порядка 13, полученного от квадратов Гергели путем вращения 1 интеркалята успешно завершена. Для этого потребовалось около 2 суток расчетов в проекте RakeSearch и последующая обработка хвоста в однопоточном режиме, на что ушло 4,5 суток. В результате спектр расширен с 282 до 37849 элементов (см. нижний ряд диаграмм на картинке во вложении). К расчету подготовлены чуть более чем 37 тыс. WU'шек с целью дальнейшего расширения данного спектра путем вращения 1 цикла.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array
Шмяка отреагировал на эту запись.
Шмяка

В OEIS подтверждены правки по добавлению двух новых числовых рядов:

* https://oeis.org/A357473 — число типов обобщенных симметрий в ДЛК;
* https://oeis.org/A357514 — минимальное число трансверсалей в ДЛК.

Второй ряд интересен тем, что с его использованием можно наложить соответствующее условие при работе канонизатора и заранее отсекать квадраты с малым числом трансверсалей, не производя для них поиск покрытия (т.е. не делая одну итерацию запуска DLX), что снижает необходимые вычислительные затраты на 10-15% (тестирование выполнено совместно с Assa).

Первый ряд интересен в куда большей степени. Симметриями в ДЛК мы занимаемся довольно давно (плоскостными, двойной, центральной, обобщенными, затем частичными в хронологическом порядке), однако в OEIS данная тематика ранее не была отражена (как нами по ДЛК, так и другими научными группами по ЛК, свойства которых исследованы в куда большей мере, чем свойства ДЛК). Так сказать первая ласточка в данном направлении, радует, что ряд добавили без особых дискуссий. Впереди еще 3 аналогичных уже готовых ряда, будем добавлять...

Также подтверждены правки в числовом ряду https://oeis.org/A345760 (мощность спектра числа интеркалятов в ДЛК) по результатам недавно завершенного эксперимента полнопереборного эксперимента по спектрам в ДЛК порядка 9.

Array
Шмяка отреагировал на эту запись.
Шмяка

В OEIS добавлено описание нового числового ряда https://oeis.org/draft/A358394 — число типов обобщенных симметрий в ОДЛК, а также серия мелких правок в добавленных ранее рядах. Ждем подтверждения...

Array
Шмяка отреагировал на эту запись.
Шмяка

В настоящей серии экспериментов, выполняемых на моей машине ("легкие" запуски и обработка хвостов) и в проекте RakeSearch ("тяжелые" запуски), основное внимание уделено построению спектров ДЛК. А еще есть спектры ОДЛК, по которым ранее были выполнены отдельные эксперименты на моей машине и в перспективе планируются еще. Нельзя ли из первых спектров, которые в достаточной степени близки к идеалу, попытаться получить вторые? Можно, для этого необходимо взять значения спектров ДЛК и отсеять из них те, которые являются пустышками. Для этого были дописаны несколько подпрограмм, суть которых сводится к построению не всех покрытий по известному множеству трансверсалей, а только первого из них. Каждое покрытие (речь идет об алгоритме DLX) представляет собой отдельный ОДЛК, которых в общем случае может быть достаточно много (для ОДЛК порядка 12 до нескольких миллиардов) и их построение может занимать достаточно много времени (до месяца на грид). А в данном случае для того, чтобы убедиться в том, что проверяемый ДЛК не является пустышкой, достаточно получить только один ортогональный соквадрат, а не все, что существенно быстрее.

На данный момент новый код был апробирована на ДЛК порядков 10-12. Для порядка N=10 новых значений в спектрах ОДЛК не появилось, что в общем-то логично, т.к. у нас в наличии имеется внушительный список КФ ОДЛК данного порядка (почти 20 млн. КФ), который был получен различными способами (случайные ДЛК, симметричные, частично-симметричные, от простых преобразований) и по которому производилось построение данных спектров. Для порядка N=11 спектры числа трансверсалей и интеркалятов так же расширить не удалось, а вот мощность спектра числа диагональных трансверсалей удалось увеличить с 390 до 452 элементов, новые элементы группируются в основном в старшей части спектра. В настоящее время аналогичные эксперименты для размерности N=12 выполняются в однопоточном режиме на моей машине (при необходимости в перспективе они могут быть перенесены в проект). Ждем результатов...

#ODLS

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array
DrMOS и Шмяка отреагировали на эту запись.
DrMOSШмяка
PreviousPage 161 of 161