Définitions

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.

Recevez des exclus !

Contenus liés

Abonnez-vous et recevez des infos en exclu

24pm academy
17 rue etex 75018 Paris
O6 62 55 OO 1O

Search