1. 0 lim Page I Jeudi, 22. juin 2006 5:03 17 INTRODUCTION LALGORITHMIQUE Cours et exercices Thomas Cormen Professeur associ dinformatique au Darmouth College Charles Leiserson Professeur dinformatique au MIT Ronald Rivest Professeur dinformatique au MIT Clifford Stein Professeur associ au gnie industriel et de recherche oprationelle luniversit de Columbia Prface de Philippe chrtienne , Claire Hanen, Alix Munier, Christophe Picouleau 1re dition traduite de lamricain par Xavier Cazin Complments et mises jour de la 2e dition traduits par Georges-Louis Kocher 2e dition

2. 0 lim Page II Jeudi, 22. juin 2006 5:03 17 Ldition originale de ce livre a t publie aux tats-Unis par The MIT Press, Cambridge, Massachusetts, sous le titre Introduction to Algorithms, second edition. The Massachusetts Institute of Technology, 2001 First edition 1990 Ce pictogramme mrite une explication. Son objet est dalerter le lecteur sur la menace que reprsente pour lavenir de lcrit, particulirement dans le domaine de ldition technique et universitaire, le dveloppement massif du photocopillage. Le Code de la proprit intellectuelle du 1er juillet 1992 interdit en effet expressment la photocopie usage collectif sans autorisation des ayants droit. Or, cette pratique sest gnralise dans les tablissements denseignement suprieur, provoquant une baisse brutale des achats de livres et de revues, au point que la possibilit mme pour les auteurs de crer des uvres nouvelles et de les faire diter correctement est aujourdhui menace. Nous rappelons donc que toute reproduction, partielle ou totale, de la prsente publication est interdite sans autorisation du Centre franais dexploitation du droit de copie (CFC, 20 rue des GrandsAugustins, 75006 Paris). Dunod, Paris, 1994, pour la 1re dition Dunod, Paris, 2004, pour la prsente dition ISBN 2 10 003922 9 Toute reprsentation ou reproduction intgrale ou partielle faite sans le consentement de lauteur ou de ses ayants droit ou ayants cause est illicite selon le Code de la proprit intellectuelle (Art L 122-4) et constitue une contrefaon rprime par le Code pnal. Seules sont autorises (Art L 122-5) les copies ou reproductions strictement rserves lusage priv du copiste et non destines une utilisation collective, ainsi que les analyses et courtes citations justifies par le caractre critique, pdagogique ou dinformation de luvre laquelle elles sont incorpores, sous rserve, toutefois, du respect des dispositions des articles L 122-10 L 122-12 du mme Code, relatives la reproduction par reprographie.

3. Table des matires PRFACE LDITION FRANAISE PRFACE XVII XXI PARTIE 1 INTRODUCTION CHAPITRE 1 RLE DES ALGORITHMES EN INFORMATIQUE 3 1.1 Algorithmes Exercices 3 8 8 11 PROBLMES 11 CHAPITRE 2 PREMIERS PAS 13 2.1 Tri par insertion Exercices 13 18 2.2 Analyse des algorithmes Exercices c Dunod La photocopie non autorise est un dlit 1.2 Algorithmes en tant que technologie Exercices 19 25 2.3 Conception des algorithmes Exercices 25 34 PROBLMES 35 CHAPITRE 3 CROISSANCE DES FONCTIONS 39 3.1 Notation asymptotique Exercices 40 48 3.2 Notations standard et fonctions classiques Exercices 48 54 PROBLMES 55

4. IV Table des matires CHAPITRE 4 RCURRENCES 59 4.1 Mthode de substitution Exercices 60 64 4.2 Mthode de larbre rcursif Exercices 64 68 4.3 Mthode gnrale Exercices 69 71 4.4 Dmonstration du thorme gnral Exercices 72 80 PROBLMES 80 CHAPITRE 5 ANALYSE PROBABILISTE ET ALGORITHMES RANDOMISS 87 5.1 Le problme de lembauche Exercices 87 90 5.2 Variables indicatrices Exercices 91 94 5.3 Algorithmes randomiss Exercices 95 100 5.4 Analyse probabiliste et autres emplois des variables indicatrices Exercices 101 112 PROBLMES 113 PARTIE 2 TRI ET RANGS CHAPITRE 6 TRI PAR TAS 121 6.1 Tas Exercices 121 123 6.2 Conservation de la structure de tas Exercices 124 125 6.3 Construction dun tas Exercices 126 128 6.4 Algorithme du tri par tas Exercices 129 129 6.5 Files de priorit Exercices 131 134 PROBLMES 135

5. Table des matires V 139 7.1 Description du tri rapide Exercices 139 142 7.2 Performances du tri rapide Exercices 143 146 7.3 Versions randomises du tri rapide Exercices 147 148 7.4 Analyse du tri rapide Exercices 148 152 PROBLMES 153 CHAPITRE 8 TRI EN TEMPS LINAIRE 159 8.1 Minorants pour le tri Exercices 159 161 8.2 Tri par dnombrement Exercices 162 164 8.3 Tri par base Exercices 164 167 8.4 Tri par paquets Exercices 167 171 PROBLMES 171 CHAPITRE 9 MDIANS ET RANGS 177 9.1 Minimum et maximum Exercices 178 179 9.2 Slection en temps moyen linaire Exercices c Dunod La photocopie non autorise est un dlit CHAPITRE 7 TRI RAPIDE 179 183 9.3 Slection en temps linaire dans le cas le plus dfavorable Exercices 183 186 PROBLMES 187 PARTIE 3 STRUCTURES DE DONNES CHAPITRE 10 STRUCTURES DE DONNES LMENTAIRES 195 10.1 Piles et les Exercices 195 197

6. VI Table des matires 10.2 Listes chanes Exercices 199 203 10.3 Implmentation des pointeurs et des objets Exercices 203 207 10.4 Reprsentation des arborescences Exercices 208 209 PROBLMES 211 CHAPITRE 11 TABLES DE HACHAGE 215 11.1 Tables adressage direct Exercices 216 217 11.2 Tables de hachage Exercices 218 222 11.3 Fonctions de hachage Exercices 223 230 11.4 Adressage ouvert Exercices 231 238 11.5 Hachage parfait Exercices 238 242 PROBLMES 243 CHAPITRE 12 ARBRES BINAIRES DE RECHERCHE 247 12.1 Quest-ce quun arbre binaire de recherche ? Exercices 248 249 12.2 Requte dans un arbre binaire de recherche Exercices 250 253 12.3 Insertion et suppression Exercices 254 257 12.4 Arbres binaires de recherche construits alatoirement Exercices 258 261 PROBLMES 262 CHAPITRE 13 ARBRES ROUGE-NOIR 267 13.1 Proprits des arbres rouge-noir Exercices 267 270 13.2 Rotation Exercices 271 272

7. Table des matires VII 13.3 Insertion Exercices 273 280 13.4 Suppression Exercices 281 286 PROBLMES 287 CHAPITRE 14 EXTENSION DUNE STRUCTURE DE DONNES 295 14.1 Rangs dynamiques Exercices 296 300 14.2 Comment tendre une structure de donnes Exercices 301 303 14.3 Arbres dintervalles Exercices 304 309 PROBLMES 310 PARTIE 4 TECHNIQUES AVANCES DE CONCEPTION ET DANALYSE 315 15.1 Ordonnancement de chanes de montage Exercices 316 322 15.2 Multiplications matricielles enchanes Exercices 323 330 15.3 lments de la programmation dynamique Exercices 330 341 15.4 Plus longue sous-squence commune Exercices c Dunod La photocopie non autorise est un dlit CHAPITRE 15 PROGRAMMATION DYNAMIQUE 341 347 15.5 Arbres binaires de recherche optimaux Exercices 347 354 PROBLMES 354 CHAPITRE 16 ALGORITHMES GLOUTONS 361 16.1 Un problme de choix dactivits Exercices 362 370 16.2 lments de la stratgie gloutonne Exercices 370 375 16.3 Codages de Huffman Exercices 376 382

8. VIII Table des matires 16.4 Fondements thoriques des mthodes gloutonnes Exercices 383 388 16.5 Un problme dordonnancement de tches Exercices 389 392 PROBLMES 392 CHAPITRE 17 ANALYSE AMORTIE 395 17.1 Mthode de lagrgat Exercices 396 400 17.2 Mthode comptable Exercices 400 402 17.3 Mthode du potentiel Exercices 402 405 17.4 Tables dynamiques Exercices 406 414 PROBLMES 415 PARTIE 5 STRUCTURES DE DONNES AVANCES CHAPITRE 18 B-ARBRES 425 18.1 Dnition dun B-arbre Exercices 429 431 18.2 Oprations fondamentales sur les B-arbres Exercices 432 437 18.3 Suppression dune cl dans un B-arbre Exercices 439 442 PROBLMES 442 CHAPITRE 19 TAS BINOMIAUX 445 19.1 Arbres binomiaux et tas binomiaux Exercices 447 450 19.2 Oprations sur les tas binomiaux Exercices 451 461 PROBLMES 462

9. Table des matires IX CHAPITRE 20 TAS DE FIBONACCI 465 20.1 Structure des tas de Fibonacci 466 20.2 Oprations sur les tas fusionnables Exercices 469 477 20.3 Diminution dune cl et suppression dun nud Exercices 478 481 20.4 Borne pour le degr maximal Exercices 482 484 PROBLMES 484 CHAPITRE 21 STRUCTURES DE DONNES POUR ENSEMBLES DISJOINTS 487 21.1 Oprations sur les ensembles disjoints Exercices 487 490 21.2 Reprsentation densembles disjoints par des listes chanes Exercices 490 493 21.3 Forts densembles disjoints Exercices 494 497 21.4 Analyse de lunion par rang avec compression de chemin Exercices 498 505 PROBLMES 506 PARTIE 6 ALGORITHMES POUR LES GRAPHES 513 22.1 Reprsentation des graphes Exercices c Dunod La photocopie non autorise est un dlit CHAPITRE 22 ALGORITHMES LMENTAIRES POUR LES GRAPHES 514 516 22.2 Parcours en largeur Exercices 517 524 22.3 Parcours en profondeur Exercices 525 532 22.4 Tri topologique Exercices 534 536 22.5 Composantes fortement connexes Exercices 536 541 PROBLMES 542

10. X Table des matires CHAPITRE 23 ARBRES COUVRANTS DE POIDS MINIMUM 545 23.1 Construction dun arbre couvrant minimum Exercices 546 550 23.2 Algorithmes de Kruskal et de Prim Exercices 551 556 PROBLMES 558 CHAPITRE 24 PLUS COURTS CHEMINS ORIGINE UNIQUE 563 24.1 Algorithme de Bellman-Ford Exercices 571 574 24.2 Plus courts chemins origine unique dans les graphes orients sans circuit Exercices 575 577 24.3 Algorithme de Dijkstra Exercices 577 582 24.4 Contraintes de potentiel et plus courts chemins Exercices 583 587 24.5 Dmonstrations des proprits de plus court chemin Exercices 589 594 PROBLMES 595 CHAPITRE 25 PLUS COURTS CHEMINS POUR TOUT COUPLE DE SOMMETS 601 25.1 Plus courts chemins et multiplication de matrices Exercices 603 608 25.2 Lalgorithme de Floyd-Warshall Exercices 609 614 25.3 Algorithme de Johnson pour les graphes peu denses Exercices 616 620 PROBLMES 621 CHAPITRE 26 FLOT MAXIMUM 625 26.1 Rseaux de transport Exercices 626 631 26.2 La mthode de Ford-Fulkerson Exercices 632 643 26.3 Couplage maximum dans un graphe biparti Exercices 644 648 26.4 Algorithmes de prots Exercices 649 658

11. Table des matires XI 26.5 Algorithme rtiqueter-vers-lavant Exercices 659 669 PROBLMES 669 PARTIE 7 MORCEAUX CHOISIS 681 27.1 Rseaux de comparaison Exercices 682 685 27.2 Le principe du zro-un Exercices 686 688 27.3 Un rseau de tri bitonique Exercices 689 690 27.4 Un rseau de fusion Exercices 692 693 27.5 Un rseau de tri Exercices 694 696 PROBLMES 697 CHAPITRE 28 CALCUL MATRICIEL 701 28.1 Proprits des matrices Exercices 702 709 28.2 Algorithme de Strassen pour la multiplication des matrices Exercices 710 716 28.3 Rsolution de systmes dquations linaires Exercices c Dunod La photocopie non autorise est un dlit CHAPITRE 27 RSEAUX DE TRI 717 730 28.4 Inversion des matrices Exercices 730 734 28.5 Matrices symtriques dnies positives et approximation des moindres carrs Exercices 735 740 PROBLMES 741 CHAPITRE 29 PROGRAMMATION LINAIRE 745 29.1 Forme canonique et forme standard Exercices 752 759 29.2 Formulation de problmes comme programmes linaires Exercices 760 764

12. XII Table des matires 29.3 Algorithme du simplexe Exercices 765 778 29.4 Dualit Exercices 779 784 29.5 Solution de base ralisable initiale Exercices 785 790 PROBLMES 791 CHAPITRE 30 POLYNMES ET TRANSFORME RAPIDE DE FOURIER 795 30.1 Reprsentation des polynmes Exercices 797 802 30.2 Transforme discrte de Fourier et transforme rapide de Fourier Exercices 803 810 30.3 Implmentations efcaces de la FFT Exercices 811 816 PROBLMES 816 CHAPITRE 31 ALGORITHMES DE LA THORIE DES NOMBRES 821 31.1 Notions de thorie des nombres Exercices 823 827 31.2 Plus grand commun diviseur Exercices 828 832 31.3 Arithmtique modulaire Exercices 833 839 31.4 Rsolution dquations linaires modulaires Exercices 839 842 31.5 Thorme du reste chinois Exercices 843 845 31.6 Puissances dun lment Exercices 846 850 31.7 Le cryptosystme cls publiques RSA Exercices 850 856 31.8 Test de primarit Exercices 856 865 31.9 Factorisation des entiers Exercices 865 870 PROBLMES 870

13. XIII CHAPITRE 32 RECHERCHE DE CHANES DE CARACTRES 875 32.1 Algorithme naf de recherche de chane de caractres Exercices 878 879 32.2 Algorithme de Rabin-Karp Exercices 880 884 32.3 Recherche de chane de caractres au moyen dautomates nis Exercices 885 891 32.4 Algorithme de Knuth-Morris-Pratt Exercices 891 898 PROBLMES 899 CHAPITRE 33 GOMTRIE ALGORITHMIQUE 901 33.1 Proprits des segments de droite Exercices 902 907 33.2 Dterminer si deux segments donns se coupent Exercices 908 914 33.3 Recherche de lenveloppe convexe Exercices 915 924 33.4 Recherche des deux points les plus rapprochs Exercices 925 929 PROBLMES 930 CHAPITRE 34 NP-COMPLTUDE 933 34.1 Temps polynomial Exercices c Dunod La photocopie non autorise est un dlit Table des matires 939 945 34.2 Vrication en temps polynomial Exercices 946 950 34.3 NP-compltude et rductibilit Exercices 951 960 34.4 Preuves de NP-compltude Exercices 961 968 34.5 Problmes NP-complets Exercices 969 982 PROBLMES 983

14. XIV Table des matires CHAPITRE 35 ALGORITHMES DAPPROXIMATION 987 35.1 Problme de la couverture de sommets Exercices 989 992 35.2 Problme du voyageur de commerce Exercices 992 997 35.3 Problme de la couverture densemble Exercices 997 1002 35.4 Randomisation et programmation linaire Exercices 1002 1007 35.5 Problme de la somme de sous-ensemble Exercices 1007 1012 PROBLMES 1013 PARTIE 8 ANNEXES : LMENTS DE MATHMATIQUES ANNEXE A SOMMATIONS 1021 A.1 Formules et proprits des sommations Exercices 1022 1025 A.2 Bornes des sommations Exercices 1025 1031 PROBLMES 1031 ANNEXE B ENSEMBLES, ETC. 1033 B.1 Ensembles Exercices 1033 1037 B.2 Relations Exercices 1038 1040 B.3 Fonctions Exercices 1040 1042 B.4 Graphes Exercices 1043 1046 B.5 Arbres Exercices 1047 1053 PROBLMES 1054

15. Table des matires XV 1057 C.1 Dnombrement Exercices 1057 1061 C.2 Probabilits Exercices 1063 1068 C.3 Variables alatoires discrtes Exercices 1069 1073 C.4 Distributions gomtrique et binomiale Exercices 1074 1078 C.5 Queues de la distribution binomiale Exercices 1079 1084 PROBLMES 1085 BIBLIOGRAPHIE 1087 INDEX c Dunod La photocopie non autorise est un dlit ANNEXE C DNOMBREMENT ET PROBABILITS 1109

16. c Dunod La photocopie non autorise est un dlit Prface ldition franaise Vous savez compter. Un ordinateur aussi ! Mais connaissez-vous les mcanismes utiliss ? Etes-vous vraiment sr que le rsultat afch soit juste ? Combien de temps devrez-vous attendre la n du calcul ? Ny a-t-il pas un moyen de lobtenir plus vite ? Que vous soyez ingnieur, mathmaticien, physicien, statisticien et surtout informaticien, toutes ces questions vous vous les posez. Si vous tes tudiant, elles surgiront trs rapidement. tudier lalgorithmique, cest apporter des rponses vos questions. Cette science est le cur de linformatique. Pour tout ceux qui doivent ou devront faire travailler un ordinateur, il est essentiel de comprendre ses principes fondamentaux et de connatre ses lments de base. Une formule 1 ne se conduit pas comme une voiture pdales. De mme un ordinateur se sutilise pas comme un boulier. Lalgorithmique est le permis de conduire de linformatique. Sans elle, il nest pas concevable dexploiter sans risque un ordinateur. Cette introduction remarquable lalgorithmique donne au lecteur dune part les bases thoriques indispensables et lui fournit dautre part les moyens de concevoir rigoureusement des programmes efcaces permettant de rsoudre des problmes varis issus de diffrentes applications. Lventail des algorithmes prsents va des plus classiques, comme les algorithmes de tri et les fonctions de hachage, aux plus rcents comme ceux de la cryptographie. On trouve ici rassembls des algorithmes numriques, par exemple pour linversion de matrices ou la transforme de Fourier et des algorithmes combinatoires comme les algorithmes de graphes ou la recherche de motif. Une trs large place est faite aux structures de donnes, des plus simples comme les listes, aux plus sophistiques comme les tas de Fibonacci. Notons au passage limportance accorde aux diffrentes mesures de complexit (pire des cas, amortissement, en moyenne) qui permettent dapprofondir entre autres ltude de lefcacit des algorithmes de tri et des structures de donnes.

17. XVIII Prface ldition franaise Il est certain que la plupart des informaticiens spcialiss trouveront dans ce livre leurs algorithmes de base, exprims de faon unie, ainsi que certaines avances rcentes dans leur domaine. Cet ouvrage met donc en relief le rle central jou par lalgorithmique dans la science Informatique. La prsence de chapitres mthodologiques comme ceux consacrs la programmation dynamique et aux algorithmes gloutons, ainsi que les deux derniers qui traitent de la complexit des problmes et de la conception dalgorithmes approchs, permet au lecteur damorcer une rexion plus pousse sur la manire daborder un problme et de concevoir une mthode de rsolution. Ces chapitres sont illustrs par des exemples dapplication bien choisis et l encore trs divers. Cette gamme de sujets, riche par sa varit et ses niveaux de difcult, est soutenue par une pdagogie constante, qui rend la lecture de louvrage facile et agrable, sans nuire lexigence de rigueur. A titre dexemple, on peut citer la clart remarquable des chapitres consacrs aux graphes, qui, partir dun algorithme gnrique, introduisent toute une famille de variantes efcaces dont les diffrentes implmentations sont analyses avec nesse. Dune manire gnrale, les notions prsentes sont systmatiquement introduites de faon informelle partir dun exemple ou dune application particulire, avant dtre formalises. Les proprits et les algorithmes sont toujours dmontrs. La prsence dune partie consacre aux fondements mathmatiques utiliss est tout fait bienvenue et rend louvrage accessible avec trs peu de prrequis. Le lecteur peut facilement se familiariser et approfondir les notions rencontres grce aux nombreux exercices de difcult gradue. Les problmes permettent daller plus loin dans la comprhension du chapitre, et sont souvent une occasion de connatre diffrentes applications pratiques des algorithmes prsents. De ce point de vue, ce livre est une mine dor pour tout enseignant dalgorithmique. La lecture de cet ouvrage est tout fait recommande aux tudiants de second et de troisime cycle dinformatique et de mathmatiques, ainsi quaux lves ingnieurs. Tous y trouveront une aide et un support de cours utile tout au long de leurs tudes. La diversit des sujets abords, lefcacit des algorithmes prsents, et leur criture dans un pseudo-code proche des langages C et Pascal, qui les rend trs faciles implmenter, font aussi de ce livre un recueil fort utile dans la vie professionelle dun informaticien ou dun ingnieur. Enn, au del de ses besoins propres, nous souhaitons que le lecteur, quil soit ingnieur, tudiant, ou simplement curieux, prenne comme nous plaisir et intrt la lecture de cet ouvrage. Paris, mars 1994 P HILIPPE C HRTIENNE, C LAIRE H ANEN, A LIX M UNIER, C HRISTOPHE P ICOULEAU Universit Pierre et Marie Curie (LIP6)

