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

м
нет описания правки
[непроверенная версия][непроверенная версия]
мНет описания правки
'''Детерминированный алгоритм''' — [[Алгоритм|алгоритмический]] процесс, который выдаёт уникальный и предполагаемый результат для заданных входных данных.
 
== Недетерминированный алгоритм ==
В [[информатика|информатике]], '''Недетерминированный алгоритм''' это [[алгоритм]], который указывает несколько путей обработки одни и тех же входных данных, без какого либо уточнения какой именно вариант будет выбран.
 
== Использование ==
Часто [[теория алгоритмов]], термин «algorithm» указывает на детерминованый алгоритм. Недетерминированный алгоритм отличается от своего более известного двойника возможностью получения результата несколькими разными путями. Детерминированный алгоритм даёт единственный путь от входных данных к выходным, тогда как некоторые пути выполнения недетерминированного алгоритма могут привести к одинаковому результату, а некоторые к особым результатам. Эти свойства описаны математически в «недетерминированной» модели вычислений известной как [[недетерминированный автомат]].
 
В разработке алгоритмов, недетерминированные алгоритмы часто используются когда задача решаемая алгоритмом по своей сути позволяет много выходов (или когда существует один выход с многими путями через которые он может быть найден, и все одинаково хороши). Важно, что каждый выход недетерминированного алгоритму верный, независимо от путей выбранных алгоритмом во время выполнения.
 
== Примеры ==
=== Пример 1: Список покупок ===
 
Представим список покупок: список товаров для покупки.
 
Это можно осмыслить двумя способами:
* Как указание купить все эти товары в любом порядке. Это недетерминированный алгоритм.
* Как указание купить все эти товары в данном порядке. Это детерминированный алгоритм.
 
=== Приклад 2: Сортировка слиянием ===
Допустим мы имеем набор сущностей (скажем, 300 студенческих экзаменов), которые необходимо отсортировать (скажем, по номерам студентов).
 
Один из алгоритмов для этого (называется [[Сортировка слиянием]]):
* разбить набор на две приблизительно равные части
* отсортировать обе половины сортировкой слиянием (т.е. [[рекурсия|рекурсивно]])
* слить результаты
 
Элементы могут быть уникально отсортированы, если критерий сортировки всегда определяет полний порядок; т.е. номера студентов уникальны, но если сортировать экзамены по фамилиям студентов и два студента имеют одинаковые фамилии, результат сортировки остаётся неопределённым. В таких случаях, сортировка слиянием всегда будет выдавать один из возможных упорядочиваний, но какое именно остаётся неизвестно, т.е. алгоритм недетерминированный .
 
== См. также ==
* [[Конечный автомат]]
* [[Недетерминированная машина Тьюринга]]
* [[Класс NP|Алгоритмы класса NP]]
* [[Побочный эффект (программирование)]]
* [[Неоднозначная грамматика]]
 
[[Категория:Теория алгоритмов]]