Algorithme déterministe

En Informatique, un algorithme déterministe est un algorithme qui, étant donné une entrée particulière, produira toujours la même sortie, avec la machine sous-jacente passant toujours par la même séquence d'états. Les algorithmes déterministes forment, de loin, la famille d'algorithme la plus étudiée.

Formellement, un algorithme déterministe calcule une fonction mathématique ; une fonction ayant une valeur unique pour n'importe quelle entrée dans son ensemble de définition, l'algorithme produit cette valeur en sortie.

Définition formelle

Un algorithme déterministe peut se définir comme un automate : un état décrivant ce que la machine fait à un moment particulier. Les automates déterministes passent d'un état à un autre de manière discrète et prédéterminée : l'état courant est complètement déterminé par l'état précédent. On notera qu'un tel automate peut être déterministe et ne jamais terminer son calcul.

Parmi les automates déterministes, on peut trouver la machine de Turing déterministe et l' automate fini déterministe .

Cause de non-déterminisme

Plusieurs facteurs peuvent être à l'origine du fonctionnement non déterministe d'un algorithme :

  •  S'il utilise un état externe différent de son entrée, tel qu'une entrée utilisateur, un minuteur matériel, une variable aléatoire ou des données externes.
  • S'il opère d'une manière sensible au temps, par exemple si plusieurs processeurs écrivent dans la même variable au même moment. Dans ce cas, l'ordre d'écriture affecte le résultat.
  • Si une erreur matérielle entraîne un changement d'état imprévisible.

Bien que les programmes réels soient rarement purement déterministes, il est plus facile pour des êtres humains -- ou d'autres programmes --, de raisonner sur des programmes qui le sont. Pour cette raison, la plupart des langages de programmation, et spécialement en programmation fonctionnelle, font l'effort d'empêcher les évènements ci-dessus, sauf en condition contrôlée.

La prévalence des microprocesseurs multi-cœur a entraîné un regain d'intérêt pour le déterminisme, ainsi que pour le non déterminisme, en programmation parallèle[1],[2]. Nombre d'outils ont notamment été proposés[3],[4],[5],[6] pour gérer les problèmes d'interblocage et de situation de compétition.

Désavantages du déterminisme

Il peut être avantageux pour un programme, dans certains cas, de montrer un comportement non-déterministe. Le comportement d'un programme de mélange de cartes pour le jeu du Blackjack, par exemple ne doit pas être prédictible par les joueurs -- même si le code source du programme est connu. L'utilisation d'un générateur de nombres pseudo-aléatoires n'est souvent pas suffisante pour s'assurer que les joueurs ne puissent prédire l'ordre des cartes.

Notes et références

  1. ↑ Edward A. Lee, « The Problem with Threads » (consulté le )
  2. ↑ Robert L. Bocchino Jr., Vikram S. Adve, Sarita V. Adve et Marc Snir « Parallel Programming Must Be Deterministic by Default » () (lire en ligne)
    —USENIX Workshop on Hot Topics in Parallelism
  3. ↑ « Intel Parallel Inspector Thread Checker » (consulté le )
  4. ↑ Yuan Lin, « Data Race and Deadlock Detection with Sun Studio Thread Analyzer » (consulté le )
  5. ↑ Intel, « Intel Parallel Inspector » (consulté le )
  6. ↑ David Worthington, « Intel addresses development life cycle with Parallel Studio » (consulté le )