Algorithme déterministe

En informatique , un algorithme déterministe est un algorithme qui, pour une entrée donnée, produit toujours la même sortie, la machine sous-jacente parcourant toujours la même séquence d'états. Les algorithmes déterministes sont de loin les plus étudiés et les plus connus, ainsi que parmi les plus pratiques, car ils peuvent être exécutés efficacement sur des machines réelles.

Formellement, un algorithme déterministe calcule une fonction mathématique ; une fonction a une valeur unique pour toute entrée de son domaine , et l'algorithme est un processus qui produit cette valeur particulière en sortie.

Les algorithmes déterministes peuvent être définis à l'aide d'une machine à états finis : un état décrit l'activité de la machine à un instant précis. Les machines à états finis passent d'un état à l'autre de manière discrète. Dès la saisie des données, la machine se trouve dans son état initial . Si la machine est déterministe, cela signifie qu'à partir de ce moment, son état actuel détermine son état suivant ; son parcours à travers l'ensemble des états est prédéterminé. Il est important de noter qu'une machine peut être déterministe sans pour autant s'arrêter ou se terminer, et donc ne jamais produire de résultat.

Parmi les exemples de machines abstraites déterministes, on peut citer la machine de Turing déterministe et l'automate fini déterministe .

Divers facteurs peuvent amener un algorithme à se comporter de manière non déterministe, voire non déterministe :

• S'il utilise un état externe autre que l'entrée, tel qu'une entrée utilisateur, une variable globale , une valeur de minuterie matérielle, une valeur aléatoire ou des données stockées sur disque.
• Si son fonctionnement est sensible au facteur temps, par exemple si plusieurs processeurs écrivent simultanément dans les mêmes données, l'ordre précis d'écriture de chaque processeur influencera le résultat.
• Si une erreur matérielle provoque un changement d'état inattendu.

Bien que les programmes réels soient rarement purement déterministes, il est plus facile pour les humains comme pour les autres programmes de raisonner sur ceux qui le sont. C'est pourquoi la plupart des langages de programmation , et notamment les langages de programmation fonctionnelle , s'efforcent d'empêcher que les événements mentionnés ci-dessus ne se produisent, sauf dans des conditions contrôlées.

La prévalence des processeurs multicœurs a entraîné une augmentation de l'intérêt pour le déterminisme dans la programmation parallèle et les défis du non-déterminisme ont été bien documentés. Un certain nombre d'outils pour aider à relever ces défis ont été proposés pour gérer les interblocages et les conditions de concurrence .

Il est parfois avantageux qu'un programme présente un comportement non déterministe. Le comportement d'un programme de mélange de cartes utilisé au blackjack , par exemple, ne doit pas être prévisible par les joueurs, même si le code source est accessible. L'utilisation d'un générateur de nombres pseudo-aléatoires est souvent insuffisante pour garantir l'impossibilité pour les joueurs de prédire le résultat d'un mélange. Un joueur astucieux pourrait deviner précisément les nombres que le générateur choisira et ainsi déterminer à l'avance la composition complète du jeu, ce qui lui permettrait de tricher. Par exemple, le groupe de sécurité logicielle de Reliable Software Technologies a réussi à le faire pour une implémentation du Texas Hold'em Poker distribuée par ASF Software, Inc., ce qui lui a permis de prédire systématiquement le résultat des mains. Ces problèmes peuvent être partiellement évités grâce à l'utilisation d'un générateur de nombres pseudo-aléatoires cryptographiquement sécurisé , mais il reste nécessaire d' utiliser une graine aléatoire imprévisible pour initialiser le générateur. À cette fin, une source de non-déterminisme est nécessaire, telle que celle fournie par un générateur de nombres aléatoires matériel .

Il convient de noter qu'une réponse négative au problème P=NP n'implique pas que les programmes à sortie non déterministe soient théoriquement plus puissants que ceux à sortie déterministe. La classe de complexité NP peut être définie sans aucune référence au non-déterminisme à l'aide de la définition basée sur les vérificateurs .

Le langage de programmation fonctionnelle logique Mercury établit différentes catégories de déterminisme pour les modes de prédicat, comme expliqué dans la référence.

Haskell propose plusieurs mécanismes :

• Non-déterminisme ou notion d'échec
  • Les types « Peut-être » et « Soit » incluent la notion de succès dans le résultat.
  • La méthode fail de la classe Monad peut être utilisée pour signaler un échec sous forme d'exception.
  • Le transformateur de monade Maybe et de monade MaybeT permet de gérer les calculs ayant échoué (arrêter la séquence de calcul et renvoyer Nothing)
• Néterminisme/non-déterminisme avec de multiples solutions
  • Vous pouvez récupérer tous les résultats possibles d'un calcul à résultats multiples en encapsulant son type de résultat dans une monade MonadPlus . (Sa méthode mzero fait échouer un résultat et mplus collecte les résultats réussis).

Comme on le voit dans Standard ML , OCaml et Scala

• Le type d'option inclut la notion de succès.

En Java , la valeur de référence nulle peut représenter un résultat infructueux (hors domaine).