Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

41 Страницы«<394041
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#801 Оставлено : 9 марта 2019 г. 21:44:37(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,695
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1893 раз в 917 постах
Автор: AlexA Перейти к цитате
Мне кажется, что тут теории "квадратостроения", подкрепленной проверкой вычислениями набралось, как минимум, на статью или доклад.

Не было мысли как-то это обобщить и на суд общественности выставить?


Если конечно вопрос адресован мне, то доклады делаются с завидной регулярностью, статьи публикуются. Вот видео и правда мы давно не снимали, это да. Последний доклад был сделан на НСКФ в Переславле и он был посвящен обобщенным симметриями и комбинаторным структурам, получаемым в их окрестностях. Неделю назад тот же материал в более популярной форме я докладывал на научном семинаре у себя на кафедре. Ближайшее выступление планируется в мае на Распознавании (всех желающих по прежнему приглашаем в гости!) — там я планирую рассказать о том, как квадратные задачи сводятся к задаче о точном покрытии, которая решается через DLX. Если не считать Натальи (нашей, не деда Макара), остальные с докладами выступать пока скромничают, хотя тоже могли бы 199

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#802 Оставлено : 11 марта 2019 г. 15:27:44(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 251

Сказал(а) «Спасибо»: 79 раз
Поблагодарили: 191 раз в 123 постах
Представляю программу Канонизатор_ДЛК_2.0, для её работы файл hash_tabl.bin не требуется.

Файл readme.txt



Пример консольного вывода:

Код:
Канонизатор ДЛК10

Введено ДЛК:            30534
Найдено КФ:             30502
КФ записаны в файл:     output.txt
Общее время работы:     0.296 сек

Для выхода нажмите любую клавишу . . .


Меня просили дать некоторые пояснения по программам Именатор_ЛК и Деименатор_ЛК, а именно — объяснить смысл "загадочного" кода:



Этот код основан на справедливости следующего (легко доказываемого) утверждения.

Утверждение. Перестановка P имеет в лексикографическом порядке номер, запись которого в факториальной системе счисления совпадает с таблицей инверсий обратной перестановки P'.

Например, пусть P будет следующей перестановкой {0,1,2,3,4}

Код:
01342


В лексикографическом порядке эта перестановка имеет номер 3 (нумерация с нуля). Обратная ей перестановка P' будет

Код:
01423


с таблицей инверсий

Код:
00110


Здесь, первая цифра означает число цифр больших 0 стоящих слева от 0 в записи перестановки P', вторая цифра — число цифр больших 1 стоящих слева от 1, и так далее. Последняя цифра всегда 0, так как в записи любой перестановки 5-го порядка слева от 4 не может быть больших цифр.

Вообще, пусть ABCD0 будет таблицей инверсий. Рассмотрим эту запись как запись некоторого числа X в факториальной системе счислений. То есть

Код:
X = A*4! + B*3! + C*2! + D


Для нашего примера получим

Код:
X = 0*4! + 0*3! + 1*2! + 1 = 3


В полном согласии с Утверждением.

Функция get_fnum принимает перестановку 9-го порядка (константа por = 10) и находит таблицу инверсий для обратной перестановки. Рассматривая последнюю как число в факториальной системе счисления, вычисляется номер заданной перестановки.

функция unget_fnum выполняет обратную работу — переводит номер перестановки в факториальную систему счисления. Рассматривая его как таблицу инверсий обратной перестановки, строится сама перестановка.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 11.03.2019(UTC)
Offline citerra  
#803 Оставлено : 13 марта 2019 г. 21:44:08(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,966

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 363 раз в 263 постах
После старта проекта PADLS, продолжения не последовало. Нет никакой информации о состоянии дел.
Фальстарт? А что же дальше?

Отредактировано пользователем 14 марта 2019 г. 8:44:01(UTC)  | Причина: Не указана

Offline citerra  
#804 Оставлено : 14 марта 2019 г. 10:12:53(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,966

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 363 раз в 263 постах
Дед макар косит под космонавта. И соскучился по грубой силе.
А где же нежная сила? А нафига. Это думать надо. К тому же идеи кончаются.
А здесь бери область покучерявей и шлепай готовой программой.
Однушки в хозяйстве пригодятся.
Offline whitefox  
#805 Оставлено : 14 марта 2019 г. 13:16:08(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 251

Сказал(а) «Спасибо»: 79 раз
Поблагодарили: 191 раз в 123 постах
Будем называть два ЛК связанными если они различаются только поворотом одного интеркалята. Очевидно, что отношение связанности инвариантно относительно эквивалентных преобразований. Два главных класса ЛК будем называть связанными если найдётся пара связанных ЛК один из которых принадлежит первому классу, а другой — второму.

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

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

