Worldlex Wiki En informatique et en programmation informatique , un algorithme non déterministe est un algorithme qui, même pour la même entrée, peut présenter des comportements différents lors de différentes exécutions, par opposition à un algorithme déterministe .
Différents modèles de calcul donnent lieu à différentes raisons pour lesquelles un algorithme peut être non déterministe, et à différentes manières d'évaluer ses performances ou son exactitude :
- Un algorithme concurrent peut fonctionner différemment sur différentes exécutions en raison d'une condition de concurrence . Cela peut se produire même avec un algorithme monothread lorsqu'il interagit avec des ressources externes. En général, un tel algorithme est considéré comme fonctionnant correctement uniquement lorsque toutes les exécutions possibles produisent les résultats souhaités.
- Le comportement d' un algorithme probabiliste dépend d'un générateur de nombres aléatoires appelé par l'algorithme. Ceux-ci sont subdivisés en algorithmes de Las Vegas , pour lesquels (comme les algorithmes concurrents) toutes les exécutions doivent produire une sortie correcte, et algorithmes de Monte Carlo qui sont autorisés à échouer ou à produire des résultats incorrects avec une faible probabilité. Les performances d'un tel algorithme sont souvent mesurées de manière probabiliste, par exemple à l'aide d'une analyse de son temps attendu .
- En théorie de la complexité computationnelle , le non-déterminisme est souvent modélisé à l'aide d'un mécanisme explicite permettant de faire un choix non déterministe, comme dans une machine de Turing non déterministe . Pour ces modèles, un algorithme non déterministe est considéré comme fonctionnant correctement lorsque, pour chaque entrée, il existe une exécution qui produit le résultat souhaité, même lorsque d'autres exécutions produisent des résultats incorrects. Ce pouvoir existentiel rend les algorithmes non déterministes de ce type plus efficaces que les algorithmes déterministes connus pour de nombreux problèmes. Le problème P versus NP encapsule cette plus grande efficacité conjecturée dont disposent les algorithmes non déterministes. Les algorithmes de ce type sont utilisés pour définir des classes de complexité basées sur la complexité temporelle et spatiale non déterministe . Ils peuvent être simulés à l'aide de la programmation non déterministe , une méthode permettant de spécifier des algorithmes non déterministes et de rechercher les choix qui conduisent à une exécution correcte, souvent à l'aide d'une recherche de retour en arrière .
La notion de non-déterminisme a été introduite par Robert W. Floyd en 1967.
