L'Art de la programmation informatique, Volume 1

1. Algorithmes : Les recettes précises du calcul

Le sens moderne du mot « algorithme » est très proche de celui de recette, procédé, méthode, technique, procédure, routine, voire de galimatias, mais il véhicule une nuance particulière.

Définition des algorithmes. Un algorithme est un ensemble fini de règles non ambiguës qui, lorsqu’elles sont suivies, fournissent une suite d’opérations permettant de résoudre un type précis de problème. Contrairement à une recette vague, un algorithme exige une rigueur absolue, garantissant qu’un ordinateur puisse exécuter chaque étape sans aucune ambiguïté. Le terme, issu du mathématicien perse du IXe siècle al-Khwārizmī, désignait à l’origine l’arithmétique avec les chiffres arabes avant d’évoluer vers sa signification informatique actuelle.

Cinq propriétés essentielles. Tout algorithme véritable doit posséder cinq caractéristiques fondamentales :

• Finitude : Il doit toujours s’arrêter après un nombre fini d’étapes.
• Définition précise : Chaque étape doit être spécifiée de manière claire et sans ambiguïté.
• Entrée : Il doit accepter zéro ou plusieurs quantités issues d’un ensemble donné.
• Sortie : Il doit produire une ou plusieurs quantités en relation spécifiée avec les entrées.
• Efficacité : Toutes les opérations doivent être suffisamment élémentaires pour être exécutées exactement en un temps fini, même manuellement.

Au-delà de la simple exactitude. Si la correction est primordiale, un « bon » algorithme prend aussi en compte l’efficacité, l’élégance et l’adaptabilité. L’analyse algorithmique, discipline centrale, quantifie ces qualités en évaluant des métriques telles que le temps d’exécution ou la mémoire utilisée. Cette étude rigoureuse aide les programmeurs à choisir la meilleure solution parmi plusieurs, transformant la programmation d’un simple artisanat en un art scientifique.

2. L’induction mathématique : la pierre angulaire de la preuve algorithmique

En définitive, toute propriété des entiers doit être démontrée par induction à un moment donné, car, au fond, les entiers sont essentiellement définis par induction.

Démontrer des vérités universelles. L’induction mathématique est une méthode puissante pour prouver qu’une propriété P(n) est vraie pour tous les entiers positifs n. Elle repose sur deux étapes : d’abord, prouver le cas de base (P(1) est vrai), puis montrer que si P(1) à P(n) sont vraies, alors P(n+1) l’est aussi. Cette méthode fournit une preuve concluante, et non simplement conjecturale, pour une infinité d’énoncés.

Au-delà de la supposition. Contrairement à l’induction scientifique, qui élabore des hypothèses à partir d’observations, l’induction mathématique offre une certitude absolue. C’est un raisonnement logique rigoureux, pas une « meilleure supposition ». Par exemple, démontrer que la somme des n premiers nombres impairs vaut n² ou établir des propriétés de la suite de Fibonacci repose sur ce principe fondamental. Son usage s’étend à la vérification de la correction des algorithmes, assurant qu’ils fonctionnent comme prévu pour toutes les entrées valides.

Formaliser la validité algorithmique. La validité d’un algorithme peut être démontrée rigoureusement en annotant son organigramme avec des assertions sur l’état du calcul à différents points. En prouvant que chaque opération transforme des assertions valides « avant » en assertions valides « après », et que l’algorithme se termine finalement, on établit sa correction. Cette approche inductive, initiée par R. W. Floyd, transforme la vérification algorithmique en un processus systématique, presque mécanique, où l’invention des bonnes assertions constitue l’étape véritablement créative.

3. Mathématiques fondamentales : l’outillage indispensable à l’analyse

Les techniques mathématiques utilisées dans l’analyse des algorithmes possèdent souvent une saveur particulière.

Au-delà de l’arithmétique élémentaire. L’analyse des algorithmes informatiques requiert un outillage mathématique spécialisé, dépassant l’algèbre et le calcul différentiel de base. Cette « saveur particulière » implique souvent de travailler avec des quantités discrètes, des sommes finies et des relations de récurrence, indispensables pour quantifier les performances d’un algorithme. La maîtrise de ces outils est essentielle pour tout programmeur sérieux.

Concepts mathématiques clés :

