L'algorithmique
Partie 3 sur 3
6Raisonner sur un algorithme
6.1La récursivitéApprofondir
Une fonction est récursive lorsqu’elle s’appelle elle-même, sur un problème plus petit. L’algorithme d’Euclide s’écrit ainsi très naturellement : le PGCD de a et b vaut a si b est nul, et sinon celui de b et de a mod b.
fonction PGCD(a, b)
si b = 0 alors renvoyer a // cas de base : la réponse est immédiate
sinon renvoyer PGCD(b, a mod b) // appel récursif sur un problème plus petit
fin fonction
Toute fonction récursive a besoin d’un cas de base, résolu sans nouvel appel, et chaque appel doit s’en rapprocher. Sans cela, la fonction s’appelle à l’infini. Chaque appel en attente occupe une place dans une zone de mémoire appelée la pile d’appels ; quand elle est pleine, le programme s’arrête sur une erreur de débordement de pile (stack overflow). Python limite par défaut la profondeur à 1 000 appels. La récursivité est l’outil naturel des méthodes « diviser pour régner », comme le tri fusion ou le tri rapide, et du parcours des structures arborescentes, comme les dossiers d’un disque.
6.2Prouver qu’un algorithme est justeApprofondir
Tester un algorithme sur des exemples montre qu’il marche sur ces exemples, pas qu’il marche toujours. Pour le prouver, on établit deux propriétés.
- La terminaison : l’algorithme s’arrête. On la démontre souvent avec une quantité entière positive qui diminue strictement à chaque tour. Dans l’algorithme d’Euclide, b diminue toujours, puisque le reste d’une division par b est plus petit que b ; un entier positif ne peut pas diminuer indéfiniment.
- La correction : le résultat est le bon. On utilise un invariant de boucle, une propriété vraie avant la boucle et préservée par chaque tour. Pour Euclide, l’invariant est « le PGCD de a et b ne change pas ». Quand la boucle s’arrête, b vaut 0, et le PGCD de a et 0 est a : le résultat est juste.
Pour la recherche dichotomique, l’invariant est : « si la valeur cherchée est dans la liste, elle se trouve entre les positions début et fin ». En 1844, le mathématicien français Gabriel Lamé a même démontré que l’algorithme d’Euclide demande au plus cinq fois plus d’étapes que le nombre de chiffres du plus petit nombre : un des premiers résultats de complexité de l’histoire. Ces raisonnements, longtemps réservés aux mathématiciens, sont aujourd’hui outillés : des logiciels de preuve formelle vérifient mécaniquement les programmes les plus critiques, ceux des métros automatiques ou de l’aéronautique.
Pour s’exercer
Exercice 4 : une récursivité qui ne s’arrête pas
On écrit : Factorielle(n) = n × Factorielle(n − 1), avec Factorielle(0) = 1. Que se passe-t-il si l’on appelle Factorielle(−1) ? Comment corriger ?
Voir la réponse
L’appel produit Factorielle(−2), puis Factorielle(−3), et ainsi de suite : le cas de base, 0, n’est jamais atteint. Le programme s’arrête sur un débordement de pile. Il faut vérifier l’entrée et refuser les nombres négatifs, par exemple en levant une exception. La terminaison n’est garantie que si chaque appel se rapproche réellement du cas de base.
Exercice 5 : prouver l’algorithme du maximum
Quel invariant de boucle permet de prouver que l’algorithme de la Figure 2 renvoie bien le plus grand élément ?
Voir la réponse
« max est le plus grand des éléments déjà examinés. » Il est vrai au départ, puisque max vaut le premier élément. Chaque tour le préserve : si le nouvel élément x est plus grand, max prend sa valeur ; sinon, max reste le plus grand. À la fin de la boucle, tous les éléments ont été examinés : max est donc le plus grand de la liste. La boucle se termine, car la liste est finie.
7De l’algorithme au programme
La réalisation d’un logiciel suit plusieurs étapes, qui s’enchaînent et se répètent.
- L’analyse : comprendre le problème, en cerner les limites, préciser les données d’entrée et le résultat attendu. Le résultat de l’analyse s’écrit dans un langage de description : c’est l’algorithme.
- La conception de l’algorithme : choisir une méthode, l’écrire en pseudo-code, vérifier sur des exemples qu’elle est juste, y compris dans les cas limites (liste vide, valeur absente, très grands nombres).
- La programmation : traduire l’algorithme dans un langage de programmation. Ce langage sert d’intermédiaire entre l’humain et la machine : assez proche de la machine pour être traduit sans ambiguïté, mais lisible par un humain. Il impose donc une syntaxe stricte.
- La compilation ou l’interprétation : un autre programme, le compilateur, transforme le code en langage machine, les instructions que le processeur sait exécuter ; un interpréteur les exécute au fur et à mesure (voir compilation et interprétation).
- L’édition de liens : un programme utilise presque toujours des éléments qu’il n’a pas écrits lui-même, rangés dans des bibliothèques (en anglais libraries, d’où le faux ami « librairies ») : affichage, calcul, accès au réseau. L’éditeur de liens relie le code compilé à ces éléments externes pour produire un programme exécutable. Les liens peuvent être faits une fois pour toutes (liaison statique) ou au lancement du programme (liaison dynamique, avec les fichiers
.dllde Windows ou.sode Linux). - Les tests et la maintenance : vérifier le comportement réel, corriger, faire évoluer.
Voici l’algorithme de recherche dichotomique traduit en Python. La structure est la même ; seuls les mots changent.
def recherche_dichotomique(liste, valeur):
debut, fin = 0, len(liste) - 1 # en Python, on numérote à partir de 0
while debut <= fin:
milieu = (debut + fin) // 2
if liste[milieu] == valeur:
return milieu
elif liste[milieu] < valeur:
debut = milieu + 1
else:
fin = milieu - 1
return None
On remarque que le calcul du milieu diffère du pseudo-code. En Python, les nombres entiers n’ont pas de limite de taille, et (debut + fin) // 2 ne pose aucun problème. Dans un langage où les entiers ont une taille fixe, cette addition peut déborder sur de très grandes listes : c’est l’objet d’une anecdote célèbre, racontée dans l’encart À côté.
8Écrire pour être lu : les règles de style
Un programme est lu bien plus souvent qu’il n’est écrit. On parle de maintenabilité pour désigner la facilité avec laquelle on peut le comprendre et le modifier après coup, et elle se joue dès l’écriture. Dès qu’un programme s’étoffe, il devient impossible de garder en tête tous ses détails : le programmeur qui se replonge dans son propre code après plusieurs mois a tout à réapprendre, comme s’il le découvrait. D’où l’importance de la forme : commenter, indenter, et surtout bien structurer, sans chercher à être trop astucieux.
Des programmeurs expérimentés ont résumé ces principes en maximes, qui valent dans tous les langages :
- être clair pour être rigoureux : soyez clair plutôt qu’astucieux, rigoureux avant d’optimiser, et restez simple pour optimiser ;
- écrire pour être lu : soignez la forme pour aider le lecteur, écrivez pour être lu de haut en bas, commentez le code sans le trahir, évitez l’excès de commentaires, donnez à chaque variable un nom parlant et une valeur initiale ;
- être méthodique : écrivez d’abord une version simple, décomposez-la en blocs, cantonnez chaque bloc à une seule tâche bien faite, rendez visibles les liens entre les blocs et indentez pour montrer la structure logique.
Pour la présentation elle-même, des normes de fait se sont imposées par l’expérience. Chacun garde ses préférences, et le style de présentation d’un débutant évolue avec la pratique ; mais dans une équipe, tout le monde doit suivre la même convention.
- Une seule instruction par ligne, et un retour à la ligne après une condition, sauf si l’instruction reste très courte.
- L’indentation : décaler vers la droite le contenu de chaque bloc, de quatre espaces le plus souvent. En Python, elle fait partie de la syntaxe ; dans les autres langages, elle n’est que visuelle, mais tout aussi indispensable.
- Les noms : ni trop courts ni trop longs. Pour le numéro de la couleur maximale d’un tableau,
NumeroDeLaCouleurMaximumest trop long,ntrop vague ;NumCouleurMaxest un bon compromis. Les majuscules aident à lire les noms composés :FindItem,MustExist(notation dite « en chameau », à cause des bosses) ; d’autres langages préfèrent les tirets bas, commerecherche_dichotomiqueen Python. - Les commentaires, à bon escient : ils expliquent pourquoi le code fait quelque chose, pas ce qu’il fait, que le code dit déjà. Un en-tête explicatif en début de fichier rappelle le projet, l’auteur et la version.
- La coloration syntaxique de l’éditeur, ou de l’environnement de développement, met en valeur les mots-clés, les commentaires et les chaînes de caractères ; ses couleurs se règlent selon ses goûts.
{ À éviter : deux instructions sur une ligne, structure invisible }
if not Updated then Update; I := IndexOf(Name);
{ Préférable : une instruction par ligne, blocs indentés }
function FindItem(const Name: string; MustExist: Boolean): TItem;
var
I: Integer;
begin
if not Updated then
Update;
I := IndexOf(Name);
if I >= 0 then
Result := Items[I]
else
begin
if MustExist then
raise EItemNotFound.Create(Name); { lever une exception }
Result := nil;
end;
end; { FindItem }
nil (« rien ») ou lève une exception selon le paramètre MustExist. Les mots begin et end délimitent les blocs ; rappeler le nom de la fonction après le dernier end aide à se repérer dans un long fichier.Pour s’exercer
Exercice 6 : doubler les données
Un traitement prend 1 seconde pour 100 000 données. Combien de temps prendra-t-il pour 200 000 données s’il est en O(log n), O(n), O(n log n) ou O(n2) ?
Voir la réponse
En O(log n), à peine plus : une seule étape de plus. En O(n), 2 secondes. En O(n log n), un peu plus de 2 secondes (environ 2,1). En O(n2), 4 secondes. Pour un million de données, l’écart devient énorme : 10 secondes en O(n), 100 en O(n2).
Exercice 7 : remettre en forme
Réécrivez lisiblement la ligne Pascal if not Updated then Update; I := IndexOf(Name); et expliquez le piège qu’elle cache.
Voir la réponse
Écrite sur une ligne, elle laisse croire que les deux instructions dépendent de la condition. En réalité, seule Update en dépend ; I := IndexOf(Name) s’exécute toujours. Une instruction par ligne, avec indentation, rend la structure évidente (voir la Figure 5). De nombreuses failles de sécurité sont nées de ce type de confusion entre ce que l’on croit lire et ce que la machine exécute.