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

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

Уведомление

Icon
Error

38 Страницы«<2728293031>»
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#561 Оставлено : 4 февраля 2018 г. 20:48:10(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1024 раз
Поблагодарили: 1827 раз в 886 постах
Динамика находок
Пользователь evatutin прикрепил следующие файлы:
bmp.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#562 Оставлено : 4 февраля 2018 г. 22:50:07(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Всего 755 972 КФ ОДЛК
Двушек 4 805

На днях будет найден 1 000 000й КФ ОДЛК

Отредактировано пользователем 5 февраля 2018 г. 4:58:33(UTC)  | Причина: Не указана

Offline citerra  
#563 Оставлено : 9 февраля 2018 г. 21:13:05(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Всего 766 351 КФ ОДЛК
Двушек 5 348
233 четверки ( сразу 9 новых )

1 000 000я КФ ОДЛК найдена.
Но это только стотысячная часть возможных КФ. Поэтому простое пополнение списка теряет свою актуальность. Ну найдем в сто раз больше? А смысл? Все равно это будет только тысячная доля всего. Надо что-то придумывать...
Offline whitefox  
#564 Оставлено : 10 февраля 2018 г. 16:18:22(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Представляю программу Определитель БС.

Входом служит файл input.txt со списком имён СНДЛК. Для каждого введённого имени строится соответствующий квадрат и находятся все присущие ему блочные структуры. Все найденные БС канонизируются, а канонические шаблоны БС сохраняются в соответствующем виду БС файле.

Под спойлером readme.txt



Приведу протоколы обработки трёх списков имён СНДЛК:
1) список 2749 КФ квазисимметричных ОДЛК;
2) список 507456 КФ ОДЛК;
3) список 711500 КФ ОДЛК.

Код:
Определитель БС

Введено СНДЛК    : 2749
Найдено БС       : 6867

Найдено классов БС

5x5              : 1
9x5              : 22
10x5             : 554
10x9             : 7
10x10            : 23

Время работы     : 4.508 сек


Код:
Введено СНДЛК    : 507456
Найдено БС       : 8368

Найдено классов БС

5x5              : 1
9x5              : 22
10x5             : 558
10x9             : 7
10x10            : 23

Время работы     : 27.058 сек


Код:
Определитель БС

Введено СНДЛК    : 711500
Найдено БС       : 8368

Найдено классов БС

5x5              : 1
9x5              : 22
10x5             : 558
10x9             : 7
10x10            : 23

Время работы     : 37.034 сек


Видим, что основная масса БС приходится на квазисимметричные ДЛК.
Вложение(я):
BS_711500.zip (7kb) загружен 14 раз(а).
BS_opred.zip (84kb) загружен 10 раз(а).
Offline whitefox  
#565 Оставлено : 12 февраля 2018 г. 15:57:56(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Поясню, что понимается под сильно нормализованным шаблоном блочной структуры.

Определение. Шаблон называется нормализованным если его первая строка и первый столбец упорядочены в неубывающем порядке.

Определение. Нормализованный шаблон называется сильно нормализованным если его первый столбец и первая строка имеют следующий вид в зависимости от вида БС:
Код:
5x5 — 01234 x 01234
7x5 — 0011234 x 01234
8x5 — 00112234 x 01234
9x5 — 001122334 x 01234
10x5 — 0011223344 x 01234
7x7 — 0011234 x {0011234, 0012234}
8x7 — 00112234 x {0011234, 0012334}
9x7 — 001122334 x {0011234, 0012344}
10x7 — 0011223344 x 0011234
8x8 — 00112234 x {00112234, 00112334, 00123344}
9x8 — 001122334 x {00112234, 00112344}
10x8 — 0011223344 x 00112234
9x9 — 001122334 x {001122334, 001122344}
10x9 — 001122334 x 001122334
10x10 — 0011223344 x 0011223344