• Nombres : Entiers, rationnels, réels et complexes, avec leurs propriétés et représentations.
• Puissances et logarithmes : Essentiels pour exprimer les taux de croissance et les échelles, les logarithmes binaires (lg) et naturels (ln) étant particulièrement courants en informatique.
• Sommes et produits : La notation rigoureuse (∑, ∏) et les règles algébriques sont vitales pour simplifier des expressions complexes issues du comptage d’opérations.
• Fonctions entières : Partie entière (⌊x⌋), partie supérieure (⌈x⌉) et modulo (x mod y) sont fondamentaux pour les calculs discrets et la théorie des nombres.
• Théorie élémentaire des nombres : Concepts comme la divisibilité, la primalité relative et les congruences (ex. théorème de Fermat) sont indispensables pour les algorithmes cryptographiques et les fonctions de hachage.

L’art de la manipulation. Maîtriser ces notions permet de dériver élégamment des formules, souvent révélant des intuitions que de simples preuves inductives ne peuvent offrir. Cette habileté analytique donne aux programmeurs la capacité de comprendre pourquoi un algorithme fonctionne et comment il est efficace, au-delà de la simple observation de son comportement.

4. Fonctions génératrices : révéler les propriétés des suites

L’avantage d’une telle procédure est que G(z) est une quantité unique représentant toute la suite de Fibonacci d’un coup ; et si l’on découvre que G(z) est une fonction « connue », ses coefficients peuvent être déterminés.

Représenter les suites de façon compacte. Une fonction génératrice, G(z) = ∑ a_n z^n, est un outil mathématique puissant qui encode une suite infinie de nombres (a_0, a_1, a_2, ...) en une seule fonction. Cette transformation permet d’exprimer et de manipuler algébriquement des définitions inductives complexes ou des relations de récurrence, simplifiant souvent des problèmes autrement inaccessibles.

Manipulation algébrique pour l’intuition. Une fois la suite représentée par sa fonction génératrice, on peut appliquer des opérations algébriques et analytiques standard sur G(z) pour en déduire les propriétés de la suite initiale. Les techniques clés incluent :

• Addition : Combiner des suites.
• Décalage : Gérer les termes retardés dans les récurrences.
• Multiplication (convolution) : Analyser les sommes d’éléments de suites.
• Différentiation/intégration : Relier des suites comme a_n et n·a_n.
• Séries connues : Exploiter des développements en séries usuelles (binomiale, exponentielle, logarithmique) pour identifier et analyser des suites.

Résoudre récurrences et probabilités. Les fonctions génératrices sont particulièrement efficaces pour résoudre des relations de récurrence linéaires, telles que celles définissant les nombres de Fibonacci, donnant des expressions fermées élégantes comme la formule de Binet. Elles servent aussi de « fonctions génératrices de probabilités » en statistique, où leurs dérivées fournissent directement la moyenne et la variance d’une variable aléatoire, offrant des perspectives profondes sur le comportement des algorithmes sous hypothèses probabilistes.

5. Analyse asymptotique : quantifier l’efficacité pour les grands problèmes

La notation O est d’une grande aide pour les approximations, car elle décrit brièvement un concept fréquent et supprime des détails souvent sans importance.

Approcher à grande échelle. Lorsqu’on étudie des algorithmes, surtout pour de grandes entrées, les mesures exactes de performance importent moins que la compréhension de l’ordre de croissance. L’analyse asymptotique fournit des outils pour approximer ces quantités, permettant de comparer des algorithmes sans s’enliser dans des détails mineurs ou des constantes matérielles spécifiques. Cette approche se concentre sur la façon dont la performance évolue avec la taille des données.

La puissance de la notation O. La notation « grand O », O(f(n)), désigne une borne supérieure sur la grandeur d’une fonction, indiquant qu’une quantité est « inconnue précisément, mais pas trop grande ». Elle simplifie les expressions en abstrahant les facteurs constants et les termes de moindre ordre, permettant aux programmeurs de se focaliser sur les facteurs dominants influençant la performance. Par exemple :

• Un algorithme en O(n²) est généralement plus lent qu’un en O(n log n) pour de grandes valeurs de n.
• O(n) indique une croissance linéaire, O(log n) une croissance logarithmique.
• O(1) signifie un temps constant.

Au-delà des bornes supérieures. Si la notation O donne une borne supérieure, Big-Omega (Ω(f(n))) fournit une borne inférieure, et Big-Theta (Θ(f(n))) une croissance exacte. Ces notations sont essentielles pour classer rigoureusement l’efficacité des algorithmes. Par ailleurs, la formule de sommation d’Euler offre une méthode puissante pour approximer des sommes par des intégrales, fournissant des développements asymptotiques précis pour des quantités comme les nombres harmoniques (Hn ≈ ln n + γ) ou les factorielles (approximation de Stirling), reliant ainsi sommes discrètes et fonctions continues.

