[PDF] Algorithmique I - École normale supérieure de Lyon PDF poly09.pdf

1 7 Exercices 14 2 Diviser pour régner 15 2 1 Algorithme de Strassen de l'humour, dans un fichier pdf `a télécharger absolument – Compared to what Recherche dichotomique On maintient le tableau des noms trié 1 Coût au pire

13 2 1 Tri par insertion 13 Exercices 18 2 2 Analyse des algorithmes 19 Exercices 25 La recherche dichotomique est un algorithme qui répète cette

[PDF] TD : Complexité des algorithmes - limsi

algorithme permettant de calculer cette somme, pour chacune des deux représentations, puis de comparer On considère, pour effectuer la recherche d' un élément dans un tableau, la recherche séquentielle et la recherche dichotomique

[PDF] Cours, Exercices et Travaux Pratiques - Enseeiht

6 3 Exercices Un algorithme d'apprentissage artificiel permet de mettre au point un Dit différemment : « l'ACP cherche à remplacer les p variables d'un

[PDF] Exercices corrigés - u-psudfr

Énoncés des exercices Remarque Les exercices suivants sont fournis à titre d' exemples et de modèles Ils sont soit Écrire l'algorithme du calcul de : m3 = m1 −m2 msgbox("L'element cherche n'est pas dans la sequence ") sauve = None

[PDF] Calcul Scientifique: Cours, exercices corrigés et illustrations en

cherche des zéros ou le calcul d'intégrales de fonctions continues, la réso- lution de mais quand elles s'accumulent au cours d'algorithmes longs et complexes, elles La méthode de dichotomie (aussi appelée méthode de bisection)

[PDF] Exercices et problèmes dalgorithmique - Adrien Poupa

Corrigés des exercices et des problèmes une suite de noms, les algorithmes de recherche d'une chaîne de caractères dans un texte, ou les algorithmes La recherche n'est plus réellement dichotomique dans un arbre déséquilibré

[PDF] Calcul Scientifique: Cours, exercices corrigés et - Ceremade

cherche des zéros ou le calcul d'intégrales de fonctions continues, la réso- lution de lisés pour implémenter les divers algorithmes présentés, ce qui permet de vérifier, par La méthode de dichotomie (aussi appelée méthode de bisection)

[PDF] Algorithmes et structures de données : TD 4 Corrigé - LaBRI

Types - Enregistrements - Temps d'un algorithme T(n) C'est un algorithme de recherche dichotomique de recherche est restreint `a l'une de deux parties

[PDF] Synthèse de cours exercices corrigés - ACCUEIL

PEARSON Education France — Exercices d'Économétrie – 2e édition de Louvain et a été invité dans plusieurs centres de recherche internationaux, dont le algorithmique pour maximiser la fonction de vraisemblance [BOX 1976]

AlgorithmiqueI-CoursetTravauxDiri g´es

L3,Ecol eNormaleSup´er ieuredeLyon

Cours

AnneBe noit

TravauxDirig´es(200 8-2009)

BenjaminDepardon,Chris topheMouilleron,Cl´ement Resvoy

Septembre2009

Tabledesmati` eres

1In troduction:calculdex

n 9 1.1 Enonc´eduprobl`eme.. ..... ....................... ... .9

1.2Algorit hmena¨ıf............ ............... ... .. ... ..9

1.3M´et hodebinaire............. ................. ... ... 9

1.4M´et hodedesfacteurs......... ......... ................10

1.5Arbre deKnuth.... ...... .............. ... ... ... ... .10

1.6R´es ultatssurlacomplexit´e...... ......... ...... .........11

1.7Exe rcices.................... ... ... ... ... ... .. ... 12

1.8R´ef ´erencesbibliographiques.............. ................14

2D iviserpourr´egner15

2.1Algorit hmedeStrassen........ ...... ..................15

2.2Prod uitdedeuxpolynˆomes... ...... ............ .........17

2.3Maste rtheorem....... .................. ... .. ... ... .18

2.4R´es olutiondesr´ecurrences...... ........ ................19

2.4.1R´esol utiondesr´ecurrenceshomog`ene s........ ............19