Кроме случаев 5x5, 10x5 и 10x10 (для которых каждый нормализованный шаблон автоматически является сильно нормализованным) число сильно нормализованных шаблонов много меньше числа нормализованных. Поэтому канонический шаблон БС и был определён как наименьший в лексикографическом порядке сильно нормализованный шаблон.

Ранее уже приводился список из 1031 представителя классов эквивалентности блочных структур вида nx5. В файле kanon_sh_nx5.zip эти же классы представлены своими каноническими шаблонами.

Введём на множестве канонических шаблонов (а те самым и на множестве классов эквивалентности БС) линейный порядок следующим образом:
1) шаблоны с меньшей шириной предшествуют шаблонам с большей;
2) среди шаблонов одинаковой ширины, шаблоны с меньшей высотой предшествуют шаблонам с большей;
3) шаблоны одинаковой ширины и высоты (то есть одного вида) упорядочиваются лексикографически.

Как уже отмечалось, блочный ЛК может иметь несколько блочных структур. Найдём для каждой такой БС её канонический шаблон. Будем считать, что наименьший из этих канонических шаблонов определяет семейство блочных ЛК которому данный ЛК принадлежит.

Из этого определения следует, что не каждый класс эквивалентности БС определяет семейство блочных ЛК. В частности, уже отмечалось, что ЛК с блочной структурой вида nx5 в одном из срезов обязательно имеет в другом срезе блочную структуру того же вида, шаблон которой получается из шаблона первой БС инверсией строк (то есть, рассматривая строки как перестановки 5-го порядка, заменяем их обратными перестановками). Другими словами, каждый класс эквивалентности БС вида nx5 имеет двойственный ему класс того же вида. Двойственный класс может совпадать с самим классом, что, очевидно, имеет место с единственным классом вида 7x5. Но если эти классы разные, то больший из них не может представлять семейство блочных ЛК, так как всякий ЛК, имеющий БС из этого класса, обязательно имеет БС из меньшего класса.

Файл mlad_kl_nx5.zip содержит младшие члены каждой пары двойственных классов БС вида nx5:
Код:
5x5  — 2
7x5  — 1
8x5  — 7
9x5  — 45
10x5 — 549
всего: 604


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

Файл readme.txt



Приведу протоколы работы для двух списков ЛК:
1) список 2749 КФ квазисимметричных марьяжных ДЛК;
2) список 711500 КФ марьяжных ДЛК.

Код:
Определитель семейств блочных ЛК

Введено ЛК       : 2749
Из них блочных   : 2749

Найдено семейств блочных ЛК

5x5              : 1
9x5              : 16
10x5             : 300

Время работы     : 1.248 сек


Код:
Определитель семейств блочных ЛК

Введено ЛК       : 711500
Из них блочных   : 3255

Найдено семейств блочных ЛК

5x5              : 1
9x5              : 16
10x5             : 302


Выходные файлы для второго списка в архиве output_nx5.zip

Оба семейства вида 5x5 были полностью проверены, марьяжные ДЛК оказались только в одном из них. Также полностью было проверено единственное семейство вида 7x5, марьяжных ДЛК оно не имеет. Как видим, ещё 318 семейств были проверены частично, вот их-то и нужно допроверить в первую очередь.

UPD: Программа Определитель семейств блочных ЛК содержала ошибку. Заменил её версией 2.01 См. пост.

Отредактировано пользователем 18 июня 2018 г. 17:32:35(UTC)  | Причина: Не указана

Вложение(я):
kanon_sh_nx5.zip (10kb) загружен 14 раз(а).
mlad_kl_nx5.zip (6kb) загружен 13 раз(а).
output_nx5.zip (4kb) загружен 13 раз(а).
opred_sem_blk_2.01.zip (129kb) загружен 6 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 12.02.2018(UTC)
Offline whitefox  
#566 Оставлено : 13 февраля 2018 г. 15:39:20(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Присвоим имена классам эквивалентности блочных структур вида nx5 так, чтобы:
1) относительный порядок имён совпадал с относительным порядком классов;
2) канонический шаблон легко востанавливался по имени класса.