18. Prface ldition franaise XIX propos de la seconde dition : Cest avec une curiosit renouvele que lenseignant, le chercheur ou ltudiant abordera cette seconde dition du livre de rfrence de lalgorithmique. Lalgorithmicien dj familier de la prcdente dition y trouvera, parmi moult enrichissements dissmins tout le long de louvrage, de nouvelles parties, notamment celle ddie la programmation linaire, de nombreux exercices et problmes indits, ainsi quune prsentation uniformise des preuves dalgorithmes ; le lecteur, tudiant ou enseignant, qui dcouvre cette Introduction lalgorithmique, y trouvera sous un formalisme des plus limpides, le ncessaire, voire un peu plus, de cette discipline qui est lune des pierres angulaires de linformatique. c Dunod La photocopie non autorise est un dlit Paris, aot 2002 C HRISTOPHE P ICOULEAU, Laboratoire CEDRIC CNAM

19. c Dunod La photocopie non autorise est un dlit Prface Nous proposons dans ce livre une introduction complte ltude contemporaine des algorithmes informatiques. De nombreux algorithmes y sont prsents et tudis en dtail, de faon rendre leur conception et leur analyse accessibles tous les niveaux de lecture. Nous avons essay de maintenir la simplicit des explications, sans sacrier ni la profondeur de ltude, ni la rigueur mathmatique. Chaque chapitre prsente un algorithme, une technique de conception, un domaine dapplication, ou un sujet sy rapportant. Les algorithmes sont dcrits en franais et dans un pseudo-code conu pour tre lisible par quiconque ayant dj un peu programm. Le livre contient plus de 230 gures qui illustrent le fonctionnement des algorithmes. Comme nous mettons laccent sur lefcacit comme critre de conception, les temps dexcution de tous nos algorithmes sont soigneusement analyss. Ce texte est en premier lieu un support du cours dalgorithmique ou de structures de donnes de deuxime ou troisime cycle universitaire. Il est galement bien adapt la formation personnelle des techniciens professionnels, puisquil sintresse aux problmes dingnierie ayant trait la conception dalgorithmes, ainsi qu leurs aspects mathmatiques. Dans cette dition, qui est la seconde, nous avons modi lensemble du livre. Les changements vont de la simple refonte de phrases individuelles jusqu lajout de nouveaux chapitres. a) Pour lenseignant Ce livre se veut la fois complet et polyvalent. Il se rvlera utile pour toute sorte de cours, depuis un cours de structures de donnes en deuxime cycle jusqu un cours

20. XXII Prface dalgorithmique en troisime cycle. Un cours trimestriel tant beaucoup trop court pour aborder tous les sujets tudis ici, on peut voir ce livre comme un buffet garni o vous pourrez choisir le matriel le mieux adapt aux cours que vous souhaitez enseigner. Vous trouverez commode dorganiser votre cours autour des chapitres dont vous avez vraiment besoin. Nous avons fait en sorte que les chapitres soient relativement indpendants, de manire viter toute subordination inattendue ou superue dun chapitre lautre. Chaque chapitre commence en prsentant des notions simples et se poursuit avec les notions plus difciles, le dcoupage en sections crant des points de passage naturels. Dans un cours de deuxime cycle, on pourra ne faire appel quaux premires sections dun chapitre donn ; en troisime cycle, on pourra considrer le chapitre entier. Nous avons inclus plus de 920 exercices et plus de 140 problmes. Chaque section se termine par des exercices et chaque chapitre se termine par des problmes. Les exercices sont gnralement des questions courtes de contrle des connaissances. Certains servent surtout tester la comprhension du sujet ; dautres, plus substantiels, sont plutt du genre devoir la maison. Les problmes sont des tudes de cas plus labores qui introduisent souvent de nouvelles notions ; ils sont composs le plus souvent de plusieurs questions qui guident ltudiant travers les tapes ncessaires pour parvenir une solution. Les sections et exercices munis dune astrisque ( ) recouvrent des thmes destins plutt aux tudiants de troisime cycle. Un passage toil nest pas forcment plus ardu quun passage non toil, mais il risque dexiger des connaissances mathmatiques plus pointues. De mme, un exercice toil risque de demander un niveau thorique plus important ou dincorporer des subtilits au-dessus de la moyenne. b) Pour ltudiant Nous esprons que ce livre vous fournira une introduction agrable lalgorithmique. Nous avons essay de rendre chaque algorithme accessible et intressant. Pour vous aider lorsque vous rencontrez des algorithmes peu familiers ou difciles, nous les avons tous dcrits tape par tape. Nous expliquons aussi avec soin les notions mathmatiques ncessaires pour comprendre lanalyse des algorithmes. Si vous tes dj familiaris avec un sujet, vous constaterez que lorganisation des chapitres vous permet de sauter les sections dintroduction et daller rapidement aux concepts plus avancs. Ceci est un livre volumineux, et votre cours nen couvrira sans doute quune partie. Nous avons pourtant essay den faire un livre qui vous servira aussi bien maintenant comme support de cours, que plus tard dans votre carrire, comme rfrence mathmatique, ou manuel dingnierie. Quels sont les pr-requis pour lire ce livre ?

21. Prface XXIII Vous devrez avoir un petite exprience de la programmation. En particulier vous devrez comprendre les procdures rcursives et les structures de donnes simples comme les tableaux et les listes chanes. Vous devrez tre relativement familiaris avec les dmonstrations mathmatiques par rcurrence. Certaines parties de ce livre reposent sur des connaissances de calcul lmentaire. Cela dit, les parties 1 et 8 de ce livre vous apprendront toutes les techniques mathmatiques dont vous aurez besoin. c) Pour le professionnel La grande varit de sujets prsents dans ce livre en fait un excellent manuel de rfrence sur les algorithmes. Chaque chapitre tant relativement indpendant des autres, vous pourrez vous concentrer sur les sujets qui vous intressent le plus. La plupart des algorithmes tudis ont une grande utilit pratique. Nous mettons donc laccent sur limplmentation et les autres problmes dingnierie. Nous offrons le plus souvent des alternatives pratiques aux quelques algorithmes qui sont surtout dintrt thorique. Si vous souhaitez implmenter lun de ces algorithmes, vous naurez aucun mal traduire notre pseudo-code dans votre langage de programmation favori. Le pseudocode est conu pour prsenter chaque algorithme de faon claire et succincte. Nous ne nous intressons donc pas la gestion des erreurs et autres problmes de gnie logiciel qui demandent des hypothses particulires sur lenvironnement de programmation. Nous essayons de prsenter chaque algorithme simplement et directement de manire viter que leur essence ne soit masque par les idiosyncrasies dun langage de programmation particulier. c Dunod La photocopie non autorise est un dlit d) Pour nos collgues Nous donnons une bibliographie trs complte et des rfrences la littrature courante. Chaque chapitre se termine par une partie notes de chapitre qui fournissent des dtails et des rfrences historiques. Les notes de chapitre ne fournissent pas, toutefois, une rfrence complte au vaste champ des algorithmes. Malgr la taille imposante de cet ouvrage, nous avons d renoncer, faute de place, inclure nombre dalgorithmes intressants. Nonobstant les innombrables supplications manant dtudiants, nous avons dcid de ne pas fournir de solutions aux problmes et exercices ; ainsi, ltudiant ne succombera pas la tentation de regarder la solution au lieu dessayer de la trouver par lui-mme. e) Modications apportes la seconde dition Quest-ce qui a chang par rapport la premire dition de ce livre ? Pas grand chose ou beaucoup de choses, selon le point de vue adopt.

22. XXIV Prface Un examen sommaire de la table des matires montre que la plupart des chapitres de la premire dition gurent aussi dans la seconde. Nous avons supprim deux chapitres et une poigne de sections, mais nous avons ajout trois nouveaux chapitres et quatre nouvelles sections rparties sur dautres chapitres. Si vous deviez valuer lampleur des modications daprs la table des matires, vous en concluriez que les changements ont t limits. En fait, les modications vont bien au-del de ce que semble montrer la table des matires. Voici, dans le dsordre, un rsum des changements les plus signicatifs pour la seconde dition : Cliff Stein a rejoint notre quipe dauteurs. Certaines erreurs ont t corriges. Combien ? Disons, un certain nombre. Il y a trois nouveaux chapitres : Le chapitre 1 prsente le rle des algorithmes en informatique. Le chapitre 5 traite de lanalyse probabiliste et des algorithmes randomiss. Comme avec la premire dition, ces thmes reviennent souvent dans cet ouvrage. Le chapitre 29 est consacr la programmation linaire. Aux chapitres repris de la premire dition ont t ajoutes de nouvelles sections, traitant des sujets que voici : hachage parfait (section 11.5), deux applications de la programmation dynamique (sections 15.1 et 15.5), et algorithmes dapproximation utilisant randomisation et programmation linaire (section 35.4). Pour montrer davantage dalgorithmes en dbut de livre, trois des chapitres consacrs aux thories mathmatiques ont t transfrs de la partie 1 vers les annexes, savoir la partie 8. Il y a plus de 40 nouveaux problmes et plus de 185 nouveaux exercices. Nous avons rendu explicite lutilisation des invariants de boucle pour prouver la validit des algorithmes. Notre premier invariant apparat au chapitre 2, et nous en verrons une trentaine dautres tout au long de cet ouvrage. Nous avons rcrit nombre des analyses probabilistes. En particulier, nous utilisons une dizaine dendroits la technique des variables indicatrices qui simplie les analyses probabilistes, surtout quand les variables alatoires sont dpendantes. Nous avons enrichi et actualis les notes de chapitre et la bibliographie. Celleci a augment de plus de 50% et nous avons cit nombre de nouveaux rsultats algorithmiques qui ont paru postrieurement la premire dition de ce livre.

23. Prface XXV Nous avons galement procd aux changements suivants : Le chapitre consacr la rsolution des rcurrences ne contient plus la mthode ditration. la place, dans la section 4.2, nous avons promu les arbres rcursifs de faon en faire une mthode de plein droit. Nous avons trouv que tracer des arbres rcursifs est moins sujet erreur que ditrer des rcurrences Nous signalons, cependant, que les arbres rcursifs sont surtout intressants pour gnrer des conjectures qui seront ensuite vries via la mthode de substitution. La mthode de partitionnement employe pour le tri rapide (quicksort) (section 7.1) et pour la slection en temps moyen linaire (section 9.2) a chang. Nous utilisons dsormais la mthode de Lomuto qui, grce des variables indicatrices, simplie quelque peu lanalyse. La mthode utilise dans la premire dition, due Hoare, apparat sous forme de problme au chapitre 7. Nous avons modi la prsentation du hachage universel la section 11.3.3 de faon que cette tude rentre dans le cadre du hachage parfait. Il y a une analyse beaucoup plus simple de la hauteur dun arbre de recherche binaire gnr alatoirement, la section 12.4. La prsentation de la programmation dynamique (section 15.3) et celle des algorithmes gloutons (section 16.2) ont t fortement enrichies. Ltude du problme du choix dactivits, expos au dbut du chapitre consacr aux algorithmes gloutons, aide clarier les relations entre programmation dynamique et algorithmes gloutons. Nous avons remplac la dmonstration du temps dexcution de la structure de donnes union densembles disjoints, la section 21.4, par une dmonstration qui emploie la mthode du potentiel pour dterminer une borne serre. La dmonstration de la validit de lalgorithme de recherche des composantes fortement connexes, la section 22.5, est plus simple, plus claire et plus directe. c Dunod La photocopie non autorise est un dlit Le chapitre 24, consacr aux plus courts chemins origine unique, a t refondu de faon que les dmonstrations des proprits fondamentales soient places dans une section spcique. Cette nouvelle organisation nous permet de commencer plus tt ltude des algorithmes. La section 34.5 contient une prsentation enrichie de la NP-compltude, ainsi que de nouvelles dmonstrations de la NP-compltude des problmes du cycle hamiltonien et de la somme dun sous-ensemble. Enn, nous avons revu quasiment toutes les sections pour corriger, simplier et clarier explications et dmonstrations. f) Site web Un autre changement par rapport la premire dition est ce que livre a maintenant son site web lui : http ://mitpress.mit.edu/algorithms/. Vous pouvez utiliser ce site pour signaler des erreurs, obtenir la liste des erreurs connues ou

