BOINC project Rake Search

Message boards : Cafe : BOINC project Rake Search
Message board moderation

To post messages, you must log in.

1 · 2 · 3 · 4 · Next

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 441 - Posted: 13 Sep 2017, 19:20:30 UTC
Last modified: 13 Sep 2017, 20:37:59 UTC

BOINC-проект Rake Search представлен здесь
http://forum.boinc.ru/default.aspx?g=posts&t=2063#post88950

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

Более подробное описание вы можете увидеть в презентации к докладу, прочитанном на недавно завершившейся конференции BOINC::FAST'2017 (RU | EN).

Проект развёрнут на площадке Иститута прикладных математических исследований Карельского Научного Центра РАН, его младшим научным сотрудником - Натальей Никитиной, а при создании алгоритма поиска использовались идеи Олега Заикина, Эдуарда Ватутина, Алексея Журавлёва и Степана Кочемазова.

Появился проект ещё 11 августа (эта дата - его настоящий День Рождения), но до начала сентября был в стадии проверки идеи и переноса приложения на инфраструктуру BOINC. Сейчас же в нём запущен целевой эксперимент - поиск на множестве диагональных латинских квадратов (ДЛК) ранга 9.

В настоящее время в проекте есть приложение только для платформ Linux x86 и x86-64, в случае появления приложения для Windows об этом, безусловно, будет сообщено. Приглашаем всех, кому интересно участие в решении подобной задачи, присоединиться к нашему проекту, расположенному по адресу http://82.196.66.12:12179/rakesearch/ .

В цитате, к сожалению, не отображаются ссылки на презентацию доклада.
Чтобы получить эти ссылки, надо пройти к оригинальному сообщению на форум boinc.ru
Презентацию на английском языке я выложила здесь
https://boinc.progger.info/odlk/forum_thread.php?id=22&postid=383#383
https://yadi.sk/i/S417t0IpwnP6r
ID: 441 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 442 - Posted: 13 Sep 2017, 19:25:05 UTC
Last modified: 13 Sep 2017, 20:12:21 UTC

И далее сообщается новый адрес проекта

У проекта появился нормальный адрес: http://rake.boincfast.ru/rakesearch/

отсюда
http://forum.boinc.ru/default.aspx?g=posts&t=2063#post88950

Поскольку данный BOINC-проект близок по тематике нашему BOINC-проекту ODLK, предлагаю это обсуждение.

Я уже писала выше, что описание проекта, данное на главной странице, не совсем понятно. Вот это описание:

RakeSearch is a research project that uses Internet-connected computers to search for diagonal Latin squares. You can contribute to our research by running a free program on your computer.

В описании написано, насколько я могу понимать английский язык, что в проекте выполняется поиск диагональных латинских квадратов (diagonal Latin squares).
В презентации доклада речь идёт об ортогональных диагональных латинских квадратах, получаемых перестановкой строк.

Предлагаю авторам написать более точное и немного развёрнутое описание проекта.
https://yadi.sk/i/S417t0IpwnP6r
ID: 442 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 443 - Posted: 13 Sep 2017, 19:43:11 UTC
Last modified: 13 Sep 2017, 19:47:39 UTC

В презентации приведён «цикл из ОДЛК ранга 9»



Первые три ДЛК получаются друг из друга перестановкой строк.
При этом второй и третий ДЛК абсолютно одинаковые, как мне кажется.
Или это только мне так кажется? :)
Четвёртый ДЛК сам по себе, то есть перестановкой строк из первых трёх ДЛК не получается.
Кроме того, ДЛК этого цикла не являются попарно ортогональными.
На иллюстрации показаны ортогональные и не ортогональные пары ДЛК, образуемые квадратами цикла.

Далее я покажу полную систему MOLS 9-го порядка, полученную в cистеме Maple.
[MOLS означает: взаимно (или попарно) ортогональные латинские квадраты.]
https://yadi.sk/i/S417t0IpwnP6r
ID: 443 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 444 - Posted: 13 Sep 2017, 20:05:03 UTC
Last modified: 13 Sep 2017, 20:07:59 UTC

