Пример детерминированного алгоритма?

Question

Добрый вечер, мне было интересно, если бы кто-нибудь мог предоставить мне простой пример псевдокода детерминированного алгоритма... Я буду очень признателен и обязательно дам вам очки!! Спасибо

Answer 1

Для меня "детерминизм" может означать много вещей:

• При одинаковом вводе каждый раз выдает одинаковый вывод.
• При одинаковом вводе каждый раз он занимает одинаковое количество времени / памяти / ресурсов.
• Задачи сложности класса P которая может быть решена за полиномиальное время детерминированным компьютером, в отличие от задач класса сложности NP которая может быть решена только за полиномиальное время с использованием недетерминированного компьютера.

Что из этого вы имеете в виду?

Самый простой детерминированный алгоритм - это генератор случайных чисел.

def random():
    return 4 #chosen by fair dice roll, guaranteed to be random

Это дает тот же результат каждый раз, экспонаты известны O(1) время и ресурсы, и выполняется в PTIME на любом компьютере.

Answer 2

Вы действительно имеете в виду ДЕТЕРМИНИСТИЧЕСКИЙ, а не недетерминированный, я имею в виду почти все, что вы видите в любом учебнике / руководстве / стартовой книге, является детерминированным, например

for i from 1 to 9 
    print i

всегда будет печатать 123456789

Answer 3

Детерминированный алгоритм - это просто алгоритм, который имеет предопределенный вывод. Например, если вы сортируете элементы, которые строго упорядочены (нет равных элементов), выходные данные хорошо определены, и поэтому алгоритм является детерминированным.

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

Answer 4

Детерминированный алгоритм - это алгоритм, который в неформальном выражении ведет себя предсказуемо. Учитывая конкретный ввод, он всегда будет давать один и тот же вывод

public struct Point {
   public int x;
   public int y; 

   //other methods

   public override int GetHashCode() {
      return x ^ y;
   }
}

Point P=new Point();
p.x=6;
p.y=3;
int res= p.GetHashCode();

Answer 5

Вот псевдокод для детерминированного алгоритма, который проверяет, является ли данное число нечетным:

function is_odd(n):
    if n mod 2 = 1
    then return true
    else return false