Définition - Que signifie l'algorithme non déterministe?
Un algorithme non déterministe peut fournir différentes sorties pour la même entrée sur différentes exécutions. Contrairement à un algorithme déterministe qui ne produit qu'une seule sortie pour la même entrée même sur des exécutions différentes, un algorithme non déterministe se déplace dans diverses routes pour arriver aux différents résultats.
Les algorithmes non déterministes sont utiles pour trouver des solutions approximatives, lorsqu'une solution exacte est difficile ou coûteuse à dériver à l'aide d'un algorithme déterministe.
Definir Tech explique l'algorithme non déterministe
Un exemple d'algorithme non déterministe est l'exécution d'algorithmes simultanés avec des conditions de course, qui peuvent présenter différentes sorties sur différentes exécutions. Contrairement à un algorithme déterministe qui parcourt un seul chemin de l'entrée à la sortie, un algorithme non déterministe peut emprunter plusieurs chemins, certains arrivant aux mêmes sorties et d'autres arrivant à des sorties différentes. Cette fonctionnalité est mathématiquement utilisée dans les modèles de calcul non déterministes comme l'automate fini non déterministe.
Un algorithme non déterministe est capable de s'exécuter sur un ordinateur déterministe qui possède un nombre illimité de processeurs parallèles. Un algorithme non déterministe comporte généralement deux phases et étapes de sortie. La première phase est la phase de devinettes, qui utilise des caractères arbitraires pour exécuter le problème.
La deuxième phase est la phase de vérification, qui renvoie vrai ou faux pour la chaîne choisie. Il existe de nombreux problèmes qui peuvent être conceptualisés à l'aide d'algorithmes non déterministes, y compris le problème non résolu de P vs NP dans la théorie informatique.
Des algorithmes non déterministes sont utilisés pour résoudre des problèmes qui permettent des résultats multiples. 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.