Вот полная система MOLS из 8 ЛК 9-го порядка, построенная в матпакете Maple



См. мою статью
http://www.natalimak1.narod.ru/grolk.htm
(рис. 7)

В этой системе все ЛК получаются друг из друга перестановкой строк.
При этом 6 из 8 ЛК являются диагональными.

А что хотят найти авторы BOINC-проекта Rake Search?
https://yadi.sk/i/S417t0IpwnP6r
ID: 444 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 445 - Posted: 13 Sep 2017, 20:19:44 UTC

Progger
поскольку вы считаете в этом BOINC-проекте, подключайтесь к обсуждению :)
Расскажите, пожалуйста, что вы насчитали, есть ли какие-нибудь результаты.

Очень хотелось бы видеть в обсуждении авторов проекта.
Я пообсуждала бы проект на форуме boinc.ru, но увы... не могу.
https://yadi.sk/i/S417t0IpwnP6r
ID: 445 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 446 - Posted: 13 Sep 2017, 20:28:10 UTC

Один из авторов проекта hoarfrost писал на форуме boinc.ru

Первоначально было сгенерировано 1000 workunits и, в соответствии и initial replication == 2 - 2000 tasks.
Сейчас в очереди осталось 1045 задач, у нескольких сотен workunit-ов есть канонический результат. Но пар ОДЛК среди них пока нет. (Это - на вчерашний вечер).

Что означает "есть канонический результат"?

Кстати, hoarfrost участник нашего BOINC-проекта ODLK.
Может быть, он расскажет нам о проекте более подробно?
https://yadi.sk/i/S417t0IpwnP6r
ID: 446 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 447 - Posted: 13 Sep 2017, 20:35:13 UTC

BOINC-проект Rake Search обсуждается на польском форуме
http://www.boincatpoland.org/smf/ostatnio-znalezione/rakesearch/

Там и наш BOINC-проект ODLK обсуждается, поэтому я туда заглядываю и даже изредка пишу сообщения :)
https://yadi.sk/i/S417t0IpwnP6r
ID: 447 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 449 - Posted: 14 Sep 2017, 5:28:17 UTC
Last modified: 14 Sep 2017, 7:28:06 UTC

Э. Ватутин писал на форуме boinc.ru

Для некоторых размерностей ДЛК есть ОДЛК, которые получаются путем перестановки строк исходного ДЛК. Например, для N=10 таких мы не нашли, а для других размерностей они есть. Соответственно можно сделать специализированную программную реализацию, в которой будет производиться поиск таких перестановочных пар, что и сделали hoarfrost и Natalia Nik

Я тоже не нашла примеров, когда перестановка строк в ДЛК 10-го порядка даёт ДЛК ортогональный исходному.
Но! Можно получить из некоторого ДЛК 10-го порядка перестановкой строк другой ДЛК, который имеет ортогональный ДЛК.
Такой результат получается, например, от ДЛК из статьи Брауна и др. (статья указана в описании нашего BOINC-проекта ODLK).

Кроме того, перестановкой строк можно получить ЛК ортогональный исходному.
Пример я нашла, исследуя ЛК Лямзина.

Опубликовано тут
http://sat.isa.ru/pdsat/forum_thread.php?id=542#853

Псевдотройка #2

ЛК №1
9 7 5 2 4 0 8 3 6 1
7 9 8 6 3 5 1 0 4 2
5 8 9 0 7 4 6 2 1 3
2 6 0 9 1 8 5 7 3 4
4 3 7 1 9 2 0 6 8 5
0 5 4 8 2 9 3 1 7 6
8 1 6 5 0 3 9 4 2 7
3 0 2 7 6 1 4 9 5 8
6 4 1 3 8 7 2 5 9 0
1 2 3 4 5 6 7 8 0 9

