Детерминированный алгоритм: различия между версиями

м
мНет описания правки
* Как указание купить все эти товары в данном порядке. Это детерминированный алгоритм.
 
=== ПрикладПример 2: Сортировка слиянием ===
Допустим мы имеем набор сущностей (скажем, 300 студенческих экзаменов), которые необходимо отсортировать (скажем, по номерам студентов).
 
 
Элементы могут быть уникально отсортированы, если критерий сортировки всегда определяет полний порядок; т.е. номера студентов уникальны, но если сортировать экзамены по фамилиям студентов и два студента имеют одинаковые фамилии, результат сортировки остаётся неопределённым. В таких случаях, сортировка слиянием всегда будет выдавать один из возможных упорядочиваний, но какое именно остаётся неизвестно, т.е. алгоритм недетерминированный .
 
=== Пример 3: [[Тест простоты]] ===
Задача: дано [[натуральное число]] больше единицы, определить является ли это число [[простое число|простым]].
 
Недетерминированный алгоритм следующий:
# Взять любое целое ''k'' такое, что 2 ≤ ''k'' ≤ √(''n'').
# Если ''k'' является делителем ''n'', остановится с ответом '''нет'''; иначе остановится с ответом '''не известно'''.
Видно, что алгоритм не всегда даёт полезный ответ, но никогда не даёт неправильного ответа.
 
Этот алгоритм недетерминированный, он не всегда выдаёт верное решение, но только при определённой комбинации выборов. Это пример ''поискового'' типа недетерминированного алгоритма.
 
== См. также ==