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. 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 . 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.