ЛК №2
7 9 8 6 3 5 1 0 4 2
5 8 9 0 7 4 6 2 1 3
2 6 0 9 1 8 5 7 3 4
4 3 7 1 9 2 0 6 8 5
0 5 4 8 2 9 3 1 7 6
8 1 6 5 0 3 9 4 2 7
3 0 2 7 6 1 4 9 5 8
6 4 1 3 8 7 2 5 9 0
9 7 5 2 4 0 8 3 6 1
1 2 3 4 5 6 7 8 0 9

ЛК №3
6 4 1 3 8 7 2 5 9 0
9 7 5 2 4 0 8 3 6 1
7 9 8 6 3 5 1 0 4 2
5 8 9 0 7 4 6 2 1 3
2 6 0 9 1 8 5 7 3 4
4 3 7 1 9 2 0 6 8 5
0 5 4 8 2 9 3 1 7 6
8 1 6 5 0 3 9 4 2 7
3 0 2 7 6 1 4 9 5 8
1 2 3 4 5 6 7 8 0 9

В этой тройке все ЛК получаются друг из друга перестановкой строк.
Здесь две ортогональные пары: ЛК №1-ЛК №2 и ЛК №1-ЛК №3.
https://yadi.sk/i/S417t0IpwnP6r
ID: 449 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 450 - Posted: 14 Sep 2017, 10:19:25 UTC
Last modified: 14 Sep 2017, 10:22:10 UTC

Цитата из моей статьи, указанной выше:

Думаю, что для всех порядков группа взаимно ортогональных латинских квадратов, составленная в Maple, не единственная. В статье “Handbook of Combinatorial Design” нашла подтверждение для порядка 9. В этой статье приведено несколько групп взаимно ортогональных латинских квадратов 9-го порядка. Вот одна из них:

123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789
231564897 456789123 645978312 897231564 312645978 564897231 789123456 978312645
312645978 789123456 897231564 645978312 231564897 978312645 456789123 564897231
456789123 312645978 978312645 564897231 789123456 645978312 231564897 897231564
564897231 645978312 231564897 312645978 978312645 789123456 897231564 456789123
645978312 978312645 456789123 789123456 897231564 231564897 564897231 312645978
789123456 231564897 564897231 978312645 456789123 897231564 312645978 645978312
897231564 564897231 789123456 456789123 645978312 312645978 978312645 231564897
978312645 897231564 312645978 231564897 564897231 456789123 645978312 789123456

Примечание: латинские квадраты записаны в нетрадиционной форме, то есть с помощью чисел 1, 2, 3 … 9. Я не стала их переводить в традиционную форму записи.

Интересно отметить, что в этой группе тоже два не диагональных латинских квадрата, при этом не диагональные квадраты в точности совпадают с не диагональными квадратами приведённой выше группы, построенной в Maple. А все диагональные квадраты другие.

Статья, конечно, называется не "Handbook of Combinatorial Design", а "Mutually Orthogonal Latin Squares (MOLS)", авторы R. Julian R. Abel, Charles J. Colbourn, Jeffrey H. Dinitz.
В статье приведено много комплектов MOLS 9-го порядка. Надо понять, что это за комплекты, а для этого хорошо знать английский язык.

Я выложила статью на Яндекс.Диск
https://yadi.sk/i/x1w4tkQx3MsvHw

Может, кому-то интересно разобраться с этими комплектами (о них в главе 3.5 "Complete Sets of Order 9", стр. 171)
https://yadi.sk/i/S417t0IpwnP6r
ID: 450 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 477 - Posted: 19 Sep 2017, 2:25:04 UTC
Last modified: 19 Sep 2017, 3:23:18 UTC

Сообщается о первых результатах в BOINC-проекте Rake Search
Вчера, 17 сентября 2017 года н.э., в 160-годовщину со для рождения Константина Эдуардовича Циолковского, среди общего набора результатов, были обнаружены и первые пары ОДЛК, найденные несколькими наиболее активными участниками проекта и, которые вы можете увидеть на странице http://rake.boincfast.ru...search/odls_results.html .