2.4.2R´esolu tiondesr´ecurrencesavecsecon dmembre.. .............19

2.5Mult iplicationetinversiondematrices....... ...... ...........20

2.6Exer cices..................... .. ... ... ... ... ... ..21

2.7R´ef ´erencesbibliographiques.............. ................23

3P rogrammationdynamique25

3.1Pi`e cesdeMonnaies......... ...... .................. .. 25

3.2Leprob l`e medusac`ados............. ...... ..... ...... .26

3.2.1Englouton ...... ........... ... ... ... ... ... .. .26

3.2.2Parprogr ammationd ynamique................ ........26

3.3Quel quesexemplesdeprogrammationd ynamique................ ..27

3.3.1Chaˆın esdematrices............ ...... ............27

3.3.2Pluslon guesous-suite. ........... .................28

3.3.3Locationd eskis.......... ..... ............ ... ..30

3.4Exe rcices.................... ... ... ... ... ... ... .. 32

3.5R´ef ´erencesbibliographiques.............. ................34

4A lgorithmesgloutons35

4.1Exem pledugymnase.......... ...... .............. ... .35

4.2Route `asuivrepourl eglouton. ................. ........ ..36

4.3Colori aged'ungraphe...... ........... ............ ... .37

4.3.1Algorithm eglouton1.............. ............ ... 38

4.3.2Algorithm eglouton2.............. ............ .. .38

4.3.3Graphed 'intervalles.... ..........................39

4.3.4Algorithm edeBrelaz............ ...... ...........39

4.4Th´ eoriedesmatro¨ıdes..... ........ ....................41

4.4.1Matro¨ ıdes...................... ... ... ... ... ..41

4.4.2Algorith meglouton............... ........... ... ..42

4.5Ordon nancement........................... ... .. ... .42

4.6Exer cices..................... ... ... ... .. ... ... ..44

4.7R´ef ´erencesbibliographiques............. .................45

5Tri47

5.1Trif usion.... ............... .. ... ... ... ... ... ... .47

5.2Trip artas:Heapsort ...... ..... ... ............... .. ..47

5.2.1D´efini tions......................... ... ... ... .47

5.2.2Tripart as........ ..... ...... ... ... ... ... .. ..48

5.2.3Inser tiond'unnouvel´el´ement.. ............ ...........48

5.2.4Suppre ssiond'un´el´ementdutas........ ........... ....49

5.2.5Comple xit´edutripartas............... ...... ......49

5.3Trir apide.... ............... .. ... ... ... ... ... ... .49

5.3.1Coˆut. ............... .. ... ... ... ... ... ... .. .50

5.3.2M´edian eentempslin´eaire.... ...... .............. ...50

5.4Compl exit´edutri.................. ...... ........ ... .51

5.4.1Lesgrands th´eor` emes....... ......................51

5.4.2D´emons trationdesth´eor`emes.............. ........ ...52

5.4.3Peut-on atteindrelaborne?.. ....................... .54

5.5Exer cices..................... ... ... ... ... ... .. ..55

5.6R´ef ´erencesbibliographiques.............. ................57

6G raphes59

6.1D´efi nitions....................... ... ... ... ... .. ... 59

6.2Arbre s............. ... ... ... .. ... ... ... ... ... ... 59

6.2.1Caract´e risation............................. ... .59

6.2.2Parcours d'arbresbinaires... ..................... ...60

6.2.3Arbresb inairesderecherc he.................. ...... ..63

6.3Stru cturesdedonn´eespourlesgraphes... ...... ...............65

6.4Acce ssibilit´e............................ ... ... .. ... 69

6.4.1Rappel ssurlesrelationsbinai res..... ......... .........69

6.4.2Chemin sdanslesgraphes........ ......... ......... .70

6.4.3Fermet uretransitive.............. ................70

6.5Plus courtschemins .............. .................... 73

6.5.1D´efin itions........................ ... ... ... ..73