6. MIX : une machine universelle pour l’expression algorithmique

MIX est le premier ordinateur « polyinsaturé » au monde.

Une machine pédagogique. MIX, cet ordinateur « polyinsaturé », est une machine mythique conçue pour servir de modèle universel illustrant les concepts de programmation au niveau machine. Elle incarne les caractéristiques essentielles des ordinateurs des années 1960-1970, permettant d’exprimer des algorithmes dans un langage machine puissant mais simple. Cette conception rend les programmes MIX adaptables aux architectures binaires et décimales, mettant l’accent sur des principes informatiques intemporels plutôt que sur des spécificités matérielles éphémères.

Architecture et jeu d’instructions :

• Registres : Neuf registres (A, X, I1 à I6, J) pour l’arithmétique, la manipulation de données et l’indexation.
• Mémoire : 4000 mots, chacun composé de cinq octets et d’un signe.
• Instructions : Un ensemble riche d’opérations pour charger, stocker, calculer, transférer des adresses, comparer, sauter, gérer l’entrée/sortie et convertir des données.
• Champs partiels : Les instructions peuvent opérer sur des segments spécifiques d’octets dans un mot, offrant un contrôle fin.
• Temps d’exécution : Chaque opération a un temps assigné, permettant une analyse quantitative de l’efficacité des programmes.

MIXAL : le langage assembleur. MIXAL, langage symbolique d’assemblage de MIX, simplifie la programmation grâce à des codes mnémoniques et des adresses symboliques. Il inclut des pseudo-opérations (EQU, ORIG, CON) et des symboles locaux (ex. 2H, 2F) pour améliorer la lisibilité et gérer les détails administratifs. Bien que MIX soit aujourd’hui obsolète, son architecture et son langage d’assemblage restent précieux pour comprendre l’organisation fondamentale des ordinateurs et la mécanique basse-niveau de l’exécution algorithmique.

7. Sous-programmes et coroutines : modulariser les programmes complexes

Les sous-programmes sont des cas particuliers de composants plus généraux, appelés coroutines.

Structurer le code pour clarté et efficacité. Sous-programmes et coroutines sont des techniques fondamentales pour organiser des programmes complexes en modules gérables et réutilisables. Les sous-programmes, forme la plus courante, encapsulent une tâche spécifique, permettant d’exécuter un même code depuis plusieurs points sans répétition. Cela économise de la mémoire, simplifie le débogage et améliore la lisibilité.

Liaison et paramètres des sous-programmes :

• Liaison : Dans MIX, le registre J stocke l’adresse de retour, permettant de revenir au programme appelant.
• Paramètres (arguments) : Valeurs transmises au sous-programme pour personnaliser son comportement, souvent via registres ou mémoire.
• Compromis : Si l’espace mémoire est économisé, un léger surcoût temporel est induit par la liaison, et il peut être nécessaire de sauvegarder/restaurer des registres.

Coroutines : un flux de contrôle symétrique. Les coroutines représentent une relation plus générale et symétrique entre composants. Contrairement aux sous-programmes, qui démarrent toujours à un point fixe, les coroutines reprennent l’exécution là où elles s’étaient arrêtées. Ce traitement « quasi-parallèle » est idéal pour des scénarios producteur-consommateur, comme le chevauchement des entrées/sorties avec le calcul, ou pour implémenter des algorithmes multi-passes en un seul processus entrelacé. Les coroutines offrent des gains de temps significatifs en éliminant le stockage intermédiaire et les délais d’E/S inhérents aux approches séquentielles.

8. Structures d’information : organiser les données pour l’efficacité

Pour utiliser correctement un ordinateur, il faut comprendre les relations structurelles présentes dans les données, ainsi que les techniques de base pour représenter et manipuler ces structures en mémoire.

Les relations intrinsèques des données. Les programmes informatiques manipulent des données qui possèdent intrinsèquement des relations structurelles, bien au-delà de simples valeurs numériques. Comprendre ces structures — comment les éléments sont connectés, ordonnés ou groupés — est crucial pour concevoir des algorithmes efficaces et des logiciels performants. Cela implique de décider quelle part de cette structure doit être explicitement représentée en mémoire.

Concepts fondamentaux :

• Nœuds (enregistrements) : Unités de données de base, souvent composées de plusieurs champs.
• Champs : Parties nommées d’un nœud, contenant nombres, caractères ou liens.
• Liens (pointeurs) : Adresses mémoire reliant les nœuds, formant l’ossature des structures complexes.
• Lien nul (Λ) : Valeur spéciale indiquant l’absence de connexion, généralement zéro.
• Variables de lien : Pointeurs référant à des nœuds spécifiques ou au début d’une structure.

