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

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

Уведомление

Icon
Error

37 Страницы«<2930313233>»
Опции
К последнему сообщению К первому непрочитанному
Offline Disel  
#601 Оставлено : 14 мая 2018 г. 16:47:25(UTC)
Disel


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

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

Группы: Member, Russia Team Group
Зарегистрирован: 08.07.2013(UTC)
Сообщений: 3,603
Мужчина
Российская Федерация

Сказал «Спасибо»: 519 раз
Поблагодарили: 427 раз в 327 постах
Автор: whitefox Перейти к цитате

Соответствующие изменения внесены в программу Определитель семейств блочных ЛК.

Попробовал скомпилить, ругнулось на #include <intrin.h>, видимо что-то специфически виндовое. Других "жалоб" от компилятора не поступило.

Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
Offline hoarfrost  
#602 Оставлено : 14 мая 2018 г. 16:53:03(UTC)
hoarfrost


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

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Автор: Disel Перейти к цитате
Попробовал скомпилить, ругнулось на #include <intrin.h>, видимо что-то специфически виндовое. Других "жалоб" от компилятора не поступило.

Это инструкции AVX/AVX2 и т.п. от Intel. Библиотеки должны быть и под Linux.
UserPostedImage
Offline evatutin  
#603 Оставлено : 14 мая 2018 г. 22:46:49(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1023 раз
Поблагодарили: 1826 раз в 886 постах
Динамика находок: по-видимому вышли в новую область, КФы ОДЛК просто валом валят
Пользователь evatutin прикрепил следующие файлы:
bmp.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
citerra оставлено 15.05.2018(UTC)
Online citerra  
#604 Оставлено : 15 мая 2018 г. 7:16:18(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
четверок перевалило за 250
двушек 8888
Offline whitefox  
#605 Оставлено : 15 мая 2018 г. 16:07:37(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Автор: Disel Перейти к цитате

Попробовал скомпилить, ругнулось на #include <intrin.h>, видимо что-то специфически виндовое. Других "жалоб" от компилятора не поступило.


Это внутренние функции Микрософтовского компилятора. Некоторые сторонние компиляторы их тоже понимают. В программе использована только одна из них — _BitScanForward, которая просто вставляет в код машинную команду bsf.

В качестве паллиатива, функцию _BitScanForward можно определить самостоятельно, например, так:
Код:
void _BitScanForward(unsigned long* x, unsigned long y){
	unsigned long v = y & -(int)y;
	*x = 0;
	if(v & 0xffff0000) *x += 16;
	if(v & 0xff00ff00) *x += 8;
	if(v & 0xf0f0f0f0) *x += 4;
	if(v & 0xcccccccc) *x += 2;
	if(v & 0xaaaaaaaa) (*x)++;
}

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

Online citerra  
#606 Оставлено : 19 мая 2018 г. 8:13:15(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
Герасим набрал обороты
В обработаной порции есть разные типы ОДЛК, кроме девяток. Ждем.

Два года назад были такие планы-цели
Цитата:
Первая степень А ( 1000 КФ в неделю ) достигнута.
Затем
Б 10 000 в месяц
В 1 000 в день
Г 1млн за год.

И последняя цель достигнута, в ODLK1@Home, а сейчас в Герасиме.
Надо намечать новые.
Наращивание количества КФ ОДЛК потеряло актуальность. Давно настала пора анализирования. По факту так и делаем.
В Герасиме исследовались различные виды симметрий. Сейчас приступили частично-симметричным квадратам. И сразу появились результаты. Темп находок резко увеличился, а главное стали появляться новые структуры.

двушек 10565
четверок 294

thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 21.05.2018(UTC)
Offline whitefox  
#607 Оставлено : 21 мая 2018 г. 17:41:41(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Представляю программу Генератор блочных ЛК, предназначенную для построения блочных ЛК10 старших видов (7x7 и старше, вплоть до 10x10). Для заданного канонического шаблона семейства она находит все принадлежащие ему существенно различные блочные ЛК.

Файл readme.txt



Для проверки найденных блочных ЛК на наличие ОДЛК, можно воспользоваться программой klpmd.exe или пакетным файлом kanon_new.bat в который она входит.

Как уже отмечалось, семейство вида 10x10 может содержать до миллиона существенно различных блочных ЛК, то есть на обработку одного семейства может уйти целый день.
Вложение(я):
gen_blk.zip (59kb) загружен 7 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 21.05.2018(UTC)
Offline whitefox  
#608 Оставлено : 23 мая 2018 г. 16:31:10(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Возможно, следующая утилита будет полезна. smile

