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