24. XXVI Prface mettre des suggestions ; nhsitez pas nous faire signe. Nous sommes tout particulirement intresss par des ides dexercice et de problme, mais noubliez pas dy joindre les solutions. Nous regrettons dtre dans limpossibilit de rpondre personnellement tous les commentaires. g) Remerciements pour la premire dition De nombreux amis et collgues ont largement contribu la qualit de ce livre. Nous les remercions tous pour leur aide et leurs critiques constructives. Le laboratoire dinformatique du MIT nous a offert un environnement de travail idal. Nos collgues du groupe de thorie du calcul ont t particulirement comprhensifs et tolrants quant nos incessantes demandes dexpertise de tel ou tel chapitre. Nous remercions particulirement Baruch Awerbuch, Sha Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, David Shmoys et Eva Tardos. Merci William Ang, Sally Bemus, Ray Hirschfeld et Mark Reinhold pour avoir permis nos machines (DEC Microvax, Apple Macintosh et Sparcstation Sun) de fonctionner sans heurts et pour avoir recompil TEX chaque fois que nous dpassions une limite de temps de compilation. Thinking Machines Corporation a partiellement permis Charles Leiserson de travailler ce livre alors quil tait absent du MIT. De nombreux collgues ont utilis les preuves de ce texte pour leur Cours dans dautres universits. Ils ont suggr bon nombre de corrections et de rvisions. Nous souhaitons notamment remercier Richard Beigel, Andrew Goldberg, Joan Lucas, Mark Overmars, Alan Sherman et Diane Souvaine. Parmi les enseignants qui nous assistent pour nos cours, beaucoup ont contribu de manire signicative au dveloppement de ce texte. Nous remercions particulirement Alan Baratz, Bonnie Berger, Aditi Dhagat, Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou, Cindy Phillips, Mark Reinhold, Phil Rogaway, Flavio Rose, Arie Rudich, Alan Sherman, Cliff Stein, Susmita Sur, Gregory Troxel et Margaret Tuttle. Nombreux sont ceux qui nous ont apport une assistance technique complmentaire mais prcieuse. Denise Sergent a pass de nombreuses heures dans les bibliothques du MIT, la recherche de rfrences bibliographiques. Maria Sensale, la bibliothcaire de notre salle de lecture fut toujours souriante et serviable. Laccs la bibliothque personnelle dAlbert Meyer nous a conomis de nombreuses heures pendant la rdaction des notes de chapitre. Shlomo Kipnis, Bill Niehaus et David Wilson ont valid les anciens exercices, en ont conu de nouveaux et ont annot leurs solutions. Marios Papaefthymiou et Gregory Troxel ont contribu lindex. Au l des ans, nos secrtaires Inna Radzihovsky, Denise Sergent, Gayle Sherman, et surtout Be Hubbard, Ont constamment soutenu ce projet, et nous les en remercions. Parmi les erreurs releves dans les premires preuves, beaucoup lont t par nos tudiants. Nous remercions particulirement Bobby Blumofe, Bonnie Eisenberg,

25. Prface XXVII Raymond Johnson, John Keen, Richard Lethin, Mark Lillibridge, John Pezaris, Steve Ponzio, et Margaret Tuttle pour leur lecture attentive. Nos collgues ont galement effectu des relectures critiques de certains chapitres, ou donn des informations sur des algorithmes particuliers, et nous leur en sommes reconnaissants. Nous remercions particulirement Bill Aiello, Alok Aggarwal, Eric Bach, Vaek Chvtal, Richard Cole, Johan Hastad, Alex Ishii, David Johnson, Joe Kilian, Dina Kravets, Bruce Maggs, Jim Orlin, James Park, Thane Plambeck, Hershel Safer, Jeff Shallit, Cliff Stein, Gil Strang, Bob Tarjan et Paul Wang. Plusieurs de nos collgues nous ont aussi fourni gracieusement quelques problmes ; nous remercions notamment Andrew Goldberg, Danny Sleator et Umesh Vazirani. Nous avons eu plaisir travailler avec MIT Press et McGraw-Hill pendant la mise en forme de ce texte. Nous remercions particulirement Frank Satlow, Terry Ehling, Larry Cohen et Lorrie Lejeune de MIT Press et David Shapiro de McGraw-Hill pour leur encouragement, leur soutien et leur patience. Nous sommes particulirement reconnaissant Larry Cohen pour son exceptionnelle correction dpreuves. h) Remerciements pour la seconde dition c Dunod La photocopie non autorise est un dlit Quand nous demandmes Julie Sussman, P.P.A., de nous servir de correctrice technique pour cette seconde dition, nous ne savions pas que nous allions tomber sur loiseau rare. En plus de vrier le contenu technique, Julie a corrig avec ardeur notre prose. Cest pour nous une belle leon dhumilit que de voir le nombre derreurs que Julie a trouves dans nos premires preuves ; encore que, compte tenu du nombre derreurs quelle avait dceles dans la premire dition (aprs publication, hla), il ny a rien dtonnant cela. Qui plus est, Julie a sacri son emploi du temps personnel pour favoriser le ntre ; elle a mme relu des chapitres pendant des vacances aux Iles Vierges ! Julie, comment pourrions-nous vous remercier pour le travail incroyable que vous avez effectu ? La seconde dition a t prpare alors que les auteurs faisaient partie du dpartement dinformatique de Dartmouth College et du laboratoire dinformatique du MIT. Ces deux environnements ne pouvaient tre que stimulants, et nous remercions nos collgues pour leur aide. Des amis et des collgues, un peu partout dans le monde, nous ont aid, par leurs suggestions et leurs avis autoriss, a amliorer notre texte. Grand merci Sanjeev Arora, Javed Aslam, Guy Blelloch, Avrim Blum, Scot Drysdale, Hany Farid, Hal Gabow, Andrew Goldberg, David Johnson, Yanlin Liu, Nicolas Schabanel, Alexander Schrijver, Sasha Shen, David Shmoys, Dan Spielman, Gerald Jay Sussman, Bob Tarjan, Mikkel Thorup et Vijay Vazirani. De nombreux enseignants et collgues nous ont appris beaucoup de choses sur les algorithmes. Nous remercions tout particulirement nos professeurs Jon L. Bentley, Bob Floyd, Don Knuth, Harold Kuhn, H. T. Kung, Richard Lipton, Arnold Ross,

26. XXVIII Prface Larry Snyder, Michael I. Shamos, David Shmoys, Ken Steiglitz, Tom Szymanski, va Tardos, Bob Tarjan et Jeffrey Ullman. Nous remercions, pour leur contribution, tous les assistants chargs de cours dalgorithmique au MIT et Dartmouth, dont Joseph Adler, Craig Barrack, Bobby Blumofe, Roberto De Prisco, Matteo Frigo, Igal Galperin, David Gupta, Raj D. Iyer, Nabil Kahale, Sarfraz Khurshid, Stavros Kolliopoulos, Alain Leblanc, Yuan Ma, Maria Minkoff, Dimitris Mitsouras, Alin Popescu, Harald Prokop, Sudipta Sengupta, Donna Slonim, Joshua A. Tauber, Sivan Toledo, Elisheva Werner-Reiss, Lea Wittie, Qiang Wu et Michael Zhang. Lassistance informatique nous a t fournie par William Ang, Scott Blomquist et Greg Shomo au MIT, et par Wayne Cripps, John Konkle et Tim Tregubov Dartmouth. Merci galement Be Blackburn, Don Dailey, Leigh Deacon, Irene Sebeda et Cheryl Patton Wu du MIT, et Phyllis Bellmore, Kelly Clark, Delia Mauceli, Sammie Travis, Deb Whiting et Beth Young de Dartmouth pour leur assistance administrative. Michael Fromberger, Brian Campbell, Amanda Eubanks, Sung Hoon Kim et Neha Narula nous ont aussi apport une assistance opportune Dartmouth. Nombreux sont celles et ceux qui ont eu la gentillesse de signaler des erreurs dans la premire dition. Merci aux personnes suivantes, dont chacune a t la premire signaler une erreur dissimule dans la premire dition : Len Adleman, Selim Akl, Richard Anderson, Juan Andrade-Cetto, Gregory Bachelis, David Barrington, Paul Beame, Richard Beigel, Margrit Betke, Alex Blakemore, Bobby Blumofe, Alexander Brown, Xavier Cazin, Jack Chan, Richard Chang, Chienhua Chen, Ien Cheng, Hoon Choi, Drue Coles, Christian Collberg, George Collins, Eric Conrad, Peter Csaszar, Paul Dietz, Martin Dietzfelbinger, Scot Drysdale, Patricia Ealy, Yaakov Eisenberg, Michael Ernst, Michael Formann, Nedim Fresko, Hal Gabow, Marek Galecki, Igal Galperin, Luisa Gargano, John Gately, Rosario Genario, Mihaly Gereb, Ronald Greenberg, Jerry Grossman, Stephen Guattery, Alexander Hartemik, Anthony Hill, Thomas Hofmeister, Mathew Hostetter, Yih-Chun Hu, Dick Johnsonbaugh, Marcin Jurdzinki, Nabil Kahale, Fumiaki Kamiya, Anand Kanagala, Mark Kantrowitz, Scott Karlin, Dean Kelley, Sanjay Khanna, Haluk Konuk, Dina Kravets, Jon Kroger, Bradley Kuszmaul, Tim Lambert, Hang Lau, Thomas Lengauer, George Madrid, Bruce Maggs, Victor Miller, Joseph Muskat, Tung Nguyen, Michael Orlov, James Park, Seongbin Park, Ioannis Paschalidis, Boaz Patt-Shamir, Leonid Peshkin, Patricio Poblete, Ira Pohl, Stephen Ponzio, Kjell Post, Todd Poynor, Colin Prepscius, Sholom Rosen, Dale Russell, Hershel Safer, Karen Seidel, Joel Seiferas, Erik Seligman, Stanley Selkow, Jeffrey Shallit, Greg Shannon, Micha Sharir, Sasha Shen, Norman Shulman, Andrew Singer, Daniel Sleator, Bob Sloan, Michael Sofka, Volker Strumpen, Lon Sunshine, Julie Sussman, Asterio Tanaka, Clark Thomborson, Nils Thommesen, Homer Tilton, Martin Tompa, Andrei Toom, Felzer Torsten, Hirendu Vaishnav, M. Veldhorst, Luca Venuti, Jian Wang, Michael Wellman, Gerry Wiener, Ronald Williams, David Wolfe, Jeff Wong, Richard Woundy, Neal Young, Huaiyuan Yu, Tian Yuxing, Joe Zachary, Steve Zhang, Florian Zschoke et Uri Zwick.

