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