cours-complexite2

Description

Cours : complexiteChristophe RitzenthalerNovember 12, 20081 Quelques notions generales1.1 PrincipesLe temps d’execution d’un programme depend de plusieurs donnees :1. du type d’ordinateur utilise;2. du langage utilise (representation des donnees);3. de la complexite abstraite de l’algorithme sous-jacent.Pour le mesurer en MAPLE, on peut utiliser les commandes suivantes (ici pour unprogramme g) :iS := [seq([i;time(g(10 ))];i = 1::: 10)]:En general, on veut s’abstraire des deux premieres donnees. Pour se faire, il faut ^etreen mesure de donner un cadre theorique a l’algorithmique. Pour le premier point cecise fait par la de nition d’un ordinateur ‘universel’ (une machine de Turing) qui bienqu’extr^emement simple peut reproduire le comportement de n’importe quel ordinateurexistant. Pour s’abstraire du second point, on regardera des classes d’equivalence decomplexite (voir plus bas) plut^ ot que la complexite elle-m^eme, ce qui permettra de ne passe preoccuper des constantes qui interviennent dans les changements de representations‘naturelles’ et dans la de nition des operations elementaires.La mesure de la complexite d’un algorithme c’est :1. evaluer les ressources (memoire et CPU) utiles;2. Comparer deux algorithmes pour le m^eme probleme;3. donner une borne sur ce qui est e ectivement possible de resoudre. On considere60aujourd’hui qu’on peut realiser en temps raisonnable 2 operations. Quant a la10memoire elle ...

Informations

• Publié par: Thuwyer
• Nombre de lectures: 34
• Langue: Français

Extrait

Cours:complexite´ Christophe Ritzenthaler November 12, 2008

