Есть ли задача на распределенные вычисления, которую легко проверить?

Здравствуйте, мой диплом связан с распределенными вычислениями, которые хочется показывать на примере какой-то задачи. Я бы хотел узнать, существуют ли задачи вычисление решения которых может занимать весьма долгое время, но проверка этого решения будет быстрой?

В качестве варианта, можно было бы использовать вычисление простых чисел, или перемножение огромных матриц, но эти задачи не подходят, так как их сложно проверить. То есть, я не могу убедиться, что матрицы перемножены верно сразу, мне для этого их нужно перемножить заново в однопоточном режиме. Насчет простых чисел конечно проще, но опять же если условие ставится как поиск 1000 простого числа, чтобы убедиться что найденное простое число именно 1000 по счету, нужно пересчитать все до него.
  • Вопрос задан
  • 276 просмотров
Пригласить эксперта
Ответы на вопрос 4
@rPman
Алгоритмы майнинга криптовалют, любой, тот же биткоин изучен и разложен по полочкам вдоль и поперек.
У всех у них это свойство - сложно считать но легко проверить.

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

Так как у тебя академическая задача, тебе не нужно повторять именно тот самый алгоритм и настраивать инфраструктуру, просто реши задачу поиска хеша от байтового представления числа. Т.е. задача в организаци процесса - управление рабочими потоками/нодами, с раздачей заданий (интервалов в пределах которых каждый воркер будет перебирать хеши) и сбор результатов, включая обработку ошибок.
Ответ написан
Комментировать
@MagicMight
no magic quotes
Попробуйте алгоритмы факторизации чисел. Их проверка всегда занимает линейное время (по количеству множителей).
Там есть ряд алгоритмов, которые можно параллелить, типа решета числового поля (NFS) или квадратичного решета (QS)
Ответ написан
Комментировать
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Берете любую NP-complete задачу: https://en.m.wikipedia.org/wiki/List_of_NP-complet...

Все их сложно решить и легко проверить ответ.
Ответ написан
Комментировать
saboteur_kiev
@saboteur_kiev
software engineer
На СИ?
Попробуйте распределенную компиляцию, например icecc, distcc
Даже считать не нужно
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы