Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.
Недетерминированный алгоритм
В информатике, «недетерминированный алгоритм» — это алгоритм, указывающий несколько путей обработки одних и тех же входных данных, — без какого-либо уточнения, какой именно вариант будет выбран.
Использование
Теория алгоритмов
В теории алгоритмов — под термином «алгоритм» обычно понимается «детерминированный» алгоритм. «Недетерминированный» — отличается от своего более известного «двойника» возможностью получения результата разными путями («детерминированный» — следует единственным путём: от данных — к результату, — тогда как некоторые пути выполнения «недетерминированного» могут привести к одинаковому результату, а некоторые — к другим результатам). Эти свойства — описаны математически: в «недетерминированной» модели вычислений, известной как «».
Разработка алгоритмов
В разработке алгоритмов — «недетерминированные» алгоритмы часто используются, когда задача, решаемая алгоритмом, — по своей сути, — позволяет найти много выходов (или — когда существует один выход со многими путями, через которые он может быть найден, и все «одинаково хороши»). Важно, что каждый выход «недетерминированного» алгоритма — верный; — независимо от путей, «выбранных» алгоритмом во время выполнения.
Примеры
«Список покупок»
Представим «список покупок»: список товаров для покупки — что можно осмыслить двумя способами: как указание купить все эти товары...
- ...в любом порядке («недетерминированный» алгоритм);
- ...в данном порядке («детерминированный» алгоритм).
«Сортировка слиянием»
Допустим, — имеется набор «сущностей» (скажем, — 300 студентов), который необходимо «упорядочить» (скажем, — по «номерам» студентов). Один из алгоритмов для этого — «сортировка слиянием»:
- Разделить набор на две приблизительно равные группы;
- Отсортировать обе группы данной сортировкой (т.е. «рекурсивно»);
- Объединить результаты («слить воедино»; см. название метода).
Элементы могут быть «уникально» отсортированы, если критерий сортировки всегда определяет «полный» порядок (т.е. «номера» студентов «уникальны»: не повторяются между собой). Но иначе (например, — если сортировать экзамены по фамилиям студентов без учёта однофамильцев) — результат сортировки не определён: неизвестно, какое именно упорядочение считать верным; — т.е. алгоритм «недетерминированный».
«Тест простоты»
Задача: дано натуральное число больше единицы; определить, является ли оно простым.
Решение: «недетерминированный» алгоритм — следующий:
- Взять любое целое «k» — такое, что 2 ≤ k ≤ √(n);
- Если «k» является делителем «n» — остановиться с ответом «нет»; иначе — остановиться с ответом «неизвестно».
Видно, что алгоритм не всегда даёт «полезный» ответ, но никогда не даёт неправильного ответа.
Этот алгоритм — «недетерминированный»: он не всегда выдаёт «полезное» решение — но может, при определённой комбинации выборов. Это — пример «поискового» типа «недетерминированного» алгоритма.
См. также
- (Конечный автомат)
- Недетерминированная машина Тьюринга
- Алгоритмы класса NP
- Побочный эффект (программирование)
- (Неоднозначная грамматика)
- (Вероятностный алгоритм)
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер