1176
INTRODUCTION À L’ALGORITHMIQUE Cours et exercices Thomas Cormen Professeur associé d’informatique au Darmouth College Charles Leiserson Professeur d’informatique au MIT Ronald Rivest Professeur d’informatique au MIT Clifford Stein Professeur associé au génie industriel et de recherche opérationelle à l’université de Columbia Préface de Philippe chrétienne , Claire Hanen, Alix Munier, Christophe Picouleau 1 ère édition traduite de l’américain par Xavier Cazin Compléments et mises à jour de la 2 e édition traduits par Georges-Louis Kocher 2 e édition

Introduction à l'algorithmique cours et exercices corrigés

Embed Size (px)

Citation preview

  1. 1. 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 0 lim Page I Jeudi, 22. juin 2006 5:03 17
  2. 2. 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 Dunod, Paris, 1994, pour la 1re dition Dunod, Paris, 2004, pour la prsente dition ISBN 2 10 003922 9 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 tech- nique et universitaire, le dvelop- pement massif du photo- copillage. 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 Grands- Augustins, 75006 Paris). 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. 0 lim Page II Jeudi, 22. juin 2006 5:03 17
  3. 3. Table des matires PRFACE LDITION FRANAISE XVII PRFACE XXI PARTIE 1 INTRODUCTION CHAPITRE 1 RLE DES ALGORITHMES EN INFORMATIQUE 3 1.1 Algorithmes 3 Exercices 8 1.2 Algorithmes en tant que technologie 8 Exercices 11 PROBLMES 11 CHAPITRE 2 PREMIERS PAS 13 2.1 Tri par insertion 13 Exercices 18 2.2 Analyse des algorithmes 19 Exercices 25 2.3 Conception des algorithmes 25 Exercices 34 PROBLMES 35 CHAPITRE 3 CROISSANCE DES FONCTIONS 39 3.1 Notation asymptotique 40 Exercices 48 3.2 Notations standard et fonctions classiques 48 Exercices 54 PROBLMES 55 cDunodLaphotocopienonautoriseestundlit
  4. 4. IV Table des matires CHAPITRE 4 RCURRENCES 59 4.1 Mthode de substitution 60 Exercices 64 4.2 Mthode de larbre rcursif 64 Exercices 68 4.3 Mthode gnrale 69 Exercices 71 4.4 Dmonstration du thorme gnral 72 Exercices 80 PROBLMES 80 CHAPITRE 5 ANALYSE PROBABILISTE ET ALGORITHMES RANDOMISS 87 5.1 Le problme de lembauche 87 Exercices 90 5.2 Variables indicatrices 91 Exercices 94 5.3 Algorithmes randomiss 95 Exercices 100 5.4 Analyse probabiliste et autres emplois des variables indicatrices 101 Exercices 112 PROBLMES 113 PARTIE 2 TRI ET RANGS CHAPITRE 6 TRI PAR TAS 121 6.1 Tas 121 Exercices 123 6.2 Conservation de la structure de tas 124 Exercices 125 6.3 Construction dun tas 126 Exercices 128 6.4 Algorithme du tri par tas 129 Exercices 129 6.5 Files de priorit 131 Exercices 134 PROBLMES 135
  5. 5. Table des matires V CHAPITRE 7 TRI RAPIDE 139 7.1 Description du tri rapide 139 Exercices 142 7.2 Performances du tri rapide 143 Exercices 146 7.3 Versions randomises du tri rapide 147 Exercices 148 7.4 Analyse du tri rapide 148 Exercices 152 PROBLMES 153 CHAPITRE 8 TRI EN TEMPS LINAIRE 159 8.1 Minorants pour le tri 159 Exercices 161 8.2 Tri par dnombrement 162 Exercices 164 8.3 Tri par base 164 Exercices 167 8.4 Tri par paquets 167 Exercices 171 PROBLMES 171 CHAPITRE 9 MDIANS ET RANGS 177 9.1 Minimum et maximum 178 Exercices 179 9.2 Slection en temps moyen linaire 179 Exercices 183 9.3 Slection en temps linaire dans le cas le plus dfavorable 183 Exercices 186 PROBLMES 187 PARTIE 3 STRUCTURES DE DONNES CHAPITRE 10 STRUCTURES DE DONNES LMENTAIRES 195 10.1 Piles et les 195 Exercices 197 cDunodLaphotocopienonautoriseestundlit
  6. 6. VI Table des matires 10.2 Listes chanes 199 Exercices 203 10.3 Implmentation des pointeurs et des objets 203 Exercices 207 10.4 Reprsentation des arborescences 208 Exercices 209 PROBLMES 211 CHAPITRE 11 TABLES DE HACHAGE 215 11.1 Tables adressage direct 216 Exercices 217 11.2 Tables de hachage 218 Exercices 222 11.3 Fonctions de hachage 223 Exercices 230 11.4 Adressage ouvert 231 Exercices 238 11.5 Hachage parfait 238 Exercices 242 PROBLMES 243 CHAPITRE 12 ARBRES BINAIRES DE RECHERCHE 247 12.1 Quest-ce quun arbre binaire de recherche ? 248 Exercices 249 12.2 Requte dans un arbre binaire de recherche 250 Exercices 253 12.3 Insertion et suppression 254 Exercices 257 12.4 Arbres binaires de recherche construits alatoirement 258 Exercices 261 PROBLMES 262 CHAPITRE 13 ARBRES ROUGE-NOIR 267 13.1 Proprits des arbres rouge-noir 267 Exercices 270 13.2 Rotation 271 Exercices 272
  7. 7. Table des matires VII 13.3 Insertion 273 Exercices 280 13.4 Suppression 281 Exercices 286 PROBLMES 287 CHAPITRE 14 EXTENSION DUNE STRUCTURE DE DONNES 295 14.1 Rangs dynamiques 296 Exercices 300 14.2 Comment tendre une structure de donnes 301 Exercices 303 14.3 Arbres dintervalles 304 Exercices 309 PROBLMES 310 PARTIE 4 TECHNIQUES AVANCES DE CONCEPTION ET DANALYSE CHAPITRE 15 PROGRAMMATION DYNAMIQUE 315 15.1 Ordonnancement de chanes de montage 316 Exercices 322 15.2 Multiplications matricielles enchanes 323 Exercices 330 15.3 lments de la programmation dynamique 330 Exercices 341 15.4 Plus longue sous-squence commune 341 Exercices 347 15.5 Arbres binaires de recherche optimaux 347 Exercices 354 PROBLMES 354 CHAPITRE 16 ALGORITHMES GLOUTONS 361 16.1 Un problme de choix dactivits 362 Exercices 370 16.2 lments de la stratgie gloutonne 370 Exercices 375 16.3 Codages de Huffman 376 Exercices 382 cDunodLaphotocopienonautoriseestundlit
  8. 8. VIII Table des matires 16.4 Fondements thoriques des mthodes gloutonnes 383 Exercices 388 16.5 Un problme dordonnancement de tches 389 Exercices 392 PROBLMES 392 CHAPITRE 17 ANALYSE AMORTIE 395 17.1 Mthode de lagrgat 396 Exercices 400 17.2 Mthode comptable 400 Exercices 402 17.3 Mthode du potentiel 402 Exercices 405 17.4 Tables dynamiques 406 Exercices 414 PROBLMES 415 PARTIE 5 STRUCTURES DE DONNES AVANCES CHAPITRE 18 B-ARBRES 425 18.1 Dnition dun B-arbre 429 Exercices 431 18.2 Oprations fondamentales sur les B-arbres 432 Exercices 437 18.3 Suppression dune cl dans un B-arbre 439 Exercices 442 PROBLMES 442 CHAPITRE 19 TAS BINOMIAUX 445 19.1 Arbres binomiaux et tas binomiaux 447 Exercices 450 19.2 Oprations sur les tas binomiaux 451 Exercices 461 PROBLMES 462
  9. 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 469 Exercices 477 20.3 Diminution dune cl et suppression dun nud 478 Exercices 481 20.4 Borne pour le degr maximal 482 Exercices 484 PROBLMES 484 CHAPITRE 21 STRUCTURES DE DONNES POUR ENSEMBLES DISJOINTS 487 21.1 Oprations sur les ensembles disjoints 487 Exercices 490 21.2 Reprsentation densembles disjoints par des listes chanes 490 Exercices 493 21.3 Forts densembles disjoints 494 Exercices 497 21.4 Analyse de lunion par rang avec compression de chemin 498 Exercices 505 PROBLMES 506 PARTIE 6 ALGORITHMES POUR LES GRAPHES CHAPITRE 22 ALGORITHMES LMENTAIRES POUR LES GRAPHES 513 22.1 Reprsentation des graphes 514 Exercices 516 22.2 Parcours en largeur 517 Exercices 524 22.3 Parcours en profondeur 525 Exercices 532 22.4 Tri topologique 534 Exercices 536 22.5 Composantes fortement connexes 536 Exercices 541 PROBLMES 542 cDunodLaphotocopienonautoriseestundlit
  10. 10. X Table des matires CHAPITRE 23 ARBRES COUVRANTS DE POIDS MINIMUM 545 23.1 Construction dun arbre couvrant minimum 546 Exercices 550 23.2 Algorithmes de Kruskal et de Prim 551 Exercices 556 PROBLMES 558 CHAPITRE 24 PLUS COURTS CHEMINS ORIGINE UNIQUE 563 24.1 Algorithme de Bellman-Ford 571 Exercices 574 24.2 Plus courts chemins origine unique dans les graphes orients sans circuit 575 Exercices 577 24.3 Algorithme de Dijkstra 577 Exercices 582 24.4 Contraintes de potentiel et plus courts chemins 583 Exercices 587 24.5 Dmonstrations des proprits de plus court chemin 589 Exercices 594 PROBLMES 595 CHAPITRE 25 PLUS COURTS CHEMINS POUR TOUT COUPLE DE SOMMETS 601 25.1 Plus courts chemins et multiplication de matrices 603 Exercices 608 25.2 Lalgorithme de Floyd-Warshall 609 Exercices 614 25.3 Algorithme de Johnson pour les graphes peu denses 616 Exercices 620 PROBLMES 621 CHAPITRE 26 FLOT MAXIMUM 625 26.1 Rseaux de transport 626 Exercices 631 26.2 La mthode de Ford-Fulkerson 632 Exercices 643 26.3 Couplage maximum dans un graphe biparti 644 Exercices 648 26.4 Algorithmes de prots 649 Exercices 658
  11. 11. Table des matires XI 26.5 Algorithme rtiqueter-vers-lavant 659 Exercices 669 PROBLMES 669 PARTIE 7 MORCEAUX CHOISIS CHAPITRE 27 RSEAUX DE TRI 681 27.1 Rseaux de comparaison 682 Exercices 685 27.2 Le principe du zro-un 686 Exercices 688 27.3 Un rseau de tri bitonique 689 Exercices 690 27.4 Un rseau de fusion 692 Exercices 693 27.5 Un rseau de tri 694 Exercices 696 PROBLMES 697 CHAPITRE 28 CALCUL MATRICIEL 701 28.1 Proprits des matrices 702 Exercices 709 28.2 Algorithme de Strassen pour la multiplication des matrices 710 Exercices 716 28.3 Rsolution de systmes dquations linaires 717 Exercices 730 28.4 Inversion des matrices 730 Exercices 734 28.5 Matrices symtriques dnies positives et approximation des moindres carrs 735 Exercices 740 PROBLMES 741 CHAPITRE 29 PROGRAMMATION LINAIRE 745 29.1 Forme canonique et forme standard 752 Exercices 759 29.2 Formulation de problmes comme programmes linaires 760 Exercices 764 cDunodLaphotocopienonautoriseestundlit
  12. 12. XII Table des matires 29.3 Algorithme du simplexe 765 Exercices 778 29.4 Dualit 779 Exercices 784 29.5 Solution de base ralisable initiale 785 Exercices 790 PROBLMES 791 CHAPITRE 30 POLYNMES ET TRANSFORME RAPIDE DE FOURIER 795 30.1 Reprsentation des polynmes 797 Exercices 802 30.2 Transforme discrte de Fourier et transforme rapide de Fourier 803 Exercices 810 30.3 Implmentations efcaces de la FFT 811 Exercices 816 PROBLMES 816 CHAPITRE 31 ALGORITHMES DE LA THORIE DES NOMBRES 821 31.1 Notions de thorie des nombres 823 Exercices 827 31.2 Plus grand commun diviseur 828 Exercices 832 31.3 Arithmtique modulaire 833 Exercices 839 31.4 Rsolution dquations linaires modulaires 839 Exercices 842 31.5 Thorme du reste chinois 843 Exercices 845 31.6 Puissances dun lment 846 Exercices 850 31.7 Le cryptosystme cls publiques RSA 850 Exercices 856 31.8 Test de primarit 856 Exercices 865 31.9 Factorisation des entiers 865 Exercices 870 PROBLMES 870
  13. 13. Table des matires XIII CHAPITRE 32 RECHERCHE DE CHANES DE CARACTRES 875 32.1 Algorithme naf de recherche de chane de caractres 878 Exercices 879 32.2 Algorithme de Rabin-Karp 880 Exercices 884 32.3 Recherche de chane de caractres au moyen dautomates nis 885 Exercices 891 32.4 Algorithme de Knuth-Morris-Pratt 891 Exercices 898 PROBLMES 899 CHAPITRE 33 GOMTRIE ALGORITHMIQUE 901 33.1 Proprits des segments de droite 902 Exercices 907 33.2 Dterminer si deux segments donns se coupent 908 Exercices 914 33.3 Recherche de lenveloppe convexe 915 Exercices 924 33.4 Recherche des deux points les plus rapprochs 925 Exercices 929 PROBLMES 930 CHAPITRE 34 NP-COMPLTUDE 933 34.1 Temps polynomial 939 Exercices 945 34.2 Vrication en temps polynomial 946 Exercices 950 34.3 NP-compltude et rductibilit 951 Exercices 960 34.4 Preuves de NP-compltude 961 Exercices 968 34.5 Problmes NP-complets 969 Exercices 982 PROBLMES 983 cDunodLaphotocopienonautoriseestundlit
  14. 14. XIV Table des matires CHAPITRE 35 ALGORITHMES DAPPROXIMATION 987 35.1 Problme de la couverture de sommets 989 Exercices 992 35.2 Problme du voyageur de commerce 992 Exercices 997 35.3 Problme de la couverture densemble 997 Exercices 1002 35.4 Randomisation et programmation linaire 1002 Exercices 1007 35.5 Problme de la somme de sous-ensemble 1007 Exercices 1012 PROBLMES 1013 PARTIE 8 ANNEXES : LMENTS DE MATHMATIQUES ANNEXE A SOMMATIONS 1021 A.1 Formules et proprits des sommations 1022 Exercices 1025 A.2 Bornes des sommations 1025 Exercices 1031 PROBLMES 1031 ANNEXE B ENSEMBLES, ETC. 1033 B.1 Ensembles 1033 Exercices 1037 B.2 Relations 1038 Exercices 1040 B.3 Fonctions 1040 Exercices 1042 B.4 Graphes 1043 Exercices 1046 B.5 Arbres 1047 Exercices 1053 PROBLMES 1054
  15. 15. Table des matires XV ANNEXE C DNOMBREMENT ET PROBABILITS 1057 C.1 Dnombrement 1057 Exercices 1061 C.2 Probabilits 1063 Exercices 1068 C.3 Variables alatoires discrtes 1069 Exercices 1073 C.4 Distributions gomtrique et binomiale 1074 Exercices 1078 C.5 Queues de la distribution binomiale 1079 Exercices 1084 PROBLMES 1085 BIBLIOGRAPHIE 1087 INDEX 1109 cDunodLaphotocopienonautoriseestundlit
  16. 16. Prface ldition franaise Vous savez compter. Un ordinateur aussi ! Mais connaissez-vous les mcanismes uti- liss ? 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 informa- ticien, 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 fondamen- taux 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 ri- goureusement 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, amortis- sement, en moyenne) qui permettent dapprofondir entre autres ltude de lefcacit des algorithmes de tri et des structures de donnes. cDunodLaphotocopienonautoriseestundlit
  17. 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 programma- tion 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 pro- blme 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, intro- duisent 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 pr- sence 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 dal- ler 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 cri- ture 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 PHILIPPE CHRTIENNE, CLAIRE HANEN, ALIX MUNIER, CHRISTOPHE PICOULEAU Universit Pierre et Marie Curie (LIP6)
  18. 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. Lalgorith- micien 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 ensei- gnant, qui dcouvre cette Introduction lalgorithmique, y trouvera sous un forma- lisme des plus limpides, le ncessaire, voire un peu plus, de cette discipline qui est lune des pierres angulaires de linformatique. Paris, aot 2002 CHRISTOPHE PICOULEAU, Laboratoire CEDRIC CNAM cDunodLaphotocopienonautoriseestundlit
  19. 19. 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 concep- tion, 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 as- pects 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 cDunodLaphotocopienonautoriseestundlit
  20. 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 substan- tiels, 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 nces- saires 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 forc- ment 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 ma- thmatiques 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 math- matique, ou manuel dingnierie. Quels sont les pr-requis pour lire ce livre ?
  21. 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 pseudo- code 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 program- mation. 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. d) Pour nos collgues Nous donnons une bibliographie trs complte et des rfrences la littrature cou- rante. 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 d- cid 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. cDunodLaphotocopienonautoriseestundlit
  22. 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 ou- vrage. 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 consa- crs 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. Celle- ci 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. 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 rcur- sifs 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 si- gnalons, 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) (sec- tion 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 algo- rithmes gloutons (section 16.2) ont t fortement enrichies. Ltude du problme du choix dactivits, expos au dbut du chapitre consacr aux algorithmes glou- tons, 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 for- tement connexes, la section 22.5, est plus simple, plus claire et plus directe. 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 hamil- tonien et de la somme dun sous-ensemble. Enn, nous avons revu quasiment toutes les sections pour corriger, simplier et cla- rier 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 pou- vez utiliser ce site pour signaler des erreurs, obtenir la liste des erreurs connues ou cDunodLaphotocopienonautoriseestundlit
  24. 24. XXVI Prface mettre des suggestions ; nhsitez pas nous faire signe. Nous sommes tout particu- lirement 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 tra- vail 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 particulire- ment Alan Baratz, Bonnie Berger, Aditi Dhagat, Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou, Cindy Phillips, Mark Reinhold, Phil Rogaway, Fla- vio Rose, Arie Rudich, Alan Sherman, Cliff Stein, Susmita Sur, Gregory Troxel et Margaret Tuttle. Nombreux sont ceux qui nous ont apport une assistance technique complmen- taire mais prcieuse. Denise Sergent a pass de nombreuses heures dans les biblio- thques 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. 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 re- connaissant Larry Cohen pour son exceptionnelle correction dpreuves. h) Remerciements pour la seconde dition Quand nous demandmes Julie Sussman, P.P.A., de nous servir de correctrice tech- nique 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 der- reurs que Julie a trouves dans nos premires preuves ; encore que, compte tenu du nombre derreurs quelle avait dceles dans la premire dition (aprs publica- tion, 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 dparte- ment 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, Alexan- der 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, cDunodLaphotocopienonautoriseestundlit
  26. 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 dal- gorithmique au MIT et Dartmouth, dont Joseph Adler, Craig Barrack, Bobby Blu- mofe, Roberto De Prisco, Matteo Frigo, Igal Galperin, David Gupta, Raj D. Iyer, Nabil Kahale, Sarfraz Khurshid, Stavros Kolliopoulos, Alain Leblanc, Yuan Ma, Ma- ria 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 Dart- mouth. 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 ad- ministrative. 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, Alexan- der Brown, Xavier Cazin, Jack Chan, Richard Chang, Chienhua Chen, Ien Cheng, Hoon Choi, Drue Coles, Christian Collberg, George Collins, Eric Conrad, Peter Csas- zar, Paul Dietz, Martin Dietzfelbinger, Scot Drysdale, Patricia Ealy, Yaakov Eisen- berg, 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, Mar- cin Jurdzinki, Nabil Kahale, Fumiaki Kamiya, Anand Kanagala, Mark Kantrowitz, Scott Karlin, Dean Kelley, Sanjay Khanna, Haluk Konuk, Dina Kravets, Jon Kro- ger, 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, Pa- tricio Poblete, Ira Pohl, Stephen Ponzio, Kjell Post, Todd Poynor, Colin Prepscius, Sholom Rosen, Dale Russell, Hershel Safer, Karen Seidel, Joel Seiferas, Erik Se- ligman, 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. 27. 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 Ra- machandran et John Reif. Nous remercions galement les personnes suivantes qui nous nous renvoy le questionnaire : James Abello, Josh Benaloh, Bryan Beresford- Smith, Kenneth Blaha, Hans Bodlaender, Richard Borie, Ted Brown, Domenico Can- tone, M. Chen, Robert Cimikowski, William Clocksin, Paul Cull, Rick Decker, Mat- thew Dickerson, Robert Douglas, Margaret Fleck, Michael Goodrich, Susanne Ham- brusch, Dean Hendrix, Richard Johnsonbaugh, Kyriakos Kalorkoti, Srinivas Kanka- nahalli, Hikyoo Koh, Steven Lindell, Errol Lloyd, Andy Lopez, Dian Rae Lopez, George Lucker, David Maier, Charles Martel, Xiannong Meng, David Mount, Al- berto 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 sugges- tions, mais cette seconde dition aurait d alors faire dans les 3000 pages ! La seconde dition a t faite avec LATEX 2. Michael Downes a converti les ma- cros LATEX pour les faire passer de LATEX classique LATEX 2 ; il a aussi converti les chiers texte pour quils utilisent les nouvelles macros. David Jones a fourni une assistance sur LATEX 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 biblio- graphie a t prpare avec BIBTEX. 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 Lei- serson ; 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. THOMAS H. CORMEN Hanover, New Hampshire CHARLES E. LEISERSON Cambridge, Massachusetts RONALD L. RIVEST Cambridge, Massachusetts CLIFFORD STEIN Hanover, New Hampshire Mai 2001 cDunodLaphotocopienonautoriseestundlit
  28. 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 lana- lyse des algorithmes. Les parties suivantes de ce livre sappuieront sur toutes ces fondations. 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 pro- blme 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 pro- grammation 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. cDunodLaphotocopienonautoriseestundlit
  29. 29. 2 Partie 1 Le chapitre 3 dnira plus formellement cette notation, que nous appellerons nota- tion asymptotique. Il commencera par dnir plusieurs notations asymptotiques qui nous serviront borner, majorer et/ou minorer, les dures dexcution des al- gorithmes. 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. Lana- lyse 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 cer- tains 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 al- gorithme dont le comportement dpend non seulement de lentre, mais aussi de va- leurs 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 no- tions (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 prsen- ts 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. 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. 1.1 ALGORITHMES Voici une dnition informelle du terme algorithme : procdure de calcul bien d- nie 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 gn- raux, 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 crois- sant. Ce problme, qui revient frquemment dans la pratique, offre une base fertile pour lintroduction de nombre de techniques de conception et doutils danalyse stan- dard. 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. cDunodLaphotocopienonautoriseestundlit
  31. 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 princi- pale, 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. Contraire- ment 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 dtermi- ner 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 algo- rithmes. (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. 32. 1.1 Algorithmes 5 Internet permet des gens parpills un peu partout dans le monde daccder rapi- dement 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 mo- teur 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 lectro- nique, 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 res- sources limites. Une compagnie ptrolire veut savoir o placer ses puits de fa- on maximiser les prots escompts. Un candidat la prsidence veut savoir dans quels supports publicitaires il doit investir pour maximiser ses chances dlec- tion. 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. Certains dtails de ces exemples sortent du cadre de cet ouvrage, mais nous don- nerons 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 inter- sections adjacentes ; il faut dterminer le trajet le plus court entre deux intersec- tions. 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 pos- sibles ? 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 pro- duit A1A2 . . . 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 fa- ons suivantes : (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4) ou (((A1A2)A3)A4). Si toutes les matrices sont carres (et ont donc la mme taille), cDunodLaphotocopienonautoriseestundlit
  33. 33. 6 1 Rle des algorithmes en informatique lordre des multiplications naffecte pas la dure de calcul du produit. Si, en re- vanche, les matrices sont de tailles diffrentes (ces tailles tant, toutefois, compa- tibles au niveau de la multiplication matricielle), alors lordre des multiplications peut faire une trs grosse diffrence. Le nombre dordres potentiels de multiplica- tion 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 pro- blme 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. Intuitive- ment, 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 som- mets 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. 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 al- gorithmes, 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 algo- rithmes 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 habi- tuelle de lefcacit est la vitesse, cest--dire la dure que met un algorithme pro- duire 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. En quoi les problmes NP-complets sont-ils intressants ? Primo, lon na jamais trouv dalgorithme efcace pour un problme NP-complet, mais personne na ja- mais prouv quil ne peut pas exister dalgorithme efcace pour un problme. Au- trement dit, lon ne sait pas sil existe ou non des algorithmes efcaces pour les pro- blmes NP-complets. Secundo, lensemble des problmes NP-complets offre la pro- prit 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 pe- tit 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 NP- complets 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 cDunodLaphotocopienonautoriseestundlit
  35. 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 avan- tages et ses inconvnients. 1.1.4 En quoi le problme du chemin minimal et celui du voyageur de commerce, prc- demment 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 mon- trer 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. 36. 1.2 Algorithmes en tant que technologie 9 a) Efcacit Il arrive souvent que des algorithmes conus pour rsoudre le mme problme dif- frent fortement entre eux en termes defcacit. Ces diffrences peuvent tre bien plus importantes que celles dues au matriel et au logiciel. titre dexemple, au chapitre 2 nous verrons deux algorithmes de tri. Le premier, appel tri par insertion, prend un temps approximativement gal c1n2 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 ap- proximativement gal c2n 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 dexcu- tion, 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 dl- ments 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 lordi- nateur 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 109 instructions/seconde = 2 000 secondes, alors que lordinateur B demande 50106 lg 106 instructions 107 instructions/seconde 100 secondes, 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 cDunodLaphotocopienonautoriseestundlit
  37. 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 aug- mente aussi lavantage relatif du tri par fusion. b) Algorithmes et autres technologies Lexemple prcdent montre que les algorithmes, linstar des matriels informa- tiques, sont une technologie. Les performances globales du systme dpendent au- tant des algorithmes que des matriels. Comme toutes les autres technologies infor- matiques, 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 d- termine 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. Lap- plication 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. Lappli- cation fonctionne en rseau ? Le routage sappuie fondamentalement sur des algo- rithmes. 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. 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 dex- cution est 100n2 sexcute plus vite quun algorithme dont le temps dexcution est 2n sur la mme machine ? PROBLMES 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 suppo- sant 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! cDunodLaphotocopienonautoriseestundlit
  39. 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]. Cer- tains 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 ou- vrages intituls Handbook of Theoretical Computer Science, Volume A [302] et CRC Hand- book 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. 40. Chapitre 2 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 algo- rithmes. 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 lalgo- rithme du tri par insertion, nous montrerons quil fait bien ce quon attend de lui et nous analyserons son temps dexcution. Lanalyse permettra dintroduire une no- tation 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 para- digme 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 . cDunodLaphotocopienonautoriseestundlit
  41. 41. 14 2 Premiers pas 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 ap- paratre 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 ding- nierie 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. 2 2 4 4 5 5 7 7 10 10 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 proc- dure appele TRI-INSERTION. Elle prend comme paramtre un tableau A[1 . . n] qui
  42. 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 TRI-INSERTION se termine, le tableau dentre A contient la squence de sortie trie. TRI-INSERTION(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 i j 1 5 tant que i > 0 et A[i] > cl 6 faire A[i + 1] A[i] 7 i i 1 8 A[i + 1] cl a) Invariants de boucle et validit du tri par insertion 1 2 3 4 5 6 5 2 4 6 1 3(a) 1 2 3 4 5 6 2 5 4 6 1 3(b) 1 2 3 4 5 6 2 4 5 6 1 3(c) 1 2 3 4 5 6 2 4 5 6 1 3(d) 1 2 3 4 5 6 2 4 5 61 3(e) 1 2 3 4 5 6 2 4 5 61 3(f) Figure 2.2 Fonctionnement de TRI-INSERTION 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) It- rations 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. cDunodLaphotocopienonautoriseestundlit
  43. 43. 16 2 Premiers pas 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 litra- tion 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 linva- riant 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 itra- tion conserve linvariant. De manire informelle, le corps de la boucle pour ext- rieure 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 for- malisme 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 TRI-INSERTION, cet instant se situe aprs affectation de la valeur 2 la variable j mais avant le premier test vriant si j longueur[A].
  44. 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 ma- trialiser 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 sub- tile 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 imm- diatement 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. 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 nutili- serons 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 valeurs dans un tableau. A[1 . . j] reprsente donc le sous- tableau de A constitu des lments A[1], A[2], . . . , A[j]. (2) Dans un vrai langage de programmation, il est gnralement dconseill dutiliser la seule indentation pour reprsenter les blocs, car il est difcile de reprer les niveaux dindentation lorsque le code tient sur plusieurs pages. (3) La plupart des langages structurs ont des constructions quivalentes, sachant que la syntaxe exacte peut diffrer de celle de Pascal. cDunodLaphotocopienonautoriseestundlit
  45. 45. 18 2 Premiers pas 7) Les donnes composes sont le plus souvent organises en objets, constitus dattributs ou champs. On accde un champ particulier grce son nom, suivi du nom de lobjet entre crochets. Par exemple, on considrera un tableau comme un objet qui a un attribut longueur indiquant le nombre dlments contenus dans lobjet. Pour spcier le nombre dlments dun tableau A, on crit longueur[A]. Bien que les crochets sutilisent tant pour lindexation des tableaux que pour laccs aux attributs des objets, le contexte indique gnralement comment on doit les interprter. Une variable reprsentant un tableau ou un objet est considre comme un poin- teur vers les donnes reprsentant le tableau ou lobjet. Pour tous les champs f dun objet x, faire y x entrane que f[y] = f[x]. Par ailleurs, si lon fait mainte- nant f[x] 3, on a ensuite non seulement f[x] = 3 mais aussi f[y] = 3. Autrement dit, x et y pointent vers le mme objet aprs laffectation y x. Il arrive quun pointeur ne fasse rfrence aucun objet. Nous lui donnons dans ce cas la valeur particulire NIL. 8) Les paramtres sont passs une procdure par valeur : la procdure appele reoit son propre exemplaire des paramtres et, si elle modie la valeur dun pa- ramtre, le changement nest pas visible pour la routine appelante. Lorsque les paramtres sont des objets, il y a copie du pointeur pointant vers les donnes re- prsentant lobjet mais il ny a pas copie des champs de lobjet. Par exemple, si x est un paramtre dune procdure appele, laffectation x y lintrieur de la procdure appele nest pas visible pour la procdure appelante. En revanche, laffectation f[x] 3 est visible. 9) Les oprateurs boolens et et ou sont court-circuitants. Cela signie que, quand on value lexpression x et y , on commence par valuer x. Si x vaut FAUX, alors lexpression globale ne peut pas tre gale VRAI et il est donc inutile dvaluer y. Si, en revanche, x vaut VRAI, alors il faut valuer y pour dterminer la valeur de lexpression globale. De mme, dans lexpression x ou y on nvalue y que si x vaut FAUX. Les oprateurs court-circuitants nous permettent dcrire des expressions boolennes du genre x NIL et f[x] = y sans que nous ayons nous soucier de ce qui se passerait si on essayait dvaluer f[x] quand x vaut NIL. Exercices 2.1.1 laide de la gure 2.2, illustrer laction de TRI-INSERTION sur le tableau A = 31, 41, 59, 26, 41, 58 . 2.1.2 Rcrire la procdure TRI-INSERTION pour trier dans lordre non croissant et non dans lordre non dcroissant. 2.1.3 Considrez le problme de la recherche : Entre : Une suite de n nombres A = a1, a2, . . . , an et une valeur v. Sortie : Un indice i tel que v = A[i], ou bien la valeur spciale NIL si v ne gure pas dans A.
  46. 46. 2.2 Analyse des algorithmes 19 crire du pseudo code pour recherche linaire, qui parcourre la suite en cherchant v. En utilisant un invariant de boucle, montrer la validit de lalgorithme. Vrier que linvariant possde bien les trois proprits requises. 2.1.4 On considre le problme consistant additionner deux entiers en reprsentation bi- naire stocks sur n bits, rangs dans deux tableaux A et B n lments. La somme des deux entiers doit tre stocke sous forme binaire dans un tableau C n + 1 lments. noncer le problme formellement et crire du pseudo-code pour additionner les deux entiers. 2.2 ANALYSE DES ALGORITHMES Analyser un algorithme est devenu synonyme de prvoir les ressources ncessaires cet algorithme. Parfois, les ressources prvoir sont la mmoire, la largeur de bande dune communication ou le processeur ; mais, le plus souvent, cest le temps de cal- cul qui nous intresse. En gnral, en analysant plusieurs algorithmes susceptibles de rsoudre le problme, on arrive aisment identier le plus efcace. Ce type dana- lyse peut rvler plus dun candidat viable, mais parvient gnralement liminer les algorithmes infrieurs. Pour pouvoir analyser un algorithme, il faut avoir un modle de la technologie qui sera employe, notamment un modle pour les ressources de cette technologie et pour leurs cots. Dans la majeure partie de ce livre, on supposera que lon a un mo- dle de calcul gnrique bas sur une machine accs alatoire(RAM) processeur unique. On devra galement avoir lesprit que nos algorithmes seront implmen- ts en tant que programmes informatiques. Dans le modle RAM, les instructions sont excutes lune aprs lautre, sans oprations simultanes. Dans des chapitres ultrieurs, cependant, nous aurons loccasion dexaminer des modles pour matriel numrique. strictement parler, il faudrait dnir prcisment les instructions du modle RAM et leurs cots. Cependant, cela serait pnible et napporterait pas grand chose en matire de conception et danalyse dalgorithme. Attention, toutefois, ne pas en- freindre allgrement le modle RAM. Par exemple, que se passerait-il si une RAM avait une instruction de tri ? Alors, on pourrait trier avec une seule instruction. Une telle RAM serait irraliste, vu que les ordinateurs ne disposent pas de ce genre dins- tructions. Nous devons donc nous laisser guider par le fonctionnement des ordina- teurs concrets. Le modle RAM contient les instructions que lon trouve dans la plupart des ordinateurs : arithmtique (addition, soustraction, multiplication, divi- sion, modulo, partie entire, partie entire suprieure, transfert de donnes (lecture, stockage, copie) et instructions de contrle (branchement conditionnel et incondition- nel, appel de sous-routine et sortie de sous-routine). Chacune de ces instructions a un temps dexcution constant. Les types de donnes du modle RAM sont le type entier et le type virgule ot- tante. Nous ne nous soucierons gnralement pas de la prcision dans cet ouvrage cDunodLaphotocopienonautoriseestundlit
  47. 47. 20 2 Premiers pas mais, pour certaines applications, la prcision est un lment crucial. Nous suppose- rons aussi quil existe une limite la taille de chaque mot de donnes. Ainsi, quand nous travaillerons avec des entres de taille n, nous supposerons en principe que les entiers sont reprsents par c lg n bits pour une certaine constante c 1. Nous im- posons que c 1 de faon que chaque mot puisse contenir la valeur n, ce qui n