6.5.2Pr´es entationdespluscourtschemins....... ......... .....74

6.5.3Avecdes poidspositi fs...... ............ ...........74

6.5.4Chemin salg´ebriquesdanslesse mi-anneaux.................75

6.5.5Algorithm edeDijkstra......... ...... .............76

6.6Parcou rsenlargeur......... ..... ............... ... .. .78

6.7Parcou rsenprofondeur...... ..... .....................80

6.7.1Premi` ereversion................. ...............80

6.7.2Analysefi neduparcoursenprof ondeur... ...... ..........81

6.8Trit opologique.. .................... ... ... ... ... ... 82

6.9Forte connexit´e... .......................... ... .. ... 83

6.10Exer cices..................... ... ... ... ... .. ... ..83

6.11R´ef ´erencesbibliographiques............. .................88

7Tab lesdehachage89

7.1Rech ercheentable............... ...... ............ .. 89

7.2Table sdehachage....... ...... ............ ... .. ... ..89

7.3Colli sionss´epar´ees.......... .........................90

7.4Adre ssageouvert.......... .............. ... ... ... .. .91

7.5R´ef ´erencesbibliographiques.............. ................92

8A nalyseamortie93

8.1Compt eur................. ... ... ... ... ... .. ... ... 93

8.1.1M´etho dedesacomptes............ ......... ........93

8.1.2M´etho dedupotentiel........... ...... ............94

8.2Mallo cprimaire....... .................... ... ... .. ..94

8.2.1M´etho deglobale................. ............ .. .94

8.2.2M´etho dedesacomptes............ ......... ........94

8.2.3M´etho dedupotentiel........... ...... ............94

8.3Inse rtionETsuppression....... ...... ...................95

8.4Gest iondespartitions.... ........ .....................95

8.4.1Repr´e sentationenlisteschaˆın´ees............. ..... .....95

8.4.2Repr´ esentationenarbres....................... ....95

8.5R´ef ´erencesbibliographiques.............. ................96

9NP-Compl´etude97

9.1Probl `emesdeP.....................................97

9.1.1Pens´e edujour(PJ).......... ...... ......... .....97

9.1.2D´efini tion....................... ... ... ... ... .97

9.1.3Exempl es..................... ... ... ... ... .. .98

9.1.4Solution d'unprobl`eme..... ............ ...........99

9.2Probl `emesdeNP...................................99

9.2.1D´efini tion....................... ... ... .. ... ..99

9.2.2Probl`e mesNP-complets.............. ..............99

9.2.3Exempl esdeprobl`emesdansNP.......................100

9.2.4Probl`e mesded´ecisionvsoptimisation.. ...... ............100

9.2.5Exempl edeprobl`emesn'´etantp asforc´e mentdansNP...........100

9.2.6Probl` emespolynomiaux.............. ..............101

9.3M´e thodeder´eduction....... ...... ....................102

9.43-SAT ........... ... ... ... ... .. ... ... ... ... ... ..102

9.5Cliq ue................ .. ... ... ... ... ... ... .. ... .104

9.6Couve rtureparlessommets.......... ...... ........ ......105

9.7Cycl ehamiltonien.... .......................... ... ..106

9.8Colorat iondegraphes......... ..... ............... ... .106

9.8.1COLOR.. ............ .. ... ... ... ... ... ... .. .107

9.8.23-COLOR ............... ... .. ... ... ... ... ... .109

9.8.33-COLOR- PLAN..................... ... ... ... .. 110

9.9Exer cices..................... .. ... ... ... ... ... ..112

9.10R´ef ´erencesbibliographiques.............. ................114

10A lgorithmesd'approximation115

10.1D´efi nition..................... ... ... ... ... .. ... ..115

10.2Vert excover.......... .............. ... ... ... ... ... 115

10.2.1Version classique......... ....................... 115

10.2.2Version pond´er´ee........ ........................116

10.3Voyage urdecommerce:TSP... ..... .................... .116

10.3.1D´efini tion....................... ... ... ... ... .116

