Préface xi Avant-propos xv I Introduction à l'Algorithmique 1 1 Notion d'algorithme 3 1.1 Définition d'un algorithme 4 1.2 Notion de complexité 5 1.3 Machine abstraite 8 1.4 Langage algorithmique 9 1.5 Idée de preuve de programme 11 1.6 Preuve par récurrence 12 1.7 Principe de la preuve par invariant 13 2 Complexité algorithmique 17 2.1 Notation "O" 18 2.2 Exponentiation logarithmique 22 2.3 Arithmétique polynomiale élémentaire 24 2.3.1 Addition de polynômes 24 2.3.2 Multiplication de polynômes 25 2.3.3 Évaluation par puissances croissantes 26 2.3.4 Schéma de Horner 27 2.3.5 Lecture d'entier 28 2.3.6 Écriture d'entier 29 2.3.7 Évaluation simultanée en plusieurs points 29 2.4 Interpolation de polynômes 30 2.4.1 Interpolation de Lagrange 31 2.4.2 Interpolation de Newton 32 2.4.3 Algorithme de Neville 33 2.4.4 Interpolation d'Hermite 34 2.5 Multiplication efficace de polynômes 36 2.6 Problèmes en arithmétique des matrices 39 2.6.1 Addition de matrices 39 2.6.2 Multiplication de matrices 39 2.7 Sur la multiplication efficace de matrices 40 3 Le type ensemble de données 41 3.1 Type de données concret 41 3.2 Notion de type abstrait 41 3.3 Le type abstrait "ensemble de données" 43 3.3.1 Implémentation par tableau 44 3.3.2 Recherche d'un élément 46 3.3.3 Implémentation par tableau trié 47 3.3.4 Recherche d'un élément par dichotomie 48 L'algorithme récursif 48 Calcul de la complexité 49 3.4 Exemples d'algorithmes de tri d'ensembles 51 3.4.1 Calcul du minimum 52 3.4.2 Tri d'un ensemble 52 3.4.3 Tri par insertion 53 Recherche de la position d'insertion 53 Fonction d'insertion 54 Complexité de l'algorithme d'insertion 54 Algorithme de tri par insertion 55 Complexité du tri par insertion 55 3.4.4 Tri par sélection du minimum 56 Preuve de correction 56 Calcul de la complexité 57 3.4.5 Tri à bulles 57 Calcul des transpositions élémentaires 57 Algorithme et complexité 57 Amélioration de l'algorithme 57 3.5 Étude comparée des algorithmes de tri élémentaires 58 3.5.1 Tri par insertion 58 3.5.2 Tri par sélection du minimum 60 3.5.3 Tri à bulles 61 4 Structures linéaires 63 4.1 Chaînage explicite 64 4.1.1 Chaînage par curseur 64 4.1.2 Intérêt d'un chaînage explicite 65 4.1.3 Notion de pointeur 66 4.2 Liste chaînée par pointeurs 67 4.2.1 Représentation effective en mémoire 68 4.2.2 Insertion d'une cellule 69 4.2.3 Suppression d'une cellule 71 4.3 Structure de pile 72 4.3.1 Exemple du bon parenthésage 73 4.3.2 Récursivité et dérécursivation 74 4.3.3 Implémentation par tableau 76 4.3.4 Implémentation par liste chaînée 79 4.3.5 Codage par pile du tri par insertion 80 4.4 Structure de file 82 4.4.1 Implémentation par tableau 83 4.4.2 Implémentation par liste chaînée 84 4.4.3 Utilisation d'une liste chaînée circulaire 87 5 Structures d'arbre 89 5.1 Arbres et images noir et blanc 90 5.2 Codage de Huffman 92 5.2.1 Notion de code préfixe 93 5.2.2 Construction d'un code de Huffman 95 5.2.3 Principe général de codage d'un fichier 97 5.3 Terminologie de base 98 5.3.1 Notion d'arbre planaire 98 5.4 Parcours en profondeur 99 5.4.1 Parcours préfixe 99 5.4.2 Parcours suffixe 100 5.4.3 Parcours infixe 100 5.5 Parcours hiérarchique 101 5.6 Opérations usuelles 101 5.7 Arbres binaires 102 5.8 Représentation des arbres 104 5.8.1 Représentation par la fonction père 104 5.8.2 Binarisation et listes de liens fils 105 5.8.3 Table de liens fils 106 5.9 Algorithmes sur les arbres binaires 107 5.9.1 Parcours en profondeur d'arbres binaires 108 5.9.2 Parcours en largeur d'arbres binaires 111 5.10 Arbres binaires de recherche 113 5.10.1 Recherche d'un élément 114 5.10.2 Insertion d'un élément 116 5.10.3 Suppression d'un élément 117 5.10.4 Efficacité des algorithmes 118 II Programmation Impérative 119 6 Introduction au langage C 121 6.1 Structure de base d'un programme C et compilation 122 6.2 Préprocesseur et macro-instructions 126 6.2.1 Définition de constantes par substitution 126 6.2.2 Macro-instructions avec paramètres 127 6.2.3 Inclusion de fichier 128 6.3 Instructions et mots-clés 130 6.4 Variables et adresses 131 6.5 Définition d'une fonction 132 6.6 Fonctions d'entrées-sorties 135 6.6.1 Les fonctions getchar et putchar 135 6.6.2 Saisie formatée : la fonction scanf 137 6.6.3 Affichage formaté : la fonction printf 139 6.6.4 Les opérations d'entrée-sortie sur fichier 141 6.7 Les différents types d'instructions 144 6.7.1 Instructions construites à partir d'expressions 144 6.7.2 Instructions conditionnelles 144 Conditionnelle simple 144 Aiguillage 146 6.7.3 Instructions d'itération 148 La boucle for 148 La boucle while 149 La boucle do-while 149 6.7.4 Construction d'une instruction à partir d'un bloc 150 6.7.5 Instructions de rupture de séquence 151 6.8 Les différents types d'expressions 153 6.8.1 Principe d'évaluation d'une expression 153 6.8.2 Les caractères 153 6.8.3 Les nombres entiers 154 6.8.4 Les nombres réels 155 Le standard IEEE 156 6.8.5 La représentation des booléens 158 6.8.6 L'expression conditionnelle 159 6.8.7 Notion de séquence 160 6.9 Notion de compatibilité de types 160 6.9.1 La coercition 161 6.9.2 Le principe de conversion en affectation 161 6.9.3 Un type particulier : void 162 6.10 Les différents opérateurs 162 6.10.1 Les opérateurs arithmétiques 162 6.10.2 Les comparateurs 164 6.10.3 Les opérateurs logiques 164 6.10.4 Les opérateurs bit à bit 165 Complément bit à bit 165 Opérateurs de décalage bit à bit 165 Opérateurs logiques bit à bit 166 6.10.5 L'opérateur d'affectation 166 6.10.6 Priorité et associativité des opérateurs 167 6.10.7 Notion de taille en mémoire : l'opérateur sizeof 169 6.11 Déclarations des variables et fonctions 170 6.11.1 Déclaration, définition et initialisation 171 6.11.2 Variables globales et variables locales 171 6.11.3 Domaine de validité d'une déclaration 174 6.11.4 Domaine de validité des fonctions 176 6.12 Les tableaux et les chaînes de caractères 176 6.12.1 Les tableaux 176 6.12.2 Les chaînes de caractères 178 6.13 Les pointeurs 179 6.13.1 Arithmétique des pointeurs 180 6.14 Les types structurés et la définition de types 182 6.14.1 Les structures 182 6.14.2 Définition de type 183 6.14.3 Les unions 184 6.14.4 Les constantes énumérées 185 6.15 Arguments de la ligne de commande 186 6.16 Notion d'allocation dynamique de mémoire 187 7 Algorithmique : exercices en C 193 7.1 Concepts de base 193 7.2 Autour des fonctions 196 7.3 Un peu d'analyse lexicale 198 7.4 Calcul de la solution d'une équation f(x)=0 198 7.5 Pointeurs et tableaux 200 7.6 Calcul matriciel 202 7.7 Récursivité 203 7.8 Listes chaînées par pointeur 204 7.9 Listes chaînées triées 207 7.10 Arbres binaires de recherche 208 8 Codage de Huffman dynamique en langage C 211 8.1 Description générale du codage adaptatif 212 8.2 Structures de données utilisées 213 8.3 Les sources C du programme 213 8.4 Complexité de l'algorithme 222 8.5 Limitations de l'algorithme dynamique 222 9 Examens d'algorithmique et de langage C 223 9.1 Manipulation d'entiers et de flottants en langage C 223 9.2 Manipulation d'entiers, langage C, algorithmique 226 9.3 Tableaux, ensembles, complexité algorithmique 229 9.4 Vecteurs booléens, arithmétique et permutations 232 9.5 Algorithmique des tableaux et vecteurs booléens 233 III Programmation Fonctionnelle 237 10 Introduction au système Caml-Light 239 10.1 Premiers pas en Caml-Light 242 10.1.1 Expressions de type int 243 10.1.2 Expressions de type float 243 10.1.3 Expressions booléennes 244 10.1.4 Chaînes de caractères 245 10.1.5 Produits cartésiens 247 10.1.6 Le type unit 247 10.1.7 Les déclarations globales 247 10.1.8 Expressions fonctionnelles 249 10.1.9 Les fonctions de plusieurs arguments 253 10.1.10 Fonctions récursives 254 10.1.11 Les déclarations locales 255 10.1.12 Notions de typage et de polymorphisme 257 10.1.13 Les listes 259 10.1.14 La fonctionnelle map 261 10.1.15 Fonctionnelle d'itération sur les listes 262 10.1.16 Les vecteurs 265 10.2 Définition de types 267 10.2.1 Les types énumérés 268 10.2.2 Les types somme 268 10.2.3 Types récursifs 270 10.2.4 Type des arbres binaires 272 10.2.5 Syntaxe abstraite 274 10.2.6 Les enregistrements 275 10.3 Le point sur le filtrage 277 10.3.1 La construction as 277 10.3.2 Un motif particulier 278 10.3.3 La construction match 278 10.3.4 Déclaration locale et filtrage 278 10.3.5 Sur la linéarité des motifs 279 10.4 Le mécanisme d'exception 280 11 Exercices de contrôle en Caml-Light 283 11.1 Questions de typage 283 11.2 Autour des listes 286 11.3 Manipulation d'ensembles de données 288 11.4 Algorithmes de tri 289 11.5 Structures d'arbre 290 11.6 Arbres et expressions arithmétiques 291 11.7 Arbres à branchements finis 292 11.8 Sur les vecteurs 292 11.9 Pour les passionnés... 294 12 Examens de Caml-Light 297 12.1 Une histoire de mobile 297 12.2 Raisonnement par récurrence 300 12.3 Fonctionnelles d'itération, arbres binaires 303 13 Le mot de la fin 307 Les Annexes 313 A Correction des exercices en langage C 315 Concepts de base 315 Autour des fonctions 323 Un peu d'analyse lexicale 328 Calcul de la solution d'une équation f(x)=0 330 Pointeurs et tableaux 333 Calcul matriciel 338 Récursivité 343 Listes chaînées par pointeur 347 Listes chaînées triées 351 Arbres binaires de recherche 354 B Correction des sujets d'examen d'algorithmique et langage C 361 Manipulation d'entiers et de flottants en langage C 361 Manipulation d'entiers, langage C, algorithmique 365 Tableaux, ensembles, complexité algorithmique 369 Vecteurs booléens, arithmétique et permutations 372 Algorithmique des tableaux et vecteurs booléens 373 C Correction des exercices en Caml-Light 377 Questions de typage 377 Autour des listes 385 Manipulation d'ensembles de données 389 Algorithmes de tri 393 Structures d'arbre 397 Arbres et expressions arithmétiques 401 Arbres à branchements finis 405 Sur les vecteurs 406 Pour les passionnés... 409 D Correction des sujets d'examen en Caml-Light 415 Une histoire de mobile 415 Raisonnement par récurrence 419 Fonctionnelles d'itération, arbres binaires 422 E L'index 425 F Références bibliographiques 447 À propos d'algorithmique 448 À propos de programmation impérative 449 À propos de programmation fonctionnelle 450