IN101 - cours 04 - 8 octobre 2010

Matthieu Finiasz

Description

Un probl`eme concretLaquelle de ces deux fonctions est la meilleure?IN 101 - Cours 041 int factoriel(int n) {2 int i, res;3 res = 1;30 septembre 20114 for (i=2; i 0, ∃n ∈N , ∀n ≥ n , 0 ≤ f(n) ≤ c ×g(n).0 04 for (i=1; i 0, ∃n ∈N, ∀n ≥ n , c ×g(n) ≤ f(n) ≤ c ×g(n).6 } 0 07 return sum;8 }Exemples : 2 2 2n +n+1=Θ n =Θ 2000n +1000000Pour une simple boucle for la complexit´e est facile `acalculer:log(n)=O(n)la taille ...

Informations

• Publié par: Aprea
• Nombre de lectures: 18
• Langue: Français

Extrait

IN 101 - Cours 04 30 septembre 2011

pre´sente´par Matthieu Finiasz

La notion de complexite´

Unprobl`emeconcret

Laquelle de ces deux fonctions est lameilleure?

1 intfactoriel(intn) { 2 inti, res; 3 res = 1; for (i=2; i<n+1; i++) { 4 5 res *= i; 6 } 7 return res; 8 } 9 intbinom1(intn,intp) { 10 return factoriel(n)/factoriel(p)/factoriel(n-p); } 11

1 intbinom2(intn,intp) { 2 if ((p==0) || (n==p)) { 3 return 1; 4 } else { 5 return binom2(n-1,p-1) + binom2(n-1,p); } 6 7 }

Qu’est-cequelacomplexite´? La notion centrale en algorithmique

Lacomplexite´d’unalgorithmemesuresonequeins`nirttie´cfficae: enfonctiondelatailledesdonne´esa`traiter, asymptotiquement, dans le pire cas, ou en moyenne.

Enpratique,pouruneentr´eedetaillen: on compte le nombre d’dsbeitnoe´arpoaseres,ssai´ecen onregardecommentcenombre´evolueasymptotiquement.

Ils’agiteng´en´eraldexelpe´timoclempteelor ons’inte´ressesouventaussia`laixelpmocpatit´esale.

Un premier exemple simple

1 unsigned intsum_of_squares(unsigned intn) { 2 unsigned intsum = 0; inti; 3 4 for (i=1; i<n+1; i++) { sum += i*i; 5 6 } return sum; 7 } 8

Pour une simple boucleforre:lcul`acacilestfaee´tixelpmocal latailledel’entr´eeestn la fonction faitnmultiplications etnadditions  molpxetilcatsee´nileriae´leiltalatrenl’dee´.ene Unpeudere´flexionpermetdecalculercelaentempsconstant: n(n+1)(2n+1) sum of squares(n) = 6  2 additions, 3 multiplications, une division.

Notationsdecomplexite´ Comparaison asymptotique

De´finitions: Complexit´epolynomiale  silaelbaosrte´vune k ∃k>0,f(n) =O(n). Complexit´eexponentielle  elbasilaeeralirr´eng´en´ n ∃b>1,b=O(f(n)).

Complexite´doublement exponentielle n 2 par exemple :f(n.) = 2 Complexite´sous-exponentielle √ n par exemple :f(n) = 2 .

√ 2 log(n)nnnlog(n)n n 3n n2 n2exp(n)n!n2

Notationsdecomplexite´ Comparaison asymptotique

D´efinitions: f(n) =O(g(n))si ∗ ∃c>0,∃n 0 ∈N,∀n≥n 0 ,0≤f(n)≤c×g(n). f(n) =Θ(g(n))si  ∃c,c>0,∃n 0 ∈N,∀n≥n 0 ,c×g(n)≤f(n)≤c×g(n).

Exemples :     2 2 2 n+n+ 1 =Θn=Θ2000n+ 1000000 log(n) =O(n) n =O(n) log(n)

√ 2 log(n)nnnlog(n)n n 3n n2 n2exp(n)n!n2

Quelques ordres de grandeur

30 Un PC standard fait de l’ordre de2deonecrspaesirnaibsnoitare´po 40 2op´erationssimples  ealisablr´omel.ednrapetuot

60 Lesrecordsactuelssontunpeuau-dela`de2nairnsbiesooitare´p re´alisablepardesgensmotive´s  NSA, Folding@home...  

80 Encryptographieonconside`reque2erianibsnoitare´tonspso irr´ealisables(aujourd’hui) Clefs de 128 bits  se.seuqreuqleruˆuops’asd´ennizsdneai

Premiers exemples :

Unprobl`eme-quatre algorithmes

Fibonacci – Algorithme 1 Versionre´cursivebeˆte

1 unsigned intfibo1(unsigned intn) { if (n < 2) { 2 3 return n; 4 } 5 return fibo1(n-1) + fibo1(n-2); } 6

Ici,lacomplexit´eestlenombred’appels`afibo1 lere´sultatsede´composeenunesommedeF 1 etF 0 : F 4 =F 3 +F 2 = (F 2 +F 1 ) + (F 1 +F 0 ) = (F 1 +F 0 ) +F 1 +F 1 +F 0

F 1 = 1 etF 0 = 0 donc il y a au moinsF n applerse´ucsrsif n  colatseet´xilempΘ(F n ) =Θ(ϕ).

Leprobl`eme La suite de Fibonacci