Теперь можно хотя бы увидеть, что ищется.
Итак, показаны ортогональные пары ДЛК 9-го порядка (ортогональность не проверяла), получающиеся друг из друга перестановкой строк.

Из 6 ДЛК этой группы MOLS 9-го порядка



можно составить 15 подобных ортогональных пар.

Далее в указанной выше статье приведены 19 не эквивалентных групп MOLS 9-го порядка. Есть и такие группы, в которых ЛК получаются перестановкой строк (кажется, их две, но не уверена - тщательно не рассматривала группы).
Цитирую статью:

3.77 Remarks Owens and Preece [1710] determined the 19 equivalence classes of complete
sets of MOLS of order 9, using a definition of equivalence that permits reordering the
rows and columns of all squares together, and the symbols of each square individu-
ally. There are four nonisomorphic projective planes: the desarguesian plane Φ, the
translation plane Ω, the dual translation plane ΩD, and the Hughes plane Ψ. See
§VII.2.
3.78 Table The 19 inequivalent complete sets of order 9. For each, the eight orthogonal
latin squares are given, and under each is provided a name for the isotopy class to
which the square belongs (see [1710]), and the number of intercalates in the square.
For each set, the plane from which it arises is given along with some information
about the manner in which the complete set is formed. Here, �∞ is the line at infinity,
t is the translation line of Ω, and T is the translation point of ΩD. In the Hughes
plane, lines are classified as real or complex [1819]. Details are given in [1710]. 172 Mutually Orthogonal Latin Squares (MOLS) III.3

Вопрос: не являются ли найденные в проекте решения эквивалентными давно известным ортогональным парам ДЛК 9-го порядка?

Я не знаю механизм получения эквивалентных групп MOLS 9-го порядка. В цитате говорится о переупорядочении строк и столбцов вместе (то есть, как я понимаю, одновременно во всех квадратах группы).
https://yadi.sk/i/S417t0IpwnP6r
ID: 477 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 481 - Posted: 19 Sep 2017, 5:59:24 UTC
Last modified: 19 Sep 2017, 6:06:38 UTC

Да, совсем забыла.
Надо привлечь теорию Белышева о канонической форме (КФ) ДЛК.
Тогда сразу можно проверять найденные ортогональные пары на уникальность.

Может, авторы проекта так и делают (?)

И далее размышляю.
Если взять конкретный нормализованный ДЛК 9-го порядка, выполнить в нём все перестановки строк (их не так и много, всего 8!=40320), выбрать из полученных ЛК все ДЛК, их тоже будет не так много. Затем среди полученных ДЛК искать ортогональные пары.
Правильно я понимаю алгоритм поиска?
Тогда львиную долю времени займёт второй этап - проверка на ортогональность. Тут всё зависит от того, как много получится ДЛК.

А в качестве исходного ДЛК, наверное, надо брать как раз КФ ДЛК. И ортогональные соквадраты искать к нему же.
https://yadi.sk/i/S417t0IpwnP6r
ID: 481 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 494 - Posted: 20 Sep 2017, 4:30:54 UTC
Last modified: 20 Sep 2017, 4:34:09 UTC

Вопрос с форума boinc.ru

А вот у меня вопрос: найденные пары ОДЛК принципиально новые (никогда ранее никем не были найдены) или просто первые на этом проекте?

Хороший вопрос :)
Точно такой же вопрос я задала чуть выше.
Ответа пока нет - ни тут, ни там.
https://yadi.sk/i/S417t0IpwnP6r
ID: 494 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 502 - Posted: 20 Sep 2017, 13:18:10 UTC - in response to Message 494.  
Last modified: 20 Sep 2017, 13:22:37 UTC

А вот и ответ hoarfrost

Утверждать, что эти пары ОДЛК никогда и никто не видел - было бы наверное глупо - прямо в стиле проблемы чайника Рассела.
Но и задача проекта - не открыть какие-то отдельные пары, а получив набор таких ОДЛК, изучить их свойства на этапе постобработки.