Представляю программу tzs_lk, частично выполняющую эту задачу (на заданную глубину).

файл readme.txt


Фактически, граф GIL даёт нам ещё одну меру близости между ЛК — если два ЛК (то есть их главные классы) принадлежат одной компоненте связности графа GIL, то "расстояние" между ними равно кратчайшему расстоянию между соответствующими вершинами графа GIL. По определению полагаем, что расстояние между ЛК из разных компонент связности графа GIL равно бесконечности.

Задавая поиск на глубину d, мы полностью исследуем d-окрестность заданного ЛК. Очевидно, что эта d-окрестность лежит в 4d-окрестности в смысле расстояния Хэмминга.

Например, рассмотрим ЛК:

Код:
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 7 6 9 8
2 3 4 5 6 7 8 9 0 1
3 2 5 4 7 6 9 8 1 0
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 0 1 2 3 4 5
7 6 9 8 1 0 3 2 5 4
8 9 0 1 2 3 4 5 6 7
9 8 1 0 3 2 5 4 7 6

Программа Интеркалятор показывает, что этот ЛК имеет 25 не пересекающихся интеркалятов. То что интеркаляты не пересекаются большая удача — это позволит нам полностью исследовать всю соответствующую компоненту связности графа GIL, для чего будет достаточно задать глубину поиска 25.

Код:
Частичное транзитивное замыкание связанности ЛК

Задайте глубину поиска: 25

Построено КФ ЛК: 23
Сохранение     : выполнено
Время работы   : 4.867 сек

Для выхода нажмите Enter . . .


На самом деле, глубину поиска можно было задать и 4.

Код:
Частичное транзитивное замыкание связанности ЛК

Задайте глубину поиска: 4

Построено КФ ЛК: 23
Сохранение     : выполнено
Время работы   : 2.964 сек

Для выхода нажмите Enter . . .


Заданный ЛК является блочным ЛК вида 5x5 из семейства JQS в которое входят 23 ЛК. Вот их-то мы и получили. То есть все эти 23 ЛК лежат в 4-окрестности заданного ЛК в смысле графа GIL, и в 16-окрестности в смысле расстояния Хэмминга.

Ещё пример, возьмём ЛК:

Код:
0 3 8 9 2 7 5 6 4 1
3 1 6 8 9 4 2 5 0 7
5 4 2 7 6 9 0 3 1 8
8 9 0 3 7 2 4 1 5 6
9 5 7 0 4 6 1 8 2 3
1 2 4 6 8 5 7 9 3 0
7 8 3 5 0 1 6 4 9 2
4 0 9 2 1 3 8 7 6 5
6 7 5 1 3 0 9 2 8 4
2 6 1 4 5 8 3 0 7 9

Интеркалятор показывает, что этот ЛК имеет 57 интеркалятов. Множество пересекающихся интеркалятов приводит к тому, что соответствующая компонента связности графа GIL огромна. Исследуем её на глубину 4.

Код:
Частичное транзитивное замыкание связанности ЛК

Задайте глубину поиска: 4

35995 14890
73115 12589
104409 10444
136677 8332
164118 6187
190667 4100
212606 2033

Построено КФ ЛК: 228616
Сохранение     : выполнено
Время работы   : 42.978 сек
Для выхода нажмите Enter . . .


Сам заданный ЛК является марьяжным ДЛК "единицей" с КФ соквадрата (тоже "единицей" ):

Код:
0 4 6 5 8 2 7 9 3 1
9 1 7 4 3 8 5 6 2 0
1 7 2 6 5 9 8 3 0 4
8 9 5 3 2 1 0 4 6 7
2 8 0 9 4 6 1 5 7 3
6 0 3 1 7 5 4 8 9 2
7 2 1 8 9 3 6 0 4 5
5 3 9 0 6 4 2 7 1 8
3 5 4 7 1 0 9 2 8 6
4 6 8 2 0 7 3 1 5 9


А в его 4-окрестности находятся ещё две "двойки":



и одна "единица":



Замыкание даёт ещё три "единицы":

Отредактировано пользователем 16 марта 2019 г. 10:33:38(UTC)  | Причина: Не указана

Вложение(я):
tzs_lk.zip (43kb) загружен 5 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 14.03.2019(UTC)
Offline citerra  
#806 Оставлено : 15 марта 2019 г. 8:00:00(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,966

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 363 раз в 263 постах
Сегодня ожидается преодоление барьера в 10 000 00 КФ ОДЛК
Offline whitefox  
#807 Оставлено : 15 марта 2019 г. 12:50:56(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 251

