Есть ли задача на распределенные вычисления, которую легко проверить?
Здравствуйте, мой диплом связан с распределенными вычислениями, которые хочется показывать на примере какой-то задачи. Я бы хотел узнать, существуют ли задачи вычисление решения которых может занимать весьма долгое время, но проверка этого решения будет быстрой?
В качестве варианта, можно было бы использовать вычисление простых чисел, или перемножение огромных матриц, но эти задачи не подходят, так как их сложно проверить. То есть, я не могу убедиться, что матрицы перемножены верно сразу, мне для этого их нужно перемножить заново в однопоточном режиме. Насчет простых чисел конечно проще, но опять же если условие ставится как поиск 1000 простого числа, чтобы убедиться что найденное простое число именно 1000 по счету, нужно пересчитать все до него.
Дополнительно:
Попробуйте написать распределённую трассировку лучей (путей), n компьютеров рендерят w/n h/n прямоугольник изображения, а потом все прямоугольники объединяются в одно изображение
В качестве варианта, можно было бы использовать вычисление простых чисел, или перемножение огромных матриц, но эти задачи не подходят, так как их сложно проверить. То есть, я не могу убедиться, что матрицы перемножены верно сразу, мне для этого их нужно перемножить заново в однопоточном режиме.
В таких случаях можно 1 раз просчитывать основные случаи, сохранять результат, а потом проверять на многопоточке
Насчет простых чисел конечно проще, но опять же если условие ставится как поиск 1000 простого числа, чтобы убедиться что найденное простое число именно 1000 по счету, нужно пересчитать все до него.
Можете взять готовый список простых чисел и сверить результат своих вычислений с уже известными данными. Если совпало - значит задача решена корректно.
Ответы:
Алгоритмы майнинга криптовалют, любой, тот же биткоин изучен и разложен по полочкам вдоль и поперек.
У всех у них это свойство - сложно считать но легко проверить.
По факту это хеширование строки с изменяемой частью (в нее сериализуется число - задача подобрать число чтобы хеш строки с этим числом имел заранее оговоренные свойства, например количество младших нулевых битов хеша).
Так как у тебя академическая задача, тебе не нужно повторять именно тот самый алгоритм и настраивать инфраструктуру, просто реши задачу поиска хеша от байтового представления числа. Т.е. задача в организаци процесса - управление рабочими потоками/нодами, с раздачей заданий (интервалов в пределах которых каждый воркер будет перебирать хеши) и сбор результатов, включая обработку ошибок.
Попробуйте алгоритмы факторизации чисел. Их проверка всегда занимает линейное время (по количеству множителей).
Там есть ряд алгоритмов, которые можно параллелить, типа решета числового поля (NFS) или квадратичного решета (QS)
Берете любую NP-complete задачу: https://en.m.wikipedia.org/wiki/List_of_NP-complet...
Все их сложно решить и легко проверить ответ.
На СИ?
Попробуйте распределенную компиляцию, например icecc, distcc
Даже считать не нужно
Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.
Пока нет других ответов. Будьте первым, кто поможет автору.
Ответить на вопрос
Да, существует множество задач, которые могут быть легко проверены с использованием распределенных вычислений. Одним из таких примеров может быть задача поиска всех простых чисел в заданном диапазоне.
Простые числа - это числа, которые имеют только два делителя: 1 и само число. Для проверки простоты числа, можно использовать алгоритм проверки делителей. Один из простых способов проверки простоты числа n - это перебор всех чисел от 2 до квадратного корня из n и проверка деления n на каждое из них без остатка.
Для распределенных вычислений, можно разделить диапазон чисел на несколько частей и распределить каждую часть на отдельный узел вычислительной сети. Каждый узел будет проверять простоту чисел в своей части диапазона и возвращать результаты на центральный узел, который будет собирать и агрегировать результаты.
Пример кода на PHP для решения этой задачи с использованием распределенных вычислений:
function isPrime($num){ if($num <= 1){ return false; } for($i = 2; $i <= sqrt($num); $i++){ if($num % $i == 0){ return false; } } return true; } $rangeStart = 1; $rangeEnd = 1000; $primeNumbers = []; for($i = $rangeStart; $i <= $rangeEnd; $i++){ if(isPrime($i)){ $primeNumbers[] = $i; } } print_r($primeNumbers);
Этот код будет проверять все числа в диапазоне от 1 до 1000 на простоту и выводить список всех найденных простых чисел. Для распределенных вычислений можно разделить диапазон на части и распределить задачи проверки простоты на разные узлы сети для более эффективного выполнения.