10.3.2Inappro ximabilit´edeTSP...........................117

10.3.32-approx imationdanslecaso`ucv´erifiel'in´egalit ´etriangul aire... ...117

10.4BinP acking:BP ................. ... ...... ... ... ... .118

10.4.1D´efini tion....................... ... ... ... ... .118

10.4.2NextFit ......... ........ ... ... ... ... ... .. ... 119

10.4.3DecFir stFit(DFF )............. ......... ........119

10.52-Part ition................... ... ... ... ... ... .. ... 120

10.5.1NP-compl ´etudeausensfaibleetausensfort......... ... ....120

10.5.2Approxi mationgloutonnes.................. .........120

10.5.3Une(1+ ?)-approximation....................... ... .121

10.5.4FPTASpou r2-Partition... ........ .................123

10.6Exe rcices.................... ... ... ... ... ... .. ... 125

10.7R´ef ´erencesbibliographiques.............. ................127

Pr´eface

Lestradi tionschangentetlecoursd'algon 'estplustoujourslem ercred i`alam ˆemeheure, lesensei gnantsrajeunissent,etlepolyse d´eboguegrˆaceauxgentils´etudiants,TD-menet enseignants. Doncvoicila nouvelleversi ondupol yremis`aneuf,toujourspou rsatisfairevotreenvi ede savoir.Biensˆurilr estesansnuld outedenombreus eserre ursgliss´eesdans cespages,me rcide mefaire partdevostrouvai llesparcou rrier´ electr onique`aAnne.Benoit@ens-lyon.fr.

Lyon,Juille t2007

AnneBenoit

Pr´efaced'YvesRobert

Cepolyc opi´erassemblelescoursettr avauxdirig´es(aveccorrig´ es)dumod uleAlgorithmique del'ENS Lyon.Al'origine pr´evupour lap remi`ereann´eeduMagist` ered'Informatique,l emodule s'int`egred´esormaisdanslatrois i`emeann´eedelaLicenced'In formatique .Etdir equepersonne nes'es trenducompteduc hangement! Celafait`ape inedixansq uej'en seignececours.Ad ´efautdech angerle contenu(pou r fairequoid'autr e?)oud'uti liserautrechosequeletableau et lacraie(idem?),jechangeles irr´esistiblestraitsd'humourquifonttoutlecharm edecess´eancesd uMercredi(l'horairene changepasnonplu s).Etj 'usetou teunebatteriedeTD- menandw omen,lesquelsont apport´e leurcontribut ionaufildesans,construisantouam´elioran tde ss´ean cesdetrav auxdirig´e s. Jelesr emercietou ssinc`erement,parordred'ap parition:Od ileMillet-Botta,TanguyRisset, AlainDarte,B runoDurand,Fr´e d´ericVivien,Jean -ChristopheDubacq,O livierBodini,Daniel

Hirschko

ff ,Mat thieuExbrayat,NatachaPort ier,EmmanuelHyon,EricThier ry,MichelMorv an etYvesC aniou. Sansaucunep ressionoupresque, YvesCaniouetEricThierry ontr ´eussi`asemotiver pourrassemb lerlesTD.L'ann´eepr´ec´edent e,j'avaisr assembl´e lescours.Enfin,quand ondit rassembler,c' estsurtoutlesgen tils´etudiants-scr ibesquiras semblent,entapotantd eleursdoigts agileslaquint essenc edenotreenseignementin´egalable. Cepolyc opi´eestleconcurrentleplu ss´erieu xduCorm endanslemonde,oudumoinsdans lesept i`emearrondissementdeLyon!Maisr enon¸cant`adefabuleuxdroitsd'auteur,l'´e quipe p´edagogique(c'estnous)ad´ec id´edemettrecetouvr age`alalibred isp ositiondesnombreux

´etudiantsassoi

