Fiche de cours
Définitions et règles
Le mot dérive du nom du mathématicien persan Al-Khwarizmi (IXe siècle), le père de la numération telle qu’on la connaît aujourd’hui. Un algorithme est une suite finie et non ambigüe d’opérations ou d’instructions permettant de résoudre une classe de problème.
En 1962, Donal Knuth précise dans son ouvrage The Art of Computer Programming cinq règles importantes :
1 - Un algorithme doit toujours se terminer en un nombre fini d’étapes.
2 - Chaque étape d’un algorithme doit être définie précisément.
3 - Un algorithme a une entrée (quantités fournies avant son exécution).
4 - Un algorithme a une sortie (quantités obtenues après l’exécution, liées avec l’entrée).
5 - Les instructions doivent être simples, réalisables en principe avec un papier et un crayon.
Comment estimer le coût d’un algorithme ?