Algorithme non déterministe - Nondeterministic algorithm

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 sur différentes exécutions, par opposition à un algorithme déterministe . Il existe plusieurs façons pour un algorithme de se comporter différemment d'une exécution à l'autre. Un algorithme simultané peut fonctionner différemment sur différentes exécutions en raison d'une condition de concurrence . Un algorithme probabiliste « s comportements 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 fait 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 en utilisant une solution déterministe.

La notion a été introduite par Robert W. Floyd en 1967.

Utilisation

Souvent, en théorie computationnelle , le terme «algorithme» fait référence à un algorithme déterministe . Un algorithme non déterministe est différent de son homologue déterministe plus familier dans sa capacité à arriver à des résultats en utilisant diverses voies. Si un algorithme déterministe représente un seul chemin entre une entrée et un résultat, un algorithme non déterministe représente un seul chemin aboutissant à de nombreux chemins, dont certains peuvent arriver à la même sortie et dont certains peuvent arriver à des sorties uniques. Cette propriété est capturée mathématiquement dans les modèles de calcul "non déterministes" tels que l' automate fini non déterministe . Dans certains scénarios, tous les chemins possibles sont autorisés à s'exécuter simultanément.

Dans la conception d'algorithmes, des algorithmes non déterministes sont souvent utilisés lorsque le problème résolu par l'algorithme autorise intrinsèquement plusieurs résultats (ou lorsqu'il existe un seul résultat avec plusieurs chemins par lesquels le résultat peut être découvert, chacun étant également préférable). Fondamentalement, chaque résultat produit par l'algorithme non déterministe est valide, quels que soient les choix effectués par l'algorithme lors de l'exécution.

Dans la théorie de la complexité computationnelle , les algorithmes non déterministes sont ceux qui, à chaque étape possible, peuvent permettre de multiples continuations (imaginez une personne marchant sur un chemin dans une forêt et, chaque fois qu'elle va plus loin, elle doit choisir la bifurcation qu'elle souhaite. prendre). Ces algorithmes n'arrivent pas à une solution pour chaque chemin de calcul possible; cependant, ils sont assurés d'arriver à une solution correcte pour un chemin (c'est-à-dire que la personne qui marche à travers la forêt peut seulement trouver sa cabane si elle choisit une combinaison de chemins «corrects»). Les choix peuvent être interprétés comme des suppositions dans un processus de recherche .

Un grand nombre de problèmes peuvent être conceptualisés grâce à des algorithmes non déterministes, y compris la question non résolue la plus célèbre de la théorie informatique, P vs NP .

Implémentation d'algorithmes non déterministes avec des algorithmes déterministes

Une façon de simuler un algorithme non déterministe N en utilisant un algorithme déterministe D est de traiter des ensembles d'états de N comme états de D . Cela signifie que D trace simultanément tous les chemins d'exécution possibles de N (voir la construction des ensembles de puissance pour cette technique utilisée pour les automates finis ).

Une autre est la randomisation , qui consiste à laisser tous les choix être déterminés par un générateur de nombres aléatoires . Le résultat est appelé un algorithme déterministe probabiliste .

Voir également

Les références

Lectures complémentaires