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

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

Уведомление

Icon
Error

117 Страницы«<9293949596>»
Опции
К последнему сообщению К первому непрочитанному
Offline AlexA  
#1861 Оставлено : 7 августа 2016 г. 18:28:38(UTC)
AlexA


Статус: Administration

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

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

Сказал «Спасибо»: 1250 раз
Поблагодарили: 1516 раз в 838 постах
Автор: astronom Перейти к цитате
блин, вот почему пчелы вымирают mrgreen

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

Сорри за оффтоп 199

Offline astronom  
#1862 Оставлено : 7 августа 2016 г. 19:46:40(UTC)
astronom


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

Группы: Member, Russia Team Group
Зарегистрирован: 27.07.2008(UTC)
Сообщений: 2,197
Откуда: РФ, Подольск

Сказал(а) «Спасибо»: 133 раз
Поблагодарили: 178 раз в 154 постах
муравьи не должны вымирать, у них более эффективный алгоритм поиска еды. hammer
Offline dimych  
#1863 Оставлено : 8 августа 2016 г. 19:59:07(UTC)
dimych


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

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

Сказал «Спасибо»: 445 раз
Поблагодарили: 211 раз в 170 постах
насчет самого эффективного поиска еды, муравьи тараканам даже в подметки не годятся xD
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 evatutin  
#1864 Оставлено : 8 августа 2016 г. 23:34:09(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Я смотрю тема биоинспирированных методов вызывает живой интерес не только в научном сообществе, но и в непосредственный близости от него smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Panda  
#1865 Оставлено : 9 августа 2016 г. 10:36:47(UTC)
Panda


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

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!

Группы: Member
Зарегистрирован: 19.06.2016(UTC)
Сообщений: 219
Мужчина
Российская Федерация
Откуда: St.Petersburg

Сказал «Спасибо»: 210 раз
Поблагодарили: 141 раз в 84 постах
Наличие eDRAM на процессорах с Irish Pro Gr влияет на скорость расчетов?
Offline evatutin  
#1866 Оставлено : 9 августа 2016 г. 10:54:37(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Автор: Panda Перейти к цитате
Наличие eDRAM на процессорах с Irish Pro Gr влияет на скорость расчетов?


Не тестировал, но подозреваю, что в текущем эксперименте нет. Если у вас есть такой, можете запустить многопоточный тест, результаты потом посмотрим...

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
Panda оставлено 27.08.2016(UTC)
Offline Panda  
#1867 Оставлено : 27 августа 2016 г. 19:01:21(UTC)
Panda


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

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!

Группы: Member
Зарегистрирован: 19.06.2016(UTC)
Сообщений: 219
Мужчина
Российская Федерация
Откуда: St.Petersburg

Сказал «Спасибо»: 210 раз
Поблагодарили: 141 раз в 84 постах
В проекте распределено более 500 млн. очков!!! Present Present Present
thanks 1 пользователь поблагодарил Panda за этот пост.
evatutin оставлено 28.08.2016(UTC)
Offline Vitalii Koshura  
#1868 Оставлено : 1 сентября 2016 г. 0:35:36(UTC)
Vitalii Koshura


Статус: Я тут не впервой

Группы: Member
Зарегистрирован: 24.04.2015(UTC)
Сообщений: 35
Мужчина
Украина
Откуда: Odessa

Сказал «Спасибо»: 18 раз
Поблагодарили: 23 раз в 15 постах
Тут на хабре статейка появилась про алгоритмы (автор не я, просто увидел в ленте): https://habrahabr.ru/post/308960/
thanks 3 пользователей поблагодарили Vitalii Koshura за этот пост.
hoarfrost оставлено 01.09.2016(UTC), SerVal оставлено 01.09.2016(UTC), Zabaikalec2010 оставлено 01.09.2016(UTC)
Offline evatutin  
#1869 Оставлено : 1 сентября 2016 г. 19:22:59(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Угу, это похоже на то, что мы не так давно считали в проекте. Только у нас методов было больше, тестовых примеров тоже было больше и условия сравнения были чуть другими. Если это интересно, я могу описать отличия подробнее

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
Vitalii Koshura оставлено 02.09.2016(UTC)
Offline evatutin  
#1870 Оставлено : 10 сентября 2016 г. 9:51:29(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
В текущем эксперименте осталось пройти около 9%, это где-то неделя счета. Чтобы побыстрее досчитать хвосты, я начинаю планомерно снижать дедлайн

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
Panda оставлено 11.09.2016(UTC)
Offline dimych  
#1871 Оставлено : 11 сентября 2016 г. 18:23:21(UTC)
dimych


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

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