Покажу на примере единственного класса вида 7x5. Его канонический шаблон
Код:
0 1 2 3 4 
0 1 2 4 3 
1 2 0 3 4 
1 2 0 4 3 
2 3 4 0 1 
3 4 1 2 0 
4 0 3 1 2


Вычеркнем первый столбец, а также первую и последнии строки, получим
Код:
1 2 4 3 
2 0 3 4 
2 0 4 3 
3 4 0 1 
4 1 2 0


В каждой строке имеем некоторую перестановку четырёх различных элементов, заменим её стандартной 4-перестановкой элементов {0,1,2,3} с сохранением относительного порядка элементов, получим
Код:
0 1 3 2
1 0 2 3
1 0 3 2
2 3 0 1
3 1 2 0


Заменим каждую перестановку её номером в лексикографическом порядке и запишем эти номера в строку, получим (при нумерации с нуля)
1 6 7 16 21

Теперь заменим номера соответствующими буквами латинского алфавита, получим
BGHQV

Эту строку и примем за имя класса вида 7x5. Очевидно, что оно удовлетворяет двум указанным требованиям (имена сравниваем по длине, а если длины одинаковы, то лексикографически).

Имена всех 1031 классов БС вида nx5 в архиве.
Вложение(я):
imena_kl_bs_nx5.zip (4kb) загружен 14 раз(а).
Offline whitefox  
#567 Оставлено : 17 февраля 2018 г. 16:04:02(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
И так, для всех 604 возможных семейств блочных ЛК вида nx5 нужно найти принадлежащие им существенно различные ЛК. Один из методов поиска был изложен ранее. Этот метод был усовершенствован, что позволило сократить объём работы в 1000 раз.

Пояснения буду давать на примере семейства BGHQV — единственого семейства вида 7x5. Его канонический шаблон:
Код:
0 1 2 3 4
0 1 2 4 3
1 2 0 3 4
1 2 0 4 3
2 3 4 0 1
3 4 1 2 0
4 0 3 1 2


Расширим его до БС:
Код:
0 0 1 1 2 2 3 3 4 4
0 0 1 1 2 2 4 4 3 3
1 1 2 2 0 0 3 3 4 4
1 1 2 2 0 0 4 4 3 3
2 2 3 3 4 4 0 0 1 1
2 2 3 3 4 4 0 0 1 1
3 3 4 4 1 1 2 2 0 0
3 3 4 4 1 1 2 2 0 0
4 4 0 0 3 3 1 1 2 2
4 4 0 0 3 3 1 1 2 2


И построим на основе БС базовый ЛК:
Код:
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 8 9 6 7
2 3 4 5 0 1 7 6 9 8
3 2 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


Все блоки базового ЛК имеют прямую ориентацию (то есть на главной диагонали блока стоит меньший из двух заполнителей). Изменяя ориентацию отдельных блоков, можно построить 2^25 = 33554432 различных ЛК, но многие из них будут изоморфны. Перенумеруем каким-нибудь образом блоки, и будем произвольную 25-битовую строку называть схемой ориентации блоков, полагая, что нулевой бит означает прямую ориентацию соответствующего блока, а единичный — обратную.

Будем называть схему ориентации блоков (схему, для краткости) нормальной если все блоки пересекающиеся с первой строкой и первым столбцом имеют прямую ориентацию. Очевидно, что для произвольно схемы A найдётся такая нормальная схема B, что латинские квадраты, соответствующие схемам A и B, будут изоморфны. Например, ЛК:
Код:
1 0 2 3 4 5 6 7 8 9
0 1 3 2 5 4 8 9 6 7
2 3 4 5 0 1 7 6 9 8
3 2 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


приводится переименованием элементов 0<->1 к изоморфному ЛК с нормальной схемой, а ЛК:
Код:
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 8 9 6 7
3 2 4 5 0 1 7 6 9 8
2 3 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


