1. Définitions de base
1.1. Algorithme / Programme :
Le mot algorithme vient du mathématicien arabe du 9ème siècle Al Khou Warismi. Un algorithme est une suite finie et non ambiguë d'opérations visant la résolution d'un problème. On le formule généralement comme la transformation d'un ensemble de valeurs d'entrée en un ensemble de valeurs de sortie.
Un algorithme est dit totalement correct lorsque, pour chaque instance d'un problème, il se termine en produisant la bonne sortie. Il sera dit partiellement correct si, quand il se termine, il donne la bonne sortie, sans assurer qu'il se termine. Il sera approximatif s'il ne donne qu'une approximation de la solution (comme les algorithmes numériques).
Pour tout algorithme, on se pose finalement trois questions : sa correction, sa vitesse d'exécution et la possibilité de faire mieux.
Un programme implémente un algorithme. Tout traitement demandé à la machine, par l’utilisateur, est effectué par l’exécution séquencée d’opérations appelées instructions. Une suite d’instructions est appelée un programme.
Donc, un programme est une suite d’instructions, écrites dans un langage de compréhensible (directement ou indirectement) par un ordinateur, permettant à une
système informatique d’exécuter une tâche donnée.
1.2. Structure de données :
Une structure de données est une méthode de stockage et d'organisation des données pour en faciliter l'accès et la modification. Elle regroupe des données à gérer et un ensemble d'opérations qu'on peut leur appliquer. En général, il existe plusieurs manières de représenter ces données et plusieurs implémentations de leur manipulation.
L'interface sera définie dans un type de données abstrait (TDA). Il spécifie précisément la nature et les propriétés des données à stocker et les modalités des opérations.
1.3. Récursivité :
Un algorithme est dit récursif s'il s'invoque lui-même (directement ou non - récursif multiple). Cela permet de simplifier l'expression de certains algorithmes.
Une procédure sera récursive terminale si elle n'effectue plus aucune opération après s'être invoquée récursivement.