Файл readme.txt

Вложение(я):
sos_operate.zip (20kb) загружен 13 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 23.05.2018(UTC)
Offline Disel  
#609 Оставлено : 25 мая 2018 г. 13:43:25(UTC)
Disel


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

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

Группы: Member, Russia Team Group
Зарегистрирован: 08.07.2013(UTC)
Сообщений: 3,603
Мужчина
Российская Федерация

Сказал «Спасибо»: 519 раз
Поблагодарили: 427 раз в 327 постах
Автор: whitefox Перейти к цитате
Возможно, следующая утилита будет полезна. smile



Эта программа скомпилировалась, вдруг то же понадобится под другой ос. Заодно перевел в UTF-8 код и readme.
Вложение(я):
sos_operte_l.zip (27kb) загружен 4 раз(а).
Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
thanks 1 пользователь поблагодарил Disel за этот пост.
whitefox оставлено 26.05.2018(UTC)
Offline whitefox  
#610 Оставлено : 26 мая 2018 г. 11:52:34(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
В ЛС и на закрытых форумах было задано несколько вопросов о различии между программами family_mar и klpmd. Видимо, нужно рассказать об этом и в публичном пространстве.

Хотя family_mar и была опубликована раньше чем klpmd, вторая была раньше разработана, а family_mar есть всего лишь её специализация для весьма частного применения. Само название klpmd является аббревиатурой от Канонизатор ЛК по марьяжным ДЛК, что намекает на объединение "в одном флаконе" двух программ — Канонизатор ЛК по ДЛК и Ортогон. Но так как данная программа никакой не канонизатор, то в качестве названия используется исключительно аббревиатура, которая никак не расшифровывается.

Смысл объединения двух программ в одной — в возможности существенного ускорения поиска ОДЛК. Так программа Ортогон сама по себе показывает скорость 700 ДЛК/сек, а во "флаконе" klpmd — 6300 ДЛК/сек. Столь существенное ускорение происходит из-за изменения метода построения диагональных трансверсалей — вместо их непосредственного построения для каждого найденного ДЛК, используется фильтрация предварительно найденного списка трансверсалей (обычных) общего для всех существенно различных ДЛК производных от одного ЛК. На один ЛК в среднем приходится порядка 1000 (скорее ~800) существенно различных ДЛК производных от него. А так как отфильтровывание д-трансверсалей из общего списка трансверсалей выполняется значительно быстрее чем непосредственное их построение, а поиск всех трансверсалей выполняется только один раз на 1000 ДЛК, то и получается ускорение.

Отмечу, что скорость непосредственного построения д-трансверсалей тоже можно значительно ускорить. Так экспериментальная программа, использующая идеи veinamond, показывает скорость построения д-трансверсалей 2160 ДЛК/сек. Использование этих идей в Ортогон позволило бы увеличить его скорость до 2100 ДЛК/сек, что всё равно втрое ниже чем у klpmd.

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

При выполнении эксперимента по проверке на ОДЛК всех блочных ЛК вида nx5, потребовалось универсальную программу klpmd специализировать, чтобы исключить проверку квазисимметричных ДЛК, которые уже были полностью проверены в предыдущем эксперименте. Эта необходимость возникла из-за того, что среди всех блочных ДЛК вида nx5 подавляющую часть составляют именно квазисимметричные ДЛК. Для этого и была предназначена программа family_mar, позволившая значительно сократить время выполнения данного эксперимента.

Можно сделать следующие выводы:
1) на входных файлах, не содержащих блочных ЛК вида nx5, обе программы работают одинаково, только klpmd потенциально чуть быстрее (примерно на 0,5%), так как не проверяет построенные ДЛК на квазисимметричость, что делает family_mar;
2) на входных файлах, содержащих достаточно много блочных ЛК вида nx5, family_mar имеет значительное преимущество в скорости перед klpmd, так как не проверяет на ОДЛК построенные квазисимметричные ДЛК, что делает klpmd;
3) во втором случае klpmd может найти больше марьяжных ДЛК чем family_mar, но излишек составляют исключительно квазисимметричные марьяжные ДЛК, которые уже все найдены.

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

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