Сказал «Спасибо»: 445 раз
Поблагодарили: 211 раз в 170 постах
думаю через дня три дохомячим. если что, мой компик готов досчитывать хвосты. инет вроде не глючит, охлад стабильный, все надежно.
хост Computer ID: 22826
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)
thanks 3 пользователей поблагодарили dimych за этот пост.
Panda оставлено 11.09.2016(UTC), evatutin оставлено 11.09.2016(UTC), Pavel Kirpichenko оставлено 14.09.2016(UTC)
Offline Pavel Kirpichenko  
#1872 Оставлено : 14 сентября 2016 г. 6:41:20(UTC)
Pavel Kirpichenko


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

Медали: Первооткрывателю: Результат в проекте SAT@home

Группы: Member
Зарегистрирован: 14.03.2014(UTC)
Сообщений: 680
Мужчина
Российская Федерация
Откуда: Новосибирская обл.

Сказал «Спасибо»: 296 раз
Поблагодарили: 115 раз в 72 постах
Меньше 1% осталось...
http://boincstats.com/signature/-1/user/2499467/sig.png
Offline tanos  
#1873 Оставлено : 15 сентября 2016 г. 6:14:40(UTC)
tanos


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

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

Группы: Member
Зарегистрирован: 08.10.2012(UTC)
Сообщений: 1,502
Мужчина
Откуда: Astronomy.Ru Forum

Сказал «Спасибо»: 580 раз
Поблагодарили: 660 раз в 396 постах
Автор: evatutin Перейти к цитате
В текущем эксперименте осталось пройти около 9%, это где-то неделя счета. Чтобы побыстрее досчитать хвосты, я начинаю планомерно снижать дедлайн

Ну вот, говорили год считать будем..., smile evatutin, как долго продлиться пауза в проекте?

команда Astronomy.Ru Forum - http://vk.com/club53333580
Offline evatutin  
#1874 Оставлено : 15 сентября 2016 г. 19:49:52(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Автор: tanos Перейти к цитате
Ну вот, говорили год считать будем..., smile


Я так и предполагал. Кто ж знал, что Степан мою версию кода еще в 3 раза ускорит smile

Цитата:
evatutin, как долго продлиться пауза в проекте?


Пока не знаю, есть несколько причин кроме необходимости досчета, постобработки и проверки, которые пока под вопросом. Я наверное скоро окончательно наберусь наглости и отпишусь в ветку про образование о том, что у нас сейчас в вузе происходит и чем мы занимаемся в свободное от преподавания время Не получается

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline evatutin  
#1875 Оставлено : 16 сентября 2016 г. 11:52:32(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Опубликован сборник материалов конференции Информационно-измерительная техника и технологии 2016, которая проходила в мае в Томске на базе Томского государственного университета. В сборнике есть статья

Vatutin E.I., Titov V.S. On the selection of optimal structure organization of logic multicontrollers // Information-measurement technics and technologies 2016. Tomsk: TSU, 2016. P. 596–607.