приводится к изоморфному ЛК с нормальной схемой переименованием элементов 2<->3 совместно с перестановкой столбцов 2 и 3.

Следовательно для каждого семейства достаточно будет рассмотреть 2^16 = 65536 различных нормальных схем.

Удобно выбрать такую нумерацию блоков, чтобы блоки первой строки и первого столбца имели наибольшие номера, например (при нумерации с 0):
Код:
24 23 22 21 20
16  ?  ?  ?  ?
17  ?  ?  ?  ?
18  ?  ?  ?  ?
19  ?  ?  ?  ?


а остальные блоки занумеровать по мере появления верхнего левого угла каждого блока при сканировании БС сверху вниз слева направо:
Код:
24 23 22 21 20
16 00 04 08 12
17 01 05 09 13
18 02 06 10 14
19 03 07 11 15


Для наглядности, заменим в БС элементы каждого блока номером соответствующего блока:
Код:
24 24 23 23 22 22 21 21 20 20
24 24 23 23 22 22 08 08 12 12
16 16 00 00 04 04 21 21 20 20
16 16 00 00 04 04 08 08 12 12
17 17 01 01 05 05 09 09 13 13
17 17 01 01 05 05 09 09 13 13
18 18 02 02 06 06 10 10 14 14
18 18 02 02 06 06 10 10 14 14
19 19 03 03 07 07 11 11 15 15
19 19 03 03 07 07 11 11 15 15

При такой нумерации блоков каждая нормальная схема представляется 16-битным целым числом.

Будем называть две схемы A и B эквивалентными, если существует изоморфизм соответствующих ЛК, переводящий БС в себя с сохранением однотипности блоков. Другими словами, группа эквивалентных преобразований схем состоит из автоморфизмов БС и изменяющих ориентацию блоков переименований элементов ЛК. Эту группу можно представить в виде прямого произведения группы трансформаций и группы инверсий. Трансформации это, по сути, автоморфизмы шаблона БС, они переставляют блоки и, иногда, могут изменить ориентацию отдельных блоков. Инверсии только изменяют ориентацию блоков.

Всякая инверсия является комбинацией элементарных инверсий. Каждому типу блоков соответствует своя элементарная инверсия, изменяющая ориентацию всех блоков данного типа. Каждой паре одинаковых столбцов БС соответствует своя элементарная инверсия, изменяющая ориентацию всех блоков принадлежащих этой паре столбцов. Каждой паре одинаковых строк БС соответствует своя элементарная инверсия, изменяющая ориентацию блоков принадлежащих этой паре строк. Пять типов блоков имеются всегда, все БС вида nx5 имеют по пять пар одинаковых столбцов, БС вида 7x5 (а также 7x7) имеют три пары одинаковых строк, то есть группа инверсий для вида 7x5 порождается 13 элементарными инверсиями, а общее число инверсий равно 2^13 = 8192.

Использование нормальных схем (вместо сбалансированных, как предлагалось в предыдущем варианте метода) позволяет ограничиться только инверсиями переводящими нормальные схемы в нормальные, а их всего 8 для вида 7x5 (4 для 8x5, 2 для 9x5, 1 для 10x5).

Найдём автоморфизмы канонического шаблона вида 7x5, их всего 6:
Код:
0123456 01234 01234
2301465 02143 10243
0123645 12034 20134
2301654 10243 21043
0123564 20134 12034
2301546 21043 02143


