Algorithme déterministe - Deterministic algorithm

En informatique , un algorithme déterministe est un algorithme qui, étant donné une entrée particulière, produira toujours la même sortie, la machine sous-jacente passant toujours par la même séquence d'états. Les algorithmes déterministes sont de loin le type d'algorithme le plus étudié et le plus familier, ainsi que l'un des 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 dans son domaine , et l'algorithme est un processus qui produit cette valeur particulière en sortie.

Définition formelle

Les algorithmes déterministes peuvent être définis en termes de machine à états : un état décrit ce qu'une machine fait à un instant donné. Les machines à états passent de manière discrète d'un état à un autre. Juste après avoir entré l'entrée, la machine est dans son état initial ou état de démarrage . Si la machine est déterministe, cela signifie qu'à partir de ce point, son état actuel détermine quel sera son prochain état ; son parcours à travers l'ensemble des états est prédéterminé. Notez qu'une machine peut être déterministe et ne jamais s'arrêter ou finir, et donc ne pas fournir de résultat.

Des exemples de machines abstraites particulières qui sont déterministes incluent la machine de Turing déterministe et l' automate fini déterministe .

Qu'est-ce qui rend les algorithmes non déterministes ?

Une variété de facteurs peut amener un algorithme à se comporter d'une manière qui n'est pas déterministe ou non déterministe :

• S'il utilise un état externe autre que l'entrée, comme une entrée utilisateur, une variable globale , une valeur de minuterie matérielle, une valeur aléatoire ou des données de disque stockées.
• S'il fonctionne d'une manière sensible au temps, par exemple, s'il a plusieurs processeurs écrivant sur les mêmes données en même temps. Dans ce cas, l'ordre précis dans lequel chaque processeur écrit ses données affectera 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 ainsi que pour d'autres programmes de raisonner sur des programmes qui le sont. Pour cette raison, la plupart des langages de programmation et en particulier les langages de programmation fonctionnels s'efforcent d'empêcher les événements ci-dessus de se produire, sauf dans des conditions contrôlées.

La prévalence des processeurs multicœurs a entraîné un regain d'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 les défis ont été proposés pour faire face aux impasses et aux conditions de course .

Inconvénients du déterminisme

Il est avantageux, dans certains cas, qu'un programme présente un comportement non déterministe. Le comportement d'un programme de mélange de cartes utilisé dans un jeu de blackjack , par exemple, ne devrait pas être prévisible par les joueurs, même si le code source du programme est visible. L'utilisation d'un générateur de nombres pseudo-aléatoires n'est souvent pas suffisante pour garantir que les joueurs sont incapables de prédire le résultat d'un remaniement. Un joueur intelligent pourrait deviner avec précision les nombres que le générateur choisira et ainsi déterminer à l'avance le contenu entier du jeu, ce qui lui permettra de tricher ; par exemple, le Software Security Group de Reliable Software Technologies a pu le faire pour une implémentation du Texas Hold 'em Poker qui est distribué par ASF Software, Inc, leur permettant de prédire systématiquement le résultat des mains à l'avance. Ces problèmes peuvent être évités, en partie, grâce à l'utilisation d'un générateur de nombres pseudo-aléatoires sécurisé cryptographiquement , mais il est toujours nécessaire d'utiliser une graine aléatoire imprévisible pour initialiser le générateur. Pour cela, une source de non-déterminisme est requise, telle que celle fournie par un générateur de nombres aléatoires matériel .

Notez qu'une réponse négative au problème P=NP n'impliquerait pas que les programmes avec une sortie non déterministe sont théoriquement plus puissants que ceux avec une sortie déterministe. La classe de complexité NP (complexité) peut être définie sans aucune référence au non-déterminisme en utilisant la définition basée sur le vérificateur .

Catégories de déterminisme dans les langues

Mercure

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

Haskell

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 fail comme exception.
• les transformateurs de la monade Maybe et de la monade MaybeT permettent des calculs échoués (arrêtez la séquence de calcul et retournez Nothing)

déterminisme/non-dét avec des solutions multiples

vous pouvez récupérer tous les résultats possibles d'un calcul de résultats multiples, en enveloppant son type de résultat dans une monade MonadPlus . (sa méthode mzero fait échouer un résultat et mplus recueille les résultats réussis).

Famille ML et langages dérivés

Comme on le voit dans Standard ML , OCaml et Scala

• Le type d' option inclut la notion de réussite.

Java

• La valeur de référence nulle peut représenter un résultat infructueux (hors domaine).

Voir également

• Algorithme aléatoire

Les références