Приведу выдержки из протоколов работы обеих программ на семействе блочных ЛК вида 10x10 с каноническим шаблоном:
Код:
0 0 1 1 2 2 3 3 4 4
0 0 1 1 2 2 4 4 3 3
1 2 0 2 3 3 0 1 4 4
1 2 0 2 4 4 0 1 3 3
2 3 2 3 4 4 1 0 0 1
2 4 2 4 3 3 1 0 0 1
3 1 3 0 0 1 4 4 2 2
3 4 3 4 1 0 2 2 1 0
4 1 4 0 0 1 3 3 2 2
4 3 4 3 1 0 2 2 1 0

family_mar:


klpmd:

thanks 1 пользователь поблагодарил whitefox за этот пост.
Demis оставлено 04.06.2018(UTC)
Offline AlexA  
#611 Оставлено : 1 июня 2018 г. 18:27:42(UTC)
AlexA


Статус: Administration

Медали: Переводчику: За помощь в создании сайта

Группы: Editors, Member, Administration, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 6,140
Мужчина
Российская Федерация
Откуда: "Russia Team"

Сказал «Спасибо»: 1250 раз
Поблагодарили: 1516 раз в 838 постах
У меня возник такой вопрос:
За последние 1-2 года в поиске разных вариантов ОДЛК произошел резкий скачек. И в плане количества найденных и известных на текущий момент. Усилиями народной общественности (не побоюсь этого слова) запущено и функционирует несколько проектов с различными алгоритмами поиска. Усилиями "белого лиса" сделан скачек в теоретическом описании и подходе к пониманию квадратов.

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

Я думаю, что тут на эту тему нам хотелось бы увидеть посты от whitefox, citerra, evatutin, Максима и Натальи Никитиной. Мнение Progger-а тоже интересно.
thanks 4 пользователей поблагодарили AlexA за этот пост.
key оставлено 01.06.2018(UTC), svb оставлено 01.06.2018(UTC), SerVal оставлено 02.06.2018(UTC), Demis оставлено 04.06.2018(UTC)
Offline evatutin  
#612 Оставлено : 5 июня 2018 г. 11:43:49(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1023 раз
Поблагодарили: 1826 раз в 886 постах
Выскажу свое стратегическое мнение, думаю остальные заинтересованные лица сделают то же самое.
1. Экстенсивный поиск КФ ОДЛК в общем-то себя исчерпал — хорошо видно, что он дает в основном однушки, редко что-то еще, это не очень интересно, необходимо искать особенности.
2. Из особенных типов ДЛК можно выделить (на данный момент, имхо):
* симметричные в одной плоскости ДЛК;
* обобщенно-симметричные ДЛК;
* частично-симметричные ДЛК.
На данный момент первые два пункта пройдены, третий обрабатывается и дает интересные решения.
3. Недавно была изменена стратегия канонизации ДЛК, что опять таки дало очень хороший прирост по числу решений. Что она даст впереди еще предстоит выяснить...

Зачем все это?
1. Поиск новых комбинаторных структур из ДЛК на множестве отношения ортогональности — в литературе они не описаны, новизна однозначно есть. Теоретически в них могут найтись особенности...
2. Поиск псевдотроек с целью повышения ХО.
3. Попытка найти тройку ВОДЛК.

Если интересно, последние результаты экспериментов интересны с позиции п. 1, но по п. 2 ХО получаются низкие, обычно не выше 30 при рекорде (нашем же кста) в 74.

Есть и еще направления развития (те же блочные структуры) — я сам в это пока глубоко не лез, тут лучше пусть whitefox расскажет...

PS. Мысли есть и еще, но их надо реализовывать и пробовать, на это нужно время. Если складывается ощущение, что мы просто по инерции пытаемся экстенсивно расширять список КФов, то это не так, работа ведется в интенсивном режиме. На те же частично-симметричные ДЛК по моим прикидкам мы потратим как минимум лето, а может быть и часть осени — тут впереди много работы... Ну а когда у нас у всех иссякнут идеи, тогда расчеты можно будет сворачивать 199

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
AlexA оставлено 05.06.2018(UTC)
Online citerra  
#613 Оставлено : 5 июня 2018 г. 11:54:52(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
Автор: evatutin Перейти к цитате
Ну а когда у нас у всех иссякнут идеи, тогда расчеты можно будет сворачивать 199

Или продолжить. Тут работы на десятилетия. Но это не так интересно. Но тем кому важен спортивный интерес, будет довольны.