1Quelquesnotionsg´ene´rales 1.1 Principes Letempsd’exe´cutiond’unprogrammede´penddeplusieursdonn´ees: 1.dutyped’ordinateurutilis´e; 2.dulangageutilise´(repre´sentationdesdonne´es); 3.delacomplexite´abstraitedel’algorithmesous-jacent. Pour le mesurer en MAPLE, on peut utiliser les commandes suivantes (ici pour un programme g ) : S := [ seq ([ i, time ( g (10 i ))] , i = 1 . . . 10)] . Enge´n´eral,onveuts’abstrairedesdeuxpremi`eresdonn´ees.Poursefaire,ilfauteˆtre enmesurededonneruncadrethe´oriquea`l’algorithmique.Pourlepremierpointceci sefaitparlad´efinitiond’unordinateur‘universel’(une machine de Turing ) qui bien qu’extrˆemementsimplepeutreproduirelecomportementden’importequelordinateur existant.Pours’abstrairedusecondpoint,onregarderadesclassesd’´equivalencede complexit´e(voirplusbas)plutoˆtquelacomplexit´eelleˆme,cequipermettradenepas -me sepre´occuperdesconstantesquiinterviennentdansleschangementsderepr´esentations ‘naturelles’etdanslade´finitiondesope´rationse´le´mentaires. Lamesuredelacomplexite´d’unalgorithmec’est: 1.´evaluerlesressources(m´emoireetCPU)utiles; 2.Comparerdeuxalgorithmespourlemˆemeproble`me; 3.donnerunebornesurcequiesteffectivementpossibleder´esoudre.Onconside`re aujourd’huiqu’onpeutr´ealiserentempsraisonnable2 60 op´erations.Quanta`la memoire elle est de l’ordre de 10 10 octets. ´ Onpeutdoncs’int´eresser`adeuxtypesdecomplexite´:entempsetenm´emoire.Nous id´ereronsquelapmi` ne cons re ere. Lacomplexite´abstraitesemesureenfonctiondelatailledesentr´ees.

1

Example 1. Pourunentier,ils’agitdunombresdechiffresn´ecessaires`ason´ecriture. Onpeutbiensˆurimaginerdescirconstanceso`ud’autresfacteursseraientplusimpor- tants.Parexemplesiunalgorithmefactoriseunnombreal´eatoiredeplusenplusgrand a ` chaque fois qu’il rencontre un 9 dansl’e´crituredunombre.Onnotera | a | b la taille de a en base b .Onabiensˆur | a | b = b log b a c + 1 . Remarquons qu’un changement de base multiplie la taille par une constante. Pouruneliste,leparame`treestlecardinaldelaliste.Onpeutnoterquececiestcohe´rent aveclacomplexite´pourlesentiers,carletableaupourraitcontenirleschiffresdunom- bre. Dans l’algorithme de la division euclidienne, on a deux entiers a, b enentr´ee.Onmesur- eralacomplexit´eenfonctiondu sup( | a | , | b | ) . Pourunematricecarr´eedetaille n c’est n leparam`etre.Danslecasd’ope´rationssur lesmatrices,lacomplexite´seraalorsexprime´ecommeunefonctionde n desope´rations concernantlescoefficients(quin’aurontpaslemeˆmecoˆut´el´ementaireselonlanature descoefficients-lacomplexit´eenfonctiondesop´erations´ele´mentairespouvantˆetrealors calcule´edansundeuxie`metemps). Lorsqu’onmanipuledesre´els,lasituationest´egalementcomplique´e:ilfaudrade´finir unee´crituretronque´epourpouvoirr´ealiserlescalculs.Maisattentionalorsauxerreurs d’arrondis ! Pourunpolynˆome,c’estsondegre´. Enfindanscertainscas,iln’estpaspossibledenefaireintervenirqu’unedonn´ee.Par exemplepourungraphe,lenombredesommetsetd’areˆtespeuventˆetretouslesdeux desfacteursimportantsetpourtantcompl`etementinde´pendants. Commeannoncer,afindesimplifierl’´etude,onregardeuniquementdescomplexit´es asymptotiques(c’est-a`-direquandlatailledel’entr´eetendversl’infini)quined´ependent quedeladerni`erecondition.Cettecomplexite´existesousplusieursformes:dansle meilleur des cas, dans le pire ou en moyenne. Ici encore, on regardera surtout la com- plexite´danslepiredescaspuisquec’estellequinousassurequel’algorithmeseterminera toujoursavecletempsauplusannonc´e.Remarquonstoutdemeˆmequelesautrescom- plexite´speuventaussiˆetreutiles:parexemple,encryptographie,c’estletempsminimal danslemeilleurdescasquipermetded´ecidersiaucunalgorithmenepourracasserle protocole en un temps raisonnable.

Lestableauxci-dessousdonnentl’influencedelacomplexite´quand n devient 2 n .

1 log 2 ( n ) n n log 2 ( n ) n 2 n 3 2 n t t + 1 2 t 2 t +  4 t 8 t t 2

1 log 2 ( n ) n n log 2 ( n ) n ) n 3 2 n n = 10 2 1 µs 6 µs . 1 ms . 6 ms 10 ms 1 s 4 × 10 6 a n = 10 3 1 µs 10 µs 1 ms 10 ms 1 s 16 . 6 mn ∞ n = 10 6 1 µs 20 µs 1 s 20 s 11 j 10 3 a ∞

2

Ilestparfoistr`esdifficiled’´evaluerlesconstantesenjeux.C’estpourquoiondis- tingueraplutˆotdesclassesdecomplexit´e:si n estlatailledel’entre´e,ondiraque l’algorithmeestpolynomial(resp.exponentiel)sisontempsd’ex´ecutionestdel’ordre de Θ( n b )o`u b ≥ 1 (resp. Θ(exp( an )) avec a > 0). Rappelons que deux fonctions f ` , g a valeurspositivessontdumˆemeordre( f = Θ( g )) si pour x assez grand, il existe deux constantes a, b telles que af ( x ) ≤ g ( x ) ≤ bf ( x ).Enpratique,onutiliseraplutˆotla comparaison f = O ( g ) pour simplement donner une majoration. Attentiontoutefoisauxlimitesd’unre´sultatasymptotique:pouruneplagede donne´esfix´ees(etfinies)ilsepeutqu’unalgorithmeen O ( Cn 2 ) soit plus rapide qu’un algorithme en O ( C 0 n ) si la constante C est beaucoup plus petite que la constante C 0 . C’est par exemple le cas de la multiplication par l’algorithme FFT. Cesdeuxclassesse´parentlesalgorithmesditsefficaces(=polynomial)desautres (=exponentiel). En effet supposons que pour un nombre entier de taille n le programme A soitdecomplexite´ n 3 et le programme B decomplexit´e2 n . Alors si la puissance de calculestmultiplie´epar1000, A pourratraiterdesdonne´es n 0 = 10 n fois plus grande alors que le programme B seulement n 0 ≈ n + 10. Enfonconsleclouetre´pe´tonsencoreunefoislecaracte`reinvariantdecesnotions: ¸ par exemple par un changement de base, un entier de taille n devient de taille αn avec α uneconstante.Cecinechangedoncpaslesclassesdecomplexite´etmˆemel’ordredans le cas polynomial. 1.2Mesuredelacomplexit´ed’unalgorithme R`eglesge´ne´rales: 1.Letempsd’e´xe´cutiond’uneaffectationoud’untestestconside´r´ecommeconstant; 2.Letempsd’unese´quenced’instructionestlasommedestempsdesinstructions qui la composent; 3.letempsd’unbranchementconditioneleste´galautempsdesmaximumdesalter- natives 4.Letempsd’uneboucleeste´galauproduitdutempsdesinstructionscontenues dans la boucle par le nombre de passages dans celle-ci. Donnonsquelquescomplexit´esclassiques: • Comparaison de deux entiers de taille n : O ( n ). • addition de deux entiers de taille n : O ( n ). • multiplication de deux entiers de taille n : O ( n 2 ). • division euclidienne de deux entiers de taille n : O ( n ). 3