27. c Dunod La photocopie non autorise est un dlit Prface XXIX Nombre de nos collgues ont fourni des compte-rendus dtaills ou ont rempli un long questionnaire. Merci donc Nancy Amato, Jim Aspnes, Kevin Compton, William Evans, Peter Gacs, Michael Goldwasser, Andrzej Proskurowski, Vijaya Ramachandran et John Reif. Nous remercions galement les personnes suivantes qui nous nous renvoy le questionnaire : James Abello, Josh Benaloh, Bryan BeresfordSmith, Kenneth Blaha, Hans Bodlaender, Richard Borie, Ted Brown, Domenico Cantone, M. Chen, Robert Cimikowski, William Clocksin, Paul Cull, Rick Decker, Matthew Dickerson, Robert Douglas, Margaret Fleck, Michael Goodrich, Susanne Hambrusch, Dean Hendrix, Richard Johnsonbaugh, Kyriakos Kalorkoti, Srinivas Kankanahalli, Hikyoo Koh, Steven Lindell, Errol Lloyd, Andy Lopez, Dian Rae Lopez, George Lucker, David Maier, Charles Martel, Xiannong Meng, David Mount, Alberto Policriti, Andrzej Proskurowski, Kirk Pruhs, Yves Robert, Guna Seetharaman, Stanley Selkow, Robert Sloan, Charles Steele, Gerard Tel, Murali Varanasi, Bernd Walter et Alden Wright. Nous aurions aim pouvoir rpondre toutes vos suggestions, mais cette seconde dition aurait d alors faire dans les 3000 pages ! A La seconde dition a t faite avec LTEX 2. Michael Downes a converti les maA A A cros LTEX pour les faire passer de LTEX classique LTEX 2 ; il a aussi converti les chiers texte pour quils utilisent les nouvelles macros. David Jones a fourni une A assistance sur LTEX 2. Les gures de la seconde dition ont t ralises par les auteurs laide de MacDraw Pro. Comme pour la premire dition, lindex a t compil avec Windex, qui est un programme C dvelopp par les auteurs ; la bibliographie a t prpare avec B IBTEX. Ayorkor Mills-Tettey et Rob Leathern ont aid la conversion des gures vers MacDraw Pro ; Ayorkor a, en outre, contrl notre bibliographie. Comme cela avait t le cas pour la premire dition, travailler avec The MIT Press et McGraw-Hill fut un vrai plaisir. Nos superviseurs, Bob Prior pour The MIT Press et Betsy Jones pour McGraw-Hill, ont support nos caprices et nous ont maintenu dans le droit chemin en maniant adroitement la carotte et le bton. Enn, nous remercions nos femmes (Nicole Cormen, Gail Rivest et Rebecca Ivry), nos enfants (Ricky, William et Debby Leiserson ; Alex et Christopher Rivest ; Molly, Noah et Benjamin Stein) et nos parents (Renee et Perry Cormen ; Jean et Mark Leiserson ; Shirley et Lloyd Rivest ; Irene et Ira Stein) pour leur amour et leur soutien pendant lcriture de ce livre. La patience et les encouragements de nos familles ont permis ce projet de voir le jour. Nous leur ddions affectueusement ce livre. T HOMAS H. C ORMEN C HARLES E. L EISERSON RONALD L. R IVEST C LIFFORD S TEIN Mai 2001 Hanover, New Hampshire Cambridge, Massachusetts Cambridge, Massachusetts Hanover, New Hampshire

28. PARTIE 1 INTRODUCTION Cette partie prsente les fondamentaux qui doivent vous guider pour concevoir et analyser des algorithmes. Elle a pour objectif dexposer en douceur la manire de spcier les algorithmes, certaines stratgies de conception qui nous serviront tout au long de ce livre, ainsi que bon nombre des concepts essentiels sous-jacents lanalyse des algorithmes. Les parties suivantes de ce livre sappuieront sur toutes ces fondations. c Dunod La photocopie non autorise est un dlit Le chapitre 1 donne une prsentation gnrale des algorithmes et de leur place dans les systmes informatiques modernes. Ce chapitre dnit ce quest un algorithme et donne des exemples. Il signale aussi, au passage, que les algorithmes sont une technologie, au mme titre que les matriels, les interfaces utilisateur graphique, les systmes orients objet ou les rseaux. Au chapitre 2, nous verrons nos premiers algorithmes, lesquels rsolvent le problme qui consiste trier une suite de n nombres. Ils seront crits en un pseudo code qui, mme sil nest pas directement traduisible en quelque langage de programmation traditionnel que ce soit, rete la structure de lalgorithme de manire sufsamment claire pour quun programmeur comptent puisse le mettre en uvre dans le langage de son choix. Les algorithmes de tri que nous tudierons sont le tri par insertion, qui utilise une stratgie incrmentale, et le tri par fusion, qui utilise une technique rcursive baptise diviser pour rgner . Bien que la dure dexcution de chacun de ces algorithmes croisse avec la valeur de n, le taux de croissance nest pas le mme pour les deux algorithmes. Nous dterminerons ces temps dexcution au chapitre 2 et introduirons une notation trs pratique pour les exprimer.

29. 2 Partie 1 Le chapitre 3 dnira plus formellement cette notation, que nous appellerons notation asymptotique. Il commencera par dnir plusieurs notations asymptotiques qui nous serviront borner, majorer et/ou minorer, les dures dexcution des algorithmes. Le reste du chapitre 3 consistera essentiellement en une prsentation de notations mathmatiques. Le but recherch est de garantir que les notations que vous employez concordent avec celles utilises dans cet ouvrage, et non de vous enseigner de nouveaux concepts mathmatiques. Le chapitre 4 approfondira la mthode diviser-pour-rgner, introduite au chapitre 2. En particulier, le chapitre 4 donnera des mthodes pour la rsolution des rcurrences, qui sont trs utiles pour dcrire les dures dexcution des algorithmes rcursifs. Une technique trs puissante ici est celle appele mthode gnrale , qui permet de rsoudre les rcurrences induites par les algorithmes de type diviser-pour-rgner. Une bonne partie du chapitre 4 sera consacre la dmonstration de la justesse de la mthode gnrale ; vous pouvez, sans inconvnient aucun, sauter cette dmonstration. Le chapitre 5 introduira lanalyse probabiliste et les algorithmes randomiss. Lanalyse probabiliste sert gnralement dterminer la dure dexcution dun algorithme dans le cas o, en raison de la prsence dune distribution probabiliste intrinsque, le temps dexcution peut varier pour diffrentes entres de la mme taille. Dans certains cas, nous supposerons que les entres obissent une distribution probabiliste connue, de sorte que nous ferons la moyenne des temps dexcution sur lensemble des entres possibles. Dans dautres cas, la distribution probabiliste ne viendra pas des entres, mais de choix alatoires faits pendant lexcution de lalgorithme. Un algorithme dont le comportement dpend non seulement de lentre, mais aussi de valeurs produites par un gnrateur de nombres alatoires est un algorithme randomis. Nous pouvons employer des algorithmes randomiss pour garantir une distribution probabiliste sur les entres, et ainsi garantir quaucune entre particulire nentrane systmatiquement de pitres performances, voire mme pour borner les taux derreur des algorithmes qui sont autoriss donner, dans une certaine limite, des rsultats errons. Les annexes AC renferment dautres sujets mathmatiques qui vous faciliteront la lecture de cet ouvrage. Vous avez certainement dj vu une bonne partie de ces notions (bien que les conventions de notation spciques que nous utilisons ici puissent, loccasion, diffrer de ce que vous connaissiez) ; vous pouvez donc considrer les annexes comme une sorte de rfrence. En revanche, la plupart des concepts prsents dans la partie 1 sont vraisemblablement indits pour vous. Tous les chapitres de la partie 1 et toutes les annexes ont t rdigs dans un esprit trs didactique.

30. Chapitre 1 Rle des algorithmes en informatique Quest-ce quun algorithme ? En quoi ltude des algorithmes est-elle utile ? Quel est le rle des algorithmes par rapport aux autres technologies informatiques ? Ce chapitre a pour objectif de rpondre ces questions. c Dunod La photocopie non autorise est un dlit 1.1 ALGORITHMES Voici une dnition informelle du terme algorithme : procdure de calcul bien dnie qui prend en entre une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une squence dtapes de calcul qui transforment lentre en sortie. Lon peut aussi considrer un algorithme comme un outil permettant de rsoudre un problme de calcul bien spci. Lnonc du problme spcie, en termes gnraux, la relation dsire entre lentre et la sortie. Lalgorithme dcrit une procdure de calcul spcique permettant dobtenir cette relation entre/sortie. Supposons, par exemple, quil faille trier une suite de nombres dans lordre croissant. Ce problme, qui revient frquemment dans la pratique, offre une base fertile pour lintroduction de nombre de techniques de conception et doutils danalyse standard. Voici comment nous dnissons formellement le problme de tri : Entre : suite de n nombres a1 , a2 , ..., an . Sortie : permutation (rorganisation) a1 , a2 , ..., an de la suite donne en entre, de faon que a1 a2 an .