В первой колонке — перестановки строк, во второй — перестановки столбцов, в третей — переименования элементов шаблона. Им соответствуют следующие трансформации схем:
Код:
00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 : 0
22,05,07,06,23,01,03,02,12,13,15,14,08,09,11,10,24,17,19,18,21,20,00,04,16 : 3150080
04,07,05,06,16,19,17,18,08,11,09,10,12,15,13,14,00,03,01,02,20,21,24,22,23 : 0
24,19,18,17,22,07,06,05,12,15,14,13,08,11,10,09,23,03,02,01,21,20,04,16,00 : 3150080
16,18,19,17,00,02,03,01,08,10,11,09,12,14,15,13,04,06,07,05,20,21,23,24,22 : 0
23,02,01,03,24,18,17,19,12,14,13,15,08,10,09,11,22,06,05,07,21,20,16,00,04 : 3150080


Здесь до двоеточия идёт перестановка битов схемы, а после — маска, определяющая инвертируемые биты. Если S — схема, p — перестановка битов, m — маска, то схема после трансформации определяется по формуле:
S' = p(S) xor m.

Если до трансформации схема была нормальной, то после она может уже не быть таковой. Нужно привести схему к нормальному виду. Для этого потребуются элементарные инверсии:
Код:
t_0=16794136, t_1=8464448, t_2=4359169, t_3=2363522, t_4=1573156
c_0=17760256, c_1=8388623, c_2=4194544, c_3=2100992, c_4=1110016
r_2=139810,   r_3=279620,  r_4=559240

Здесь в первой строке — маски элементарных инверсий для типов, во второй — маски элементарных иверсий для столбцов, в третьей — маски элементарных инверсий для строк.

Алгоритм приведения схемы к нормальному виду следующий:
1) составим последовательность t_1, t_2, t_3, t_4, c_4, c_3, c_2, c_1, t_0;
2) просканируем биты 16 .. 24 включительно, строго в этом порядке;
3) если при сканировании попадается единичный бит, то применяем к схеме соответствующую инверсию из составленной выше последовательности.

Например, пусть установлен бит 17, а остальные старшие биты сброшены. Следовательно к схеме нужно применить второй член последовательности — t_2. При этом бит 17 сбросится, а бит 22 установится. При дальнейшем сканировании будет обнаружено, что бит 22 установлен, то есть к схеме нужно применить седьмой член последовательности — c_2. При этом бит 22 сбросится и никакие другие биты установлены не будут. В результате получим нормальную схему:
S' = S xor t_2 xor c_2.

Группа из восьми инверсий, переводящих нормальные схемы в нормальные, порождается следующими тремя инверсиями:
Код:
inv_2 = t_2 xor c_2 xor r_2
inv_3 = t_3 xor c_3 xor r_3
inv_4 = t_4 xor c_4 cor r_4

Таким образом класс эквивалентности схем ориентации блоков для семейства BGHQV содержит не более 48 нормальных схем, наименьшую из них выберем в качестве канонической схемы. Всего для этого семейства имеется 1440 классов эквивалентности схем. Ранее уже приводился список из 1440 представителей классов эквивалентности схем для единственного семейства вида 7x5, те представители были выбраны другим способом.

Списки канонических схем для всех семейств видов nx5 (кроме 5x5) можно взять здесь.

Следует отметить, что:
1) каноническая схема может определять ЛК принадлежащий меньшему семейству, а потому не принадлежащий семейству которому данная каноническая схема принадлежит;
2) разные канонические схемы могут определять изоморфные ЛК.

Последнее происходит потому, что ЛК может иметь несколько эквивалентных, но не сводимых друг к другу БС, которые могут дать разные канонические схемы. Так, например, семейство BGHQV имеет 1440 канонических схем, но только 796 существенно различных ЛК. Поэтому нужна ещё дополнительная фильтрация канонических схем.
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 17.02.2018(UTC), evatutin оставлено 18.02.2018(UTC)
Offline citerra  
#568 Оставлено : 19 февраля 2018 г. 19:05:17(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
После бурного старта, в эксперименте е44 пошли повторы
Всего 767 429 КФ ОДЛК
Двушек 5 352