Offline whitefox  
#614 Оставлено : 6 июня 2018 г. 13:16:04(UTC)
whitefox


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

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

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

Файл readme.txt



Ранее подобная программа уже была представлена, но она работала через чур медленно (на канонизацию одного ЛК требовалось две секунда). В новой программе КФ ЛК определены по другому, что позволило значительно увеличить скорость (в среднем в 40000 раз).

Будем нормализованный ЛК (то есть ЛК первая строка и первый столбец которого упорядочены в возрастающем порядке) называть сильно нормализованным если его вторая строка имеет один из следующих 12-и видов:
Код:
1032547698
1032547896
1032564897
1032567894
1034267895
1034527896
1034567892
1204537896
1204567893
1230567894
1234067895
1234567890


Число сильно нормализованных ЛК существенно меньше числа нормализованных ЛК и в качестве КФ можно было бы выбрать лексикографически наименьший сильно нормализованный ЛК, но пойдём дальше. Все сильно нормализованные ЛК, принадлежащие одному главному классу ЛК, разделим на субклассы и субкласс наименьшей мощности назовём "лучшим". КФ ЛК определим как лексикографически наименьший сильно нормализованный ЛК из лучшего субкласса.

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

Для примера, приведу протокол работы на файле из 2382421 марьяжных ДЛК.

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

Вложение(я):
kanonizator_lk.zip (37kb) загружен 6 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 06.06.2018(UTC)
Online citerra  
#615 Оставлено : 7 июня 2018 г. 20:14:30(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
Количество двушек превысило 12 000
Offline whitefox  
#616 Оставлено : 8 июня 2018 г. 10:49:44(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Исправил баг из-за которого невозможно было указать имя входного файла отличное от input.txt.

Исправленная версия в архиве из предыдущего моего поста.
Offline whitefox  
#617 Оставлено : 8 июня 2018 г. 11:05:48(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Автор: AlexA Перейти к цитате
Было бы интересно почитать какой-то обобщенный анализ того что сделано, куда и насколько продвинулись, что стало понятнее, а что - наоборот - затуманилось и какие новые вопросы и проблемы возникли. В общем - подвести какой-то промежуточный итог.

Действительно, за последний год число найденных марьяжных ДЛК10 резко возросло. В первую очередь это связано с запуском нескольких boinc-проектов, использующих более быстрые алгоритмы. Но потенциал ускорения ещё есть.

Наиболее узким местом является проверка ДЛК на наличие ОДЛК. Самым быстрым методом, решающим эту задачу, оказался метод Эйлера-Паркера. Применительно к обычным ЛК, этот метод сначала находит все трансверсали ЛК, а затем строит из трансверсалей покрытия ЛК. При этом, время поиска трансверсалей на несколько порядков меньше времени построения покрытий. Но для ДЛК10 ситуация прямо противоположная — для подавляющего числа ДЛК время построения покрытий на пару порядков меньше времени поиска диагональных трансверсалей. То есть, ускорив процедуру поиска д-трансверсалей, можно значительно ускорить поиск марьяжных ДЛК10.

В начале этого года было проведено соревнование программ поиска д-трансверсалей для ДЛК10. Первое место заняла программа, представленная veinamond. Использование его идей позволит втрое увеличить скорость проверки ДЛК10 на наличие ОДЛК.

Совсем недавно veinamond предложил перестроить организацию поиска марьяжных ДЛК, что потенциально позволит ещё больше ускорить проверку ДЛК на наличие ОДЛК. А именно — заменить генерацию КФ ДЛК генерацией КФ ЛК и уже для последних находить присущие им КФ ДЛК, которые и проверять на наличие ОДЛК. Такой подход позволит использовать алгоритм, применённый в программе klpmd, работающий в девять раз быстрее используемого ныне, и в трое быстрее алгоритма программы победительницы упомянутого соревнования.

Но даже после ускорения проверки ДЛК на наличие ОДЛК, скорость поиска марьяжных ДЛК10, всё равно, будет не достаточной для завершения тотальной проверки в обозримом будущем. В связи с этим, особый интерес представляет сплошная проверка отдельных классов ДЛК. В этом направлении исследовались два подхода:
1) проверка блочных ЛК;
2) проверка ЛК, обладающих определённой обобщённой симметрией;