31. 4 1 Rle des algorithmes en informatique Ainsi, partir de la suite 31, 41, 59, 26, 41, 58 , un algorithme de tri produit en sortie la suite 26, 31, 41, 41, 58, 59 . propos de la suite donne en entre, on parle dinstance du problme de tri. En gnral, une instance dun problme consiste en lentre (satisfaisant aux contraintes, quelles quelles soient, imposes dans lnonc du problme) requise par le calcul dune solution au problme. Le tri est une opration majeure en informatique (maints programmes lemploient comme phase intermdiaire), ce qui explique que lon ait invent un grand nombre dalgorithmes de tri. Lalgorithme optimal pour une application donne dpend, entre autres facteurs, du nombre dlments trier, de la faon dont les lments sont plus ou moins tris initialement, des restrictions potentielles concernant les valeurs des lments, ainsi que du type de priphrique de stockage utiliser : mmoire principale, disques ou bandes. Un algorithme est dit correct si, pour chaque instance en entre, il se termine en produisant la bonne sortie. Lon dit quun algorithme correct rsout le problme donn. Un algorithme incorrect risque de ne pas se terminer pour certaines instances en entre, voire de se terminer sur une rponse autre que celle dsire. Contrairement ce que lon pourrait croire, un algorithme incorrect peut savrer utile dans certains cas, si son taux derreur est susceptible dtre contrl. Nous en verrons un exemple au chapitre 31, quand nous tudierons des algorithmes servant dterminer les grands nombres premiers. En gnral, seuls nous intresseront toutefois les algorithmes corrects. Un algorithme peut tre spci en langage humain ou en langage informatique, mais peut aussi tre bas sur un systme matriel. Lunique obligation est que la spcication fournisse une description prcise de la procdure de calcul suivre. a) Quels sont les types de problme susceptibles dtre rsolus par des algorithmes ? Le tri nest absolument pas lunique problme pour lequel ont t invents des algorithmes. (Vous lavez sans dout devin rien quen voyant la taille de cet ouvrage.) Les applications concrtes des algorithmes sont innombrables, entre autres : Le projet du gnome humain a pour objectifs didentier les 100 000 gnes de lADN humain, de dterminer les squences des 3 milliards de paires de bases chimiques qui constituent lADN humain, de stocker ces informations dans des bases de donnes et de dvelopper des outils danalyse de donnes. Chacune de ces tapes exige des algorithmes trs labors. Les solutions aux divers problmes sous-jacents sortent du cadre de ce livre, mais les concepts traits dans nombre de chapitres de cet ouvrage sont utiliss pour rsoudre ces problmes de biologie, permettant ainsi aux scientiques de faire leur travail tout en utilisant les ressources avec efcacit. Cela fait gagner du temps, aussi bien au niveau des hommes que des machines, et de largent, du fait que les expriences de laboratoire peuvent ainsi fournir davantage dinformations.

32. 1.1 Algorithmes 5 Internet permet des gens parpills un peu partout dans le monde daccder rapidement toutes sortes de donnes. Tout cela repose sur des algorithmes intelligents qui permettent de grer et manipuler de grosses masses de donnes. Exemples de problmes rsoudre : recherche de routes optimales pour lacheminement des donnes (ce genre de technique sera prsent au chapitre 24) ; utilisation dun moteur de recherche pour trouver rapidement les pages contenant tel ou tel type de donnes (les techniques affrentes seront vues aux chapitres 11 et 32). Le commerce lectronique permet de ngocier et changer, de manire lectronique, biens et services. Le commerce lectronique exige que lon prserve la condentialit de donnes telles que numros de carte de crdit, mots de passe et relevs bancaires. La cryptographie cl publique et les signatures numriques (traites au chapitre 31), qui font partie des technologies fondamentales employes dans ce contexte, sappuient sur des algorithmes numriques et sur la thorie des nombres. Dans lindustrie et le commerce, il faut souvent optimiser lallocation de ressources limites. Une compagnie ptrolire veut savoir o placer ses puits de faon maximiser les prots escompts. Un candidat la prsidence veut savoir dans quels supports publicitaires il doit investir pour maximiser ses chances dlection. Une compagnie arienne dsire raliser laffectation des quipages aux vols de telle faon que les cots soient minimiss, les vols assurs sans dfaillance et la lgislation respecte. Un fournisseur de services Internet veut savoir o placer des ressources supplmentaires pour desservir ses clients de manire plus efcace. Voil des exemples de problmes susceptibles dtre rsolus par la programmation linaire, que nous tudierons au chapitre 29. c Dunod La photocopie non autorise est un dlit Certains dtails de ces exemples sortent du cadre de cet ouvrage, mais nous donnerons des techniques qui sappliquent ces problmes et catgories de problme. Nous montrerons aussi, dans ce livre, comment rsoudre maints problmes concrets, dont les suivants : Soit une carte routire sur laquelle sont indiques toutes les distances entre intersections adjacentes ; il faut dterminer le trajet le plus court entre deux intersections. Le nombre ditinraires peut tre norme, mme si lon na pas ditinraire qui se recoupe. Comment trouver le trajet le plus court parmi tous les trajets possibles ? Ici, nous modlisons la carte (qui, elle-mme, modlise les routes relles) sous la forme dun graphe (sujet trait au chapitre 10 et lannexe B), puis nous cherchons dterminer le chemin le plus court entre deux sommets du graphe. Le chapitre 24 montrera comment rsoudre ce problme de manire efcace. Soit une suite A1 , A2 , . . . , An de n matrices, dont nous voulons calculer le produit A1 A2 . . . An . La multiplication matricielle tant associative, il existe plusieurs ordres licites pour calculer le produit. Par exemple, si n = 4, nous pourrions faire les multiplications comme si le produit tait parenths de lune quelconque des faons suivantes : (A1 (A2 (A3 A4 ))), (A1 ((A2 A3 )A4 )), ((A1 A2 )(A3 A4 )), ((A1 (A2 A3 ))A4 ) ou (((A1 A2 )A3 )A4 ). Si toutes les matrices sont carres (et ont donc la mme taille),

33. 1 Rle des algorithmes en informatique 6 lordre des multiplications naffecte pas la dure de calcul du produit. Si, en revanche, les matrices sont de tailles diffrentes (ces tailles tant, toutefois, compatibles au niveau de la multiplication matricielle), alors lordre des multiplications peut faire une trs grosse diffrence. Le nombre dordres potentiels de multiplication tant exponentiel en n, essayer tous les ordres possibles risque de demander beaucoup de temps. Nous verrons au chapitre 15 comment utiliser la technique gnrale connue sous le nom de programmation dynamique pour rsoudre ce problme de faon beaucoup plus efcace. Soit lquation ax = b (mod n) dans laquelle a, b et n sont des entiers ; nous voulons trouver tous les entiers x, modulo n, qui satisfont cette quation. Il peut y avoir zro, une ou plusieurs solutions. Nous pourrions essayer de faire x = 0, 1, . . . , n1 dans lordre, mais le chapitre 31 donnera une mthode plus efcace. Soient n points du plan, dont nous voulons dterminer lenveloppe convexe. Cette enveloppe est le plus petit polygone convexe qui contient les points. Intuitivement, nous pouvons nous reprsenter chaque point comme un clou plant dans une planche. Lenveloppe convexe serait alors reprsente par un lastique qui entoure tous les clous. Chaque clou autour duquel senroule llastique est un sommet de lenveloppe convexe. (Voir la gure 33.6 pour un exemple.) Nimporte lequel des 2n sous-ensembles des points pourrait correspondre aux sommets de lenveloppe convexe. Seulement, il ne suft pas de savoir quels sont les points qui sont des sommets de lenveloppe ; il faut aussi connatre lordre dans lequel ils apparaissent. Il existe donc bien des choix pour les sommets de lenveloppe convexe. Le chapitre 33 donnera deux bonnes mthodes pour la dtermination de lenveloppe convexe. Ces numrations sont loin dtre exhaustives (comme vous lavez probablement devin en soupesant ce livre), mais elles tmoignent de deux caractristiques que lon retrouve dans bon nombre dalgorithmes intressants : 1) Il existe beaucoup de solutions priori, mais la plupart dentre elles ne sont pas celles que nous voulons. Trouver une solution qui convienne vraiment, voil qui nest pas toujours vident. 2) Il y a des applications concrtes. Parmi les problmes prcdemment numrs, les chemins les plus courts fournissent les exemples les plus lmentaires. Une entreprise de transport, par exemple une socit de camionnage ou la SNCF, a intrt trouver les trajets routiers ou ferroviaires les plus courts, car cela diminue les cots de main duvre et dnergie. Un nud de routage Internet peut avoir dterminer le chemin le plus court travers le rseau pour minimiser le dlai dacheminement dun message. b) Structures de donnes Cet ouvrage prsente plusieurs structures de donnes. Une structure de donnes est un moyen de stocker et organiser des donnes pour faciliter laccs ces donnes et leur modication. Il ny a aucune structure de donnes qui rponde tous les

34. 1.1 Algorithmes 7 besoins, de sorte quil importe de connatre les forces et limitations de plusieurs de ces structures. c) Technique Vous pouvez vous servir de cet ouvrage comme dun livre de recettes pour algorithmes, mais vous risquez tt ou tard de tomber sur un problme pour lequel il nexiste pas dalgorithme publi (cest le cas, par exemple, de nombre des exercices et problmes donns dans ce livre !). Cet ouvrage vous enseignera des techniques de conception et danalyse dalgorithme, de faon que vous puissiez crer des algorithmes de votre cru, prouver quils fournissent la bonne rponse et comprendre leur efcacit. d) Problmes difciles Une bonne partie de ce livre concerne les algorithmes efcaces. Notre mesure habituelle de lefcacit est la vitesse, cest--dire la dure que met un algorithme produire ses rsultats. Il existe des problmes, cependant, pour lesquels lon ne connat aucune solution efcace. Le chapitre 34 tudie un sous-ensemble intressant de ces problmes, connus sous lappellation de problmes NP-complets. c Dunod La photocopie non autorise est un dlit En quoi les problmes NP-complets sont-ils intressants ? Primo, lon na jamais trouv dalgorithme efcace pour un problme NP-complet, mais personne na jamais prouv quil ne peut pas exister dalgorithme efcace pour un problme. Autrement dit, lon ne sait pas sil existe ou non des algorithmes efcaces pour les problmes NP-complets. Secundo, lensemble des problmes NP-complets offre la proprit remarquable suivante : sil existe un algorithme efcace pour lun quelconque de ces problmes, alors il existe des algorithmes efcaces pour tous. Cette relation entre les problmes NP-complets rend dautant plus frustrante labsence de solutions efcaces. Tertio, plusieurs problmes NP-complets ressemblent, sans tre identiques, des problmes pour lesquels nous connaissons des algorithmes efcaces. Un petit changement dans lnonc du problme peut entraner un changement majeur au niveau de lefcacit du meilleur algorithme connu. Il est intressant davoir quelques connaissances concernant les problmes NPcomplets tant donn que, chose surprenante, certains dentre eux reviennent souvent dans les applications concrtes. Si lon vous demande de concocter un algorithme efcace pour un problme NP-complet, vous risquez de perdre pas mal de temps chercher pour rien. Si vous arrivez montrer que le problme est NP-complet, vous pourrez alors consacrer votre temps dvelopper un algorithme efcace fournissant une solution qui est bonne sans tre optimale. titre dexemple concret, prenons le cas dune entreprise de camionnage ayant un dpt central. Chaque jour, elle charge le camion au dpt puis lenvoie faire des livraisons plusieurs endroits. la n de la journe, le camion doit revenir au dpt de faon pouvoir tre recharg le jour suivant. Pour rduire les cots, lentreprise

