Детерминированный и недетерминированный алгоритм (формализация)

#алгоритм #теория_автоматов

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

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

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


  К разветвляющимся алгоритмам можно отнести:  





  
  Алгоритм, поведение которого полностью зависит от входных данных, называют детерминированным
|deterministic|. Каждый его шаг заранее предопределен. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому
результату.
  





  
  Алгоритм, поведение которого невозможно предсказать (от чего оно зависит?), называют
недетерминированным |nondeterministic|.
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым,
так и к разным результатам.
  





  Иногда, решение задачи сводиться к использованию случайных величин.  
  
  
  Алгоритм, поведение которого, помимо входных данных, определяется значениями генератора
случайных (псевдослучайных) чисел, называют стохастическим |randomized|
  


Неужели никто, кроме википедии не в состоянии дать определения этих понятий,
которые в принципе, являются фундаментом программирования? Может есть подходящие
книги? В общем странно, столько людей получают высшее образование, неужели профессора
не дают таких базовых определений своим студентам?
    

Ответы

Ответ 1

Такие виды алгоритмов были введены в обращение в 
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;
}


Выведет:

71876166
708592740
1483128881

71876166
708592740
1483128881


Как видите, поведение функции rand() предсказуемо и зависит от исходного внутреннего
состояния. Вместе с тем, если вы не знаете исходного состояния, то поведение предсказать
будет сложно, если вообще возможно.

Внутреннее состояние алгоритма - это не входные данные. Вы не обязательно можете
на них влиять. Например, возьмём кошку. Если кошка сыта и здорова, но она будет рада
ласке. Если кошка голодна или больна, то при тех же действиях с вашей стороны (входных
данных) вы практически гарантировано вы будете поцарапаны. Таким образом можно сказать
что поведение кошки определяется недетерминированным алгоритмом.

Алгоритмы, которые определяются случайными числами, являются подвидом недетерминированных.
Их принято называть вероятностными алгоритмами (probabilistic algorithms). Например,
к числу таких можно было бы отнести простую нейронную сеть в которой изначальные веса
указываются случайными числами. При прочих равных для данного набора данных и данных
исходных весов после обучения вы всегда получите те же самые конечные веса. Другим
примером алгоритм, который одновременно недетерминированным и вероятностным, может
быть сверточная нейронная сеть, которая содержит содержит dropout-cлой. Итоговые веса
после обучения в такой сети могут случайно отличаться при тех же входных данных и исходных
весах.


Ответ 2

В функциональном программировании было введено понятие "чистая функция".
Это такая функция, которая при определенных аргументах возвращает один и тот же результат.
Всегда. То есть она не обращается ни к каким внешним ресурсам: не делает запросы в
БД, не получает числа из генератора случайных чисел, не получает ввод с консоли и даже
не выводит никуда данные (это тоже обращение к внешнему ресурсу: если данные выводить,
возможны какие-то ошибки ввода-вывода, и вместо ожидаемого результата может возникнуть,
например, исключение)
Алгоритм вычисления этой функции есть детерминированный алгоритм.

Функции, не являющиеся чистыми называют функциями с побочными эффектами. В них находятся
недетерминированные алгоритмы. Стохастические - это их подвид.

Например:

// эта функция детерминирована
public static int DeterministicAdd(int a, int b)
{
    return a + b;
}

// эта функция недетерминирована    
public static int NonDeterministicAdd(int a, int b)
{
    return a + b + int.Parse(Console.ReadLine());
}


Ответ 3

Дабы избежать введения лишних зависимостей (типа времени, ввода и прочего) и интроспекции
в чёрный ящик алгоритма, предлагаю такие определения:

Детерминированный: алгоритм, который при наличии нескольких верных ответов, всегда
выдаёт один и тот же.

Недетерминированный: алгоритм, который при наличии нескольких верных ответов, всегда
выдаёт один из них.

Связано это с тем, что результат работы алгоритма обычно проверяется простым естественным
вопросом, как то Найденный путь имеет длину не больше 5? или Равно ли значение функции
нулю в найденной точке?. И независимо от типа алгоритма на одних и тех же данных ответ
верификации должен быть одинаков.