Неожиданным образом эти два подхода пересеклись — оказалось, что все ЛК, обладающие плоскостной симметрией (по терминологии evatutin-а), это ровно все блочные ЛК вида nx5. Проверка последних была полностью выполнена, марьяжных среди них оказалось 3411 с точностью до изоморфизма главных классов ДЛК.

Настала очередь проверки блочных ЛК сташих видов, и ЛК с другими видами обобщёной симметрии.

Ещё одним направлением исследования является изучение отношения ортогональности ДЛК. Это бинарное отношение является симметричным и арефлексивным, поэтому его удобно изображать в виде простого не ориентированного графа (то есть графа без кратных рёбер и без петель). В частности, был составлен каталог всевозможных конфигураций компонент связности этого графа. Так как граф отношения ортогональности ДЛК построен ещё не полностью, то возможно существуют и другие конфигурации его компонент связности.

Это исследование можно обобщить если рассмотреть отношение ортогональности не на ДЛК, а на главных классах ДЛК. То есть полагать, что два главных класса ДЛК ортогональны если найдётся пара ортогональных ДЛК таких, что один из них принадлежит первому классу, а другой второму. Очевидно, что граф этого отношения уже будет ориентированным мультиграфом.

Ещё одно обобщение получим, если на главных классах ЛК определим отношение д-ортогональности. То есть будем два главных класса ЛК называть д-ортогональными если найдётся пара ортогональных ДЛК таких, что один из них принадлежит первому классу, а другой второму. Введение понятия д-ортогональности мотивируется тем, что применение программы Канонизатор_ЛК_по_ДЛК к найденным марьяжным ДЛК, приводит к тому, что наш список КФ марьяжных ДЛК замкнут относительно изоморфизма главных классов ЛК.

Отредактировано пользователем 8 июня 2018 г. 11:42:15(UTC)  | Причина: Не указана

thanks 3 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 08.06.2018(UTC), AlexA оставлено 08.06.2018(UTC), evatutin оставлено 12.06.2018(UTC)
Online citerra  
#618 Оставлено : 9 июня 2018 г. 8:55:02(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
Поток находок несколько возрос, но кол-во ОДЛК уже не цель.
Назрела необходимость изменений в системе накопления и учета.
Все таки когда их около 2 500 000 действовать надо по другому с той поры, когда их было в районе несколько тысяц.
Первая мысль с связи с реорганизацией, поделить находки на группы.
Сначала выделить однушки. Их большинство.
Обычная однушки входят в пару себе подобной. Есть одно семейство ( чуть более 30 000 ) когда у кф однушки и ортогональной кф одлк совпадают ( их нашел whitefox ).Есть еще такие однушки, у которых кф соппадает? Надо проверить.
Есть однушки, которые входят в состав более сложных структур.
Однушки простых структур нужно поместить в отдельный список.
Такую же процедуру можно проделать с двушками.
Сначала выделяем двушки с простыми структурами.
Первая содержит двушку и две однушки
B - A - C ( бабочка ), A - двушка, ( в дальнейшим одлк A будем обозначать кф с большим числом одлк-связей )
Вторая у которых кф однушек совпадает
A - B или
Цитата:

B
|| или просто
A

A
|
B

( бабочка с сложенными крыльями )
Теоритически может быть когда все три кф одинаковые. Пока такой цели не ставилось. Надо проверять.
Отсеяв одлк простых структур, остается совсем немного КФ ОДЛК, менее тысячи.
Составление каталога "сложных" структур началось. Здесь нужно еще уточнить его, учитывая совпадения КФ.
Прошерстив еще можно найти еще свойства квадратов, которые надо учитывать ( трансверсали, тип симметрии, блочные струтуры )
Вот такое состояние дел и направления работы по учету квадратов
thanks 2 пользователей поблагодарили citerra за этот пост.
AlexA оставлено 10.06.2018(UTC), evatutin оставлено 12.06.2018(UTC)
Online citerra  
#619 Оставлено : 12 июня 2018 г. 15:05:47(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 499 раз
Поблагодарили: 344 раз в 250 постах
10139 новых кф

12093 двушек ( +85 )
72 трешки ( прибавки нет )
316 четверок ( +2 )

Отредактировано пользователем 12 июня 2018 г. 16:49:00(UTC)  | Причина: Не указана

