Algorithmique-CoursetTravauxDirig sEcoleNormaleSup rieuredeLyonR dactionEtudiants-scribes,MIM2003et2004CoursYvesRobertTravauxDirig sYvesCaniouetEricThierry2003-2004-20052Tabledesmati res1Introduction:calculdexn111.1 nonc duprobl me..................................111.2Algorithmena f.....................................111.3M thodebinaire....................................111.4M thodedesfacteurs..................................121.5ArbredeKnuth.....................................121.6R sultatssurlacomplexit ..............................131.7Exercices........................................141.8R f rencesbibliographiques..............................172Diviserpourr gner192.1AlgorithmedeStrassen.................................192.2Produitdedeuxpolyn mes..............................202.3Mastertheorem.....................................222.4R solutiondesr currences...............................232.4.1R solutiondesr currenceshomog nes....................232.4.2R solutiondesr currencesavecsecondmembre...............232.5Multiplicationetinversiondematrices........................242.6Exercices........................................252.7R f rencesbibliographiques..............................333Programmationdynamique353.1Pi cesdeMonnaies...................................353.2Leprobl medusac dos...............................363.2.1Englouton...................................363.2.2Parprogrammationdynamique........................363.3Quelquesexemplesdeprogrammationdynamique..................373.3.1Cha nesdematrices..............................373.3.2Pluslonguesous-suite.............................383.3.3Locationdeskis................................403.4Exercices........................................423.5R f rencesbibliographiques..............................504Algorithmesgloutons514.1Exempledugymnase..................................514.2Coloriagedungraphe.................................524.2.1Algorithmeglouton1..............................534.2.2Algorithmeglouton2..............................534.2.3Graphedintervalles..............................5334.2.4AlgorithmedeBrelaz..............................544.3Th oriedesmatro des.................................544.3.1Matro des....................................554.3.2Algorithmeglouton...............................554.4Ordonnancement....................................564.5Exercices........................................574.6R f rencesbibliographiques..............................625Tri635.1Trirapide........................................635.1.1Co t.......................................635.1.2M dianeentempslin aire...........................635.2Trifusion........................................645.3Tripartas:Heapsort.................................655.3.1D nitions...................................655.3.2Tripartas....................................655.3.3Insertiondunnouvel l ment.........................665.3.4Suppressiondun l mentdutas.......................665.4Complexit dutri....................................675.4.1Lesgrandsth or mes.............................675.4.2D monstrationdesth or mes.........................675.4.3Peut-onatteindrelaborne?..........................695.5Exercices........................................705.6R f rencesbibliographiques..............................856Graphes876.1D nitions........................................876.2Arbres..........................................876.2.1Caract risation.................................876.2.2Parcoursdarbresbinaires...........................886.2.3Arbresbinairesderecherche..........................916.3Structuresdedonn espourlesgraphes........................936.4Accessibilit .......................................976.4.1Rappelssurlesrelationsbinaires.......................976.4.2Cheminsdanslesgraphes...........................986.4.3Fermeturetransitive..............................986.5Pluscourtschemins..................................1016.5.1D nitions...................................1016.5.2Pr sentationdespluscourtschemins.....................1016.5.3Avecdespoidspositifs.............................1026.5.4Cheminsalg briquesdanslessemi-anneaux.................1026.5.5AlgorithmedeDijkstra.............................1036.6Parcoursenlargeur...................................1056.7Parcoursenprofondeur.................................1076.7.1Premi reversion................................1076.7.2Analyseneduparcoursenprofondeur...................1086.8Tritopologique.....................................1106.9Forteconnexit .....................................1106.10Exercices........................................1106.11R f rencesbibliographiques..............................11747Tablesdehachage1197.1Rechercheentable...................................1197.2Tablesdehachage...................................1197.3Collisionss par es...................................1207.4Adressageouvert....................................1217.5R f rencesbibliographiques..............................1228Analyseamortie1238.1Compteur........................................1238.1.1M thodedesacomptes.............................1238.1.2M thodedupotentiel.............................1248.2Mallocprimaire.....................................1248.2.1M thodeglobale................................1248.2.2M thodedesacomptes.............................1248.2.3M thodedupotentiel.............................1248.3InsertionETsuppression................................1258.4Gestiondespartitions.................................1258.4.1Repr sentationenlistescha n es.......................1258.4.2Repr sentationenarbres............................1258.5R f rencesbibliographiques..............................1269NP-Compl tude1279.1PversusNP.......................................1279.23-SAT..........................................1279.3Clique..........................................1299.4Couvertureparlessommets..............................1309.5Circuithamiltonien...................................1309.6Colorationdegraphes.................................1319.6.1COLOR.....................................1319.6.23-COLOR....................................1339.6.33-COLOR-PLAN................................1349.7Exercices........................................1379.8R f rencesbibliographiques..............................14310Algorithmesdapproximation14510.1D nition........................................14510.2Vertexcover.......................................14510.2.1Versionclassique................................14510.2.2Versionpond r e................................14610.3Voyageurdecommerce:TSP.............................14710.3.1D nition....................................14710.3.2Inapproximabilit deTSP:..........................14710.3.32-approximationdanslecaso cv rielin galit triangulaire.......14710.4BinPacking:BP....................................14810.4.1D nition....................................14810.4.2NextFit.....................................14910.4.3DecFirstFit..................................15010.52-Partition........................................15010.5.1NP-compl tudeausensfaibleetausensfort................15010.5.2Approximationgloutonnes...........................151510.5.3Une(1+!)-approximation...........................15210.5.4FPTASpour2-Partition............................15410.6Exercices........................................15610.7R f rencesbibliographiques..............................1586Pr faceCepolycopi rassemblelescoursettravauxdirig s(aveccorrig s)dumoduleAlgorithmiquedelENSLyon.Aloriginepr vupourlapremi reann eduMagist redInformatique,lemodulesint gred sormaisdanslatroisi meann edelaLicencedInformatique.Etdirequepersonnenesestrenducompteduchangement!Celafait peinedixansquejenseignececours.Ad fautdechangerlecontenu(pourfairequoidautre?)oudutiliserautrechosequeletableauetlacraie(idem?),jechangelesirr sistiblestraitsdhumourquifonttoutlecharmedecess ancesduMercredi(lhorairenechangepasnonplus).EtjusetouteunebatteriedeTD-menandwomen,lesquelsontapport leurcontributionauldesans,construisantouam liorantdess ancesdetravauxdirig s.Jelesremercietoussinc rement,parordredapparition:OdileMillet-Botta,TanguyRisset,AlainDarte,BrunoDurand,Fr d ricVivien,Jean-ChristopheDubacq,OlivierBodini,DanielHir-schko,MatthieuExbrayat,NatachaPortier,EmmanuelHyon,EricThierry,MichelMorvanetYvesCaniou.Sansaucunepressionoupresque,YvesCaniouetEricThierryontr ussi semotiverpourrassemblerlesTD.Lann epr c dente,javaisrassembl lescours.Enn,quandonditrassem-bler,cestsurtoutlesgentils tudiants-scribesquirassemblent,entapotantdeleursdoigtsagileslaquintessencedenotreenseignementin galable.Cepolycopi estleconcurrentlepluss rieuxduCormendanslemonde,oudumoinsdanslesepti mearrondissementdeLyon!Maisrenon ant defabuleuxdroitsdauteur,l quipep dagogique(cestnous)ad cid demettrecetouvrage lalibredispositiondesnombreux tudiantsassoi sdesavoir(cestvous).Enjoy!Etmercidesignalererreursetomissionsparcourrier lectronique [email protected],Mai2005YvesRobertBiblioVoiciquelquespointeursbibliographiques(voiraussilesr f rencesdonn es landechaquechapitre):IntroductiontoAlgorithmsdeT.H.Cormen,C.E.LeisersonetR.L.Rivest[2].Lou-vrageder f renceparexcellence, acheteretconservertoutesaviedinformaticien.Ilsemurmurequunedeuxi me ditionestparue,avecunauteurdeplus.Etunetraductionfran aise.ComputersandIntractability,aGuidetotheTheoryofNP-CompletenessdeM.R.GareyetD.S.Johnson[5].Essentiellementpoursonintroduction laNP-compl tudeausensfort,etquelquesjoliesr ductions.Onrevienttoujours soncataloguedeprobl mesNP-complets.7TheartofComputerProgramming,lestroistomesdeKnuth[6],etbient tquatre,pourleursexercicesincroyables8Sinon,jaimebien:TypesdeDonn esetAlgorithmes,lelivredeFroidevaux,GaudeletSoria[3],pourlanalysenedesprobl mesdetrileNP-compendium,maintenusurleWeb(http://www.nada.kth.se/~viggo/problemlist/compendium.html),pourlesr sultatsdapproximation.Lelivrequicorrespond,ComplexityandApproximation,deAusielloetal.[1]estvraimenttr scomplet,avecunebonneintro-ductionauxsch masdapproximation.AlgorithmsandComplexity,lelivredeWilf[12],dontlapremi re dition, puis e,estdisponiblelibrement lurlhttp://www.cis.upenn.edu/~wilf/.Unejolieintroduction laNP-compl tude,avecunepreuveconciseduth or medeCook,pleindalgorithmes,delhumour,dansunchier.pdf t l chargerabsolumentComparedtowhat?:anintroductiontotheanalysisofalgorithms,lelivredeRawlins[8],quicontientuneminedexercicesoriginauxIntroductiontoGraphTheory,deWest[11],monlivrepr f r degraphesEnn,deuxlivresplusdiciles, r serverauxplusaventureux:celuideKozen[7],Thedesignandanalysisofalgorithms,contientlesnotesdecoursetexercices(certainscorrig s)duncoursdeniveauavanc donn Cornell,etceluideVazirani[10],Approximationalgorithms,dontletitrer sumebienlecontenu.910Chapitre1Introduction:calculdexn1.1 nonc duprobl meOn tudieleprobl meducalculdexn, tantdonn sxetn(n tantunentierpositif).Soulignonsquexnestpasn cessairementunnombre,ilpeutsagirdunematriceoudunpolyn me plusieursind termin es:silamultiplicationaunsens,ladivisionnenapas!Onposey0=x,etonutiliselar gledujeusuivante:sijaid j calcul y1,y2,...,yi1,jepeuxcalculeryicommeproduitdedeuxr sultatspr c dentsarbitraires:yi=yj yk,avec0dj,kdi1Lebutestdatteindrexnleplusvitepossible,i.e.detrouverOpt(n)=min{i/yi=xn}.1.2Algorithmena fConsid ronslalgorithmena fsuivant:yi=y0 yi1Onayn1=xn,leco testdoncden1.1.3M thodebinaireOntrouvefacilementunalgorithmeplusecace:xn=!xn/2 xn/2sinestpair,x"n/2# x"n/2# xsinestimpair.Onpeutaussiformulerlalgorithmedelafa onsuivante.On critnen criturebinaire.Puisonremplacechaque1parSXetchaque0parS,etonenl velepremierSX(celuiquiest gauche).Lemotobtenudonneunfa ondecalculerxn,entraduisantSparlop rationmettreaucarr (squaring),etXparlop rationmultiplierparx.Parexemple,pourn=23,lacha neobtenueestSXSSXSXSX,enenlevantlepremierSX,onobtientSSXSXSX.Oncalculedoncdanslordrex2,x4,x5,x10,x11,x22,etx23.Lacorrectiondelalgorithmesejustiefacilement partirdespropri t sdusyst mebinaire.Leco testde:#logn$+ (n)1,11o (n)repr sentelenombrede1dansl criturebinaireden.Biens r,commedanstoutouvragedinformatiquequiserespecte,leslogarithmessontenbase2.Cettem thodebinairenestpasoptimale:parexempleavecn=15,onobtientlacha neSXSXSX,do 6multiplicationalorsqueenremarquantque15=3 5,onabesoinde2multiplicationspourtrouvery=x3(y=(x x) x)puisde3autrespourcalculerx15=y5(onappliquelam thodebinaire:y2,y4,y5).1.4M thodedesfacteursLam thodedesfacteursestbas esurlafactorisationden:xn=!(xp)qsipestlepluspetitfacteurpremierden,xn1 xsinestpremier.Remarque:Aveclespuissancesde2,cettem thodeestidentique lam thodebinaire.Remarque:Cettem thodenestpasoptimale,parexemplepourn=33ona7multiplicationsaveclam thodedesfacteursetseulement6aveclam thodebinaire.Remarque:Ilexisteuneinnit denombrespourlesquelslam thodedesfacteursestmeilleurequelam thodebinaire(prendren=15 2k),etr ciproquement(prendren=33 2k).Ilfautsoulignerqueleco tdelarecherchedelad compositiondenenfacteurspremiersnestpasprisencomptedansnotreformulation.Cestpourtantn cessairepourquantiercor-rectementleco tdelam thodedesfacteurs.Leprobl meestquonnesaitpas, cejour,trouverlad compositionentempspolynomialenn.1.5ArbredeKnuthUneautrem thodeconsiste utiliserlarbredeKnuth,repr sent Figure1.1.Lecheminmenantdelaracinedelarbre nindiqueunes quencedexposantspermettantdecalculerxndefa onecace.123571419212810112213232615253020406918273612244848161733343264Fig.1.1LesseptpremiersniveauxdelarbredeKnuth.12ConstructiondelarbreLe(k+1)- meniveaudelarbreestd ni partirdeskpremiersniveauxdelafa onsuivante:prendrechaquenSudnduk- meniveau,degauche droite,etlesrelieraveclesnSudsn+1,n+a1,n+a2,...,n+ak1=2n(danscetordre),o 1,a1,...,ak1=nrepr sentelechemindelaracine n.OnnajouterapasunnSudsiceluiciestd j pr sentdanslarbre.Voiciquelquesstatistiquesdues Knuth:lespluspetitsnombrespourlesquelslam thodenestpasoptimalesontn=77,154,233.Lepluspetitnpourlequellam thodedelarbreestsup rieure lafois lam thodebinaireet celledesfacteursestn=23.Lepluspetitnpourlequellam thodedelarbreestmoinsbonnequecelledesfacteursestn=19879=103 193;detelscassontrares:pournd100000,larbrebatlesfacteurs88803fois,faitmatchnul11191foisetperdseulement6fois.1.6R sultatssurlacomplexit Th or me1.Opt(n)e&lognPreuve.Soitunalgorithmepermettantdecalculerlespuissancesdex,avecpourtouti,yi=x (i).Montronsparr currenceque (i)d2i.Pourlabase,onabieny0=xdo 1d20=1.Soitiunentier,ilexistejetk(j,k<k)telsqueyi=yj yk.Ona (i)= (j)+ (k),parlhypoth sedinduction, (j)d2jd2i1etdem me (k)d2i1.Onend duitdoncque (i)d2i1+2i1=2i.Intuitivement,lapreuveexprimequonnepeutpasfairemieuxquedoublerlexposantobtenu chaque tapedelalgorithme.Gr ceauth or mepr c dent,et l tudedelam thodebinaire,dontlenombred tapesestinf rieur 2logn,onaler sultatsuivant:1dlimn Opt(n)lognd2.Th or me2.limn Opt(n)logn=1Preuve.Lid eestdam liorerlam thodebinaireenappliquantcettem thodeenbasem.Posonsm=2k,o kserad termin plustard,et crivonsnenbasem:n= 0mt+ 1mt1+ + t,o chaque iestunchireenbasem,donccomprisentre0etm1.Puisoncalculetouslesxd,1dddm1)parlam thodena ve,cequirequiertm2multiplications.Enfait,onnapasforc mentbesoindetoutescesvaleurs,seulementdesx i,maiscommeonlescalculeauvolonpeutlescalculertoussanssurco t.Ensuiteoncalculesuccessivement:y1=(x 0)m x 1y2=(y1)m x 2=x( 0m+ 1)m+ 2...yt=(yt1)m x t=xn13Oneectuepourchaquelignek+1op rations(k l vationsaucarr pourcalculerlapuissancem- me,etunemultiplication),do leco ttotalducalculdexn:t (k+1)+(m2).Enrempla antmpar2k,ettpar#logmn$,ontrouveunco ttotalde#logmn$(k+1)+2k2dlog2nk(k+1)+2k.Ilsutdoncdeprendrektendantverslinni,pourque(k+1)/ktendevers1,ettelque2k=o(logn),parexemplek=#1/2log(logn)$(onauraalors2kdlogn).1.7ExercicesExercice1.7.1.LegrandsautLeprobl meestded terminer partirdequel tagedunimmeuble,sauterparunefen treestfatal.Vous tesdansunimmeuble n tages(num rot sde1 n)etvousdisposezdek tudiants.Ilnyaquuneop rationpossiblepourtestersilahauteurdun tageestfatale:fairesauterun tudiantparlafen tre.Silsurvit,vouspouvezler utiliserensuite,sinonvousnepouvezplus.Vousdevezproposerunalgorithmepourtrouverlahauteur partirdelaquelleunsautestfatal(renvoyern+1sionsurvitencoreensautantdun- me tage)enfaisantleminimumdesauts.1-Sike&log2(n),proposerunalgorithmeenO(log2(n))sauts.2-Sik<&log2(n),proposerunalgorithmeenO(k+n2k1)sauts.3-Sik=2,proposerunalgorithmeenO(n)sauts.Correction.1-Lacomplexit enO(log2(n))quiestindiqu enousaiguilleversunedichotomie.Eneet,ensupposantquelonake&log2(n),onobtientler sultatsurles tagesdei jenjetantun tudiantdepuislen me tage,o n=ji/2,puisenit rantleproc d surles tagesdei n1silachute t fatale,etsurles tagesden jdanslecascontraire.Lam thodedichotomiquenousgarantitalorsquelonobtientlebonr sultat(lorsquilneresteplusquunseul tage,cest- -direlorsqueloncalculepourles tagesdei=j),etceavecunecomplexit logarithmiquedanslepiredescas.2-Puisquicionnedisposequedek<&log2(n) tudiants,onnepeutpasappliquerdirectementlam thodedichotomiquepropos epr c demment.Cependant,onvarem dierauprobl medemani resimpleenappliquantunerecherchedichotomiqueaveck1 tudiants,demani re d limiterunintervalled tagesdanslequelsetrouvel tagerecherch .Onsesertalorsdudernier tudiantrestantpourparcourirlintervalledefa onlin aire,doncenlejetantdechaque tageenpartantduplusbasdelintervalle,jusquauplushaut.Apr savoirjet lesk1premiers tudiants,silonnapasencoretrouv lebon tage,ilresteexactementn/2k1 tagesdanslintervallederecherche,do unecomplexit danslepiredescasenO(k+n/2k1)sauts.3-Danslecasparticuliero lonak=2,onneveutpasavoir testerchaque tagedefa onlin aire,cestpourquoionvareprendre notrecomptelesid espr c dentes,etnotammentcellequiconsiste d limiterunintervallederecherche.Nousd couponsdonclensembledes tages14entranchesden tages,avantdejeterlepremier tudiantdechacundes tagesded butdetranche.Lorsquel tudiantylaissesapeau,onseram neaudernier tagentest quinesoitpasfatal,etonnaplusqu parcourirdemani relin airelintervalleallantdel tagen+1 l tagefataltrouv pr c demment.Onaainsideuxs riesdessaisenO(n),etdoncunecomplexit naledanslepiredescas galementenO(n)sauts.Exercice1.7.2.CherchezlastarDansungroupedenpersonnes(num rot esde1 npourlesdistinguer),unestarestquelquunquineconnaitpersonnemaisquetouslesautresconnaissent.Pourd masquerunestar,silenexisteune,vousavezjusteledroitdeposerdesquestions, nimportequelindividuidugroupe,dutypeest-cequevousconnaissezj?(not i j?),onsupposequelesindividusr pondentlav rit .Onveutunalgorithmequitrouveunestar,silenexiste,ousinonquigarantitquilnyapasdestardanslegroupe,enposantlemoinsdequestionspossibles.1-Combienpeut-ilyavoirdestarsdanslegroupe?2-Ecrirelemeilleuralgorithmequevouspouvezetdonnersacomplexit ennombredequestions(onpeutyarriverenO(n)questions).3-Donneruneborneinf rieuresurlacomplexit (ennombredequestions)detoutalgorithmer solvantleprobl me.((Dicile)prouverquelameilleureborneinf rieurepourceprobl meest3n#log2(n)$3).Correction.1-Ilnepeutyavoirquuneseulestardanslegroupe,puisquesilyenaune,elleneconnaitpersonne,etdonctouslesautressontinconnusdaumoinsunepersonne,etnepeuventdonc treeuxaussidesstars.2-Lorsquoneectueletest&&i j?&&,cest- -direlorsqueloncherche savoirsilapersonneiconna tlapersonnej,onobtientler sultatsuivant:sioui,alorsinestpasunestar,maisjenestpotentiellementune.sinon,alorsjnestpasunestar,maisienestpotentiellementune.Lalgorithmeconsistealorsaparcourirletableaudespersonnesunefois,engardantenmemoire chaqueinstantlapersonneiquiestjusquicireconnuepartous,tandisquauj metest,touteslesautrespersonnes,dontlesindicessontlesk<j(aveck=i,biens r)nepeuventpasdesstars.Cetalgorithmes critdoncdelamani resuivante:i 1etj 2tantquejdnfaire!si&&i j&&alorsfairej j+1sinonfairei jetj j+1istar vraietk 1tantque(kdnetistar)faire!si&&k i&&alorsfairek k+1sinonfaireistar fauxsiistaralorsfaireretourneriestlastarsinonfaireretournerilnyapasdestar3-Enobservantnotrealgorithme,onconstatequelonpeututilisercommeborneinf rieurepourlenombredequestionslavaleur3n2,puisquelonfaiticideuxbouclessurn1personnes15etunebouclesurlensembledesnpersonnes.Pourcequiestdelaborneinf rieureoptimale,ilsagitdunequestiondicile,dontonnexpliciterapaslasolutionici.Exercice1.7.3.BricolageDansuneboite outils,vousdisposezden crousdediam trestousdi rentsetdesnboulonscorrespondants.Maistoutestm lang etvousvoulezappareillerchaque crouavecleboulonquiluicorrespond.Lesdi rencesdediam treentreles croussonttellementminimesquilnestpaspossibleded terminer lSilnusiun crouestplusgrandquunautre.Ilenvadem meaveclesboulons.Parcons quent,leseultypedop rationautoris consiste essayerun crouavecunboulon,cequipeutamenertroisr ponsespossibles:soitl croueststrictementpluslargequeleboulon,soitileststrictementmoinslarge,soitilsontexactementlem mediam tre.1-EcrireunalgorithmesimpleenO(n2)essaisquiappareillechaque crouavecsonboulon.2-Supposonsquaulieudevouloirappareillertouslesboulonset crous,vousvoulezjustetrouverlepluspetit crouetlebouloncorrespondant.Montrerquevouspouvezr soudreceprobl meenmoinsde2n2essais.3-Prouverquetoutalgorithmequiappareilletousles crousavectouslesboulonsdoiteectuer&(nlogn)essaisdanslepiredescas.Probl meouvert:proposerunalgorithmeeno(n2)essaispourr soudreceprobl me.Correction.1-AlgorithmePourappareillerlesboulonsetles crous,ilsutdeprendreunboulonarbitrairement,deletesteravectousles crous.Ontrouvealorslebonenauplusntestsetilsutalorsderecommenceravectouslesautresboulons.Onobtientdoncler sultatenauplusn(n1)2=O(n2)tests.2-Lepluspetit crouetsonboulonLeprincipeestdenum roterlesboulonsetles crousde1 n,demani rearbitraire,etdefaireprogresserdescompteurs(parexempleietj)pourmarquerleminimuncourantdanslunedescat gories,etlastructureencoursdetestdanslautre.d butwhile(idn)&&(jdn)dosii=j=nalorssortirdelaboucle;siecrou.i=boulon.jalorssensouveniretfairei:=i+1;siecrou.i<boulon.jalorsj:=j+1;min=ecrou;siecrou.i>boulon.jalorsi:=i+1;min=boulon;nAlandecetteboucle,simin= crou,l crouiestlepluspetit.simin=boulon,leboulonjestlepluspetit.Etdanslesdeuxcas,onsaitd j quelestl l mentquicorrespond:eneet,lecompteurdelautrecat gorievautn+1(oundansuncassp cial),etonadoncd j rencontr leminimum.laseuleraisonpossiblepourlaquelleilnapas t conserv estdoncquilait t test aveclautreminimum.Pourlecassp cialoui=j=n,lederniertestestinutile:eneet,onsaitquelundesdeux,estminimum,etqueunefoisleboulonminimumatteind,jrestexe:do leboulonnestminimum,etsonhomologueasoitd j t trouv ,soitestl crourestant.16Cetteboucleeectuedoncauplus2n2tests.3-Algorithmedappareillagedes crousetdeleurboulonOnnotef(T)lenombredefeuillesdelarbreeth(T)sahauteur.SiTestunarbreternaireh(T)e&log3f(T).ParinductionsurlahauteurdeT:Pourh(T)=0larbre unefeuilledonconabienh(T)e&log3f(T)&.Pourh(T)>0unarbreternaireatroisls,lelsgauchefg,lelscentralfc,etlelsdroitfddehauteurinf rieur h(T)1.Onsupposequeh(T)e&log3f(T)estvraipourh(T)dkk tantx onveutd montrerquecettepropri t estvraiaussipourh(T)=k+1.Lesfeuillesdunarbresontaussicellesdesesls.Donc!"#$f"f&$f"f'$f'f&f"f($f(f"#$#!"#$)1f(T)=f(fd)+f(fg)+f(fd)deplus:h(T)dh(fd)+1h(T)dh(fg)+1h(T)dh(fc)+1orparinductioncommeh(T)=k+1,h(fg)dk,h(fg)dk,eth(fg)dkona:k=h(fc)d&log3f(fc)h(fd)d&log3f(fd)h(fg)d&log3f(fg)Doncf(fc),f(fg),f(fd)d3kor:f(T)=f(fc)+f(fg)+f(fd)donc:f(T)d3 3k=3k+1Do onend duitque:h(T)elog3f(T)Ilya!nagencementsboulons- crouspossiblesdonclarbreded cision,quiestternaireapourhauteur:log3!n
Algorithmique et Travaux Dirigés
1/159
100%
Rendu du PDF...