отсюда
http://forum.boinc.ru/default.aspx?g=posts&m=89114#post89114

После этого ответа у меня появилось ещё больше вопросов.

1. Могут ли авторы проекта установить эквивалентность найденных ортогональных пар известным ортогональным парам?
2. Если все найденные ортогональные пары эквивалентны известным ортогональным парам, зачем их заново искать?
Можно взять известные ортогональные пары и изучать их свойства.
3. Какие свойства ортогональных пар авторы хотят изучить?
Ну, ортогональная пара ДЛК 9-го порядка, получаются ДЛК перестановкой строк. Дальше что?
4. Ищут в проекте только ортогональные пары ДЛК 9-го порядка?
А например, группы из 2, 3, 4 и т.д. ортогональных пар ДЛК, - не ищут?
https://yadi.sk/i/S417t0IpwnP6r
ID: 502 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 503 - Posted: 20 Sep 2017, 14:44:44 UTC

Согласно данным, приведённым в книге Ю. В. Чебракова "Магические квадраты. Теория чисел, Алгебра, Комбинаторный анализ" (С Петербург, 1995), существует 192 ДЛК, получаемых из данного ДЛК 9-го порядка М-преобразованиями (то есть такими перестановками строк и столбцов, которые сохраняют диагональность квадрата). Умножив это число на 8 основных преобразований, получаем 1536 ДЛК. Всего!
Эти ДЛК надо нормализовать и выбрать из полученных нормализованных ДЛК минимальный ДЛК в лексикографическом порядке. Это и будет КФ (каноническая форма) данного ДЛК 9-го порядка.

У Белышева наверняка есть программа канонизации ДЛК 9-го порядка.
Точно такая же, как программа канонизации ДЛК 10-го порядка, которой мы пользуемся в нашем BOINC-проекте ODLK.
Мы ведь в нашем проекте тоже ищем ортогональные пары, только для ДЛК 10-го порядка (а также группы из 2, 3, 4 и т.д. ортогональных пар).
Но мы ищем только уникальные ортогональные пары (и группы ортогональных пар), отбрасывая все изоморфные (эквивалентные) ортогональные пары. Для определения изоморфных (эквивалентных) ортогональных пар и служат КФ ДЛК.

Впрочем, что я это всё рассказываю... Авторы проекта, наверное, всё это знают и применяют.
Очень трудно обсуждать, если заинтересованные лица в обсуждении не участвуют.
https://yadi.sk/i/S417t0IpwnP6r
ID: 503 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 504 - Posted: 21 Sep 2017, 6:32:02 UTC
Last modified: 21 Sep 2017, 6:34:40 UTC

Я всё-таки продолжу.
Ещё эффективнее задействовать сильно нормализованные (СН) ДЛК, их намного меньше, чем нормализованных ДЛК.
Интересная информация о ДЛК 8-го порядка, выложенная Белышевым на форуме boinc.ru

Вот, например, выдача программы подсчета ДЛК8 в один поток на ноутбуке:

Линейка Классов     СНДЛК        НДЛК
 
lin 1:     8148    855680    10268160
lin 2:   137801   1087936   208883712
lin 3:    10092    607872    14588928
lin 4:   270633   1075784   413101056
lin 5:   214433   1714248   329135616
lin 6:   193044   1537024   295108608
lin 7:   421525   1678124   644399616
lin 8:    51530   1607168    77144064
lin 9:   414374   1656184   635974656
lin 10:  412695   1649308   633334272
lin 11:  135729   1072016   205827072
lin 12:   46301   1472416    70675968
lin 13:  103873   1641968   157628928
lin 14:    4040    480000     5760000
lin 15:  135595   2079952   199675392
lin 16:  213166   1701792   326744064
lin 17:  837748   1673128  1284962304
lin 18:  405668   1621760   622755840
lin 19:  419434   1675696   643467264
lin 20:  437267   1739980   668152320
Всего:  4873096  28628036  7447587840
 