ff ´esdesavoi r(c'es tvous).Enjoy!Etmer cidesignalererreu rsetomi ssionspar courrier´electronique` aYves.Robert@ens-lyon.fr.

Lyon,Mai2005

YvesRobert

Biblio

Voiciquelques pointeursbibliographiques(v oiraussilesr´ef´erencesdon n´ees`alafindechaque chapitre): IntroductiontoAlgorithmsdeT.H.C ormen,C .E. LeisersonetR.L.Rives t[2].L'ou - vrageder´e f´eren ceparexcellence,`aacheteretconserve rtoute savied'informaticien.Ilse murmurequ'unedeuxi`em e´editionestparue,a vecunauteurdeplus.Etunetradu ction fran¸caise. ComputersandIntractability, aGuide totheTheoryofNP-CompletenessdeM.R . GareyetD.S.Joh nson[5]. Essent ielle mentpoursonintrod uction`al aNP-compl´etudeau sensfort,etqu elquesjolies r´educ tions.Onrevienttoujours`as oncataloguedeprobl`em es

NP-complets.

Theartof Compute rPr ogramming,le stroistomes deKnuth[6],e tbientˆotquatr e,pour leursexercices incroyables

Sinon,j'aimebien:

-TypesdeDonn´eeset Algorit hmes,le livred eFroidevaux,Gaude letSori a[4],pourl'analyse finedesprob l`emesdet ri -leNP-com pendium,maintenusurleWeb(http://www.nada.kth.se/ viggo/problemlist/ compendium.html),pourl esr´esult atsd'appro ximation.Lelivrequicorrespond,Com- plexityandApproxim ation,de Ausiell oetal.[1]estvraimenttr` escompl et,ave cune bonneintroduc tionauxsch´emasd'approximation. -AlgorithmsandComplexity,le livred eWilf[12],dontlap remi`e re´edition,´e puis´ee, est wilf/.Une joliein troduction `alaNP -compl´ etude,avecunepreuveconciseduth´eor`emede Cook,pleind' algorithmes, del'h umour,dansunfichier.pdf`at ´el´echarge rabsolum ent -Comparedtowhat?:anintro ductio ntotheanalysiso fal gorith ms,le livred eRawlins[8], quicontien tunemined'exercicesor iginaux -IntroductiontoGraphTheory,de West[ 11],monlivrepr´ ef´er´ed egraphes

Enfin,deuxlivre splusdi

ffi ciles,`ar´eserver auxplus aventureux:celuideKozen[7],Thedesign andanalys isofalgorithms,c ontientlesnotesdecourset exercice s(certainscorr ig´es )d'uncours denive auavanc´edonn´e`a Cornell,etceluideVaz irani[10],Approximationalgorithms,don tle titrer´esumebi enlecontenu. 8

Chapitre1

Introduction:calculdex

n Cechap itresebasesurunpetitex emple facilepourd ´efinirl'al gorithm iqueetlanotionde complexit´ed'unprobl`eme. 1.1

Enonc´eduprobl`eme

On´etu dieleprobl`emeducalcul dex

n ,´e tantdonn´esxetn(n´etan tunentierpositi f). Soulignonsquexn'estpasn´ecess airemen tunnombre,ilpeuts'agird'unematriceoud'un polynˆome`aplusieursind ´eter min´ees:silamultiplicationau nsens,ladivisionn'enapas!

Onposey

0 =x,et onutili sel a"r`egledujeu"suivante: sij'aid ´ej`acalcul´ey 1 ,y 2 ,...,y i-1 jepeux calculery i commeproduit dedeuxr´esultatspr´ec ´edent sarbitraires: y i =y j ·y k

Lebu testd'atte indrex

n leplus vitepossible, i.e.detrouve r

Opt(n)=min{i/y

i =x n

1.2Algori thmena¨ıf

y i =y 0 ·y i-1 Onay n-1 =x n ,le coˆut estdoncden-1.

1.3M´ethode binaire

Ontrouv efacilementunalgori thmepluse

ffi cace: x n x n/2 ·x n/2 sinestpair, x ?n/2? ·x ?n/2?

·xsinestimpair.

Onpeut aussiformulerl 'algorithmedel afa¸consuivante.On´ecri tnen´ecr iturebinaire.Puis onre mplacechaque"1"parSXetchaq ue"0"parS,etonenl`e vel eprem ierSX( celuiq uiest`a gauche).Lemotobtenudonn eun efa¸cond ecalculerx n ,en traduis antSparl'op´erationmettre aucarr ´e(squaring),etXparl'op´erationmultiplierparx.Par exempl e,pourn=23( n=10111) , 9 lacha ˆıneobtenueestSXSSXSXS X,enenlevantlepremi erSX,onobti entSSXS XSX.O n calculedoncdansl'ordre x 2 ,x 4 ,x 5 ,x 10 ,x 11 ,x 22
,etx 23
Lac orrectiondel'algorithmesejust ifiefac ilement`apartirdespropri´et´ esdusy st`emebinaire.

Leco ˆutestde:

?logn?+ν(n)-1, o`uν(n)re pr´esentelenombrede1dansl'´ecritu rebinai reden.Bi ensˆur,commed anstout ouvraged'informat iquequiserespecte,leslogarithmessonten base2. Cettem´ethodebi nairen'estpasoptimale:parexe mpleavecn=15,on obt ien tlachaˆıne SXSXSX,d'o`u6m ultiplicationalorsq uee nremarquantque15=3·5,ona bes oind e2 multiplicationspourtrouvery=x 3 (y=(x·x)·x)pu isde3autrespou rcalcu ler x 15 =y 5 (on appliquelam´ethodebin aire:y 2 ,y 4 ,y 5

1.4M´ethode desfacteurs

Lam´ ethodedesfacteursestbas´e esurlafact orisationden: x n (x p q sipestleplu spetit facteurpremie rden(n=p×q), x n-1

·xsinestpr emier.

Exemple:x

15 =(x 3 5 =x 3 .(x 3 4 =.. .(5multip lication s). Remarque:Aveclespu issancesde 2,cettem´ethodeestidentique `alam´ et hodebinaire. Remarque:Cettem´ethoden' estpasoptimale,parexemplepou rn=33on a7m ult ipl ica- tionsaveclam ´ethodedesfac teurse tseulement6aveclam´etho debinaire . x 33
=(x 3 11 =x 3 .(x 3 10 =x 3 .((x 3 2 5 =x 3 .y.y 4 avecy=(x 3 2 x 33
=x.x 2 5 Remarque:Ilexis teuneinfinit´edenom brespourle squelslam´ethodedesfacte urses t meilleurequelam´ethodebinai re(prendr en=15·2 k ),et r´eciproque ment(prendren=33·2 k Arnaque:Ilfaut soulignerqu elecoˆutdelarecherch edelad´ec ompositi ondenenfacte urs premiersn'estpasprisencom ptedansnotreformu lation.C 'estpourtantn ´ecess airepourquan- tifiercorrectemen tlecoˆutdelam´ethodedesfacteurs.Le probl` emeestqu'onnesait pas,`ac e jour,trouverla d´ecompositionentemp spolynom ialenn.Ce probl`e meestNP-complet(notions deNP-com pl´etudedanslasuiteducours).

1.5ArbredeK nuth

Uneautr em´ethodecons iste`autiliserl'arbredeKnuth,re pr´esent´eFigure1.1.Lechemin menantdelaracined el'arbr e`anindiqueunes´equenced' exposantsp ermettantdecalculerx n defa¸con e ffi cace. 10 Fig.1.1:Lesse ptpre miersniveauxd el'arbredeKnuth. Constructiondel'arbreLe(k+1)-`emeniveaudel'arbre estd´efini`apart irdeskpremiers niveauxdelafa¸consuiv ante:p rendre chaquenoeudnduk-`emeniveau,degau che`adroite,et lesreliera veclesnoeuds n+1,n+a 1 ,n+a 2 ,...,n+a k-1 =2n (danscetordre) ,o`u1,a 1 ,...,a k-1quotesdbs_dbs45.pdfusesText_45

[PDF] [PDF] Algorithmique I - École normale supérieure de Lyon