Algorithme déterministe
From Wikipedia, the free encyclopedia
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 .