Offline whitefox  
#569 Оставлено : 22 февраля 2018 г. 14:40:55(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Выкладываю архив содержащий схемы ориентации блоков всех существенно различных блочных ЛК вида nx5 (кроме двух семейств вида 5x5).
Offline whitefox  
#570 Оставлено : 27 февраля 2018 г. 15:02:02(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Архив уникальных канонических схем блочных ЛК вида nx5 заменил на новый. В старом были ошибки. Ссылка прежняя.

Всего существует более 26 миллионов (26045080) таких существенно различных ЛК.
Offline citerra  
#571 Оставлено : 28 февраля 2018 г. 19:52:33(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Всего 1 247 575 КФ ОДЛК
Двушек 6 363
Offline whitefox  
#572 Оставлено : 1 марта 2018 г. 17:54:34(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Представляю программу для построения всех блочных ЛК выбранного семейства.

Файл readme.txt



Для работы программы нужен файл family_baza.bin. Также в архиве есть исходники.
Вложение(я):
unpack_family.zip (236kb) загружен 16 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 01.03.2018(UTC)
Offline citerra  
#573 Оставлено : 2 марта 2018 г. 9:43:38(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Взял на обработку 100 семейств - с 100й по 199ю
Offline evatutin  
#574 Оставлено : 4 марта 2018 г. 22:55:19(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1024 раз
Поблагодарили: 1827 раз в 886 постах
Динамика находок за последнее время
Пользователь evatutin прикрепил следующие файлы:
bmp.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#575 Оставлено : 5 марта 2018 г. 16:46:31(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Представляю программу family_mar заточенную специально на проверку семейств блочных ЛК вида nx5. Фактически это Канонизатор_ЛК_по_ДЛК совместно с Ортогоном в "одном флаконе". smile Причём последний игнорирует квазисимметричные ДЛК. Так как последние тоже являются блочными ЛК вида nx5, но уже были все проверены.

Файл readme.txt



Для работы программы нужен файл hash_tabl.bin, который можно взять в архиве https://yadi.sk/d/7xDAd9FS3HL9EC

Отредактировано пользователем 5 марта 2018 г. 17:32:07(UTC)  | Причина: Не указана

Вложение(я):
family_mar.zip (33kb) загружен 14 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 05.03.2018(UTC)
Offline citerra  
#576 Оставлено : 5 марта 2018 г. 19:44:17(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Замечательная программа!!
Если сначала я рассчитывал затратить где-то пол-года в 6 потоков на все 604 семейства, то сейчас можно и за неделю управиться, даже меньше.
Плюс, меньше шумов, отсекаются уже найденные ОДЛК, больше внимание находкам, а они уже есть.
Offline citerra  
#577 Оставлено : 6 марта 2018 г. 7:45:31(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
За ночь проверилось 85 БС. Большинство пустышек.
С результатам 18 семейств.
Они дали 13 повторных КФ и 26 новых, в т.ч двушку.
Цедим помаленьку, выхлоп мог бы и по больше.
Offline citerra  
#578 Оставлено : 7 марта 2018 г. 8:39:04(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Решил вечером проверить мелкие семейства на ноутбуке, начал с начала, включая уже исследованные.
10 первых проверилось за полчаса, в т.ч все вида 8х5.
Новых не нашлось. Первые находки попались только в 16 и 17 семействах.

На данный момент проверено всего 293 семейств, с ОДЛК 70.
Найдено 185 КФ, но все равно много повторных - 89,
Новых - 96, в т.ч 2 двушки и 1 четверка.
Offline whitefox  
#579 Оставлено : 7 марта 2018 г. 13:24:00(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 179 раз в 113 постах
Приведу примеры автоматизации проверки семейств блочных ЛК.

Например, для проверки семейств с номерами от 4 до 10 включительно (т.е. всех семейств вида 8x5) можно использовать пакетный файл:

Код:
@echo off
for /l %%i in (4,1,10) do unpack_family.exe %%i > nul
for /f %%j in ('dir /b lk_*') do family_mar.exe %%j && del %%j
pause


Замените числа 4 и 10 первым и последним номером нужного интервала семейств.