Oncherche`acalculerF n , lenobiFedetiusaledebromenemi`-i:nacc F 0 = 0 etF 1 = 1 F n =F n − 1 +F n − 2 pourn>1 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

On sait faire le calcul direct : suiter´ecurrentedouble`acoefficientsconstants 2 onr´esoutx=x+ 1 √ √ 1 1  r 1 =ϕ+ 5) et= (1 r 2 = 1−ϕ= (1−5) 2 2 1 n n √ F n = (ϕ−(1−ϕ) ). 5

n ϕ √ r 2  −0.62 donc pourn>1,F n est l’entier le plus proche de . 5

Fibonacci – Algorithme 2 Versionavecm´emoire

OnneveutpasrecalculerplusieursfoislameˆmevaleurF i on utilise un tableau pour stocker tous lesF i .

1 unsigned intfibo2(unsigned intn) { 2 unsigned int*fib =(int*) malloc((n+1) * sizeof(int)); 3 inti; 4 fib[0] = 0; fib[1] = 1; 5 for (i=2; i<n+1; i++) { 6 fib[i] = fib[i-1] + fib[i-2]; 7 8 } 9 intres = fib[n]; 10 free(fib); 11 return res; 12 }

Complexite´deΘ(n) maismplecolaite´tixapsedeΘ(n) aussi.

Fibonacci – Algorithme 3 Versionsansm´emoire

Onconstatequechaquee´l´ementdutableaun’estluque2fois: aux´etapesiet+ 1 ide la boucle.+ 2

1 unsigned intfibo3(unsigned intn) { 2 unsigned intfib0 = 0; 3 unsigned intfib1 = 1; 4 inti; 5 for (i=2; i<n+1; i++) { 6 fib1 = fib0 + fib1; 7 fib0 = fib1 - fib0; 8 } 9 return fib1; } 10

Complexit´edeΘ(n) toujours maiscomplexite´spatialedeΘ(1) maintenant.

Comparaison des quatre algorithmes The´orieetpratiquesontd’accord

Temps de calcul pour les quatre algorithmes :

fibo1 fibo2 fibo3 fibo4

n n Θ(ϕ) Θ(n) Θ(n) Θ(log(n))

40 31s 0s 0s 0s

25 2

18s 4s 0s

28 31 2 2 calculirre´alisable Segmentation fault 25s 195s 0s 0s

Fibonacci – Algorithme 4 Version optimale

Onutiliselecalculdirect,maisone´vitelesnombresflottants. On a : F n = 1×F n − 1 + 1×F n − 2 F n − 1 = 1×F n − 1 + 0×F n − 2 Donc :       F n 1 1F n − 1 =× F n − 1 1 0F n − 2   n − 1   1 1F 1 =× 1 0F 0

Simpleprobl`emed’exponentiation matricielleDT40)(r´esoluen complexite´Θ(log(n)) complexite´spatialeΘ(1).

Note : les valeurs propres de la matrice sontϕet 1−ϕ.

M´ethodesde programmation

Algorithme glouton

Unalgorithmegloutonestunalgorithmeite´ratifqui`achaque´etape essaye des’approcher au maximumde la solution.

Par exemple : lerendudemonnaie:quellesommedebillets/pie`cespermet d’atteindreunevaleurdonn´ee? Pour rendre 37 euros, on calcule 37 = 20 + 10 + 5 + 2.  ets/billcesfpi`eseavldsseelrutesaleuqtnonoitulosoptimale. leproble`meduvoyageurdecommerce:quelestlepluscourt chemin passant parneenv´s?leilonsd Onvatoujoursa`lavillelaplusprochenonencorevisit´ee.  donne une bonne solution, mais rarement optimale.

Quelquesautresme´thodes

Forcebrute:nomdonne´a`unalgorithmequitrouvelasolutionen essayant toutes les solutions possibles. recherche de clef en cryptographie.

Diviserpourre´gner:m´ethoder´ecursivequiconsiste`adiviser unproble`meensous-probl`emes,´ruoseerdroblus-pset`emelosse recombiner.tstaul´rselse algorithmes de tri (voir cours 05).

Algorithmesg´en´etiques:algorithmepourtrouverunesolution (quasi-)optimaled’unprobl`emed’optimisationenpartantdeso- lutionsapproch´ees,enlesfaisante´volueretenless´electionnant. un des projets d’IN104.

Programmation dynamique

Laprogrammationdynamiqueconsiste`asotkcreelrs´esultatsdes instancesd’unprobl`emequel’onre´soutpournejamaisavoira` re´soudredeuxfoisunemˆemeinstance. permetparfoisderendreefficaceunalgorithmere´cursifsimple.

Par exemple : suitedoublementr´ecursive:enstockantlesvaleursinterm´ediaires defibo1on obtientfibo2. n  passe deΘ()`2aΘ(nome´.erinu)elitintsapeunemud coefficients binomiaux avec le triangle de Pascal  voir TD 04.

The´oriedelacomplexite´