La fonction dicte la forme. Le choix de la représentation des données n’est pas arbitraire ; il dépend fortement des opérations les plus fréquentes sur ces données. Par exemple, une liste optimisée pour des insertions et suppressions rapides diffère d’une liste conçue pour un accès aléatoire rapide. Ce principe de « la fonction dicte la forme » est central dans la conception efficace des structures de données, garantissant que la représentation choisie correspond aux exigences computationnelles de l’application.

9. Listes linéaires : piles, files et deques pour données ordonnées

Une application informatique sollicite rarement l’ensemble des neuf opérations dans leur généralité complète, ce qui explique la diversité des représentations des listes linéaires selon les opérations les plus fréquentes.

Séquences ordonnées de données. Une liste linéaire est une structure fondamentale représentant une séquence de nœuds où la propriété principale est la position relative des éléments en ligne. Les opérations incluent accès, insertion, suppression, combinaison et division d’éléments. L’efficacité de ces opérations influence fortement le choix entre allocation séquentielle et chaînée.

Listes linéaires spécialisées :

• Pile (LIFO) : Dernier entré, premier sorti. Les éléments sont ajoutés (« empilés ») et retirés (« dépilés ») uniquement par un bout (« sommet »). Cruciale pour les algorithmes récursifs et le traitement des langages.
• File (FIFO) : Premier entré, premier sorti. Les éléments sont ajoutés à une extrémité (« arrière ») et retirés à l’autre (« avant »). Essentielle pour gérer des tâches dans l’ordre.
• Deque (file double) : Permet insertions et suppressions aux deux extrémités.

Stratégies d’allocation :

• Allocation séquentielle : Stocke les éléments dans des emplacements mémoire contigus. Efficace pour l’accès aléatoire, mais lente pour insertions/suppressions au milieu. Peut être optimisée pour plusieurs listes de taille variable en les faisant croître l’une vers l’autre, nécessitant parfois un « réarrangement » de la mémoire.
• Allocation chaînée : Chaque nœud contient un lien vers le suivant. Flexible pour insertions/suppressions n’importe où, mais plus lente pour l’accès aléatoire. Nécessite la gestion d’une liste d’espace disponible (pile AVAIL) pour les nouveaux nœuds. Les listes circulaires et doublement chaînées offrent une flexibilité supplémentaire pour certaines opérations.

10. Arbres : structures ramifiées pour données hiérarchiques

Les arbres existent bien sûr depuis le troisième jour de la création, et à travers les âges, les structures arborescentes (notamment les arbres généalogiques) ont été couramment utilisées.

Modéliser les relations hiérarchiques. Les arbres sont des structures de données non linéaires fondamentales qui modélisent des relations ramifiées ou hiérarchiques, à l’image des arbres naturels ou des généalogies. Définis récursivement, un arbre se compose d’une racine et de sous-arbres disjoints. Le vocabulaire clé comprend parent, enfant, frère, ancêtre, descendant et degré (nombre d’enfants).

Types et représentations :

• Arbres ordonnés : L’ordre des sous-arbres importe.
• Arbres orientés : L’ordre des sous-arbres n’a pas d’importance.
• Arbres binaires : Chaque nœud a au plus deux enfants (gauche et droite), pouvant être vides. Concept distinct d’un arbre général.
• Représentations :
  • Correspondance binaire : Tout arbre ou forêt général peut être représenté de manière unique par un arbre binaire (enfants gauches-frères droits), faisant des arbres binaires un outil central en informatique.
  • Séquentielle : Nœuds stockés selon des ordres spécifiques (préordre, postordre, niveau) pour des structures compactes et statiques.
  • Chaînée : Nœuds contenant des pointeurs (LLINK, RLINK, PARENT) définissant les relations.
  • Arbres filés : Les liens nuls sont remplacés par des « fils » vers d’autres parties de l’arbre, facilitant le parcours sans pile auxiliaire.

Parcours et applications. Parcourir un arbre signifie visiter chaque nœud une seule fois. Les ordres clés pour les arbres binaires sont préordre, infixe (symétrique) et postordre, chacun ayant des applications spécifiques. Les arbres sont indispensables pour représenter des formules algébriques, des systèmes de fichiers et des processus décisionnels, la longueur des chemins étant une mesure critique d’efficacité, souvent minimisée par des techniques comme l’algorithme de Huffman.