Она является логическим продолжением вот этой статьи 2012 года, в которой по первым результатам расчетов (точнее, по кривым загиба показателей, см. приаттаченную внизу картинку) можно было дать рекомендацию о том, какая аппаратная конфигурация контроллеров в составе логического мультиконтроллера является достаточной для реализации абсолютного большинства параллельных алгоритмов управления. В статье 2012 года получилось, что сложность должна быть достаточно большой (много связей, много памяти). Если эти требования не соблюсти и сделать конфигурацию более простой (менее аппаратно сложной), то в сторону ухудшения "поплывут" все оптимизируемые параметры (= технические характеристики системы). В новой статье старые данные были проанализированы еще раз и было показано, что если мы допускаем небольшое 5%-е ухудшение технических характеристик мультисистемы, то это позволяет сократить аппаратную сложность до 10 раз, приближая конфигурацию проектируемой системы управления к реально практически достижимой! Ну и если говорить о методах, то старые жадные методы работают хорошо только при слабых ограничениях, т.е. когда контроллеры большие и аппаратно избыточные. Если же мы уменьшаем их сложность в указанные 10 раз (что для практики очень и очень важно), то старые методы работают плохо, им нужно искать более хорошую замену. На сегодняшний день ситуация с подобной заменой такова: для небольших алгоритмов управления нужно применять итерационные методы (случайный перебор, взвешенный случайный перебор, муравьев, ...), а для больших — наше детище, метод параллельно-последовательной декомпозиции smile. В перспективе у меня есть надежды, что эти две группы методов получится "скрестить" (если по умному, то построить из них гибридную схему по одной из стратегий гибридизации smile ). Ну и на всякий случай: без выполненных экспериментов графиков загиба у меня не было бы, т.к. аналитически угадать поведения кривых скорее всего не удалось бы, поэтому это "структурно-параметрическое" направление научных работ — еще одна польза от расчетов, выполненных в проекте. Всем участвовавшим еще раз спасибо! Present

PS. Русская версия статьи в немного расширенном виде должна скоро выйти в журнале Телекоммуникации, где наша грид-тематика вообще говоря подходит, но освещена на данный момент слабо, надо работать в этом направлении 199. По итогам конференции английская статья с рядом исправлений была рекомендована в крутой журнал во Франции, сейчас решаются административные вопросы, научные мы решали фактически всю весну и все лето smile, надеюсь скоро тоже будет опубликована.

Отредактировано пользователем 16 сентября 2016 г. 12:29:32(UTC)  | Причина: Не указана

Пользователь evatutin прикрепил следующие файлы:
sail.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 10 пользователей поблагодарили evatutin за этот пост.
Yura12 оставлено 16.09.2016(UTC), Nauchnik оставлено 16.09.2016(UTC), Pushok оставлено 16.09.2016(UTC), Zabaikalec2010 оставлено 17.09.2016(UTC), vk_DiMoH оставлено 17.09.2016(UTC), Panda оставлено 17.09.2016(UTC), 256Ghz оставлено 17.09.2016(UTC), hoarfrost оставлено 18.09.2016(UTC), dimych оставлено 18.09.2016(UTC), tanos оставлено 20.09.2016(UTC)
Offline citerra  
#1876 Оставлено : 17 сентября 2016 г. 10:44:41(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 504 раз
Поблагодарили: 346 раз в 251 постах
Research progress: 99.990%

....

Finish

Отредактировано пользователем 17 сентября 2016 г. 13:36:53(UTC)  | Причина: Не указана

thanks 1 пользователь поблагодарил citerra за этот пост.
Panda оставлено 17.09.2016(UTC)
Offline evatutin  
#1877 Оставлено : 4 октября 2016 г. 18:04:56(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
На мой взгляд пора выходить из сумрака smile. Сперва приведу результат последних расчетов, а потом в двух словах опишу, как мы к нему пришли. Итак, по результатам расчетов опубликована работа

Ватутин Э.И., Титов В.С., Заикин О.С., Кочемазов С.Е., Валяев С.Ю., Журавлев А.Д., Манзюк М.О. Использование грид-систем для подсчета комбинаторных объектов на примере диагональных латинских квадратов порядка 9 // Информационные технологии и математическое моделирование систем 2016. М.: изд-во Центра информационных технологий в проектировании РАН, 2016. С. 154–157.

В ней есть найденное число нормализованных латинских квадратов (ДЛК) порядка 9, равное 5059716385604360 (значение неправильное, см. тут), и общее число ДЛК порядка 9, которое получается путем умножения предыдущего значения на 9! (тут нужна длинная арифметика, 64-битных целых чисел не хватает) и равно 1836069882008110156800 (значение неправильное, см. тут).

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

Заикин О.С., Кочемазов С.Е. Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@Home // Вестник ЮУрГУ (DOI: 10.14529/cmse150308),

в ней с использованием подхода с вариацией поиска с возвратом со случайным выбором очередного элемента ячейки (я тут еще не участвовал) удалось достичь рекордного на тот момент темпа в 1 ДЛК/с. Потом кое-что начало получаться и у меня, результатом чего стала статья