Время работы: 90.457 сек

Так быстро для ДЛК порядка 8 - всего 90 секунд!
Конечно, для ДЛК порядка 9 сложнее.
Ещё сложнее для ДЛК порядка 10, но мы пользуемся в нашем BOINC-проекте теорией о СН ДЛК, потому что она эффективна.
https://yadi.sk/i/S417t0IpwnP6r
ID: 504 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 616 - Posted: 6 Oct 2017, 18:01:38 UTC
Last modified: 6 Oct 2017, 18:05:42 UTC

Секретные данные? :)



отсюда
http://forum.boinc.ru/default.aspx?g=posts&m=89307#post89307

Впервые такое встречаю на форумах.
Хотя... на одном форуме было более круто (правда, давно): ничего вообще читать не давали.
https://yadi.sk/i/S417t0IpwnP6r
ID: 616 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 89
Credit: 368,863
RAC: 373
Message 617 - Posted: 7 Oct 2017, 3:38:00 UTC - in response to Message 616.  

Это похоже какой-то глюк - я там точно залогинин, но у меня такое-же сообщение появляется.
ID: 617 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 782 - Posted: 26 Oct 2017, 6:11:11 UTC
Last modified: 26 Oct 2017, 6:18:27 UTC

Завершено построение всех центрально симметричных ОДЛК порядка 9: всего за 2 суток в 1 поток найдено около 6 млн. пар ОДЛК

Среди них есть квадрат

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

которому ортогональны 516 других ОДЛК (для N=9 пока это рекорд)

отсюда
http://forum.boinc.ru/default.aspx?g=posts&m=89479#post89479

Смотрим на полную систему MOLS 9-го порядка



Видим приведённый в цитате ДЛК - во втором ряду третий.
Вот, значит, какой рекордсмен :)
Небось в найденных парах (и других группах) ОДЛК 9-го порядка имеются и такие, в которых ДЛК получаются друг из друга перестановкой строк.
Такие пары ОДЛК имеются и на показанной иллюстрации - ровно 15 пар (уже писала об этом выше).
Например, пара №1
берём этот самый рекордсмен и прибавляем к нему третий квадрат на иллюстрации, вот вам и пара ОДЛК:

Square A
0 1 2 3 4 5 6 7 8 
6 7 8 0 1 2 3 4 5 
3 4 5 6 7 8 0 1 2 
5 3 4 8 6 7 2 0 1 
2 0 1 5 3 4 8 6 7 
8 6 7 2 0 1 5 3 4 
7 8 6 1 2 0 4 5 3 
4 5 3 7 8 6 1 2 0 
1 2 0 4 5 3 7 8 6

Square B
0 1 2 3 4 5 6 7 8
3 4 5 6 7 8 0 1 2
6 7 8 0 1 2 3 4 5
7 8 6 1 2 0 4 5 3
1 2 0 4 5 3 7 8 6
4 5 3 7 8 6 1 2 0
5 3 4 8 6 7 2 0 1
8 6 7 2 0 1 5 3 4
2 0 1 5 3 4 8 6 7

И так можно составить ровно 15 пар ОДЛК, и в каждой этой паре ДЛК получаются друг из друга перестановкой строк.
Дарю эти 15 пар ОДЛК BOINC-проекту Rake Search :)
К тому же, можно составить не только пары ОДЛК, но и тройки, четвёрки и т.д. вплоть до группы из 6 попарно ортогональных ДЛК.
При этом шестёрка будет одна, пятёрок - 6, четвёрок - 15, троек - 20, двушек - 15.

