Algorithmique et Travaux Dirigés

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.2Coloriaged’ungraphe.................................524.2.1Algorithmeglouton1..............................534.2.2Algorithmeglouton2..............................534.2.3Graphed’intervalles..............................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éfinitions...................................655.3.2Tripartas....................................655.3.3Insertiond’unnouvelélément.........................665.3.4Suppressiond’uné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éfinitions........................................876.2Arbres..........................................876.2.1Caractérisation.................................876.2.2Parcoursd’arbresbinaires...........................886.2.3Arbresbinairesderecherche..........................916.3Structuresdedonnéespourlesgraphes........................936.4Accessibilité.......................................976.4.1Rappelssurlesrelationsbinaires.......................976.4.2Cheminsdanslesgraphes...........................986.4.3Fermeturetransitive..............................986.5Pluscourtschemins..................................1016.5.1Définitions...................................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.2Analysefineduparcoursenprofondeur...................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..............................14310Algorithmesd’approximation14510.1Définition........................................14510.2Vertexcover.......................................14510.2.1Versionclassique................................14510.2.2Versionpondérée................................14610.3Voyageurdecommerce:TSP.............................14710.3.1Définition....................................14710.3.2InapproximabilitédeTSP:..........................14710.3.32-approximationdanslecasoùcvérifiel’inégalitétriangulaire.......14710.4BinPacking:BP....................................14810.4.1Définition....................................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)dumoduleAlgorithmiquedel’ENSLyon.Al’origineprévupourlapremièreannéeduMagistèred’Informatique,lemodules’intègredésormaisdanslatroisièmeannéedelaLicenced’Informatique.Etdirequepersonnenes’estrenducompteduchangement!Celafaitàpeinedixansquej’enseignececours.Adéfautdechangerlecontenu(pourfairequoid’autre?)oud’utiliserautrechosequeletableauetlacraie(idem?),jechangelesirrésistiblestraitsd’humourquifonttoutlecharmedecesséancesduMercredi(l’horairenechangepasnonplus).Etj’usetouteunebatteriedeTD-menandwomen,lesquelsontapportéleurcontributionaufildesans,construisantouaméliorantdesséancesdetravauxdirigés.Jelesremercietoussincèrement,parordred’apparition:OdileMillet-Botta,TanguyRisset,AlainDarte,BrunoDurand,FrédéricVivien,Jean-ChristopheDubacq,OlivierBodini,DanielHir-schkoff,MatthieuExbrayat,NatachaPortier,EmmanuelHyon,EricThierry,MichelMorvanetYvesCaniou.Sansaucunepressionoupresque,YvesCaniouetEricThierryontréussiàsemotiverpourrassemblerlesTD.L’annéeprécédente,j’avaisrassemblélescours.Enfin,quandonditrassem-bler,c’estsurtoutlesgentilsétudiants-scribesquirassemblent,entapotantdeleursdoigtsagileslaquintessencedenotreenseignementinégalable.CepolycopiéestleconcurrentleplussérieuxduCormendanslemonde,oudumoinsdansleseptièmearrondissementdeLyon!Maisrenonçantàdefabuleuxdroitsd’auteur,l’équipepédagogique(c’estnous)adécidédemettrecetouvrageàlalibredispositiondesnombreuxétudiantsassoiffésdesavoir(c’estvous).Enjoy!Etmercidesignalererreursetomissionsparcourrierélectroniqueà[email protected],Mai2005YvesRobertBiblioVoiciquelquespointeursbibliographiques(voiraussilesréférencesdonnéesàlafindechaquechapitre):IntroductiontoAlgorithmsdeT.H.Cormen,C.E.LeisersonetR.L.Rivest[2].L’ou-vragederéférenceparexcellence,àacheteretconservertoutesavied’informaticien.Ilsemurmurequ’unedeuxiè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,j’aimebien:–TypesdeDonnéesetAlgorithmes,lelivredeFroidevaux,GaudeletSoria[3],pourl’analysefinedesproblèmesdetri–leNP-compendium,maintenusurleWeb(http://www.nada.kth.se/~viggo/problemlist/compendium.html),pourlesrésultatsd’approximation.Lelivrequicorrespond,ComplexityandApproximation,deAusielloetal.[1]estvraimenttrèscomplet,avecunebonneintro-ductionauxschémasd’approximation.–AlgorithmsandComplexity,lelivredeWilf[12],dontlapremièreédition,épuisée,estdisponiblelibrementàl’urlhttp://www.cis.upenn.edu/~wilf/.UnejolieintroductionàlaNP-complétude,avecunepreuveconciseduthéorèmedeCook,pleind’algorithmes,del’humour,dansunfichier.pdfàtéléchargerabsolument–Comparedtowhat?:anintroductiontotheanalysisofalgorithms,lelivredeRawlins[8],quicontientunemined’exercicesoriginaux–IntroductiontoGraphTheory,deWest[11],monlivrepréférédegraphesEnfin,deuxlivresplusdifficiles,àréserverauxplusaventureux:celuideKozen[7],Thedesignandanalysisofalgorithms,contientlesnotesdecoursetexercices(certainscorrigés)d’uncoursdeniveauavancédonnéàCornell,etceluideVazirani[10],Approximationalgorithms,dontletitrerésumebienlecontenu.910Chapitre1Introduction:calculdexn1.1ÉnoncéduproblèmeOnétudieleproblèmeducalculdexn,étantdonnésxetn(nétantunentierpositif).Soulignonsquexn’estpasnécessairementunnombre,ilpeuts’agird’unematriceoud’unpolynômeàplusieursindéterminées:silamultiplicationaunsens,ladivisionn’enapas!Onposey0=x,etonutilisela“règledujeu”suivante:sij’aidéjàcalculéy1,y2,...,yi−1,jepeuxcalculeryicommeproduitdedeuxrésultatsprécédentsarbitraires:yi=yj·yk,avec0≤j,k≤i−1Lebutestd’atteindrexnleplusvitepossible,i.e.detrouverOpt(n)=min{i/yi=xn}.1.2AlgorithmenaïfConsidéronsl’algorithmenaïfsuivant:yi=y0·yi−1Onayn−1=xn,lecoûtestdoncden−1.1.3MéthodebinaireOntrouvefacilementunalgorithmeplusefficace:xn=!xn/2·xn/2sinestpair,x"n/2#·x"n/2#·xsinestimpair.Onpeutaussiformulerl’algorithmedelafaçonsuivante.Onécritnenécriturebinaire.Puisonremplacechaque“1”parSXetchaque“0”parS,etonenlèvelepremierSX(celuiquiestàgauche).Lemotobtenudonneunfaçondecalculerxn,entraduisantSparl’opérationmettreaucarré(squaring),etXparl’opérationmultiplierparx.Parexemple,pourn=23,lachaîneobtenueestSXSSXSXSX,enenlevantlepremierSX,onobtientSSXSXSX.Oncalculedoncdansl’ordrex2,x4,x5,x10,x11,x22,etx23.Lacorrectiondel’algorithmesejustifiefacilementàpartirdespropriétésdusystèmebinaire.Lecoûtestde:#logn$+ν(n)−1,11oùν(n)représentelenombrede1dansl’écriturebinaireden.Biensûr,commedanstoutouvraged’informatiquequiserespecte,leslogarithmessontenbase2.Cetteméthodebinairen’estpasoptimale:parexempleavecn=15,onobtientlachaîneSXSXSX,d’où6multiplicationalorsqueenremarquantque15=3·5,onabesoinde2multiplicationspourtrouvery=x3(y=(x·x)·x)puisde3autrespourcalculerx15=y5(onappliquelaméthodebinaire:y2,y4,y5).1.4MéthodedesfacteursLaméthodedesfacteursestbaséesurlafactorisationden:xn=!(xp)qsipestlepluspetitfacteurpremierden,xn−1·xsinestpremier.Remarque:Aveclespuissancesde2,cetteméthodeestidentiqueàlaméthodebinaire.Remarque:Cetteméthoden’estpasoptimale,parexemplepourn=33ona7multiplicationsaveclaméthodedesfacteursetseulement6aveclaméthodebinaire.Remarque:Ilexisteuneinfinitédenombrespourlesquelslaméthodedesfacteursestmeilleurequelaméthodebinaire(prendren=15·2k),etréciproquement(prendren=33·2k).Ilfautsoulignerquelecoûtdelarecherchedeladécompositiondenenfacteurspremiersn’estpasprisencomptedansnotreformulation.C’estpourtantnécessairepourquantifiercor-rectementlecoûtdelaméthodedesfacteurs.Leproblèmeestqu’onnesaitpas,àcejour,trouverladécompositionentempspolynomialenn.1.5ArbredeKnuthUneautreméthodeconsisteàutiliserl’arbredeKnuth,représentéFigure1.1.Lecheminmenantdelaracinedel’arbreànindiqueuneséquenced’exposantspermettantdecalculerxndefaçonefficace.123571419212810112213232615253020406918273612244848161733343264Fig.1.1–Lesseptpremiersniveauxdel’arbredeKnuth.12Constructiondel’arbreLe(k+1)-èmeniveaudel’arbreestdéfiniàpartirdeskpremiersniveauxdelafaçonsuivante:prendrechaquenœudnduk-èmeniveau,degaucheàdroite,etlesrelieraveclesnœudsn+1,n+a1,n+a2,...,n+ak−1=2n(danscetordre),où1,a1,...,ak−1=nreprésentelechemindelaracineàn.Onn’ajouterapasunnœudsiceluiciestdéjàprésentdansl’arbre.VoiciquelquesstatistiquesduesàKnuth:lespluspetitsnombrespourlesquelslaméthoden’estpasoptimalesontn=77,154,233.Lepluspetitnpourlequellaméthodedel’arbreestsupérieureàlafoisàlaméthodebinaireetàcelledesfacteursestn=23.Lepluspetitnpourlequellaméthodedel’arbreestmoinsbonnequecelledesfacteursestn=19879=103·193;detelscassontrares:pourn≤100000,l’arbrebatlesfacteurs88803fois,faitmatchnul11191foisetperdseulement6fois.1.6RésultatssurlacomplexitéThéorème1.Opt(n)≥&logn’Preuve.Soitunalgorithmepermettantdecalculerlespuissancesdex,avecpourtouti,yi=xα(i).Montronsparrécurrencequeα(i)≤2i.Pourlabase,onabieny0=xd’où1≤20=1.Soitiunentier,ilexistejetk(j,k<k)telsqueyi=yj·yk.Onaα(i)=α(j)+α(k),parl’hypothèsed’induction,α(j)≤2j≤2i−1etdemêmeα(k)≤2i−1.Onendéduitdoncqueα(i)≤2i−1+2i−1=2i.Intuitivement,lapreuveexprimequ’onnepeutpasfairemieuxquedoublerl’exposantobtenuàchaqueétapedel’algorithme.Grâceauthéorèmeprécédent,etàl’étudedelaméthodebinaire,dontlenombred’étapesestinférieurà2logn,onalerésultatsuivant:1≤limn→∞Opt(n)logn≤2.Théorème2.limn→∞Opt(n)logn=1Preuve.L’idéeestd’améliorerlaméthodebinaireenappliquantcetteméthodeenbasem.Posonsm=2k,oùkseradéterminéplustard,etécrivonsnenbasem:n=α0mt+α1mt−1+···+αt,oùchaqueαiestun“chiffre”enbasem,donccomprisentre0etm−1.Puisoncalculetouslesxd,1≤d≤m−1)parlaméthodenaïve,cequirequiertm−2multiplications.Enfait,onn’apasforcémentbesoindetoutescesvaleurs,seulementdesxαi,maiscommeonlescalcule“auvol”onpeutlescalculertoussanssurcoût.Ensuiteoncalculesuccessivement:y1=(xα0)m·xα1y2=(y1)m·xα2=x(α0m+α1)m+α2...yt=(yt−1)m·xαt=xn13Oneffectuepourchaquelignek+1opérations(kélévationsaucarrépourcalculerlapuissancem-ème,etunemultiplication),d’oùlecoûttotalducalculdexn:t·(k+1)+(m−2).Enremplaçantmpar2k,ettpar#logmn$,ontrouveuncoûttotalde#logmn$(k+1)+2k−2≤log2nk(k+1)+2k.Ilsuffitdoncdeprendrektendantversl’infini,pourque(k+1)/ktendevers1,ettelque2k=o(logn),parexemplek=#1/2log(logn)$(onauraalors2k≤√logn).1.7ExercicesExercice1.7.1.LegrandsautLeproblèmeestdedétermineràpartirdequelétaged’unimmeuble,sauterparunefenêtreestfatal.Vousêtesdansunimmeubleànétages(numérotésde1àn)etvousdisposezdekétudiants.Iln’yaqu’uneopérationpossiblepourtestersilahauteurd’unétageestfatale:fairesauterunétudiantparlafenêtre.S’ilsurvit,vouspouvezleréutiliserensuite,sinonvousnepouvezplus.Vousdevezproposerunalgorithmepourtrouverlahauteuràpartirdelaquelleunsautestfatal(renvoyern+1sionsurvitencoreensautantdun-èmeétage)enfaisantleminimumdesauts.1-Sik≥&log2(n)’,proposerunalgorithmeenO(log2(n))sauts.2-Sik<&log2(n)’,proposerunalgorithmeenO(k+n2k−1)sauts.3-Sik=2,proposerunalgorithmeenO(√n)sauts.Correction.1-LacomplexitéenO(log2(n))quiestindiquéenousaiguilleversunedichotomie.Eneffet,ensupposantquel’onak≥&log2(n)’,onobtientlerésultatsurlesétagesdeiàjenjetantunétudiantdepuislenèmeétage,oùn=j−i/2,puisenitérantleprocédésurlesétagesdeiàn−1silachuteàétéfatale,etsurlesétagesdenàjdanslecascontraire.Laméthodedichotomiquenousgarantitalorsquel’onobtientlebonrésultat(lorsqu’ilneresteplusqu’unseulétage,c’est-à-direlorsquel’oncalculepourlesétagesdei=j),etceavecunecomplexitélogarithmiquedanslepiredescas.2-Puisqu’icionnedisposequedek<&log2(n)’étudiants,onnepeutpasappliquerdirectementlaméthodedichotomiqueproposéeprécédemment.Cependant,onvaremédierauproblèmedemanièresimpleenappliquantunerecherchedichotomiqueaveck−1étudiants,demanièreàdélimiterunintervalled’étagesdanslequelsetrouvel’étagerecherché.Onsesertalorsdudernierétudiantrestantpourparcourirl’intervalledefaçonlinéaire,doncenlejetantdechaqueétageenpartantduplusbasdel’intervalle,jusqu’auplushaut.Aprèsavoirjetélesk−1premiersétudiants,sil’onn’apasencoretrouvélebonétage,ilresteexactementn/2k−1étagesdansl’intervallederecherche,d’oùunecomplexitédanslepiredescasenO(k+n/2k−1)sauts.3-Danslecasparticulieroùl’onak=2,onneveutpasavoiràtesterchaqueétagedefaçonlinéaire,c’estpourquoionvareprendreànotrecomptelesidéesprécédentes,etnotammentcellequiconsisteàdélimiterunintervallederecherche.Nousdécouponsdoncl’ensembledesétages14en“tranches”de√nétages,avantdejeterlepremierétudiantdechacundesétagesdedébutdetranche.Lorsquel’étudiantylaissesapeau,onseramèneaudernierétagentestéquinesoitpasfatal,etonn’aplusqu’àparcourirdemanièrelinéairel’intervalleallantdel’étagen+1àl’étagefataltrouvéprécédemment.Onaainsideuxsériesd’essaisenO(√n),etdoncunecomplexitéfinaledanslepiredescaségalementenO(√n)sauts.Exercice1.7.2.CherchezlastarDansungroupedenpersonnes(numérotéesde1ànpourlesdistinguer),unestarestquelqu’unquineconnaitpersonnemaisquetouslesautresconnaissent.Pourdémasquerunestar,s’ilenexisteune,vousavezjusteledroitdeposerdesquestions,àn’importequelindividuidugroupe,dutype“est-cequevousconnaissezj?”(noté“i→j?”),onsupposequelesindividusrépondentlavérité.Onveutunalgorithmequitrouveunestar,s’ilenexiste,ousinonquigarantitqu’iln’yapasdestardanslegroupe,enposantlemoinsdequestionspossibles.1-Combienpeut-ilyavoirdestarsdanslegroupe?2-Ecrirelemeilleuralgorithmequevouspouvezetdonnersacomplexitéennombredequestions(onpeutyarriverenO(n)questions).3-Donneruneborneinférieuresurlacomplexité(ennombredequestions)detoutalgorithmerésolvantleproblème.((Difficile)prouverquelameilleureborneinférieurepourceproblèmeest3n−#log2(n)$−3).Correction.1-Ilnepeutyavoirqu’uneseulestardanslegroupe,puisques’ilyenaune,elleneconnaitpersonne,etdonctouslesautressontinconnusd’aumoinsunepersonne,etnepeuventdoncêtreeuxaussidesstars.2-Lorsqu’oneffectueletest&&i→j?&&,c’est-à-direlorsquel’onchercheàsavoirsilapersonneiconnaîtlapersonnej,onobtientlerésultatsuivant:–sioui,alorsin’estpasunestar,maisjenestpotentiellementune.–sinon,alorsjn’estpasunestar,maisienestpotentiellementune.L’algorithmeconsistealorsaparcourirletableaudespersonnesunefois,engardantenmemoireàchaqueinstantlapersonneiquiestjusqu’icireconnuepartous,tandisqu’aujèmetest,touteslesautrespersonnes,dontlesindicessontlesk<j(aveck*=i,biensûr)nepeuventpasdesstars.Cetalgorithmes’écritdoncdelamanièresuivante:i←1etj←2tantquej≤nfaire!si&&i→j&&alorsfairej←j+1sinonfairei←jetj←j+1istar←vraietk←1tantque(k≤netistar)faire!si&&k→i&&alorsfairek←k+1sinonfaireistar←fauxsiistaralorsfaireretourner“iestlastar”sinonfaireretourner“iln’yapasdestar”3-Enobservantnotrealgorithme,onconstatequel’onpeututilisercommeborneinférieurepourlenombredequestionslavaleur3n−2,puisquel’onfaiticideuxbouclessurn−1personnes15etunebouclesurl’ensembledesnpersonnes.Pourcequiestdelaborneinférieureoptimale,ils’agitd’unequestiondifficile,dontonn’expliciterapaslasolutionici.Exercice1.7.3.BricolageDansuneboiteàoutils,vousdisposezdenécrousdediamètrestousdifférentsetdesnboulonscorrespondants.Maistoutestmélangéetvousvoulezappareillerchaqueécrouavecleboulonquiluicorrespond.Lesdifférencesdediamètreentrelesécroussonttellementminimesqu’iln’estpaspossiblededétermineràl’œilnusiunécrouestplusgrandqu’unautre.Ilenvademêmeaveclesboulons.Parconséquent,leseultyped’opérationautoriséconsisteàessayerunécrouavecunboulon,cequipeutamenertroisréponsespossibles:soitl’écroueststrictementpluslargequeleboulon,soitileststrictementmoinslarge,soitilsontexactementlemêmediamètre.1-EcrireunalgorithmesimpleenO(n2)essaisquiappareillechaqueécrouavecsonboulon.2-Supposonsqu’aulieudevouloirappareillertouslesboulonsetécrous,vousvoulezjustetrouverlepluspetitécrouetlebouloncorrespondant.Montrerquevouspouvezrésoudreceproblèmeenmoinsde2n−2essais.3-ProuverquetoutalgorithmequiappareilletouslesécrousavectouslesboulonsdoiteffectuerΩ(nlogn)essaisdanslepiredescas.Problèmeouvert:proposerunalgorithmeeno(n2)essaispourrésoudreceproblème.Correction.1-AlgorithmePourappareillerlesboulonsetlesécrous,ilsuffitdeprendreunboulonarbitrairement,deletesteravectouslesécrous.Ontrouvealorslebonenauplusntestsetilsuffitalorsderecommenceravectouslesautresboulons.Onobtientdonclerésultatenauplusn(n−1)2=O(n2)tests.2-LepluspetitécrouetsonboulonLeprincipeestdenuméroterlesboulonsetlesécrousde1àn,demanièrearbitraire,etdefaireprogresserdescompteurs(parexempleietj)pourmarquerleminimuncourantdansl’unedescatégories,etlastructureencoursdetestdansl’autre.débutwhile(i≤n)&&(j≤n)dosii=j=nalorssortirdelaboucle;siecrou.i=boulon.jalorss’ensouveniretfairei:=i+1;siecrou.i<boulon.jalorsj:=j+1;min=ecrou;siecrou.i>boulon.jalorsi:=i+1;min=boulon;finAlafindecetteboucle,–simin=écrou,l’écrouiestlepluspetit.–simin=boulon,leboulonjestlepluspetit.Etdanslesdeuxcas,onsaitdéjàquelestl’élémentquicorrespond:eneffet,lecompteurdel’autrecatégorievautn+1(oundansuncasspécial),etonadoncdéjàrencontréleminimum.laseuleraisonpossiblepourlaquelleiln’apasétéconservéestdoncqu’ilaitététestéavecl’autreminimum.Pourlecasspécialoui=j=n,lederniertestestinutile:eneffet,onsaitquel’undesdeux,estminimum,etqueunefoisleboulonminimumatteind,jrestefixe:d’oùleboulonnestminimum,etsonhomologueasoitdéjàététrouvé,soitestl’écrourestant.16Cetteboucleeffectuedoncauplus2∗n−2tests.3-Algorithmed’appareillagedesécrousetdeleurboulonOnnotef(T)lenombredefeuillesdel’arbreeth(T)sahauteur.SiTestunarbreternaireh(T)≥&log3f(T)’.ParinductionsurlahauteurdeT:–Pourh(T)=0l’arbreàunefeuilledonconabienh(T)≥&log3f(T)&.–Pourh(T)>0unarbreternaireatroisfils,lefilsgauchefg,lefilscentralfc,etlefilsdroitfddehauteurinférieuràh(T)−1.Onsupposequeh(T)≥&log3f(T)’estvraipourh(T)≤kkétantfixéonveutdémontrerquecettepropriétéestvraiaussipourh(T)=k+1.Lesfeuillesd’unarbresontaussicellesdesesfils.Donc!"#$f"f&$f"f'$f'f&f"f($f(f"#$#!"#$)1f(T)=f(fd)+f(fg)+f(fd)deplus:h(T)≤h(fd)+1h(T)≤h(fg)+1h(T)≤h(fc)+1orparinductioncommeh(T)=k+1,h(fg)≤k,h(fg)≤k,eth(fg)≤kona:k=h(fc)≤&log3f(fc)’h(fd)≤&log3f(fd)’h(fg)≤&log3f(fg)’Doncf(fc),f(fg),f(fd)≤3kor:f(T)=f(fc)+f(fg)+f(fd)donc:f(T)≤3×3k=3k+1D’oùonendéduitque:h(T)≥log3f(T)Ilya!nagencementsboulons-écrouspossiblesdoncl’arbrededécision,quiestternaireapourhauteur:log3!n∼nlog3n,donclacomplexitédanslepirecasdel’algoestde:Ω(n×logn).1.8RéférencesbibliographiquesLaprésentationducourss’inspiredeKnuth[6].LesexercicesLegrandsautetBricolagesonttirésdeRawlins[8].1718Chapitre2Diviserpourrégner2.1AlgorithmedeStrassenCalculonsunproduitdematrices:"rstu#="abcd#·"efgh#L’algorithmeclassiquecalculeenAdd(n)=n2(n−1)additionsetMult(n)=n3multipli-cations.Eneffet,ilyan2coefficientsàcalculer,chacuncorrespondantunproduitscalairedetaillen,doncavecnmultiplications,n−1additions,etuneaffectation.Peut-onfairemieux?1V.Strassenrépondqueoui:soientp1=a(g−h)p2=(a+b)hp3=(c+d)ep4=d(f−e)p5=(a+d)(e+h)p6=(b−d)(f+h)p7=(a−c)(e+g)alorsonpeutécrirer=p5+p4−p2+p6s=p1+p2t=p3+p4u=p5+p1−p3−p7Comptonsmaintenantlesopérations:ClassiqueStrassenMult(2)=8Mult(2)=7Add(2)=4Add(2)=18Onagagnéunemultiplication,maisenperdant14additions;donc,pourdesmatrices2x2,c’estunbilannégatif.Parcontre,ilestremarquablequel’opérationnenécessitepaslacommu-tativitédelamultiplication.Onpeutdoncl’utiliseravecdesmatricesdetaillenpaire.1Danslestempsanciensdel’informatique,ilétaitsurtoutintéressantdediminuerlenombredemultiplications,quitteàaugmenterlenombred’additions.L’architecturepipelinéedesprocesseursactuelspermetderéaliser,enmoyenne,uneadditionouunemultiplicationpartempsdecycle.19Supposonsdoncn=2mpair,etutilisonslaméthodeprécédenteuneseulefois,enpar-titionnantchaquematricededépartenquatresous-blocsdetaillem×m.Oneffectueram3multiplicationspourchaquepi,d’oùuntotaldeMult(n)=7m3=7n3/8multiplications.Pourlesadditions,ilyadeuxsources:lesadditionseffectuéesdanschaqueproduitpi,doncaunombrede7m2(m−1),etlesadditionspourformerles18matricesauxiliaires,aunombrede18m2.D’oùAdd(n)=7m3+18m2=7n3/8+18n2/4.Asymptotiquement,letermedominantestenn3/7pourMult(n)commepourAdd(n),etlanouvelleméthodeestgagnantepournassezgrand.Laraisonprofondeestlasuivante:unemultiplicationdedeuxmatricesdetaillenrequiertO(n3)opérations,alorsqueleuradditionn’endemandequeO(n2).Pourngrand,lesadditionssont“gratuites”enfacedesmultiplications.Cequin’étaitpaslecaspourlesnombresréels.L’algorithmedeStrassenestl’applicationrécursivedeladécompositionprécédente.Onconsi-dèrelecasoùnestunepuissancede2,i.e.n=2s.Sinn’estpasunepuissancede2,onétendlesmatricesavecdes0àlapuissancede2supérieure:"X000#etonremplaceradanslesformulesquisuiventlognpar&logn’.Prenonsdoncn=2s.Onfonctionnedemanièrerécursive:onrefaitlemêmedécoupagepourchacundesproduitsdematricepi.Ons’arrêteraquandonarriveàdesmatricesdetaille1,oumieux,àlataillepourlaquellelaméthodeestpluscoûteusequelaméthodeclassique(n≈32).Soient:–M(n)=nombredemultiplicationsréaliséesparl’algorithmedeStrassenpourmultiplier2matricesdetaillen–A(n)=nombred’additionsréaliséesparl’algorithmedeStrassenpourmultiplier2ma-tricesdetaillenOna:!M(1)=1M(n)=7×M(n/2)=⇒M(n)=7s=7log2(n)=nlog2(7)Commeprécédemment,lesadditionsviennentde2sources:lesadditionsliéesauxadditionsdematricespourlaconstructiondestermespietlesadditionseffectuéespourlesmultiplicationsdematrices(appelsrécursifs).Onadonc:!A(1)=0A(n)=7×A(n/2)+18×(n/2)2=⇒A(n)=6×(nlog2(7)−n2)(onverraSection2.4commentrésoudrecetterécurrence).Onvoitquel’ordredegrandeurducoûtdescalculsn’estplusenn3,maisseulementennlog27.L’algorithmedeStrassenn’estpassouventutilisécarilintroduitdesproblèmesd’instabi-liténumérique.Notonsenfinqu’ilexistedesalgorithmesdecomplexitémeilleurequecelledeStrassen,etqueleproblèmededéterminerlacomplexitéduproduitdedeuxmatricesestencoreouvert.LaseuleborneinférieureconnueestenO(n2):ilfautbientoucherchaquecoefficientaumoinsunefois.2.2ProduitdedeuxpolynômesLebutestdemultiplierdeuxpolynômes.Onnoteran-polynômeslespolynômesdedegréstrictementinférieuràn,doncavecncoefficients.Soient:–P:n-polynôme:$n−1i=0aiXi20–Q:n-polynôme:$n−1i=0biXi–R=P×Q=?:(2n−1)-polynômeSoient:–M(n)=nombredemultiplicationsréaliséesparl’algorithmepourmultiplierdeuxn-polynômes–A(n)=nombred’additionsréaliséesparl’algorithmepourmultiplierdeuxn-polynômesAvecl’algorithmeusueldemultiplicationden-polynômes:M(n)=n2etA(n)=n2−(2n−1)%&’(affectations=(n−1)2Onsupposenpair,n=2mP=P1+Xm×P2Q=Q1+Xm×Q2#avecP1,P2,Q1,Q2m-polynômesSoient:R1=P1×Q1R2=P2×Q2R3=(P1+P2)×(Q1+Q2)Onaalors:R=R1+(R3−R2−R1)×Xm+R2×X2mQuelestl’intérêt?Onneréaliseque3multiplicationsdepolynômesdetaillemoitié.Lesad-ditionssontdedeuxtypes:lesadditionsdepolynômes,etlesadditionsliéesauxmultiplicationsdem-polynômes.Onsupposemaintenantquen=2setonappliquel’algorithmedemanièrerécursive.!M(1)=1M(n)=3×M(n/2)=⇒M(n)=3s=nlog2(3)A(1)=0A(n)=3×A(n/2)%&’(appelsrecursifs+2×n/2%&’(pouravoirR3+2×(n−1)%&’(pouravoirR3−R2−R1+(n−2)%&’(constructiondeREneffet,pourlaconstructiondeR:R=R1+(R3−R1−R2)×Xm+R2×X2m=n−2,i=0r1i×Xi%&’(X0→Xn−2+n−2,i=0zi×Xi+n/2+n−2,i=0r2i×Xi+n%&’(Xn→X2n−2Touslestermesdutermedumilieus’additionnentauxtermesdegaucheetdedroite,ilfautdoncfairen−2additions.D’oú:!A(1)=0A(n)=3×A(n/2)+4×n−4=⇒A(n)=6nlog2(3)−8n+2(onverraSection2.4commentrésoudrecetterécurrence)RemarqueLemeilleuralgorithmedemultiplicationdepolynômesestenO(n×log(n)),ilestobtenupartransforméedeFourrierrapide(FFT).P,Q−→%&’(evaluationP(xi),Q(xi)%&’(en2npoints−→P(xi)×Q(xi)−→%&’(interpolationP×QL’évaluationetl’interpolationsontréaliséesenn2parlaméthodeclassique,enutilisantNewtonetLagrange.PourlaFFT,onévaluelespolynômesenlesracinescomplexesdel’unité.212.3MastertheoremDiviserpourrègner:Onconsidèreunproblèmedetaillen,qu’ondécoupeenasous-problèmesdetaillen/bpermettantderésoudreleproblème.Lecoûtdel’algorithmeestalors:S(1)=1S(n)=a×S(n/b)+Reconstruction(n)%&’(c×nαengeneralabαcStrassen72218Polynomes3214S(n)=a×S(n/b)+R(n)=a2×S(n/b2)+a×R(n/b)+R(n)=...Onposen=bk,onaalors:S(n)=ak%&’(nlogb(a)×S(1)+k−1,i=0ai×R(n/bi)%&’(avecR(n)=c×nαet:,=c×nαk−1,i=0(a/bα)iOndistinguealorsplusieurscas:1.(a>bα):$∼nα×(abα)k∼ak=⇒S(n)=O(nlogb(a))2.(a=bα):$∼k×nα=⇒S(n)=O(nα×log(n))3.(a<bα):$∼c×nα×11−abα=⇒S(n)=O(nα)RetoursurStrassen:Alalumièredecequiprécède,etsiondécoupaitlesmatricesen9blocsdetaillen/3aulieude4blocsdetaillen/2?×Ona:abαca32Pourquel’algorithmesoitplusintéressantqueStrassen,ilfautque:log3(a)<log2(7)⇒a<elog2(7)×log2(3)⇒a<7log2(3)≈21,8C’estunproblèmeouvert:onconnaîtuneméthodeaveca=23maispasaveca=21!222.4Résolutiondesrécurrences2.4.1Résolutiondesrécurrenceshomogènes!p0×sn+p1×sn−1+···+pk×sn−k=0piconstantesSoitP=$ki=0pi×Xk−i.OncherchelesracinesdeP.SilesracinesdePsontdistinctes:sn=k,i=0ci×rinSinon,siqiestl’ordredemultiplicitéderisn=l,i=0Pi(n)%&’(polynomededegreqi−1×rin2.4.2RésolutiondesrécurrencesavecsecondmembreOnnoteEl’opérateurdedécalage:E{sn}={sn+1}Ondéfinitlesopérationssuivantessurlessuites:c.{sn}={c.sn}(2.1)(E1+E2){sn}=E1{sn}+E2{sn}(2.2)(E1E2){sn}=E1(E2{sn})(2.3)"ex:(E−3){sn}={sn+1−3sn}(2+E2){sn}={2sn+sn+2}#P(E)annule{sn}siP(E){sn}=0ex:suiteannulateur{c}E−1{Qk(n)}(E−1)k+1{cn}E−c{cn×Qk(n)}(E−c)k+1oùQk(n)estunpolynômededegrék.Eneffet,ilsuffitdemontrerladernièrerelation,parrécurrencesurk:(E−c)k+1{cn×Qk(n)}%&’({cn×(a0nk+Qk−1(n))}=(E−c)k[(E−c){cn(a0nk+Qk−1(n))}]%&’({cn+1(a0(n+1)k+Qk−1(n+1))−cn+1(a0nk+Qk−1(n))}=(E−c)k[cn+1×Rk−1(n)]=0(parhypothèsederécurrence)Résolutionpourlesadditionsdansl’algorithmedeStrassen:A(n)=7×A(n/2)+18×n2423Onan=2s,onposeAs=A(2s)As+1=7×As+18×(2s+1)24=7×As+18×4s(E−4)(E−7){As}%&’(As+1−7As=18×4s=0⇒As=k1×7s+k2×4savec:A0=0A1=18Onendéduitlesvaleursdek1etk2donnéesplushaut.Résolutionpourlesadditionsdansl’algorithmedemultiplicationdepolynômes:A(n)=3×A(n/2)+4n−4As=3×As−1+4×2s−4D’où:(E−1)(E−2)(E−3){As}=0⇒As=k1×3s+k2×2s+k3avec:A0=0A1=4A2=24Onendéduitlesvaleursdek1=6,k2=−8etk3=2donnéesplushaut.2.5MultiplicationetinversiondematricesSoient:–M(n)=coûtdelamultiplicationde2matricesd’ordren–I(n)=coûtdel’inversiond’unematriced’ordren–Hypothèses:−O(n2)≤M(n)I(n)≤O(n3)−M(n)etI(n)croissantsThéorème3.M(n)etI(n)ontlemêmeordredegrandeur.Preuve.Onmontrequechaqueopérationestaumoinsaussi“difficile”quel’autre:Lamultiplicationestaumoinsaussicomplexequel’inversionOnveutmultiplierlesmatricesAetBdetaillen.SoitZdetaille3nsuivante:Z=IA00IB00I⇒Z−1=I−AA.B0I−B00ID’où:M(n)≤I(3n)24L’inversionestaumoinsaussicomplexequelamultiplicationOnprocèdeendeuxétapes:SiAestsymétriquedéfiniepositiveA="BtCCD#SoitS=D−C.B−1.tC(Shurcomplement).A−1="B−1+B−1.tC.S−1.C.B−1−B−1.tC.S−1−S−1.C.B−1S−1#Ilsuffitdeconstruire:B−1,C.B−1,(C.B−1).tC,S−1,S−1.(C.B−1),t(C.B−1).(S−1.C.B−1)d’où:I(n)=2×I(n/2)+4×M(n)+O(n2)=O(M(n))CasgénéralOnposeB=tA×A.OnveutcalculerA−1,etonsaitcalculerB−1carBestsymétriquedéfiniepositive.I=B−1.B=B−1.(tA.A)=(B−1.tA).A⇒A−1=B−1.tAD’où:I(n)=2×M(n)+O(M(n))=O(M(n))2.6ExercicesExercice2.6.1.MatricesdeTœplitzUnematricedeTœplitzestunematricen×n(ai,j)tellequeai,j=ai−1,j−1pour2≤i,j≤n.1-LasommededeuxmatricesdeTœplitzest-elleunematricedeTœplitz?Etleproduit?2-Trouverunmoyend’additionnerdeuxmatricesdeTœplitzenO(n).3-Commentcalculerleproduitd’unematricedeTœplitzn×nparunvecteurdelongueurn?Quelleestlacomplexitédel’algorithme?Correction.1–Parlinéarité,lasommededeuxTœplitzresteuneTœplitz.Cen’estpasvraipourleproduit.Parexemple,"1011#×"1101#="1112#2–Onn’additionnequelespremièreslignesetlespremièrescolonnes,cequifait2n−1opéra-tions.3–Onneconsidèrequelesmatricesdetaille2k×2k.Ondécomposelamatriceenblocsdetaillen=2k−1M×T="ABCA#×"XY#25Onpose:U=(C+A)XV=A(Y−X)W=(B+A)Yetoncalcule:M×T="W−VU+V#Calculdelacomplexité:OnnoterespectivementM(n)etA(n)lenombredemultiplicationsetd’additionspourunproduitdematricesn×n.M(2k)=3M(2k−1)M(1)=1A(2k)=3A(2k−1)+2(2k−1)+3.2k−1A(1)=0Onrésoudlesrécurrences:onposeMs=M(2s),etonposeAs=A(2s).lecalculpourlesmultiplications:!Ms=3Ms−1M0=1(E−3)Ms=¯0;Ms=3logn=nlog3puislecalculpourlesadditions:!As=3As−1+7.2s−1−2A0=0(E−3)(E−2)(E−1){As}=¯0As=i3s+j2s+lA0=A(1)=0−→i+j+l=0A1=A(2)=5−→3i+2j+l=5A2=A(4)=27−→9i+4j+l=27D’oùi=6,j=−7,l=126Exercice2.6.2.Recherched’unélémentmajoritaireSoitEunelistedenélémentsrangésdansuntableaunumérotéde1àn.Onsupposequelaseuleopérationqu’onsaiteffectuersurlesélémentsestdevérifiersideuxélémentssontégauxounon.Onditqu’unélémentx∈Eestmajoritairesil’ensembleEx={y∈E|y=x}astrictementplusden/2éléments.Saufaviscontraire,onsupposeraquenestunepuissancede2.Ons’intéresseraàlacomplexitédanslepiredescas.1-AlgorithmenaïfÉcrireunalgorithmecalculantlecardinaldecxdeExpourunxdonné.EndéduireunalgorithmepourvérifiersiEpossèdeunélémentmajoritaire.Quelleestlacomplexitédecetalgorithme?2-Diviserpourrègner2.1-DonnerunautrealgorithmerécursifbasésurundécoupagedeEendeuxlistesdemêmetaille.Quelleestsacomplexité?2.2-Donnerunalgorithmesimilaire(enprécisantsacomplexité)danslecasgénéraloùnn’estpasunepuissancede2.3-EncoremieuxPouraméliorerl’algorithmeprécédent,onvasecontenterdansunpremiertempsdemettreaupointunalgorithmepossédantlapropriétésuivante:–soitl’algorithmegarantitqueEnepossèdepasd’élémentmajoritaire,–soitl’algorithmefournitunentierp>n/2etunélémentxtelsquexapparaisseaupluspfoisdansEettoutélémentautrequexapparaîtauplusn−pfoisdansE.3.1-Donnerunalgorithmerécursifpossédantcettepropriété.Quelleestsacomplexité?3.2-Mêmequestionquandnn’estpasunepuissancede2.3.3-EndéduireunalgorithmeefficacevérifiantsiEpossèdeunélémentmajoritaire.4-EncoreencoremieuxOnchangelamanièredevoirleschoses.Onaunensembledenballesetoncherchelecaséchéants’ilyaunecouleurmajoritaireparmilesballes.4.1-Supposonsquelesballessoientrangéesenfilesuruneétagère,demanièreàn’avoirjamaisdeuxballesdelamêmecouleuràcôté.Quepeut-onendéduiresurlenombremaximaldeballesdelamêmecouleur?Onaunensembledenballes,uneétagèrevideoùonpeutlesrangerenfileetunecorbeillevide.Considéronsl’algorithmesuivant:-Phase1-Prendrelesballesuneparunepourlesrangersurl’étagèreoudanslacorbeille.SIlaballen’estpasdelamêmecouleurqueladernièreballesurl’étagère,larangeràcôté,etsidepluslacorbeillen’estpasvide,prendreuneballedanslacorbeilleetlarangeràcôtésurl’étagère.SINON,c’estàdiresilaballeestdelamêmecouleurqueladernièreballesurl’étagère,lamettredanslacorbeille.-Phase2-SoitClacouleurdeladernièreballesurl’étagèreàlafindelaphase1.Oncomparesuccessivementlacouleurdeladernièreballesurl’étagèreavecC.SIlacouleurestlamêmeonjettelesdeuxdernièresballessurl’étagère,saufs’iln’enrestequ’une,auquelcasonlametdanslacorbeille.SINONonlajetteetonjetteunedesballesdelacorbeille,saufsila27corbeilleestdéjàvideauquelcasons’arrêteendécrétantqu’iln’yapasdecouleurmajoritaire.Quandonaépuisétouteslesballessurl’étagère,onregardelecontenudelacorbeille.Sielleestvidealorsiln’yapasdecouleurmajoritaire,etsiellecontientaumoinsuneballealorsCestlacouleurmajoritaire.4.2-(Correctiondel’algorithme)Montrerqu’àtoutmomentdelaphase1,touteslesballeséventuellementprésentesdanslacorbeilleontlacouleurdeladernièreballedel’étagère.Endéduireques’ilyaunecouleurdominantealorsc’estC.Prouverlacorrectiondel’algorithme.4.3-(Complexité)Donnerlacomplexitédanslepiredescasennombredecomparaisonsdecouleursdesballes.5-OptimalitéOnconsidèreunalgorithmedemajoritépourlescouleursdenballes.Lebutestderegarderfairel’algorithme,enchoisissantaufuretàmesurelescouleursdesballespourquel’algorithmeaitlemaximumdetravail(toutenrestantcohérentdanslechoixdescouleurs).Onobtiendraainsiuneborneinférieuredecomplexitépourunalgorithmedemajorité.C’estlatechniquedel’adversaire.Àtoutmomentdel’algorithme,onauraunepartitiondesballesendeuxensembles:l’arèneetlesgradins.L’arènecontientuncertainnombredecomposantesconnexesdedeuxsortes:lesbinômesetlestroupeaux.Unbinômeestunensemblededeuxballespourlesquellesl’algorithmeadéjàtestésiellesétaientdelamêmecouleuretarépondunon.Untroupeauestunensemblenonvidedeballesdelamêmecouleur,connectéespardestestsdel’algorithme.Ainsi,untroupeauaveckélémentsasubiaumoinsk−1comparaisonsdecouleursentresesmembres.SoientBlenombredebinômesetTlenombredetroupeaux.Soientglenombred’élémentsdanslesgradinsettlenombretotald’élémentsdanstouslestroupeaux.Enfin,soitm=#n/2$+1le“seuildemajorité”.Audébutdel’algorithmetouteslesballessontdestroupeauxàunélément.Lastratégiedel’adversaireestlasuivante.L’algorithmeeffectueuntestcouleur(x)=couleur(y)?1.Sixouysontdanslesgradins,laréponseestnon.2.Six(resp.y)estdansunbinôme,laréponseestnonetx(resp.y)estenvoyédanslesgradinsalorsquel’élémentrestantdevientuntroupeausingleton.3.Sixetysontdanslemêmetroupeaularéponseestoui.4.Sixetysontdansdestroupeauxdifférentsalorsceladépendded=B+t.(a)d>m:celasignifiequelesballessontdansdestroupeauxsingletons.Laréponseestnonetlesballesdeviennentunnouveaubinôme.(b)d=m:laréponseestouietlestroupeauxdexetyfusionnent.5.1-Vérifierquelesquatrecasprécédentstraitenttouslescaspossibles.Montrerqu’àtoutmomentd≥metquesid>malorstouslestroupeauxsontdessingletons.5.2-Montrerqu’àtoutmomentlesdeuxcoloriagessuivantssontconsistantsaveclesréponsesdel’adversaire:(i)Touteslesballessontdecouleursdifférentessaufcellesquisontdansunmêmetroupeau.(ii)Unemêmecouleurestattribuéeàtouteslesballesdetouslestroupeauxetàuneballedechaquebinôme.Lesballesrestantesontchacuneunecouleurdistincte.5.3-Montrerquesiunalgorithmecorrects’arrêtealorsl’arènenecontientqu’uneseulecompo-santeconnexequiestuntroupeaudetaillem.285.4-Àtoutmomentlenombredecomparaisonsinégaleseffectuéesparl’algorithmeestaumoins2g+Betlenombredecomparaisonségalesestaumoinst−T.5.5-Considéronsunalgorithmequirésoutlamajorité.Montrerqu’ilexisteunedonnéepourlaquellel’algorithmeeffectueaumoins2(n−m)=2&n/2’−1comparaisonsd’inégalitéetaumoins#n/2$comparaisonsd’égalité,etdoncaumoinsautotal3&n/2’−2comparaisons.Correction.Onserestreinticiauxalgorithmesoùlaseuleopérationqu’onsaiteffectuersurlesélémentsestdetestersideuxélémentssontégaux.SilaréponseestOUI,ondiraqu’ils’agitd’unecomparaisonégale,etsilaréponseestNONd’unecomparaisoninégale.Remarque:s’ilexisteunélémentmajoritaire,ilestnécessairementunique.1-Algorithmenaïfdébutpouride1ànfairec←0;pourjde1ànfairesiE[j]=E[i]alorsc←c+1;sic>n/2alorsretourner“E[i]estmajoritaire”Retourner“Pasd’élémentmajoritaire”.finComplexité:nombretotaldecomparaisons=n2.2-DiviserpourrègnerEEE12n/2n/22.1-Principe:–CouperEendeuxtableauxE1etE2detaillesn/2(onsupposenpair).–S’ilexisteunélémentmajoritairexdansE,alorsxestmajoritairedansaumoinsunedesdeuxlistesE1etE2(eneffetsixnonmajoritairedansE1,nidansE2,alorsdansE,cx≤n/4+n/4=n/2).–Algorithmerécursif:calculerlesélémentsmajoritairesdeE1etdeE2(s’ilsexistent)aveclenombretotald’occurencesdechacunetendéduiresil’undesdeuxestmajoritairedansE.L’algorithmesuivantMajoritaire(i,j)renvoieuncouplequivaut(x,cx)sixestmajoritairedanslesous-tableauE[i..j]aveccxoccurencesetquivaut(−,0)s’iln’yapasdemajoritairedansE[i..j],l’appelinitialétantMajoritaire(1,n).LafonctionOccurence(x,i,j)calculelenombred’occurencesdexdanslesous-tableauE[i..j].29Algorithm:Majoritaire(i,j)débutsii=jalorsretourner(E[i],1);sinon(x,cx)=Majoritaire(i,#(i+j)/2$);(y,cy)=Majoritaire(#(i+j)/2$+1,j);sicx*=0alorscx←cx+Occurence(x,#(i+j)/2$+1,j);sicy*=0alorscy←cy+Occurence(x,i,#(i+j)/2$);sicx&g