Ватутин Э.И., Журавлев А.Д., Заикин О.С., Титов В.С. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 18–30.

В ней было показано, что путем некоторого количества хитростей ДЛК все же складываются с темпом несколько сотен за 16 часов (темп — ключевая вещь!) с использованием эвристических методов и несколько тысяч за те же 16 часов (~ 0,01 ДЛК/с) — с использованием метода ограниченного полного перебора. Отмечу, что 2/3 этой статьи были написаны в поезде по дороге домой (30 ч!) из Петрозаводска с последнего BOINC FAST'а — нечем мне было заняться... smile. Дальше мы (уже коллектив авторов smile ) попытались поднять темп генерации ДЛК, сделав окончательную ставку на метод полного перебора, в результате чего была опубликована серия статей (статья — темп генерации ДЛК)

* Ватутин Э.И., Журавлев А.Д., Заикин О.С., Титов В.С. Учет алгоритмических особенностей задачи при генерации диагональных латинских квадратов // Известия ЮЗГУ. 2016. № 2 (65). C. 46–59.340 000 ДЛК/с
* Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzuk M.O., Kochemazov S.E., Titov V.S. Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares // Distributed computing and grid-technologies in science and education (GRID’16): book of abstracts of the 7th international conference. Dubna: JINR, 2016. p. 114–115.790 000 ДЛК/с
* Ватутин Э.И., Заикин О.С., Журавлев А.Д., Манзюк М.О., Кочемазов С.Е., Титов В.С. О влиянии порядка заполнения ячеек на темп генерации диагональных латинских квадратов // Информационно-измерительные диагностирующие и управляющие системы (Диагностика – 2016). Курск: изд-во ЮЗГУ, 2016. С. 33–39.790 000 ДЛК/с
* Еще одна статья, которая пока в черновиках и скоро пойдет в печать — 6 600 000 ДЛК/с

Статей 4 не потому, что мы хотели сделать как можно больше публикаций smile, а потому, что новые идеи начинали возникать уже после того, как очередная публикация была отправлена в печать (хорошая мысля, как известно, приходит опосля smile ). Полный перечень идей можно почерпнуть непосредственно из статей, я лишь приведу 3 ключевые, которые дали наибольший прирост темпа (были и еще, много ценных советов и идей дали hoarfrost и citerra, но некоторые либо не дали большого темпа, либо сами собой оказались ненужны в результате эволюции кода). Первая из них была предложена Alexone'ом и заключалась в том, что вместо рекуррентной программной реализации (одна подпрограмма с параметрами, вызывающая сама себя) необходимо использовать итеративную программную реализацию с N*N вложенными циклами (позднее мы это число циклов сократили до N*N - 2*N). Вторая идея моя и связана она с выбором порядка заполнения ячеек ДЛК. Корни у нее растут из других моих задач (разбиения и расписания — совсем ведь другие задачи, а как в математике все связано!), в них был выявлен эффект сильной вариации качества решений от порядка его складывания (статьи 1, 2, 3), однако сам оптимальный порядок не был найден. А в квадратах все встало на свои места (по крайней мере у меня в голове): оказалось, что оптимальный порядок может быть найден путем заполнения того элемента решения (ячейки ДЛК), на которую сейчас есть максимальное количество ограничений или, другими словами, для ее заполнения есть минимальное количество возможностей — см. рисунок во вложении (у меня есть скромная претензия на научную новизну, однако если вы укажете на применение данного принципа в других задачах до меня, напирать на приоритет не буду smile, буду признателен и буду ссылаться на других). Принцип универсальный, в будущем я планирую его апробацию и в других задачах... В задаче генерации ДЛК кроме числа ограничений еще можно учесть, что ДЛК — это частный случай магического квадрата, у которого есть магическая константа и которую можно использовать при вычислении последнего элемента диагонали, строки или столбца (не циклом, а по формуле, что гораздо быстрее). Ну и еще одна идея принадлежит Степану Кочемазову, который предложил использовать битовые операции как для хранения ДЛК, так и для пометки занятых/свободных элементов строк, столбцов и диагоналей. В совокупности данные основные идеи и позволили поднять темп по цепочке <1 ДЛК/с -> 300 000 ДЛК/с -> 1 800 000 ДЛК/с -> 6 600 000 ДЛК/с (приблизительно, т.к. часть оптимизаций я опустил, в статьях по ссылкам выше они есть). Таким образом, у нас на руках оказался высокоэффективный генератор ДЛК. А раз так, оказалось возможным посчитать зависимость числа ДЛК от его порядка. До N=8 это было сделано на 1 машине, на что программной реализации с темпом 790 000 ДЛК/с (на тот момент другой еще не было) потребовалось 30 часов. Для N=9 при наличии около 1000 машин в гриде нужно было около 1 года, соответствующий эксперимент был запущен в июле. После разработки более эффективной реализации и смены версии расчетника указанное время сократилось до 3 месяцев, т.е. посчитали мы быстрее. Без наших идей с использованием рекуррентной реализации в лоб на это потребовались бы сотни лет.

