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

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