Agregation de mathematiques Option C algebre et calcul formel

Publié par

Niveau: Supérieur, Bac+8
Agregation de mathematiques — Option C : algebre et calcul formel COMPLEXITE DES ALGORITHMES METHODE DU SIMPLEXE O. Marguin — 4/05/11 1. Generalites (1.1) Notion de complexite Un algorithme comporte : - une partie temporelle : sequence d'instructions en principe savamment orchestree, - une partie spatiale : ensemble de donnees plus ou moins structurees (nombres, vecteurs, matrices, listes. . . ). L'algorithme a un cout qui est lie : - au nombre d'operations e?ectuees (operations arithmetiques, logiques, transferts. . . ), - a l'espace-memoire occupe par les donnees. Evaluer ce cout revient a mesurer ce qu'on appelle la complexite de l'algorithme, en temps comme en espace. Il s'agit donc de denombrer des operations et des octets. Lorsqu'on parle de complexite (tout court), on entend generalement complexite en temps. Il faut bien sur preciser quelles sont les operations a prendre en compte. Generalement, pour un algorithme numerique ce sont les operations arithmetiques usuelles (+,?,?,÷) ; pour un algorithme de tri, ce sont les comparaisons entre elements a trier (qui sont en principe les plus couteuses). Les transferts de valeurs ou a?ectations sont souvent negligees. Dans toute la suite, nous ecrirons ces a?ectations sous la forme a ? b, signifiant que la variable a rec¸oit la valeur de l'expression b.

  • tri fusion

  • complexite en temps

  • operations

  • chi?re

  • complexite

  • ordre minimal

  • comparaisons entre elements du tableau e?ectuees


