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

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

Уведомление

Icon
Error

Опции
К последнему сообщению К первому непрочитанному
Offline AlexA  
#1 Оставлено : 6 июля 2014 г. 9:01:47(UTC)
AlexA


Статус: Administration

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

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

Сказал «Спасибо»: 1249 раз
Поблагодарили: 1515 раз в 837 постах
Нашел вот в Википедии статью о нерешенных математических задачах (проблемах).
Есть среди них и те, над которыми работают некоторые boinc-проекты, например Гипотеза Коллатца (гипотеза 3n+1).

Посмотрел на список своим нематематическим взглядом: много задач, которые требуют именно математического решения, формулами и доказательствами. Но есть и такие, где достаточно просто найти решение (единственное или несколько, либо доказать что его нет, либо найти более оптимальное/минимальное, чем уже известное). В этом смысле такие задачи чем-то похожи на решенную в рамках проекта судоку.

Ну, например (могу ошибаться):
- Задача о перемещении дивана (не доказана максимальность наилучшей оценки снизу (константы Гервера).)
- Существует ли треугольник с целочисленными сторонами, медианами и площадью?
- Найдётся ли в единичном квадрате точка, расстояние от которой до каждой из 4 вершин рационально?
- Задача о 9 кругах. Существует ли 9 кругов, таких, что каждые два пересекаются, и центр каждого круга лежит вне остальных кругов? (Время выполнения проверочного алгоритма — слишком большое).
- Какое наименьшее количество плиток может содержать множество плиток Ванга (англ.), которым можно замостить плоскость только непериодически? Наименьший известный результат — 13.
- Можно ли разместить 8 точек на плоскости так, чтобы никакие 3 из них не лежали на одной прямой, никакие 4 не лежали на одной окружности и расстояние между любыми 2 точками было целым числом? Решение для 7 точек было найдено в 2007 году.

Наверное такие задачи вполне можно решать в рамках boinc-проектов, ведь тут можно перебрать множество вариантов с различными начальными параметрами.
Или я ошибаюсь?
Offline Disel  
#2 Оставлено : 8 июля 2014 г. 17:06:37(UTC)
Disel


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

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

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

Сказал «Спасибо»: 516 раз
Поблагодарили: 426 раз в 326 постах
По видимому это зависит от требуемой мощности вычислительной системы, для поиска решения. Но не только. Ведь можно найти численное значение в какой-то определенной задаче + для каких-то определенных условий, но так и не узнать, можно ли решить задачу с использованием простого инженерного калькулятора. Например алгоритм шифрования RSA то же относится к таким задачам. Можно его атаковать всеми мощностями планеты и даже, если повезет, найти решение (для относительно коротких ключей такие решения уже находили, как раз в проектах распределенных вычислений), но до сих пор никто не представил формулу показывающую, как это сделать много более простым способом (а потому для другого ключа нужно будет опять наваливаться всей планетой), ровно как нет доказательств обратного, т.е. того, что это невозможно.
Думаю такие проекты могут помочь в сборе статистики, для выбора правильного направления математического поиска, хотя работа над некоторыми задачами, как например с окружностями и точками, возможно сразу же позволит дать окончательный ответ, хотя опять же методом перебора.

Отредактировано пользователем 8 июля 2014 г. 17:25:19(UTC)  | Причина: Не указана

Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
Offline evatutin  
#3 Оставлено : 18 февраля 2015 г. 14:16:47(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
Думаю, что тут все не так просто, как кажется. Дело в том, что полным перебором можно решить любую задачу, но вопрос в затратах времени, которые обычно растут очень быстро, даже для гридов или суперкомпьютеров. Подозреваю, что в этих задачах уже были попытки параллельного решения, просто вики дает лишь вершину айсберга, 5% наиболее простой для понимания информации, остальное надо рыть. Поэтому подозреваю, что с нахрапу за счет большого числа участников получится мало что. Несколько подтверждающих примеров.
1. Все мы более менее знаем, что делал Олег и К с квадратами в SAT, а Олег и его коллеги знают в 10 раз больше нас. Теперь откройте вики про латинские квадраты и посмотрите, есть ли там информация об этом. И это не недоработка Олега или кого-либо из нас, ссылка на проект в статье есть, просто копание в такой специфике вряд ли будет интересно для большинства читателей вики или авторов статей. Если, например, я напишу программу для решения задачи полным перебором, то к результатам Олега я даже близко не подойду, в том числе и с использованием грид. Я это знаю, поэтому этого делать не буду. По крайней мере так, как описал, т.к. у меня есть другие мысли на этот счет, но об этом пока говорить рано smile
2. Изоморфизм графов — в этой теме я более менее ориентируюсь и статья в вики на данный момент более менее отражает мои знания в этой теме, но... В ней есть серьезные пробелы по изоморфизму специфичных графов (например, планарных, деревьев, из нескольких компонент связности и пр.), которые надо восполнять. Я это знаю, а большинство других нет, соответственно если решать задачу в лоб полным перебором, даже на грид, то ничего хорошего не получится. Есть подходы (я, Валяев (не SerVal, другой smile ), Трофимов, Пролубников, Intel, ...), для которых не доказана правильность или неправильность, про них в вики ни слова. Сейчас я подал для опубликования очередной небольшой материал по изоморфизму, заранее не могу сказать, как к нему отнесется сообщество и будут ли интересные научные следствия. В нашей литературе данная тема практически не освещается последние 25 лет, однако оказывается, что за бугром есть профильные журналы, которые надо бы посмотреть (я их недавно обнаружил почти случайно, очень интересно, теперь надо внимательно изучить). И наверняка там будет что-нить интересное по данной тематике, что вряд ли найдет отражение в вики
3. В yoyo@home был подпроект Euler, который искал решения диофантова уравнения вида a1^2 + a2^2 + ... + aN^2 = b1^2 + b2^2 + ... + bM^2 для одного из частных случаев, и у меня тогда чесались руки попробовать хотя бы один из других. Когда спустя пару лет вышла статья авторов с результатами, оказалось, что в ней они используют нетривиальную стратегию раннего отсечения неперспективных решений, которая на несколько порядков снижает сложность перебора. Их проект работал около 2 лет, если память не изменяет, если бы я сделал "в лоб", было бы 2000 лет.
Примеры могу привести и еще, если надо

Вывод: взяться можно, но нужен глубокий анализ состояния проблемы на данный момент или грамотный специалист-математик, которые уже разбирается в теме. А дальше можно говорить об организации параллельного расчетного модуля и его запуска в грид. Иначе вместо громкого открытия можно вызвать громкий смех, чего бы не хотелось smile. Если спецы-математики найдутся, готов участвовать. На данный момент мне, ввиду объективных ограничений на свободное время, вполне хватает своей дискретной сферы проблем, с запасом на несколько лет вперед smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Пользователи, просматривающие эту тему
Guest
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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