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