Некоторые наши коллеги (не будем показывать пальцем smile ) почти догадались, что мы считаем, однако ошиблись с порядком ДЛК: они предположили, что считаем N=10, а мы считали N=9 (и посчитали!). На данный момент могу утверждать, что число ДЛК порядка 10 минимум в миллион раз больше, соответственно для его определения в нашем проекте потребуется минимум 3 миллиона месяцев = 250 тысяч лет, что нереально. Даже если мы разработаем, например, высокоэффективную GPU-реализацию, которая в 100 раз эффективнее нынешней CPU-реализации, время в 2,5 тысячи лет все равно не внушает оптимизма. По нашим оценкам если закон Мура продолжит работать, а вместе с ним продолжит расти производительность вычислительной техники, то к 2040 году это станет реально (мне будет 57 лет, если маразм не нагрянет, вернемся к этому вопросу, ждите smile ). Если взять суперкомпьютер топового класса (на десятки петафлопс) в монопольное использование (чего на самом деле никто не даст), то указанную характеристику можно будет посчитать за время порядка года — возможно имеет смысл забросить удочку Китайцам, они ща возглавляют TOP500... smile

Ну и пару слов о том, что дальше. Полученные нами оценки скорее всего правильные, но требуют проверки. Для этого сейчас Nauchnik на кластере выполняет аналогичный эксперимент, чтобы получить аналогичную оценку — сейчас у него готово чуть больше 80% объема расчетов, к конце октября скорее всего будет готов полный объем. Если все совпадет, хорошо, если нет — будем сверять, искать ошибки и возможно часть данных перепроверять еще раз другими методами. После этого мы планируем подготовить пару больших публикаций (на русском и английском), в которых в строгой форме изложим все то, что здесь я изложил на научпоп языке, и публикацию найденных значений в OEIS. А дальше задач много: и у ДЛК есть некоторые комбинаторные характеристики, которые на сегоднящний день еще не посчитаны, и в других задачах найденный принцип применим, и эвристические методы мы еще не все обсчитали не во всех задачах. Так что впереди большая работа angry, если нас окончательно не задавит наш минобр, который в последнее время просто житья не дает Не получается, вы наверное не догадываетесь, но мы работаем страшно неэффективно, если минобр это докажет (а как известно, можно и до столба...), дальше работать не будем, выгонят на улицу. Пока этого не произошло, думаю еще пару тройку экспериментов организуем, а там видно будет.

Всем кранчерам спасибо за поддержку вычислительными мощностями! :stolko: Надеюсь и дальше будете поддерживать, пока неплохо получается, мои 50 кафедральных машин — это всего около 4,5% от общего объема вычислений 199

Отредактировано пользователем 8 ноября 2016 г. 12:04:31(UTC)  | Причина: Не указана

Пользователь evatutin прикрепил следующие файлы:
fig.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 14 пользователей поблагодарили evatutin за этот пост.
Alexone оставлено 04.10.2016(UTC), Yura12 оставлено 04.10.2016(UTC), barbulo оставлено 04.10.2016(UTC), AlexA оставлено 04.10.2016(UTC), PinkFloyd оставлено 04.10.2016(UTC), Panda оставлено 04.10.2016(UTC), SerVal оставлено 05.10.2016(UTC), Pavel Kirpichenko оставлено 05.10.2016(UTC), hoarfrost оставлено 05.10.2016(UTC), Dancer King оставлено 05.10.2016(UTC), Zabaikalec2010 оставлено 06.10.2016(UTC), Arahaez оставлено 06.10.2016(UTC), citerra оставлено 07.10.2016(UTC), tanos оставлено 10.10.2016(UTC)
Offline Alexone  
#1878 Оставлено : 4 октября 2016 г. 18:14:34(UTC)
Alexone


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

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