35. 8 1 Rle des algorithmes en informatique veut choisir un ordre de livraisons tel que la distance parcourue par le camion soit minimale. Ce problme, qui nest autre que le fameux problme du voyageur de commerce , est un problme NP-complet. Il na pas dalgorithme efcace connu. Sous certaines hypothses, cependant, il existe des algorithmes efcaces donnant une distance globale qui nest pas trop loigne de la distance minimale. Le chapitre 35 prsente ce genre dalgorithmes, dits algorithmes dapproximation . Exercices 1.1.1 Donnez un exemple concret qui intgre lun des problmes suivants : tri, optimisation de lordre de multiplication des matrices, dtermination de lenveloppe convexe. 1.1.2 part la vitesse, quest-ce qui pourrait servir mesurer lefcacit dans un contexte concret ? 1.1.3 Slectionnez une structure de donnes que vous avez dj vue, puis tudiez ses avantages et ses inconvnients. 1.1.4 En quoi le problme du chemin minimal et celui du voyageur de commerce, prcdemment mentionns, se ressemblent-ils ? En quoi sont-ils diffrents ? 1.1.5 Trouvez un problme concret pour lequel seule conviendra la solution optimale. Trouvez ensuite un problme pour lequel une solution approche pourra faire laffaire. 1.2 ALGORITHMES EN TANT QUE TECHNOLOGIE Supposez que les ordinateurs soient inniment rapides et que leurs mmoires soient gratuites. Faudrait-il encore tudier les algorithmes ? Oui, ne serait-ce que pour montrer que la solution ne boucle pas indniment et quelle se termine avec la bonne rponse. Si les ordinateurs taient inniment rapides, nimporte quelle mthode correcte de rsolution dun problme ferait laffaire. Vous voudriez sans doute que votre solution entre dans le cadre dune bonne mthodologie dingnierie (cest--dire quelle soit bien conue et bien documente), mais vous privilgierez le plus souvent la mthode qui est la plus simple mettre en uvre. Si rapides que puissent tre les ordinateurs, ils ne sont pas inniment rapides. Si bon march que puisse tre la mmoire, elle nest pas gratuite. Le temps machine est donc une ressource limite, et il en est de mme de lespace mmoire. Il faut utiliser ces ressources avec parcimonie, et des algorithmes performants, en termes de dure et dencombrement, vous aideront atteindre cet objectif.

36. 1.2 Algorithmes en tant que technologie 9 a) Efcacit Il arrive souvent que des algorithmes conus pour rsoudre le mme problme diffrent fortement entre eux en termes defcacit. Ces diffrences peuvent tre bien plus importantes que celles dues au matriel et au logiciel. c Dunod La photocopie non autorise est un dlit titre dexemple, au chapitre 2 nous verrons deux algorithmes de tri. Le premier, appel tri par insertion, prend un temps approximativement gal c1 n2 pour trier n lments, c1 tant une constante indpendante de n. La dure du tri est donc, grosso modo, proportionnelle n2 . Le second, appel tri par fusion, prend un temps approximativement gal c2 n lg n, o lg n dsigne log2 n et c2 est une autre constante indpendante, elle aussi, de n. Le tri par insertion a gnralement un facteur constant infrieur celui du tri par fusion, de sorte que c1 < c2 . Nous verrons que les facteurs constants peuvent tre beaucoup moins signicatifs, au niveau de la dure dexcution, que la dpendance par rapport au nombre n de donnes trier. L o le tri par fusion a un facteur lg n dans son temps dexcution, le tri par insertion a un facteur n, qui est beaucoup plus grand. Le tri par insertion est gnralement plus rapide que le tri par fusion pour de petits nombres de donnes mais, ds que le nombre n dlments trier devient sufsamment grand, lavantage du tri par fusion (lg n contre n) fait plus que compenser la diffrence entre les facteurs constants. Mme si c1 est trs infrieur c2 , il y a toujours un palier au-del duquel le tri par fusion devient plus rapide. Pour avoir un exemple concret, comparons un ordinateur rapide (ordinateur A) excutant un tri par insertion et un ordinateur lent (ordinateur B) excutant un tri par fusion. Ces deux machines doivent chacune trier un tableau dun million de nombres. Supposez que lordinateur A excute un milliard dinstructions par seconde et que lordinateur B nexcute que dix millions dinstructions par seconde, de sorte que lordinateur A est 100 fois plus rapide que lordinateur B en termes de puissance de calcul brute. Pour rendre la diffrence encore plus sensible, supposez que le meilleur programmeur du monde crive le tri par insertion en langage machine pour lordinateur A et que le code rsultant demande 2n2 instructions pour trier n nombres. (Ici, c1 = 2.) Le tri par fusion, en revanche, est programm pour lordinateur B par un programmeur mdiocre utilisant un langage de haut niveau avec un compilateur peu performant, de sorte que le code rsultant demande 50n lg n instructions (donc, c2 = 50). Pour trier un million de nombres, lordinateur A demande 2(106 )2 instructions = 2 000 secondes, 109 instructions/seconde alors que lordinateur B demande 50106 lg 106 instructions 100 secondes, 107 instructions/seconde Avec un algorithme dont le temps dexcution crot plus lentement, mme si le compilateur est mdiocre la machine B tourne 20 fois plus vite que la machine

37. 10 1 Rle des algorithmes en informatique A ! Lavantage du tri par fusion ressort encore plus si nous trions dix millions de nombres : l o le tri par insertion demande environ 2,3 jours, le tri par fusion prend moins de 20 minutes. En gnral, plus la taille du problme augmente et plus augmente aussi lavantage relatif du tri par fusion. b) Algorithmes et autres technologies Lexemple prcdent montre que les algorithmes, linstar des matriels informatiques, sont une technologie. Les performances globales du systme dpendent autant des algorithmes que des matriels. Comme toutes les autres technologies informatiques, les algorithmes ne cessent de progresser. Lon peut se demander si les algorithmes sont vraiment si importants que cela sur les ordinateurs modernes, compte tenu de ltat davancement dautres technologies telles que horloges ultra-rapides, pipelines et architectures superscalaires, interfaces utilisateur graphiques conviviales et intuitives, systmes orients objet, et technologies de rseau local et de rseau tendu. La rponse est oui. Mme si certaines applications nexigent pas explicitement dalgorithmes au niveau de lapplication elle-mme (cest le cas, par exemple, de certaines applications simples bases sur le web), la plupart intgrent une certaine dose intrinsque dalgorithmes. Prenez le cas dun service bas sur le web qui dtermine des trajets pour aller dun endroit un autre. (Ce genre de service existe dj lheure o nous crivons ces lignes.) Sa mise en uvre exige des matriels rapides, une interface utilisateur graphique, des technologies de rseau tendu, voire des fonctionnalits objet. cela sajoutent des algorithmes pour certains traitements tels que recherche ditinraires (utilisant vraisemblablement un algorithme de chemin minimal), dessin de cartes et interpolation dadresses. Qui plus est, mme une application qui nemploie pas dalgorithmes au niveau de lapplication elle-mme sappuie indirectement sur une foule dalgorithmes. Lapplication sexcute sur des matriels performants ? La conception de ces matriels a utilis des algorithmes. Lapplication tourne par dessus des interfaces graphiques ? Toutes les interfaces utilisateur graphiques reposent sur des algorithmes. Lapplication fonctionne en rseau ? Le routage sappuie fondamentalement sur des algorithmes. Lapplication a t crite dans un langage autre que du code machine ? Alors, elle a t traduite par un compilateur, un interprteur ou un assembleur, toutes ces belles choses faisant un usage intensif dalgorithmes. Les algorithmes sont au cur de la plupart des technologies employes dans les ordinateurs modernes. Enn, avec les capacits sans cesse accrues des ordinateurs, ces derniers traitent des problmes de plus en plus vastes. Comme nous lavons vu dans la comparaison

38. Notes 11 entre le tri par insertion et le tri par fusion, cest avec les problmes de grande taille que les diffrences defcacit entre algorithmes sont les plus agrantes. Possder une base solide en algorithmique, voil qui fait toute la diffrence entre le programmeur dlite et le programmeur lambda. Les technologies informatiques modernes permettent de faire certaines tches mme si lon ne sy connat gure en algorithmes ; mais avec une bonne formation en algorithmique, lon peut aller beaucoup, beaucoup plus loin. Exercices 1.2.1 Donnez un exemple dapplication exigeant des algorithmes intrinsques, puis discutez les fonctions des algorithmes concerns. 1.2.2 On veut comparer les implmentations du tri par insertion et du tri par fusion sur la mme machine. Pour un nombre n dlments trier, le tri par insertion demande 8n2 tapes alors que le tri par fusion en demande 64n lg n. Quelles sont les valeurs de n pour lesquelles le tri par insertion lemporte sur le tri par fusion ? 1.2.3 Quelle est la valeur minimale de n pour laquelle un algorithme dont le temps dexcution est 100n2 sexcute plus vite quun algorithme dont le temps dexcution est 2n sur la mme machine ? PROBLMES c Dunod La photocopie non autorise est un dlit 1.1. Comparaison de temps dexcution Pour chaque fonction f (n) et pour chaque dure t du tableau suivant, dterminez la taille maximale n dun problme susceptible dtre rsolu dans le temps t, en supposant que lalgorithme mette f (n) microsecondes pour traiter le problme. 1 1 1 1 1 1 1 seconde minute heure jour mois an sicle lg n n n n lg n n2 n3 2n n!

39. 12 1 Rle des algorithmes en informatique NOTES Il existe nombre de textes excellents sur le thme gnral des algorithmes, dont les ouvrages de Aho, Hopcroft et Ullman [5, 6], Baase et Van Gelder [26], Brassard et Bratley [46, 47], Goodrich et Tamassia [128], Horowitz, Sahni et Rajasekaran [158], Kingston [179], Knuth [182, 183, 185], Kozen [193], Manber [210], Mehlhorn [217, 218, 219], Purdom et Brown [252], Reingold, Nievergelt et Deo [257], Sedgewick [269], Skiena [280] et Wilf [315]. Certains des aspects plus concrets de la conception des algorithmes sont traits par Bentley [39, 40] et Gonnet [126]. Vous trouverez aussi une introduction lalgorithmique dans les ouvrages intituls Handbook of Theoretical Computer Science, Volume A [302] et CRC Handbook on Algorithms and Theory of Computation [24]. Enn, vous trouverez des prsentations dalgorithmes utiliss en biologie informatique dans les manuels de Guseld [136], Pevzner [240], Setubal et Medinas [272] et Waterman [309].