Publié le : vendredi 8 juin 2012
Lecture(s) : 52
Source : math.univ-lyon1.fr
Nombre de pages : 10
Voir plus Voir moins
1.
Agr´egationdemathe´matiquesOptionC:alg`ebreetcalculformel
COMPLEXITE DES ALGORITHMES METHODE DU SIMPLEXE
Ge´ne´ralite´s
O. Marguin — 4/05/11
(1.1)oNitnoxit´edecomple Un algorithme comporte : - une partietemporelleneece´uqs:nsenctiostrudinnemmavasepicnirp,eer´sthercto - une partiespatialeesneelbmodede´nn:cuut´ree(sonbmeresplusoumoinsstr,seceuctves,riat,mrs listes. . .). L’algorithme a unuˆtcoiuseq:elt´i -aunombredop´erationseectu´ees(op´erationsarithm´etiques,logiques,transferts. . .), -`alespace-m´emoireoccupe´parlesdonn´ees. Evaluercecoˆutrevienta`mesurercequonappellelae´tiexplomcde l’algorithme, en temps comme en espace.Ilsagitdoncded´enombrerdesope´rationsetdesoctets. Lorsqu’on parle demplecoe´tix)truoctuot(ern´´edgenntne,oneibruˆsmolpxetilamenects.Ilfaut´eentemp pre´ciserquellessontlesope´rations`aprendreencompte.Ge´n´eralement,pourunalgorithmenume´riquece sontlesope´rationsarithme´tiquesusuelles(+,,×,÷) ; pour un algorithme de tri, ce sont les comparaisons entre´ele´mentsa`trier(quisontenprincipelespluscouˆteuses).Lestransfertsdevaleursouaffectations sontsouventn´eglige´es.Danstoutelasuite,nous´ecrironscesaectationssouslaformeab, signifiant que la variablearpseisnocoe¸rxeledruelavaltib.
(1.2)Ordre de grandeur Soient deux fonctionsfetg:NNdit que. On fetgontpmotaysementiquˆemetlemgederdroruednar, et on notef= Θ(g), s’il existe deux constantesk, Kstrictement positives telles que, pournassez grand, on ait : k g(n)f(n)K g(n)
(cequi´equivaut`aladoublecondition:f= O(g) etg= O(f)). Sinveesndiomarseuctelpmexersnemidal´lseinup,)notuesqunetianledesdonn´ees(pa´tle´ieea`alatli parle d’lgor´eaeexdietcoimtphlmg(n), oualgorithme eng(nplomacesqurslo),rofaledtsee´tixemeΘ(g). Un algorithme en 1 (respn) est diten temps constant(resp.´nilreiae).
(1.3)t´eamilpOit Pourr´esoudreunprobl`emedonn´e,lobjectifeste´videmmentdetrouverunalgorithmeoptimalc,tse-a`-diredontlacomplexite´soitdordreminimal.Commeexempledalgorithmeline´aireetoptimal,onpeut citerlalgorithmedeHo¨rnerpermettantde´valuerlespolynˆomesdedegre´ntnuiodprsmdeıfa¨seˆemeL. 2 polynoˆmesestenn. Le produit, le calcul de l’inverse, la factorisationLU . . .atricescarr´eessruelms 3 d’ordrensont ennal´rselotuoidnu,uaer.issaylIpsedysnsemt`inelai´enoenqsu`emeroblcilesdisaitpasr´esoudreentempspolynoˆmial(parexemplelefameuxprobl`emeduvoyageur de commerce). Ame´liorerlecacit´edunalgorithme,cest-`a-direendiminuerlacomplexit´e,estsouventtre`sde´licat.Par exemple, au prix de certaines astuces (voir [3],§2.11),Strassenntdeetta´euvroatiroglanumrepemht log 7 2,8 multiplier deux matricesn×neuqenided(meˆmeletmalersveunerrtci)enenn, ce qui est un 2 3 peu mieux quengr´ededesuoN.dqarstlusponrrvepiilumtleptuunoomeslynˆuxpoerdenennlogn graˆcea`lalgorithmedetransformation de Fourier rapide(FFT).
1
Agr´egationdemathe´matiquesOptionC:alg`ebreetcalculformel
(1.4)Lacomplexit´edunalgorithme,danslecasou`lesdonn´eessontlesplusfavorablesa`sonaccom-plissement, s’appellelpxetie´sacscmoleildeurnsdamelene´edtidnO.leaˆmmensc´edaxetimolp le pire des casainsi que laeet´xileneenoynmpmocsee´ssopelbisquetouteslesdonno,u`noocsndie`er sonte´quiprobables.L´evaluationdecestroistypesdecomplexite´estimportantepourjugerparexemple delecacite´dunalgorithmedetri:voir§4.
(1.5)ar´tgeeitSresividqnocruopireru´ Onaunprobl`eme`are´soudresurunestructuredetaillensrrae´osulitnoa`:iL.ee´dnscoteisra`aneme -lar´esolutiondumeˆmeprobl`emesurplusieursstructuresdetailledivisantn, -puisaurecollementdecessolutionspourobtenirlasolutioncherch´ee. En notantC(nmplexit´)lacoiallepeuolrtanr´neurecalnasuor:epyo,cnertude
C(n) =a C(n/b) +f(n)
o`uaetbsont des entiers,a1, b >uoo`et1ete`rpretninn/bsoit parn/b, soit parn/b.
Th´eore`me: logalogalogaε Avec ces notations, sif(n) = Θ(n), alorsC(n) = Θ(nlogn); sif(n) = O(n)avec b b b loga εconstante>0, alorsC(n) = Θ(n). b
(pourunepreuve:voir[1],th´eore`me4.1).
Dans le premier cas aveca=b= 2, on obtientC(n) = Θ(nlognverrons un exemple d’application). Nous decettestrat´egieau§5.
2.
Recherche dans un tableau
Ilsagitd´ecrireunalgorithmepermettantdede´tecterlapre´sencedun´ele´mentxdans un tableauT[1..n] de taillen.
(2.1)Consid´eronslalgorithme(ditdu drapeau) : existefaux pouri1`deanfaire six=T[i] alors existevrai fin du si fin du pour
(*)
etprenonsencompteuniquementlescomparaisonseectue´esa`laligne(*).Lescomplexit´esdanslepire descas,danslemeilleurdescasetenmoyennesonttoutestroise´gales`an.
(2.2)Pourlemeˆmeprobl`eme,lalgorithmesuivant,quicomporteunebouclea`deuxsorties,estplus efficace : existefaux pouride1`antant que nonexistefaire existex=T[i] fin du pour
carilestfaciledevoirquesacomplexite´est: - dans le pire des cas :n, - dans le meilleur des cas : 1, (n+1) - en moyenne : . 2
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi

suivant