подключайте свои компьютеры к Российскому исследовательскому проекту SAT@home
Dicki
29 3490 01:04 29.04.2012
Проект SAT@home
SAT@home - исследовательский проект, использующий соединяемые через сеть Интернет компьютеры для решения трудных и практически важных задач (обращения дискретных функций, дискретной оптимизации, биоинформатики и т.д.), которые могут быть эффективно сведены к задаче о выполнимости булевых формул. На данный момент в проекте запущен поиск тройки взаимно ортогональных латинских квадратов порядка 10.
Главная страница:
Организаторы:
Институт системного анализа РАН (Центр грид-технологий и распределенных вычислений),
Институт динамики систем и теории управления Сибирского отделения РАН
Научная цель проекта
3. Какие задачи уже решены в проекте? Завершен эксперимент, направленный на решение 10 задач криптоанализа генератора A5/1, которые не решаются с помощью rainbow-таблицы, построенной специально для этих целей (см. A5/1 cracking project). С помощью rainbow-таблиц задачи криптоанализа генератора A5/1 решаются быстро, но успешное решение не гарантировано на 100%. В SAT-подходе эти задачи решаются дольше, но их решение находится с вероятностью 100%. Сделали мы наши задачи так:
-сгенерировали случайным образом 1000 задач криптоанализа генератора A5/1; -попробовали решить эти 1000 задач с помощью rainbow-таблицы. Не решились 125 из 1000; -из 125 случайно выбрали 10, по ним построили SAT-задачи, которые и были решены в проекте.
Кроме этого, были найдены 17 новых пар диагональных ортогональных латинских квадратов порядка 10.
В разделе Найденные решения размещена таблица с результатами.
4. Какие задачи решаются в проекте сейчас? На данный момент запущен поиск тройки взаимно ортогональных латинских квадратов порядка 10.
4.1. Зачем нужно решать задачу поиска тройки взаимно ортогональных латинских квадратов порядка 10? Данная задача интересна сама по себе, поскольку это своего рода вызов человеческому интеллекту. Впервые она сформулирована еще Л. Эйлером в XVIII веке. На текущий момент 10 - это минимальный порядок, для которого неизвестно существование тройки попарно ортогональных латинских квадратов. У этой задачи есть и практические приложения. Многие используемые на практике комбинаторные конструкции, например некоторые классы кодов, исправляющих ошибки при передаче информации, теснейшим образом связаны с латинскими квадратами. Имеется связь латинских квадратов с задачами планирования экспериментов, а также с различными головоломками, например судоку.
4.2. Насколько сложна задача поиска тройки взаимно ортогональных латинских квадратов порядка 10? Эта задача является очень сложной. На сегодня известны десятки работ на эту тему и какого-либо серьезного прогресса в решении этой задачи пока не наблюдается. Наша оптимистическая оценка состоит в том, что в проекте SAT@home эту задачу удастся решить. Однако на данный момент понятно, что необходима существенная оптимизация алгоритмов решения SAT-задач. Поэтому сейчас в проекте SAT@home решаются задачи поиска пар ортогональных латинских квадратов порядка 9 и 10 с дополнительным условием «диагональности». Данные задачи проще, чем задача поиска троек попарно ортогональных латинских квадратов порядка 10, поэтому некоторые пары квадратов уже известны. Тем не менее представляет интерес нахождение новых ортогональных диагональных пар. Кроме этого, исследуя данные задачи, мы пытаемся найти возможные направления для улучшения производительности используемых нами алгоритмов. .
некоторые наверно знают что это такое, народ давайте подключайтесь к вычислениям, пока вы общаетесь на форуме, Ваш ПК помогает нашим ученым
как подключится к проекту описано тут
если в кратце, качаете софтинку , включаете ее, она коннектится к серверу проекта , на ваш ПК скидывается часть информации которую нужно обработать, ПК ее обрабатывает и отсылает на сервер, дальше вы снова получаете информацию для обработки, все происходит в автоматическом режиме
результаты иследований выкладывают на форум и сайт , те везунчики кто нашел решение задач могут рассчитывать, что их Ники появятся на сайте.
форум данного проекта
страница где в % показан прогресс исследования.
07:38 29.04.2012
А я давно подключен к SETI@home
12:38 29.04.2012
Вячеслав 12286 писал(а) в ответ на :
>А я давно подключен к SETI@home
я раньше тоже гонял свой пк , пару лет перерыв сделал, на днях зашел. увидел, что наконец то наши институты начали пользоваться таким способом
вот на данном проекте, у них есть свой не очень мощный супер пк в институте, но то что они обсчитывают благодаря SAT@home за 10 дней, им бы пришлось на своем 30 дней делать, не говоря уже о очередях на этот супер пк.
так что своим то вдвойне приятно помочь.... тем более intel core i7 простаивает
13:09 29.04.2012
Dicki писал(а) в ответ на :
> Проект SAT@home >
хрен тебе а не мой компьютер . сам справлюсь тем что мне надо - а нужна помощь обращайся .
19:44 29.04.2012
Вячеслав 12286 писал(а) в ответ на :
>А я давно подключен к SETI@home
можете свою статистику скинуть?
18:26 17.06.2012
по проекту Завершен эксперимент, направленный на решение 10 задач криптоанализа генератора A5/1
4. Какие задачи решаются в проекте сейчас? На данный момент решаются задачи поиска ортогональных пар диагональных латинских квадратов порядка 9 и 10. В ближайшем будущем мы надеемся найти тройку взаимно ортогональных латинских квадратов порядка 10 либо доказать отсутствие такой тройки.
подключайтесь народ.
18:35 17.06.2012
сколько умных буков... можно как-нибудь по-колхозному объяснить в двух словах - че за связи, и для чего оно?
18:51 17.06.2012
Чиклино писал(а) в ответ на :
> сколько умных буков... можно как-нибудь по-колхозному объяснить в двух словах - че за связи, и для чего оно?
где то у меня было более понятным языком от научного сотрудника в ИДСТУ СО РАН, найду скину, пока вот: 4.1. Зачем нужно решать задачу поиска тройки взаимно ортогональных латинских квадратов порядка 10? Данная задача интересна сама по себе, поскольку это своего рода вызов человеческому интеллекту. Впервые она сформулирована еще Л. Эйлером в XVIII веке. На текущий момент 10 - это минимальный порядок, для которого неизвестно существование тройки попарно ортогональных латинских квадратов. У этой задачи есть и практические приложения. Многие используемые на практике комбинаторные конструкции, например некоторые классы кодов, исправляющих ошибки при передаче информации, теснейшим образом связаны с латинскими квадратами. Имеется связь латинских квадратов с задачами планирования экспериментов, а также с различными головоломками, например судоку.
4.2. Насколько сложна задача поиска тройки взаимно ортогональных латинских квадратов порядка 10? Эта задача является очень сложной. На сегодня известны десятки работ на эту тему и какого-либо серьезного прогресса в решении этой задачи пока не наблюдается. Наша оптимистическая оценка состоит в том, что в проекте SAT@home эту задачу удастся решить. Однако на данный момент понятно, что необходима существенная оптимизация алгоритмов решения SAT-задач. Поэтому сейчас в проекте SAT@home решаются задачи поиска пар ортогональных латинских квадратов порядка 9 и 10 с дополнительным условием «диагональности». Данные задачи проще, чем задача поиска троек попарно ортогональных латинских квадратов порядка 10, поэтому некоторые пары квадратов уже известны. Тем не менее представляет интерес нахождение новых ортогональных диагональных пар. Кроме этого, исследуя данные задачи, мы пытаемся найти возможные направления для улучшения производительности используемых нами алгоритмов.
22:06 04.07.2012
Выпустили версию 2.0 расчетного приложения.
версия 1.19 требовала до 300 мб памяти, а 2.0 - до 160.
подключаемся народ .
22:31 04.07.2012
Публикации
О.С. Заикин, М.А. Посыпкин, А.А. Семёнов, Н.П. Храпов. Организация добровольных вычислений на платформе BOINC на примере проектов OPTIMA@home и SAT@home // CAD/CAM/CAE Observer # 3 (71) / 2012. С. 87-92
Заикин О.С. Посыпкин М.А. Семенов А.А. Храпов Н.П. Опыт организации добровольных вычислений на примере проектов OPTIMA@home и SAT@home // Труды муждународной конференции ПАВТ 2012. С. 157-166.
А.А. Семенов. Криптоанализ с применением rainbow-таблиц. Доклад в Институте математики им. С.Л. Соболева СО РАН 14.12.2011.
22:33 04.07.2012
Добрый вечер!
Интересную тут решают задачу - о трёх попарно ортогональных ЛК 10-го порядка. Я тоже пыталась её решать Моя идея - использовать квази-разностные матрицы.
> > Интересную тут решают задачу - о трёх попарно ортогональных ЛК 10-го порядка. > Я тоже пыталась её решать > Моя идея - использовать квази-разностные матрицы. > > Не знаю, разрешаются ли здесь ссылки.
> Рискну: > >
Добрый вечер, да я припоминаю данную статью, на форуме проекта выкладывали и один из авторов проекта назвал ее достаточно интересной ) . можете пообщаться с ним(ник Nauchnik научный сотрудник в ИДСТУ СО РАН) на том форуме.
на 44 странице если точнее
оттуда же
Сейчас решается задача поиска пар ортогональных латинских квадратов с дополнительным усложняющим условием, что они диагональные. Т.е. не только в каждом столбце и строке значения должны быть различны, но и на главной и побочной диагоналях. Затем мы будем решать задачу поиска тройки взаимно ортогональных латинских квадратов порядка 10, но уже без условия диагональности. Она очень сложная, сколько именно будет заданий пока не знаю.
так что работы работы думаю на на год вычислений...
08:25 05.07.2012
Я посмотрела стр. 44 по указанной ссылке. Там речь идёт о другой моей статье - "Ортогональные латинские квадраты десятого порядка".
Здесь я дала ссылку на статью о квази-разностных матрицах (КРМ). Пыталась решать задачу построения трёх попарно ортогональных ЛК 10-го порядка с использованием КРМ. Возникли вычислительные сложности. Для порядка 4, например, алгоритм прекрасно работает.
Мой коллега по форуму tolstopuz тоже попробовал реализовать идею. Здесь (стр. 38) он написал отчёт об этой работе.
Эти квадраты диагональные латинские (в каждой строке, столбце, главной и побочной диагонали числа 0..8 не повторяются) и составляют ортогональную пару (все пары чисел, полученные накладыванием одного квадрата на другой, различны).
01:04 03.09.2012
В текущем эксперименте найдено более 100 пар ортогональных диагональных латинских квадратов размерности 9. .
сегодня запущен новый эксперимент для размерности 10.