Offline whitefox  
#620 Оставлено : 13 июня 2018 г. 12:28:09(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 73 раз
Поблагодарили: 179 раз в 113 постах
Выполняю обещание:
Автор: whitefox Перейти к цитате
Алгоритм разделения на субклассы и выбора лучшего из них опишу в следующий раз.


Для каждого класса изотопии ЛК определим инвариант, который назовём "циклическим инвариантом изотопии". Строить его для конкретного ЛК будем так:
1) для всех строк ЛК выполним:
а) выберем очередную строку ЛК;
б) переименуем элементы ЛК так чтобы выбранная строка стала нормализованной;
в) найдём циклические структуры остальных строк и присвоим им соответствующие предопределённые символы;
г) лексикографически упорядочим эти символы и запишем их в строку;
// таким образом каждой строке ЛК10 мы сопоставим девяти-буквенную упорядоченную строку символов
2) лексикографически упорядочим полученные упорядоченные строки символов.

Всего существует 12 различных циклических структур перестановок десяти элементов не имеющих единичных циклов:

Код:
10
2,8
3,7
4,6
5,5
2,2,6
2,3,5
2,4,4
3,3,4
2,2,2,4
2,2,3,3
2,2,2,2,2


Упорядочим их в порядке возрастания наименьших представителей и сопоставим им соответствующие буквы латинского алфавита:

Код:
A -> 1032547698 = (01)(23)(45)(67)(89)
B -> 1032547896 = (01)(23)(45)(6789)
C -> 1032564897 = (01)(23)(456)(789)
D -> 1032567894 = (01)(23)(456789)
E -> 1034267895 = (01)(234)(56789)
F -> 1034527896 = (01)(2345)(6789)
G -> 1034567892 = (01)(23456789)
H -> 1204537896 = (012)(345)(6789)
I -> 1204567893 = (012)(3456789)
J -> 1230567894 = (0123)(456789)
K -> 1234067895 = (01234)(56789)
L -> 1234567890 = (0123456789)

Тогда, например, ЛК:

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


будет иметь следующий циклический инвариант изотопии:

Код:
AIIIILLLL
AKKKKLLLL
BBCDEEILL
BBCDEEILL
BBCDEEILL
BBCDEEILL
CCDEEKKLL
CCDEEKKLL
CCDEEKKLL
CCDEEKKLL

Так как циклическая структура обратной перестановки равна циклической структуре самой перестановки, то парастрофы ЛК, различающиеся только инверсией строк, имеют одинаковые циклические инварианты изотопии.

Циклический инвариант главного класса ЛК определим как лексикографически упорядоченную тройку циклических инвариантов изотопии для следующих парастрофов ЛК:

1) сам ЛК;
2) транспонированый ЛК;
3) ЛК с инвертированными столбцами.

Например, приведённый ЛК имеет следующий циклический инвариант:



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

Упорядоченная тройка состоящая из:
1) какой-нибудь секции цикличиского инварианта;
2) какой-нибудь строки данной секции;
3) какого-нибудь символа данной строки;
определяет субкласс сильно нормализованных ЛК принадлежащих данному главному классу ЛК.

Чтобы подсчитать число субклассов:
1) удалим из циклического инварианта дублирующие секции;
2) из оставшихся секций удалим дублирующие строки;
3) из оставшихся строк удалим дублирующие символы.
Число оставшихся в инварианте символов равно числу субклассов.

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

Код:
ACDEFGIKL
ACDEGKL
AEGJL
AEGJKL
AFGJKL
AIJL

AIL
AKL
BCDEIL
CDEKL


то есть данный главный класс ЛК имеет 54 субкласса сильно нормализованных ЛК.

Каждому символу сопоставим вес равный порядку группы автосопряжённости для соответствующего класса сопряжённости перестановок, а именно:

Код:
A -> 3840
B -> 192
C -> 144
D -> 48
E -> 30
F -> 64
G -> 16
H -> 72
I -> 21
J -> 24
K -> 50
L -> 10

Вес субкласса определим как произведение кратности соответствующей секции на кратность соответствующей строки на кратность соответствующего символа на вес этого символа. Например, субкласс, определяемый тройкой:

Код:
ACDEFGIKL   AEGJJKLLL   L
ACDEFGIKL
ACDEGGKLL
ACDEGGKLL
AEEGGJJLL
AEGJJKLLL
AEGJJKLLL
AFGJJKLLL
AFGJJKLLL
AIIJJLLLL


имеет вес равный 2 * 2 * 3 * 10 = 120

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

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