Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme déterministe
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.