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

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

Уведомление

Icon
Error

21 Страницы«<1112131415>»
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#241 Оставлено : 16 марта 2017 г. 23:11:05(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 931 раз
Поблагодарили: 1508 раз в 735 постах
Автор: dimych Перейти к цитате
угу, таки сбылась мечта скандальной форумчанки


Если я не ошибаюсь, то тему поиска ОДЛК впервые тут поднял Naucknik в SAT'е. А все остальное пошло уже потом...

Цитата:
я случайно на рабочем компе наблюдал слив результатов посчитанных заданий. почти все результаты размером 1 байт, а одно задание посчиталось с результатом размером 477 байт, не иначе что-то насчиталось, отличное от нуля...


1 байт — ничего не нашлось, 400+ байт — нашлась однушка, с чем и поздравляю drinks

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline dimych  
#242 Оставлено : 17 марта 2017 г. 18:31:59(UTC)
dimych


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

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2011(UTC)
Сообщений: 1,835
Мужчина
Российская Федерация
Откуда: Смоленск

Сказал «Спасибо»: 445 раз
Поблагодарили: 211 раз в 170 постах
сегодня модем забирал, комп оффлайн считал, счас пришел домой, глянул результаты по ВУшкам, везде по 1 байту, а в одной ВУшке вот такая фигня оказалась ))))
Код:

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

0 1 2 3 4 5 6 7 8 9
4 3 0 1 8 6 2 9 5 7
5 7 4 6 9 2 8 0 3 1
2 5 7 9 6 8 1 4 0 3
8 9 6 0 1 3 4 2 7 5
3 8 5 4 2 7 9 1 6 0
1 6 3 7 0 4 5 8 9 2
9 2 8 5 3 0 7 6 1 4
7 4 9 8 5 1 0 3 2 6
6 0 1 2 7 9 3 5 4 8
ASUS P9X79 WS/I7-3930K@3.2 GHz/32 GB DDR3-1600 MHz/MSI R7950 Twin Frozr 3GD5 V2/OC 3 Gb (880/5000 MHz)
Offline citerra  
#243 Оставлено : 17 марта 2017 г. 18:52:30(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Автор: dimych Перейти к цитате
а в одной ВУшке вот такая фигня оказалась ))))

Это не фигня, а пара ОДЛК ортогональные диагональные латинские квадраты
Offline citerra  
#244 Оставлено : 19 марта 2017 г. 22:47:18(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Продублирую
Всего в списке 10336 КФ ОДЛК
7579 однушек
2541 двушка
1 тройка
205 четверок
6 шестерок
4 восьмерки

поехали дальше

Отредактировано пользователем 20 марта 2017 г. 7:13:01(UTC)  | Причина: Не указана

Offline citerra  
#245 Оставлено : 21 марта 2017 г. 15:16:42(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Вот список из 10437 КФ ОДЛК

7677 однушек
2544 двушек
1 тройка
205 четверок
6 шестерок
4 восьмерки

( почистил список, на одном из этапов в него вместе с КФ попали и сами ОДЛК )
Вложение(я):
k10437.rar (393kb) загружен 4 раз(а).
Offline citerra  
#246 Оставлено : 27 марта 2017 г. 10:10:46(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
За последние время в поиске ОДЛК произошли тектонические изменения:
- запустился боинк-проект Gerasim, к котором теперь ищутся ОДЛК,
- появилась отличнейшая программа от Harry White, которая ищет SODLS самоортогональные ДЛК. Выхлоп программы отличный, но увы поиск проходит в закрытом режиме.
Мои поиски на фоне этих монстров выглядят бледно, но по 4-8 КФ ОДЛК в сутки есть. Запущены потоки для случайного поиска, поиск в начале диапазона ( уже найдены первые 42 КФ ОДЛК ) и симметричные ДЛК ( на данный момент 2549 двушек )
thanks 1 пользователь поблагодарил citerra за этот пост.
AlexA оставлено 27.03.2017(UTC)
Offline citerra  
#247 Оставлено : 27 марта 2017 г. 21:38:17(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Шикарный нашелся ОДЛК

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

с 2 КФ четверками и 8 КФ однушками. Увы и ах, все повторные
Offline citerra  
#248 Оставлено : 28 марта 2017 г. 8:54:59(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Глас услышан и у меня программа, которая ищет
SODLS ( самоортогональные DLK ).Программа сырая, без интерфейса.
Я бы мог еще продолжать перечислять недостатки, но главное, она РАБОТАЕТ!!.

Вот первая пара

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

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

Во втором квадрате все элементы "отражены" относительно главной диагонали.

А вот еще пара

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

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

Теперь осталось определить темп. Ориентир: у HARRY - 23 мин на SODLS


Offline citerra  
#249 Оставлено : 28 марта 2017 г. 15:41:28(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
За 7 часов 8 SODLS. Недурственно !!!
Offline whitefox  
#250 Оставлено : 28 марта 2017 г. 21:02:55(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 26 раз
Поблагодарили: 98 раз в 55 постах
Вот здесь перечислены все 121642 представителя классов RC-paratopism SOLS10 (осторожно, почти 12 МБ). Не так и много, но SODLS может быть на несколько порядков больше (или меньше smile ).

