Есть ли задача на распределенные вычисления, которую легко проверить?
Здравствуйте, мой диплом связан с распределенными вычислениями, которые хочется показывать на примере какой-то задачи. Я бы хотел узнать, существуют ли задачи вычисление решения которых может занимать весьма долгое время, но проверка этого решения будет быстрой?
В качестве варианта, можно было бы использовать вычисление простых чисел, или перемножение огромных матриц, но эти задачи не подходят, так как их сложно проверить. То есть, я не могу убедиться, что матрицы перемножены верно сразу, мне для этого их нужно перемножить заново в однопоточном режиме. Насчет простых чисел конечно проще, но опять же если условие ставится как поиск 1000 простого числа, чтобы убедиться что найденное простое число именно 1000 по счету, нужно пересчитать все до него.
Попробуйте написать распределённую трассировку лучей (путей), n компьютеров рендерят w/n h/n прямоугольник изображения, а потом все прямоугольники объединяются в одно изображение
Еще хотел добавить, что есть ощущение, что можно использовать перемножение матриц особой формы, произведение которых легко проверить (возможно должна получается диагональная матрица)
Quttar, Так трассировка лучей и не требует реализации 3d движка. Вам же нужно только отрендерить статическую картинку. Есть серия статей "Ray Tracing in One Weekend," название намекает, что реализация не так много времени занимает.
В качестве варианта, можно было бы использовать вычисление простых чисел, или перемножение огромных матриц, но эти задачи не подходят, так как их сложно проверить. То есть, я не могу убедиться, что матрицы перемножены верно сразу, мне для этого их нужно перемножить заново в однопоточном режиме.
В таких случаях можно 1 раз просчитывать основные случаи, сохранять результат, а потом проверять на многопоточке
Насчет простых чисел конечно проще, но опять же если условие ставится как поиск 1000 простого числа, чтобы убедиться что найденное простое число именно 1000 по счету, нужно пересчитать все до него.
Можете взять готовый список простых чисел и сверить результат своих вычислений с уже известными данными. Если совпало - значит задача решена корректно.
Алгоритмы майнинга криптовалют, любой, тот же биткоин изучен и разложен по полочкам вдоль и поперек.
У всех у них это свойство - сложно считать но легко проверить.
По факту это хеширование строки с изменяемой частью (в нее сериализуется число - задача подобрать число чтобы хеш строки с этим числом имел заранее оговоренные свойства, например количество младших нулевых битов хеша).
Так как у тебя академическая задача, тебе не нужно повторять именно тот самый алгоритм и настраивать инфраструктуру, просто реши задачу поиска хеша от байтового представления числа. Т.е. задача в организаци процесса - управление рабочими потоками/нодами, с раздачей заданий (интервалов в пределах которых каждый воркер будет перебирать хеши) и сбор результатов, включая обработку ошибок.
Попробуйте алгоритмы факторизации чисел. Их проверка всегда занимает линейное время (по количеству множителей).
Там есть ряд алгоритмов, которые можно параллелить, типа решета числового поля (NFS) или квадратичного решета (QS)
Простой
Простой
