Детерминированный алгоритм


Детерминированный алгоритм

Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.

Содержание

Недетерминированный алгоритм

В информатике, недетерминированный алгоритм — это алгоритм, который указывает несколько путей обработки одних и тех же входных данных, без какого-либо уточнения, какой именно вариант будет выбран.

Использование

В теории алгоритмов под термином «алгоритм» обычно понимается детерминованый алгоритм. Недетерминированный алгоритм отличается от своего более известного двойника возможностью получения результата несколькими разными путями. Детерминированный алгоритм следует единственным путём от входных данных к выходным, тогда как некоторые пути выполнения недетерминированного алгоритма могут привести к одинаковому результату, а некоторые к другим результатам. Эти свойства описаны математически в «недетерминированной» модели вычислений известной как недетерминированный автомат.

В разработке алгоритмов, недетерминированные алгоритмы часто используются, когда задача, решаемая алгоритмом, по своей сути позволяет много выходов (или когда существует один выход с многими путями через которые он может быть найден, и все одинаково хороши). Важно, что каждый выход недетерминированного алгоритма верный, независимо от путей выбранных алгоритмом во время выполнения.

Примеры

Список покупок

Представим список покупок: список товаров для покупки.

Это можно осмыслить двумя способами:

  • Как указание купить все эти товары в любом порядке. Это недетерминированный алгоритм.
  • Как указание купить все эти товары в данном порядке. Это детерминированный алгоритм.

Сортировка слиянием

Допустим мы имеем набор сущностей (скажем, 300 студенческих экзаменов), которые необходимо отсортировать (скажем, по номерам студентов).

Один из алгоритмов для этого (называется Сортировка слиянием):

  • разбить набор на две приблизительно равные части
  • отсортировать обе половины сортировкой слиянием (т.е. рекурсивно)
  • слить результаты

Элементы могут быть уникально отсортированы, если критерий сортировки всегда определяет полный порядок; т.е. номера студентов уникальны, но если сортировать экзамены по фамилиям студентов и два студента имеют одинаковые фамилии, результат сортировки остаётся неопределённым. В таких случаях, сортировка слиянием всегда будет выдавать один из возможных упорядочиваний, но какое именно остаётся неизвестно, т.е. алгоритм недетерминированный .

Тест простоты

Задача: дано натуральное число больше единицы, определить является ли это число простым.

Недетерминированный алгоритм следующий:

  1. Взять любое целое k такое, что 2 ≤ k ≤ √(n).
  2. Если k является делителем n, остановится с ответом нет; иначе остановится с ответом не известно.

Видно, что алгоритм не всегда даёт полезный ответ, но никогда не даёт неправильного ответа.

Этот алгоритм недетерминированный, он не всегда выдаёт верное решение, но только при определённой комбинации выборов. Это пример поискового типа недетерминированного алгоритма.

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Детерминированный алгоритм" в других словарях:

  • Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов)  в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… …   Википедия

  • Алгоритм Полига — Хеллмана — Алгоритм Полига  Хеллмана (также называемый алгоритм Силвера  Полига  Хеллмана)  детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм… …   Википедия

  • Алгоритм Полига-Хеллмана — (также называемый алгоритм Силвера  Полига  Хеллмана)  детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным. Содержание 1 История… …   Википедия

  • Алгоритм Полига — Алгоритм Полига  Хеллмана (также называемый алгоритм Сильвера  Полига  Хеллмана)  детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностью алгоритма является то,… …   Википедия

  • алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… …   Исторический словарь галлицизмов русского языка

  • Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил …   Википедия

  • древовидный алгоритм — 05.02.59 древовидный алгоритм [ tree algorithm]: Детерминированный алгоритм, используемый устройством считывания/опроса, при котором после обнаружения коллизии сигналов радиочастотных меток осуществляется поиск по доступному пространству… …   Словарь-справочник терминов нормативно-технической документации

  • Вероятностный алгоритм — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.