Отредактировано пользователем 28 марта 2017 г. 21:33:59(UTC)  | Причина: Не указана

Offline evatutin  
#251 Оставлено : 28 марта 2017 г. 22:12:01(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 931 раз
Поблагодарили: 1508 раз в 735 постах
Автор: whitefox Перейти к цитате
Вот здесь перечислены все 121642 представителя классов RC-paratopism SOLS10 (осторожно, почти 12 МБ). Не так и много, но SODLS может быть на несколько порядков больше (или меньше smile ).


И среди них 71 ДЛК, от которых получилось построить 142 представителя ОДЛК 199

Отредактировано пользователем 28 марта 2017 г. 22:27:12(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#252 Оставлено : 29 марта 2017 г. 7:31:14(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Программа Степана работает уже почти сутки, 23 часа найдено 42 ODLS, таким образом 32 мин в среднем на квадрат.

Вчера вечером стала доступна и программа Harry White ( далее под заголовком SODLS10).Запустил в три потока. За 10 часов нашлись 9, 5, 9 SODLS10. Получается 78 мин на квадрат, в два с лишнем раза дольше.

Теперь надо чуть подождать, чтобы Степан добавил в программу разные точки входа.
Мечта: запустить в 5 потоков и снимать по 200+ в сутки ( перегнать Gerasim ). А затем подключить программу в боинк. И повалятся тысяча квадратов...

Как уже писал evatutin в списке whitefox 71 ДЛК и 71 ОДЛК, после обработки получается 96 КФ ОДЛК. Но из них можно что-то еще вытянуть...

Найдена 43 по порядку КФ ОДЛК
Offline whitefox  
#253 Оставлено : 29 марта 2017 г. 12:50:02(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 26 раз
Поблагодарили: 98 раз в 55 постах
Автор: evatutin Перейти к цитате
И среди них 71 ДЛК, от которых получилось построить 142 представителя ОДЛК 199


Это только те, что лежат на поверхности. Нужно копать глубже. smile

Имеем 121642 класса эквивалентности SOLS, в каждый класс входят до 2*(10!)^2 = 26336378880000 SOLS, из них до 2*10! = 7257600 нормализованных (с главной диагональю вида 0123456789) SOLS. В качестве представителя каждого класса был выбран наименьший в лексикографическом порядке нормализованный SOLS.

Так получилось, что у 71 класса эквивалентности наименьший SOLS оказался ДЛК (а потому и SODLS). Но всякий SODLS является SOLS, а потому принадлежит какому-то классу эквивалентности SOLS. И чтобы найти все SODLS достаточно только найти все ДЛК входящие во все эти классы эквивалентности SOLS. Для этого не понадобится выполнять по 7257600 преобразований для каждого класса эквивалентности, достаточно будет выполнить только по 945. smile

Составим список перестановок 10 порядка вида {a[0],a[1],...,a[8],a[9]} с условием:
a[0] < a[9]
a[1] < a[8]
a[2] < a[7]
a[3] < a[6]
a[4] < a[5]
a[0] < a[1] < a[2] < a[3] < a[4]
Всего таких перестановок 10! / (5! * 2^5) = 945. Составим также список перестановок a_inv, обратных к первым. И выполним для каждого класса эквивалентности SOLS и каждой перестановки из нашего списка проверку — все ли элементы побочной диагонали различны у квадрата S = a_inv(a(L)), где L — это представитель класса эквивалентности. Код проверки, например, такой:
Код:

inline bool proverka(int L[10][10], int a[10], int a_inv[10]){
    for(int i = 0, flag = 0, t; i < 10; i++){
        t = 1 << a_inv[L[a[i]][a[9 - i]]];
        if(flag & t) return false;
        flag |= t;
    }
    return true;
}


Если проверка выполнена успешно, то SODLS найден. Построим его и сохраним.
Код:
void soxranitq(int S[10][10]);
int S[10][10];
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) S[i][j] = a_inv[L[a[i]][a[j]]];
soxranitq(S);


Сложность имеет порядок 121642 * 945 * 10 = 1 149 516 900, считанные секунды для современной машины. smile
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 29.03.2017(UTC), evatutin оставлено 29.03.2017(UTC)
Offline evatutin  
#254 Оставлено : 29 марта 2017 г. 13:59:03(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 931 раз
Поблагодарили: 1508 раз в 735 постах
whitefox
Общую идею вроде уловил, но надо бы проверить программно...

Цитата:
Составим список перестановок 10 порядка вида {a[0],a[1],...,a[8],a[9]} с условием:
a[0] < a[9]
a[1] < a[8]
a[2] < a[7]
a[3] < a[6]
a[4] < a[5]
a[0] < a[1] < a[2] < a[3] < a[4]


Вот это откуда следует? Если я правильно понимаю логику, то это попытка получить не все подряд ЛК/ДЛК в рамках класса изоморфизма, а только КФ... Или неправильно понимаю и это попытка ликвидировать симметрию в перестановках? Или еще что-то...

Отредактировано пользователем 29 марта 2017 г. 14:45:19(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline veinamond  
#255 Оставлено : 29 марта 2017 г. 15:37:47(UTC)
veinamond


Статус: Новичок

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 4
Российская Федерация
Откуда: Иркутск

Сказал(а) «Спасибо»: 3 раз
Поблагодарили: 2 раз в 1 постах
Whitefox,
А как будет выглядеть картина для SODLS порядка 8? Для них легко все проверить и быстро. Ну в крайнем случае для длк 9, для них тоже реально. Можете, пожалуйста, подробнее описать предполагаемый эксперимент?
Offline whitefox  
#256 Оставлено : 29 марта 2017 г. 17:00:33(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 26 раз
Поблагодарили: 98 раз в 55 постах
Автор: evatutin Перейти к цитате

Цитата:
Составим список перестановок 10 порядка вида {a[0],a[1],...,a[8],a[9]} с условием:
a[0] < a[9]
a[1] < a[8]
a[2] < a[7]
a[3] < a[6]
a[4] < a[5]
a[0] < a[1] < a[2] < a[3] < a[4]


Вот это откуда следует?


Возьмём произвольный SOLS L и произвольную перестановку p, и пусть p' означает перестановку обратную к p. Построим новый ЛК S по правилу:
S(i,j) = p'(L(p(i),p(j))
Известно, что S тоже будет SOLS.

Если же L SODLS, а p произвольная М-перестановка ("магическая" то есть такая, что для всех i будет p(i) + p(9-i) = 9), то S тоже будет SODLS.

Все М-перестановки составляют подгруппу в симметрической группе, и нам достаточно будет проверить по одному элементу из каждого смежного класса по М-подгруппе. Всего таких смежных классов 945, а указанные условия на перестановки как раз-таки определяют по одному представителю из этих смежных классов.

Вот список этих перестановок (первый столбец) и обратных к ним (второй столбец):
Вложение(я):
perest_945.zip (5kb) загружен 4 раз(а).
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 29.03.2017(UTC), evatutin оставлено 30.03.2017(UTC)
Offline whitefox  
#257 Оставлено : 29 марта 2017 г. 17:17:53(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 26 раз
Поблагодарили: 98 раз в 55 постах
Автор: veinamond Перейти к цитате
Whitefox,
А как будет выглядеть картина для SODLS порядка 8? Для них легко все проверить и быстро. Ну в крайнем случае для длк 9, для них тоже реально. Можете, пожалуйста, подробнее описать предполагаемый эксперимент?

Всё тоже самое, только список перестановок будет другим. Вот исходный код программы для составления этого списка:


Для порядка 8 нужно константу por изменить на 8, аналогично для любого чётного порядка. Для нечётного порядка программу нужно немного подправить.
Offline whitefox  
#258 Оставлено : 29 марта 2017 г. 20:42:01(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 26 раз
Поблагодарили: 98 раз в 55 постах
Написал программу. Было найдено 30534 SODLS, из них существенно различных 30502. Время работы 4 секунды.

Отредактировано пользователем 3 апреля 2017 г. 9:06:14(UTC)  | Причина: Добавил ссылку на КФ SODLS10

thanks 3 пользователей поблагодарили whitefox за этот пост.
evatutin оставлено 29.03.2017(UTC), citerra оставлено 30.03.2017(UTC), veinamond оставлено 30.03.2017(UTC)
Offline citerra  
#259 Оставлено : 30 марта 2017 г. 1:43:04(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 353 раз
Поблагодарили: 310 раз в 224 постах
Если слить с общим списком, получается 42141 КФ ОДЛК. Но пока не буду спешить.
Offline veinamond  
#260 Оставлено : 30 марта 2017 г. 6:46:33(UTC)
veinamond


Статус: Новичок

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 4
Российская Федерация
Откуда: Иркутск

Сказал(а) «Спасибо»: 3 раз
Поблагодарили: 2 раз в 1 постах
whitefox,
Программа, в результате работы которой было найдено 30534 SODLS - она обработала все RC-паратопичные классы или только часть? Если нет - то какую часть? Она работала в один поток? на каком процессоре?
Все таки, Вы не могли бы, пожалуйста, запустить ее на 8ках? Для них 1152 SODLS генерируются очень быстро и их легко сравнить.
Вообще, это очень любопытно, что так можно сделать, хотя с моими (весьма слабыми) познаниями в комбинаторике, выглядит как шаманство.
Если честно, я не устаю задумываться, а нельзя ли было похожим способом сделать для перечисления ДЛК9? Все таки, основных классов (main classes) ЛК9 сравнительно немного (19 миллиардов с хвостиком), и их можно раздобыть.
Кстати, Вы разбирались с алгоритмом McKay-я и вообще с способом, которым они строят main классы для обычных ЛК?
Пользователи, просматривающие эту тему
Guest
21 Страницы«<1112131415>»
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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