Algorithmes
Définition :
On appelle calcul une séquence d'opérations élémentaires qui est :
finie.
déterministe, i.e. à chaque étape la nouvelle opération à effectuer est entièrement déterminée par les précédentes).
réalisable (chaque opération élémentaire peut être réalisée en un temps fini).
complète (les informations requises pour une étape de l'algorithme proviennent uniquement des étapes précédentes.
La définition ci-dessus n'est pas très formelle, mais elle est suffisante pour cette première approche. Pour une définition formelle d'un calcul, il faut se ramener à un modèle de calcul plus formel tel celui de la machine de Turing.
Lorsqu'un calcul s'arrête en un temps fini et que le résultat final fournit la réponse au problème on dit alors que ce calcul est un algorithme.
Lorsqu'il s'arrête en un temps fini mais que l'on n'a pas réussi à démontrer que le résultat final est le bon, on dit alors que ce calcul est une heuristique.
On cite souvent l'exemple d'une recette de cuisine comme exemple d'algorithme primitif. Au regard des définitions précédentes une recette de cuisine est certainement un calcul, mais la preuve formelle de la validité du résultat est difficile (surtout quand je suis au fourneau !), et donc il faut les ranger dans la catégorie des heuristiques.
En résumé avant d'analyser un algorithme il faut d'abord vérifier sa preuve, i.e. qu'il s'arrête en un temps fini et que son résultat est le bon.