Группы: Editors, Member, Moderator "We wanna HELP"
Зарегистрирован: 21.10.2010(UTC)
Сообщений: 559
Мужчина
Откуда: Самара

Сказал «Спасибо»: 245 раз
Поблагодарили: 173 раз в 105 постах
Спасибо за подробное описание проделанной работы, и теплые слова.

UserPostedImage
Offline evatutin  
#1879 Оставлено : 7 октября 2016 г. 14:00:23(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1025 раз
Поблагодарили: 1833 раз в 888 постах
Я добавил ~ 150 тыс. WU'шек с именами *_rw_*, которые соответствуют методу случайных блужданий (англ. Random Walks, RW) в задаче поиска путей в графах. По методу подготовлена статья, скоро пойдет в печать. Метод является еще одной вариацией случайного перебора (RS), но работает быстрее и по качеству решений лучше простого случайного перебора с последовательным формированием решения — это плюс. С другой стороны, метод (по крайней мере как я его понимаю в дискретных задачах) является частным случаем метода имитации отжига (SA) при большой температуре, а это значит, что он принимает как хорошие, так и плохие модификации решения — при большим числе итераций это минус. При анализе скорости сходимости (см. картинку внизу) видно, что качество улучшается не монотонно, а в определенные периоды, которые по видимому соответствуют времени, когда траектория подходит к хорошим областям с хорошими решениями. Высокого качества решений я от него не ожидаю, однако убедиться в этом надо, поэтому и организован маленький эксперимент. Методы я научился писать быстрыми, поэтому время счета текущих WU'шек не будет превышать 10 с, дедлайн поэтому поставлен в 1 день, кворум 2. Надеюсь завершить эксперимент максимум за неделю, можете подтягивать ресурсы на краткосрочную перспективу 199

Отредактировано пользователем 7 октября 2016 г. 17:38:26(UTC)  | Причина: Не указана

Пользователь evatutin прикрепил следующие файлы:
200-1000.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 4 пользователей поблагодарили evatutin за этот пост.
vk_DiMoH оставлено 07.10.2016(UTC), Panda оставлено 07.10.2016(UTC), Yura12 оставлено 07.10.2016(UTC), Pavel Kirpichenko оставлено 08.10.2016(UTC)
Offline whitefox  
#1880 Оставлено : 8 октября 2016 г. 13:29:44(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 74 раз
Поблагодарили: 181 раз в 115 постах
Автор: evatutin Перейти к цитате
оказалось, что оптимальный порядок может быть найден путем заполнения того элемента решения (ячейки ДЛК), на которую сейчас есть максимальное количество ограничений или, другими словами, для ее заполнения есть минимальное количество возможностей — см. рисунок во вложении (у меня есть скромная претензия на научную новизну, однако если вы укажете на применение данного принципа в других задачах до меня, напирать на приоритет не буду smile, буду признателен и буду ссылаться на других). Принцип универсальный, в будущем я планирую его апробацию и в других задачах...

Принцип действительно универсальный. По словам Д.Кнута
Цитата:
Golomb and Baumert suggested choosing, at each stage of a backtrack procedure, a subproblem that leads to the fewest branches, whenever this can be done efficiently.

он был впервые упомянут в 1965 году в статье Solomon W. Golomb and Leonard D. Baumart "Backtrack programming":
Цитата:
This principle says in effect that, all other things being equal, it is more efficient to make the next choice from the set with fewest elements.


Кстати, Ваша задача элементарно сводится к задаче "точного покрытия". Вы не сравнивали эффективность Вашего алгоритма с алгоритмом "танцующих связей" Кнута?

Нет ли у Вас планов по подсчёту числа главных классов ДЛК?
thanks 2 пользователей поблагодарили whitefox за этот пост.
evatutin оставлено 08.10.2016(UTC), citerra оставлено 09.10.2016(UTC)
Пользователи, просматривающие эту тему
Guest (2)
117 Страницы«<9293949596>»
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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