11. Structures multilinkées : données interconnectées pour problèmes complexes

La présence de plusieurs types de liens par nœud ne rend pas nécessairement les algorithmes plus difficiles à écrire ou à comprendre que ceux déjà étudiés.

Au-delà des hiérarchies simples. Les structures multilinkées étendent le concept des listes chaînées et des arbres en incorporant plusieurs types de liens dans chaque nœud. Cela permet à un même élément de données d’appartenir simultanément à plusieurs listes ou hiérarchies logiques différentes, représentant ainsi des relations très interconnectées et complexes. Par exemple, un nœud dans une simulation discrète peut appartenir à la fois à une liste « en attente » et à une liste « active », ou des éléments d’une matrice creuse peuvent être liés par lignes et colonnes.

Principes de conception :

• Champs de liens multiples : Chaque nœud contient plusieurs pointeurs (ex. PREV, PARENT, NAME, CHILD, SIB) pour faciliter divers modes d’accès.
• Compromis : Si la mémoire utilisée augmente, les temps de recherche pour certaines relations diminuent drastiquement, rendant les algorithmes beaucoup plus rapides.
• Redondance : Certains liens peuvent être logiquement redondants (dérivables d’autres), mais sont inclus pour améliorer les performances.
• Adaptation à l’application : L’ensemble exact des liens est adapté aux opérations spécifiques requises, comme le traitement des structures COBOL ou les opérations de pivot de matrice.

Gestion de la complexité. Malgré l’apparente complexité, les algorithmes pour structures multilinkées suivent souvent des schémas familiers de manipulation de listes et d’arbres. L’essentiel est de définir clairement le rôle de chaque lien et d’utiliser des diagrammes « avant-après » pour garantir la mise à jour correcte des pointeurs lors des insertions, suppressions ou transformations. Cette méthode permet une navigation et une manipulation efficaces de relations de données complexes sans difficulté algorithmique excessive.

12. Allocation dynamique de mémoire : gérer la mémoire pour données de taille variable

Le problème consiste à déterminer si les zones adjacentes au bloc libéré sont disponibles ; si oui, il faut mettre à jour correctement la liste AVAIL.

Gestion flexible de la mémoire. L’allocation dynamique de mémoire consiste à réserver et libérer des blocs de taille variable dans un grand espace mémoire, ou « tas », au cours de l’exécution d’un programme. Ceci est crucial pour les applications où les structures de données évoluent de manière imprévisible. Les principaux défis sont de trouver efficacement des blocs libres adaptés et de fusionner correctement les blocs libres adjacents (coalescence) pour éviter la fragmentation.

Stratégies clés d’allocation :

• First-Fit (premier adapté) : Alloue le premier bloc libre suffisamment grand. Simple et généralement efficace.
• Best-Fit (meilleur adapté) : Alloue le plus petit bloc libre qui convient. Peut générer plus de petits fragments inutilisables.
• Méthode des tags de frontière : Chaque bloc (libre ou réservé) contient des champs de taille et de tag à ses frontières. Cela permet une coalescence en temps constant des blocs libres adjacents lors de la libération.
• Système de buddies : Divise la mémoire en blocs dont la taille est une puissance de deux. Lorsqu’un bloc est nécessaire, un plus grand est divisé ; lors de la libération, les buddies se fusionnent. Efficace pour les ordinateurs binaires, mais peut gaspiller de l’espace si les tailles demandées ne sont pas des puissances de deux.

Récupération de mémoire :

• Libération explicite : Les blocs sont rendus à la liste d’espace disponible (liste AVAIL) dès qu’ils ne sont plus nécessaires, avec fusion des zones libres adjacentes.
• Ramassage des déchets (garbage collection) : La mémoire est récupérée uniquement lorsque l’espace vient à manquer. Une phase de « marquage » identifie tous les blocs accessibles, suivie d’une phase de « balayage » qui collecte les blocs non marqués (déchets). Cette méthode évite la libération explicite mais peut être lente en cas de mémoire presque saturée et nécessite une discipline stricte dans l’usage des pointeurs.
• Compactage : Déplacer tous les blocs réservés vers des emplacements contigus pour éliminer la fragmentation, souvent combiné avec le ramassage des déchets.

Performance et compromis. Le choix de la stratégie d’allocation implique des compromis entre utilisation mémoire, rapidité et complexité d’implémentation. Des simulations et analyses théoriques (comme la « règle des cinquante pour cent » pour first-fit/best-fit) aident à évaluer ces compromis, montrant qu’aucune méthode n’est universellement optimale pour toutes les applications.