Кроме того, как я уже писала выше, кажется, есть ещё одна полная система MOLS 9-го порядка, не эквивалентная показанной, в которой ЛК тоже получаются перестановкой строк. И ДЛК в этой системе тоже есть. Тогда и в этой системе можно составить подобные пары ОДЛК.
Статью со всеми 19 (не эквивалентными) полными системами MOLS 9-го порядка я выложила выше.
Ну и, как уже сказала, можно посмотреть массив ортогональных пар ДЛК, о котором сообщается в цитате. Может, и там есть такие ортогональные пары ДЛК.
https://yadi.sk/i/S417t0IpwnP6r
ID: 782 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 783 - Posted: 26 Oct 2017, 6:47:31 UTC
Last modified: 26 Oct 2017, 7:09:32 UTC

Здесь
http://forum.boinc.ru/default.aspx?g=posts&m=89542#post89542
А. Белышев выложил канонизатор ДЛК 9-го порядка.
Спасибо!

КФ в формате СН ДЛК (сильно нормализованных ДЛК).
Теперь можно начать создавать БД КФ ОДЛК 9-го порядка.
Авторам проекта Rake Search будет небесполезно.

Я начинаю, господа! :)
Беру 6 ДЛК из показанной выше полной системы MOLS 9-го порядка и канонизирую их указанной программой, программа выдаёт только две КФ ДЛК! Вот они:

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

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

Посмотрите на эти ДЛК. Они ассоциативные! Чудесные квадратики!

Итак, эти две КФ можно считать началом БД КФ ОДЛК 9-го порядка.

Пожалуй, напомню:

Ещё эффективнее задействовать сильно нормализованные (СН) ДЛК, их намного меньше, чем нормализованных ДЛК.
Интересная информация о ДЛК 8-го порядка, выложенная Белышевым на форуме boinc.ru

Вот, например, выдача программы подсчета ДЛК8 в один поток на ноутбуке:

Линейка Классов     СНДЛК        НДЛК
 
lin 1:     8148    855680    10268160
lin 2:   137801   1087936   208883712
lin 3:    10092    607872    14588928
lin 4:   270633   1075784   413101056
lin 5:   214433   1714248   329135616
lin 6:   193044   1537024   295108608
lin 7:   421525   1678124   644399616
lin 8:    51530   1607168    77144064
lin 9:   414374   1656184   635974656
lin 10:  412695   1649308   633334272
lin 11:  135729   1072016   205827072
lin 12:   46301   1472416    70675968
lin 13:  103873   1641968   157628928
lin 14:    4040    480000     5760000
lin 15:  135595   2079952   199675392
lin 16:  213166   1701792   326744064
lin 17:  837748   1673128  1284962304
lin 18:  405668   1621760   622755840
lin 19:  419434   1675696   643467264
lin 20:  437267   1739980   668152320
Всего:  4873096  28628036  7447587840
 
Время работы: 90.457 сек

Так быстро для ДЛК порядка 8 - всего 90 секунд!
Конечно, для ДЛК порядка 9 сложнее.
Ещё сложнее для ДЛК порядка 10, но мы пользуемся в нашем BOINC-проекте теорией о СН ДЛК, потому что она эффективна.

Думаю, что составить БД КФ ОДЛК 9-го порядка (в формате СН ДЛК) - задача не очень сложная. По крайней мере, легче задачи составления БД КФ ОДЛК 10-го порядка.
https://yadi.sk/i/S417t0IpwnP6r
ID: 783 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 3466
Credit: 0
RAC: 0
Message 784 - Posted: 26 Oct 2017, 7:02:09 UTC
Last modified: 26 Oct 2017, 7:10:23 UTC

Кстати, КФ ДЛК-рекордсмена вот:

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

Одна из двух показанных выше КФ.

В формате нормализованного ДЛК это центрально-симметричный ДЛК (по Ватутину), а в формате СН ДЛК - это ассоциативный ДЛК.

Весьма интересно, сколько КФ имеется среди ортогональных диагональных соквадратов этого ДЛК-рекордсмена, которых аж 516.
https://yadi.sk/i/S417t0IpwnP6r
ID: 784 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · 3 · 4 · Next

Message boards : Cafe : BOINC project Rake Search


©2019 (C) Progger