Algorithme non déterministe
Un algorithme non déterministe est un algorithme qui, même pour la même entrée, peut présenter différents comportements sur différentes exécutions, par opposition à un algorithme déterministe.
Il existe plusieurs façons pour lesquels un algorithme peut se comporter différemment. Ainsi, un algorithme concurrent peut fonctionner différemment sur différentes exécutions en raison d'une situation de compétiton. Le comportement d’un algorithme probabiliste de dépend d'un générateur de nombres aléatoires. Un algorithme qui résout un problème en temps polynomial non déterministe peut s'exécuter en temps polynomial ou en temps exponentiel, en fonction des choix qu'il effectue lors de l'exécution. Les algorithmes non déterministes sont souvent utilisés pour trouver une approximation d’une solution, alors que la solution exacte serait trop coûteuse à obtenir avec un déterministe.