40. Chapitre 2 c Dunod La photocopie non autorise est un dlit Premiers pas Ce chapitre a pour but de vous familiariser avec la dmarche que nous adopterons dans ce livre quand il sagira de rchir la conception et lanalyse des algorithmes. On peut le lire indpendamment de la suite, bien quil fasse plusieurs fois rfrence des notions qui seront abordes dans les chapitres 3 et 4. (Il contient aussi plusieurs sommations que lannexe A montrera comment rsoudre). Nous commencerons par tudier lalgorithme du tri par insertion, an de rsoudre la problmatique du tri expose au chapitre 1. Nous introduirons un pseudo code qui ne devrait pas surprendre le lecteur ayant dj pratiqu la programmation, et qui nous servira spcier nos algorithmes. Aprs avoir dcrit en pseudo code lalgorithme du tri par insertion, nous montrerons quil fait bien ce quon attend de lui et nous analyserons son temps dexcution. Lanalyse permettra dintroduire une notation qui met en valeur la faon dont le temps dexcution crot avec le nombre dlments trier. Aprs avoir tudi le tri par insertion, nous prsenterons le paradigme diviser pour rgner pour la conception dalgorithmes, technique qui nous servira dvelopper lalgorithme du tri par fusion. Nous terminerons par lanalyse du temps dexcution du tri par fusion. 2.1 TRI PAR INSERTION Notre premier algorithme, savoir le tri par insertion, rsout la problmatique du tri expose au chapitre 1 : Entre : Suite de n nombres a1 , a2 , . . . , an .

41. 2 Premiers pas 14 Sortie : permutation (rorganisation) a1 , a2 , . . . , an de la suite donne en entre, de faon que a1 a2 an . Les nombres trier sont parfois appels cls. Dans cet ouvrage, nous exprimerons gnralement les algorithmes sous la forme de programmes crits en un pseudo code qui, certains gards, rappelle C, Pascal ou Java. Si vous connaissez dj lun de ces langages, vous naurez gure de mal lire nos algorithmes. Ce qui diffrencie le pseudo code du vrai code cest que, avec le pseudo code nous employons lcriture qui nous semble tre la plus claire et la plus concise pour spcier lalgorithme ; ne soyez donc pas surpris de voir apparatre un mlange de franais et de vrai code. Autre diffrence entre pseudo code et vrai code : le pseudo code ne se soucie pas, en principe, de problmes dingnierie logicielle tels quabstraction des donnes, modularit, traitement derreur, etc. Cela permet au pseudo code de reter plus clairement la substantique moelle de lalgorithme. Nous commencerons par le tri par insertion, qui est un algorithme efcace quand il sagit de trier un petit nombre dlments. Le tri par insertion sinspire de la manire dont la plupart des gens tiennent des cartes jouer. Au dbut, la main gauche du joueur est vide et ses cartes sont poses sur la table. Il prend alors sur la table les cartes, une par une, pour les placer dans sa main gauche. Pour savoir o placer une carte dans son jeu, le joueur la compare avec chacune des cartes dj prsentes dans sa main gauche, en examinant les cartes de la droite vers la gauche, comme le montre la gure 2.1. A tout moment, les cartes tenues par la main gauche sont tries ; ces cartes taient, lorigine, les cartes situes au sommet de la pile sur la table. 10 4 5 7 10 5 2 4 7 2 Figure 2.1 Tri de cartes jouer, via tri par insertion. Notre pseudo-code pour le tri par insertion se prsente sous la forme dune procdure appele T RI -I NSERTION. Elle prend comme paramtre un tableau A[1 . . n] qui

42. 2.1 Tri par insertion 15 contient une squence trier, de longueur n. (Dans le code, le nombre n dlments de A est not longueur[A]). Les nombres donns en entre sont tris sur place : ils sont rorganiss lintrieur du tableau A, avec tout au plus un nombre constant dentre eux stock lextrieur du tableau tout instant. Lorsque T RI -I NSERTION se termine, le tableau dentre A contient la squence de sortie trie. T RI -I NSERTION(A) 1 pour j 2 longueur[A] 2 faire cl A[j] 3 Insre A[j] dans la squence trie A[1 . . j 1]. 4 ij1 5 tant que i > 0 et A[i] > cl 6 faire A[i + 1] A[i] 7 ii1 8 A[i + 1] cl a) Invariants de boucle et validit du tri par insertion 1 2 3 4 5 6 (a) 5 2 4 6 1 3 1 2 3 4 5 6 (d) 2 4 5 6 1 3 1 2 3 4 5 6 (b) 2 5 4 6 1 3 1 2 3 4 5 6 (e) 1 2 4 5 6 3 1 2 3 4 5 6 (c) 2 4 5 6 1 3 1 2 3 4 5 6 (f) 1 2 3 4 5 6 c Dunod La photocopie non autorise est un dlit Figure 2.2 Fonctionnement de T RI -I NSERTION sur le tableau A = 5, 2, 4, 6, 1, 3 . Les indices apparaissent au-dessus des cases, les valeurs du tableau apparaissant dans les cases. (a)(e) Itrations de la boucle pour des lignes lines 18. chaque itration, la case noire renferme la cl lue dans A[j] ; cette cl est compare aux valeurs des cases grises situes sa gauche (test en ligne 5). Les ches grises montrent les dplacements des valeurs dune position vers la droite (ligne 6), alors que les ches noires indiquent vers o sont dplaces les cls (ligne 8). (f)Tableau tri nal. La gure 2.2 illustre le fonctionnement de cet algorithme pour A = 5, 2, 4, 6, 1, 3 . Lindice j indique la carte courante en cours dinsertion dans la main. Au dbut de chaque itration de la boucle pour extrieure , indicie par j, le sous-tableau compos des lments A[1 . . j 1] correspond aux cartes qui sont dj dans la main, alors que les lments A[j + 1 . . n] correspondent aux cartes qui sont encore sur la table. En fait, les lments A[1 . . j 1] sont les lments qui occupaient initialement les positions 1 j 1, mais qui depuis ont t tris. Nous utiliserons ces proprits de A[1 . . j 1] pour dnir ce que lon appelle, de manire plus formelle, un invariant de boucle : Au dbut de chaque itration de la boucle pour des lignes18, le sous-tableau A[1 . . j 1] se compose des lments qui occupaient initialement les positions A[1 . . j 1] mais qui sont maintenant tris.

43. 2 Premiers pas 16 Les invariants de boucle nous aideront comprendre pourquoi un algorithme est correct. Nous devons montrer trois choses, concernant un invariant de boucle : Initialisation : Il est vrai avant la premire itration de la boucle. Conservation : Sil est vrai avant une itration de la boucle, il le reste avant litration suivante. Terminaison : Une fois termine la boucle, linvariant fournit une proprit utile qui aide montrer la validit de lalgorithme. Si les deux premires proprits sont vries, alors linvariant est vrai avant chaque itration de la boucle. Notez la ressemblance avec la rcurrence mathmatique dans laquelle, pour dmontrer quune proprit est vraie, vous montrez, primo quelle est vraie pour une valeur initiale, secundo que, si elle est vraie pour le rang N, alors elle lest pour le rang N + 1 (phase inductive). La troisime proprit est peut-tre la plus importante, vu que nous utilisons linvariant de boucle pour prouver la validit de lalgorithme. Elle diffre aussi de lusage habituel de la rcurrence mathmatique, dans laquelle la phase inductive se rpte indniment ; ici, on arrte linduction quand la boucle se termine. Voyons comment ces proprits sappliquent au tri par insertion. Initialisation : Commenons par montrer que linvariant est vri avant la premire itration de la boucle, quand j = 2.(1) Le sous-tableau A[1 . . j1] se compose donc uniquement de llment A[1] qui est, en fait, llment originel de A[1]. En outre, ce sous-tableau est tri (cest une trivialit), ce qui montre bien que linvariant est vri avant la premire itration de la boucle. Conservation : Passons ensuite la deuxime proprit : montrer que chaque itration conserve linvariant. De manire informelle, le corps de la boucle pour extrieure fonctionne en dplaant A[j 1], A[j 2], A[j 3], etc. dune position vers la droite jusqu ce quon trouve la bonne position pour A[j] (lignes 47), auquel cas on insre la valeur de A[j] (ligne 8). Un traitement plus formel de la deuxime proprit nous obligerait formuler et prouver un invariant pour la boucle tant que intrieure . Pour linstant, nous ne nous encombrerons pas dun tel formalisme et nous nous appuierons uniquement sur notre analyse informelle pour montrer que la deuxime proprit est vrie pour la boucle extrieure. Terminaison : Enn, voyons ce qui se passe quand la boucle se termine. Pour le tri par insertion, la boucle pour extrieure prend n quand j dpasse n, cest--dire quand j = n+1. En substituant n+1 j dans la formulation de linvariant de boucle, lon a que le sous-tableau A[1 . . n] se compose des lments qui appartenaient originellement A[1 . . n] mais qui ont t tris depuis lors. Or, le sous-tableau (1) Quand la boucle est une boucle pour, le moment o nous contrlons linvariant avant la premire itration se situe juste aprs lassignation initiale la variable servant de compteur de boucle et juste avant le premier test dans len-tte de boucle. Dans le cas de T RI -I NSERTION, cet instant se situe aprs affectation de la valeur 2 la variable j mais avant le premier test vriant si j longueur[A].

44. 2.1 Tri par insertion 17 A[1 . . n] nest autre que le tableau complet ! Par consquent, le tableau tout entier est tri, et donc lalgorithme est correct. Nous reverrons plus loin dans ce chapitre, ainsi que dans dautres chapitres, cet emploi des invariants de boucle pour justier la validit des algorithmes. b) Conventions concernant le pseudo code Nous adopterons les conventions suivantes pour le pseudo code. 1) Lindentation indique une structure de bloc. Par exemple le corps de la boucle pour qui commence la ligne 1 se compose des lignes 28, et le corps de la boucle tant que qui commence la ligne 5 contient les lignes 67 mais pas la ligne 8. Notre style dindentation sapplique galement aux instructions si-alors-sinon. Lemploi de lindentation, au lieu dindicateurs du genre dbut et n,pour matrialiser les blocs rduit sensiblement lencombrement tout en prservant, voire amliorant, la clart. (2) . 2) Les boucles tant que, pour et rpter, ainsi que tests si, alors et sinon ont la mme signication quen Pascal. (3) Il existe, toutefois, une diffrence subtile concernant les boucles pour : en Pascal la valeur de la variable servant de compteur de boucle est indnie la sortie de la boucle, alors que dans ce livre le compteur de boucle conserve sa valeur aprs la n de la boucle. Ainsi donc, juste aprs une boucle pour, la valeur du compteur de boucle est la valeur immdiatement suprieure la limite de bouclage. Nous avons utilis cette proprit dans notre dmonstration de la conformit du tri par insertion. Len-tte de la boucle pour, en ligne 1, est pour j 2 longueur[A] ; donc, quand la boucle se termine, j = longueur[A] + 1 (ou, de manire quivalente, j = n + 1, puisque n = longueur[A]). 3) Le symbole indique que le reste de la ligne est un commentaire. c Dunod La photocopie non autorise est un dlit 4) Une affectation multiple de la forme i j e affecte aux deux variables i et j la valeur de lexpression e ; on la considre comme quivalente laffectation j e suivie de laffectation i j. 5) Les variables comme i, j et cl sont locales la procdure donne. Nous nutiliserons pas de variables globales, sauf indication explicite. 6) On accde aux lments dun tableau via le nom du tableau suivi de lindice entre crochets. Ainsi, A[i] reprsente le i-me lment du tableau A. La notation . . indique une plage de