Для проверки, например, 16-ти семейств вида 9x5 содержащих квазисимметричные марьяжные ДЛК, поместим их список

Код:
BCKFWPV
BCLDSRT
BCLDUQV
BCSFXNR
BGJEXFT
BGQPURS
BGRQUNV
BIKVXBE
DBIETQS
DBIEVRU
DBKAXRU
DGKSWDE
DIPQTRS
DIPRTQS
DJKAEUX
HCKDVLW


в файл names.txt и запустим пакетный файл:

Код:
@echo off
for /f "eol=;" %%i in (names.txt) do unpack_family.exe %%i > nul
for /f %%j in ('dir /b lk_*') do family_mar.exe %%j && del %%j
pause


Замените список имён нужным, по одному имени на строку. Пустые строки, а также строки начинающиеся с символа ';' будут проигнорированы, например, из списка:

Код:
BCKFWPV

;BCLDSRT
BCLDUQV


будут проверены только первое и последнее семейства.

Если выполнение пакетного файла будет прервано, то проверку можно продожить запустив пакетный файл:

Код:
@echo off
for /f %%j in ('dir /b lk_*') do family_mar.exe %%j && del %%j
pause


Напомню, что для ручного прерывания пакетного файла нужно нажать Ctrl-C и ответить Y на вопрос о выходе.

Если для какого-то семейства найдутся марьяжные не квазисимметричные ДЛК, то они будут записан в файл:
mar_dlk_<вид семейства>_<имя семейства>_<число не квазисимметричных марьяжных ДЛК>.txt
Например, mar_dlk_9x5_BCLDSRT_1.txt

Как уже было отмечено, семейства вида 8x5 не содержат квазисимметричных марьяжных ДЛК. Не квазисимметричных марьяжных ДЛК они тоже не содержат.

Для указанных 16-ти symm_family вида 9x5 нашлось 7 не квазисимметричных марьяжных главных классов ДЛК. Их КФ в архиве non_symm.zip

Также прилагаю архивы с именами всех семейств (imena_sem_nx5.zip) и с именами только семейств содержащих квазисимметричные марьяжные ДЛК (symm_family.zip).

Программа Определитель семейств блочных ЛК для списка ОДЛК_1238115 по ссылке из подписи citerra показывает:

Код:
Определитель семейств блочных ЛК

Введено ЛК       : 1238115
Из них блочных   : 3304

Найдено семейств блочных ЛК

5x5              : 1
9x5              : 17
10x5             : 313

Время работы     : 65.317 сек


что как минимум 14 non_symm_family тоже содержат марьяжные ДЛК. Вот список этих семейств:

Код:
DLUBXEO
BCJETQUS
BCJQSRTB
BCKPVESQ
BCLPSETQ
BINFURTE
DBIQVRTA
DBLUXFMT
DEGPWRUC
DEGQXDVM
DEHCQUXP
DGKNXFVC
DGKUXBFT
DGQEUNXF

Отредактировано пользователем 12 марта 2018 г. 17:19:59(UTC)  | Причина: Не указана

Вложение(я):
imena_sem_nx5.zip (3kb) загружен 11 раз(а).
symm_family_nx5.zip (2kb) загружен 11 раз(а).
non_symm.zip (73kb) загружен 12 раз(а).
Offline citerra  
#580 Оставлено : 8 марта 2018 г. 9:53:56(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 346 раз в 251 постах
Проверены все 604 БС вида nx5.
С решениями 131 БС, всего 174 решений.
Найдено 138 повторных КФ, 209 новых, из них
3 двушки, четверка

Отредактировано пользователем 8 марта 2018 г. 10:23:52(UTC)  | Причина: Не указана

thanks 1 пользователь поблагодарил citerra за этот пост.
whitefox оставлено 10.03.2018(UTC)
Пользователи, просматривающие эту тему
Guest
38 Страницы«<2728293031>»
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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