Сказал(а) «Спасибо»: 79 раз
Поблагодарили: 191 раз в 123 постах
Можно отношение связанности ограничить только на ДЛК. Ввиду того, что два ДЛК могут быть связаны только с помощью интеркалятов не пересекающихся с диагоналями, компоненты связности обычно значительно меньше чем в случае ЛК.

Например, выполним для вчерашнего второго примера программу tzs_dlk:

Код:
Частичное транзитивное замыкание связанности ДЛК

Задайте глубину поиска: 4

Построено КФ ДЛК: 4464
Сохранение      : выполнено
Время работы    : 4.68 сек

Для выхода нажмите Enter . . .

Найденные 4464 КФ ДЛК представляют 4420 вершины (КФ ЛК) графа GIL, против 228616 найденных программой tzs_lk. То есть программа tzs_dlk исследует существенно меньшую часть Хэмминг-окрестности чем программа tzs_lk. В частности, в 4-окрестность данного ДЛК, исследованную программой tzs_dlk, не попадают две "двойки" и "единица" имеющиеся в 4-окрестности, исследованной программой tzs_lk.

В приложенном архиве содержится файл main_tzs_dlk.cpp. Чтобы собрать программу tzs_dlk, замените этим файлом файл main_kanon.cpp в исходнике программы Канонизатор_ДЛК_2.0, и скомпилируйте полученную сборку.

Отредактировано пользователем 16 марта 2019 г. 10:39:20(UTC)  | Причина: Не указана

Вложение(я):
main_tzs_dlk.zip (3kb) загружен 4 раз(а).
Offline whitefox  
#808 Оставлено : 15 марта 2019 г. 16:40:08(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 251

Сказал(а) «Спасибо»: 79 раз
Поблагодарили: 191 раз в 123 постах
Заменил в программе tzs_lktzs_dlk) поиск в глубину на поиск в ширину. Последний находит все вершины находящиеся на расстоянии не больше заданного от начальной вершины, в то время как первый — только часть из них.

Новые версии берите по старым ссылкам.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 15.03.2019(UTC)
Offline whitefox  
#809 Оставлено : 18 марта 2019 г. 17:24:52(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 251

Сказал(а) «Спасибо»: 79 раз
Поблагодарили: 191 раз в 123 постах
Перечислим ЛК с симметрией (10,10,10).

В качестве стандартного представителя симметрии (10,10,10) возьмём автоморфизм:

Код:
** 0123564897 0123564897 0123645978




Существует 441925632 нормальных ЛК со стандартным представлением симметрии (10,10,10), существенно различных из них — 68834. Марьяжных ДЛК с симметрией (10,10,10) не существует.
Вложение(я):
generator_lk_10_10_10.zip (44kb) загружен 1 раз(а).
names_lk_10_10_10.zip (665kb) загружен 2 раз(а).
Offline citerra  
#810 Оставлено : 18 марта 2019 г. 20:06:27(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,966

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 363 раз в 263 постах
Распределение 10 млн КФ ОДЛК по симметриям

Квадратов с симметрией (1,31,31) найдено: 948 они записаны в файл symm_1_31_31.txt
Квадратов с симметрией (2,31,31) найдено: 1008 они записаны в файл symm_2_31_31.txt
Квадратов с симметрией (4,31,31) найдено: 19589 они записаны в файл symm_4_31_31.txt
Квадратов с симметрией (8,8,8) найдено: 16 они записаны в файл symm_8_8_8.txt
Квадратов с симметрией (8,31,31) найдено: 3784 они записаны в файл symm_8_31_31.txt
Квадратов с симметрией (16,16,16) найдено: 144 они записаны в файл symm_16_16_16.txt
Квадратов с симметрией (16,31,31) найдено: 2436 они записаны в файл symm_16_31_31.txt
Квадратов с симметрией (21,21,21) найдено: 1 они записаны в файл symm_21_21_21.txt
Квадратов с симметрией (21,36,36) найдено: 1 они записаны в файл symm_21_36_36.txt
Квадратов с симметрией (27,27,27) найдено: 44 они записаны в файл symm_27_27_27.txt
Квадратов с симметрией (41,41,41) найдено: 1 они записаны в файл symm_41_41_41.txt
Квадратов с симметрией (41,42,42) найдено: 1 они записаны в файл symm_41_42_42.txt

По линейкам

1034685972 698127
1034678952 679121
1034678925 648121
1034628975 633092
1032675894 629763
1230675948 578978
1034689527 320977
1204678953 318287
1034689572 317277
1032684957 179057
...
1234078956 22349
1034275698 21920
1037892654 16002
1204635978 13431
1037892645 7443
thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 18.03.2019(UTC)
Пользователи, просматривающие эту тему
Guest (2)
41 Страницы«<394041
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2019, Yet Another Forum.NET
Страница сгенерирована за 0.228 секунды.