Детерминированный и недетерминированный алгоритм (формализация)
1,00
р.
Столкнулся с тем, что качество определений википедии оставляет желать лучшего. Да, текста там много, но при этом формализация не является полной и точной. Остальная часть рунета пуста, в буквальном смысле. Все что есть, сотни сайтов копи-пасты с той же википедии. Поиск по книгам, посвященным программированию и алгоритмам (в частности) тоже не дал результатов. Определений либо вообще нет, либо приводятся отрывочно, либо качество перевода и работа редактора настолько запредельная, что сложно уловить смысл.
Решил формализовать различия между ними самостоятельно. Понял, что не смогу один с этим справиться. Кое-что у меня уже получилось, возможно с вашей помощью получится заполнить пробелы в определениях, обозначенные тильдами.
Если можете сформулировать лучше, дайте свои определения для детерминированного и недетерминированного алгоритма (стохастический, уже имеет максимально полное и при этом не большое, но понятное определение).
К разветвляющимся алгоритмам можно отнести:
Алгоритм, поведение которого полностью зависит от входных данных, называют детерминированным |deterministic|. Каждый его шаг заранее предопределен. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому результату.
Алгоритм, поведение которого невозможно предсказать (от чего оно зависит?), называют недетерминированным |nondeterministic|. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам.
Иногда, решение задачи сводиться к использованию случайных величин.
Алгоритм, поведение которого, помимо входных данных, определяется значениями генератора случайных (псевдослучайных) чисел, называют стохастическим |randomized|
Неужели никто, кроме википедии не в состоянии дать определения этих понятий, которые в принципе, являются фундаментом программирования? Может есть подходящие книги? В общем странно, столько людей получают высшее образование, неужели профессора не дают таких базовых определений своим студентам?
Ответ
Такие виды алгоритмов были введены в обращение в 1967 году Робертом Флойдом. Если обратиться к первоисточнику, то картина будет следующая:
Определение детерминированного алгоритма вы уже дали в вопросе.
Недетерминированный алгоритм отличается от детерминированного алгоритма не фактом использования случайных чисел, а наличием других переменных, влияющих на результат, кроме полученных из входных данных. Если вы возьмете какую-то функцию, реализующую недетерминированный алгоритм, то один раз для входного числа она вернёт один результат, а в другой раз для того же числа она может вернуть другой результат.
Таким критериям соответствуют функции, реализующие ГПСЧ. Вызывая функцию rand() вы получаете каждый раз другое число, даже если вы явно зададите исходное число для генератора случайных чисел вызовом srand().
#include using namespace std int main() { srand(42) std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << std::endl srand(42) std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << rand() << std::endl return 0 } <br>Выведет:
71876166 708592740 1483128881
71876166 708592740 1483128881
Как видите, поведение функции rand() предсказуемо и зависит от исходного внутреннего состояния. Вместе с тем, если вы не знаете исходного состояния, то поведение предсказать будет сложно, если вообще возможно.
Внутреннее состояние алгоритма - это не входные данные. Вы не обязательно можете на них влиять. Например, возьмём кошку. Если кошка сыта и здорова, то она будет рада ласке. Если кошка голодна или больна, то при тех же действиях с вашей стороны (входных данных) вы практически гарантировано будете поцарапаны. Таким образом можно сказать что поведение кошки определяется недетерминированным алгоритмом.
Алгоритмы, которые определяются случайными числами, являются подвидом недетерминированных. Их принято называть вероятностными алгоритмами (probabilistic algorithms). Например, к числу таких можно было бы отнести простую нейронную сеть в которой изначальные веса указываются случайными числами. При прочих равных для данного набора данных и данных исходных весов после обучения вы всегда получите те же самые конечные веса. Другим примером алгоритм, который одновременно недетерминированным и вероятностным, может быть сверточная нейронная сеть, которая содержит содержит dropout-cлой. Итоговые веса после обучения в такой сети могут случайно отличаться при тех же входных данных и исходных весах.
Решил формализовать различия между ними самостоятельно. Понял, что не смогу один с этим справиться. Кое-что у меня уже получилось, возможно с вашей помощью получится заполнить пробелы в определениях, обозначенные тильдами.
Если можете сформулировать лучше, дайте свои определения для детерминированного и недетерминированного алгоритма (стохастический, уже имеет максимально полное и при этом не большое, но понятное определение).
К разветвляющимся алгоритмам можно отнести:
Алгоритм, поведение которого полностью зависит от входных данных, называют детерминированным |deterministic|. Каждый его шаг заранее предопределен. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому результату.
Алгоритм, поведение которого невозможно предсказать (от чего оно зависит?), называют недетерминированным |nondeterministic|. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам.
Иногда, решение задачи сводиться к использованию случайных величин.
Алгоритм, поведение которого, помимо входных данных, определяется значениями генератора случайных (псевдослучайных) чисел, называют стохастическим |randomized|
Неужели никто, кроме википедии не в состоянии дать определения этих понятий, которые в принципе, являются фундаментом программирования? Может есть подходящие книги? В общем странно, столько людей получают высшее образование, неужели профессора не дают таких базовых определений своим студентам?
Ответ
Такие виды алгоритмов были введены в обращение в 1967 году Робертом Флойдом. Если обратиться к первоисточнику, то картина будет следующая:
Определение детерминированного алгоритма вы уже дали в вопросе.
Недетерминированный алгоритм отличается от детерминированного алгоритма не фактом использования случайных чисел, а наличием других переменных, влияющих на результат, кроме полученных из входных данных. Если вы возьмете какую-то функцию, реализующую недетерминированный алгоритм, то один раз для входного числа она вернёт один результат, а в другой раз для того же числа она может вернуть другой результат.
Таким критериям соответствуют функции, реализующие ГПСЧ. Вызывая функцию rand() вы получаете каждый раз другое число, даже если вы явно зададите исходное число для генератора случайных чисел вызовом srand().
#include using namespace std int main() { srand(42) std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << std::endl srand(42) std::cout << rand() << std::endl std::cout << rand() << std::endl std::cout << rand() << std::endl return 0 } <br>Выведет:
71876166 708592740 1483128881
71876166 708592740 1483128881
Как видите, поведение функции rand() предсказуемо и зависит от исходного внутреннего состояния. Вместе с тем, если вы не знаете исходного состояния, то поведение предсказать будет сложно, если вообще возможно.
Внутреннее состояние алгоритма - это не входные данные. Вы не обязательно можете на них влиять. Например, возьмём кошку. Если кошка сыта и здорова, то она будет рада ласке. Если кошка голодна или больна, то при тех же действиях с вашей стороны (входных данных) вы практически гарантировано будете поцарапаны. Таким образом можно сказать что поведение кошки определяется недетерминированным алгоритмом.
Алгоритмы, которые определяются случайными числами, являются подвидом недетерминированных. Их принято называть вероятностными алгоритмами (probabilistic algorithms). Например, к числу таких можно было бы отнести простую нейронную сеть в которой изначальные веса указываются случайными числами. При прочих равных для данного набора данных и данных исходных весов после обучения вы всегда получите те же самые конечные веса. Другим примером алгоритм, который одновременно недетерминированным и вероятностным, может быть сверточная нейронная сеть, которая содержит содержит dropout-cлой. Итоговые веса после обучения в такой сети могут случайно отличаться при тех же входных данных и исходных весах.
