algorithmique

Pour trouver le plus grand nombre d'une liste, on peut regarder le premier, le comparer au suivant, puis garder le plus grand des deux. On répète ce geste jusqu'au dernier nombre. Cette suite d'étapes forme un algorithme : elle reçoit des données, applique des règles précises et produit un résultat. L'algorithmique étudie la manière de concevoir ces suites, de vérifier qu'elles donnent le bon résultat et d'estimer les ressources qu'elles consomment.

Elle ne se limite donc pas à programmer. Un même procédé peut être décrit avant d'être traduit dans un langage informatique, puis comparé à d'autres selon sa rapidité, sa mémoire nécessaire ou sa capacité à terminer.

L'algorithmique est l'étude des méthodes générales qui transforment des données d'entrée en un résultat au moyen d'une suite finie d'étapes définies. Elle porte sur la conception de cette suite, mais aussi sur sa correction, sa terminaison et sa complexité. La correction signifie que le résultat respecte le problème posé lorsque les données satisfont les hypothèses annoncées. La terminaison signifie que le procédé s'arrête après un nombre fini d'étapes.

Un algorithme s'applique à une classe de problèmes, et non à une seule valeur isolée. Ses entrées peuvent être des nombres, des textes, des graphes ou d'autres structures de données. Sa sortie dépend des entrées et des règles choisies. L'analyse de complexité évalue notamment le temps de calcul et la mémoire nécessaires quand la taille des données augmente. Une méthode efficace dépend donc du problème, des contraintes et de la représentation des données.

Deux algorithmes peuvent être corrects pour le même problème tout en ayant des coûts différents. L'algorithmique distingue ainsi la description abstraite d'une méthode, sa preuve de validité et son implémentation dans un programme particulier.

On cherche le maximum de la liste 7, 2, 9, 4. Le procédé parcourt chaque valeur une fois et conserve le meilleur candidat rencontré.

Données : la liste contient 4 nombres ; le candidat initial est 7 ; les valeurs examinées ensuite sont 2, 9 et 4.

Le premier candidat est 7.

On compare 2 à 7 : 2 est plus petit, donc le candidat reste 7.
On compare 9 à 7 : 9 est plus grand, donc le candidat devient 9.
On compare 4 à 9 : 4 est plus petit, donc le candidat reste 9.

Le résultat est donc le maximum 9. Le contrôle consiste à comparer 9 aux quatre valeurs : aucune n'est supérieure à 9. La liste a été parcourue une fois, avec trois comparaisons après l'initialisation.

Dans un programme, l'algorithmique sert à décrire les étapes avant de choisir une syntaxe et un langage. Le geste consiste à préciser les données reçues, le résultat attendu et les règles qui relient les deux.

Pour traiter une grande quantité de données, on compare plusieurs méthodes sur leur temps de calcul et leur mémoire. Une méthode plus simple peut être préférée si les données sont peu nombreuses ou si sa vérification est plus sûre.

Pour un problème nouveau, on commence par un cas test dont le résultat est connu. On examine ensuite les cas ordinaires et les cas limites avant de mesurer le comportement sur des entrées plus grandes.

L'algorithmique ne se confond pas avec la programmation. Un algorithme est une méthode abstraite, tandis qu'un programme est sa traduction dans un langage et un environnement précis. Deux programmes différents peuvent donc mettre en œuvre le même algorithme. Le critère qui tranche est la comparaison des étapes et des résultats, indépendamment de la syntaxe utilisée.

L'algorithmique ne se réduit pas non plus à la complexité. La complexité mesure certaines ressources consommées ; elle ne suffit pas à établir la correction ni la terminaison. Une méthode qui produit rapidement un mauvais résultat n'est pas un bon algorithme pour le problème considéré.

Une suite d'instructions n'est pas automatiquement un algorithme correct. Si une condition de départ manque, une entrée vide ou d'un type inattendu peut rendre le résultat indéfini. Il faut annoncer le domaine des données et prévoir le comportement correspondant.

Dans l'exemple du maximum, la liste doit contenir au moins une valeur pour que le premier candidat existe. Pour une liste vide, le procédé s'arrête avant l'initialisation et doit renvoyer un signal d'absence de résultat ou appliquer une convention explicitement choisie.

Une méthode peut aussi terminer tout en étant trop coûteuse pour la taille visée. Une mesure sur quatre valeurs ne permet pas de conclure sur une liste beaucoup plus grande : il faut examiner la croissance du nombre d'opérations et de la mémoire utilisée.

Pour prolonger l'étude, on peut comparer une recherche qui parcourt les données une à une avec une méthode qui exploite une organisation préalable. Le lecteur gagne un repère pour relier la représentation des données, la stratégie choisie et le coût du calcul, sans confondre rapidité et correction.