(Cours 4 - R 351curer du sol au plafond...)

Verdez Gilles

Description

Programmation FonctionnellerrannolRécurer du sol au plafondur soufdGilles Enée – LS4illné LUniversité des Antilles Guyaneivité AesyaUn peu de complexiténu xi Quelle est la complexité de (fac n) ?uescolexde n(define (fac n)de (fa(if (zero? n)(ro1(* n (fac (- n 1)))))(fa 1Un peu de complexiténu xi Si on choisit come granularité une opération i ooimné pnentre deux nombres : C’est-à-dire qu’on ntuxb C-du’considère qu’une opération entre deux nombres onreneraneumbquelconques coûte 1 temps de calcul.uequoûtedeul On note C la complexité de n! Ote coité!n Alors AC = C + coul p)!>n n-1 n-1C = C + 1 Cn n-1Sachanntt que C == 0, nous ppouvons eenn déduiirree que :0C = 0+1+1+ … + 1 (n fois)+1 + s)nC = (n) (nOn parle de complexité linéaire.n depleinéUn peu de complexiténu xi Observons les résultats obtenus sur la bons ltbs lamachine :ae (time (fac 4000)) => 32 ((fa00 3 (time (fac 8000)) => 156 ((fa00 1 (time (fac 16000)) => 671 ((fa00> (time (fac 32000)) => 3015((fa00> Est-ce que la progression est linéaire ?squ pes ené ?Un peu de complexiténu xi Pourquoi ?ooi Parce que la granularité réelle est la P q glaet multiplication de deux chiffres et pas de deux mlic duxfrepa dnombres !nre Le nombre de multiplication de deux chiffres Lme iplneuiffrdans le produit de n-1! par n est de l’ordre de dleui-1r ndere(n*log²(n)). D’où :g² D C = C + n log²(n) = Cn l)n n-1 Finalement, ...

Informations

• Publié par: Ebbi
• Nombre de lectures: 41
• Langue: Français

Extrait

P r o g r ammation Fonctionnelle R écurer du sol a u plafond

Gi l l es  Enée  – L S4

Univers i t é  des  An t i l l e s Guyane



Un peu de complexité

Q u e ll e  e s t l a  comp l ex it é  de (fac n) ?

( define (fa c n )

(if ( z e r o ? n)

1

( * n (fac ( -n 1)))))



Un peu de complexité

S i on choisit come granularité une opération e n t re deu x n ombres : Cest -à -d i re   q u  o n   c o n si d è r e q uune opération entre deux nombres q u e lc o n q u e s coûte 1 temps de calcul.  On note C n la complexité de n!  Alo rs C n = C n -1 + <Le coût de multiplier n p a r   (n -1 ) ! >  C n = C n -1 + 1 Sachant que C 0 = 0, nous pouvons en   dédu i re   que : C n = 0+1+1+ … + 1 (n fois)  C n =

( n) On parle de complexit é li né aire.





Un peu de complexité

O b s e r v ons  l es  résu lt a t s  ob tenu s  s u r  l a ma c h i n e :  (time (fa c 4 000)) => 32  (time (fa c 8 000)) => 156  (time (fa c 1 6000)) => 671  (time (fa c 3 2000)) => 3015

Est -c e  que  l a  progress i on  e st linéaire ?

Un peu de complexité

 P o u rq u o i ?  Parce qu e la granularité réell e   e st l a   multipli c a tion de deux chiffres e t p a s d e   d e u x nombr e s !  Le nomb re de multiplication de deux chiffres dans le   p roduit de n -1! par n est de lordre de

( n *l o g² (n )). Doù :  C n = C n -1 + n log²(n)  Finaleme nt, on trouve grâce à la somme de Riemann   C n , q ue la complexit é   e st d e l o rd re : (n² log²(n))



Un peu de complexité

L a t h é o r i e est -e l l e  sauve  ?  Passage de n = 4000 à n = 8000 :  x   4 .6965 selon la théorie  x   4 .875 selon nos mesures !  Passage de n = 8000 à n = 16000 :  x   4 .6408 selon la théorie  x   4 .3013 selon nos mesures…  Passage de n = 16000 à n = 32000 :  x   4 .5933 selon la théorie  x   4 .4933 selon nos mesures.





Peano

I ma g i n e z que Scheme ne p o ss ède c o mm e p r i m itiv e s   ar it hmé t i ques   da ns N que :

( zero? n) (add1  n)

(sub1 n)

I n t e rd icti on  donc  du t i l i ser  l e s opérations + -* / quotien t, e t c… ni les pr édi c at s = < <=   e tc…

Peano

 D é f inisson s l  a ddition générale d a n s NxN de la m a n i è r e suivante, par récurrence sur x : ( d efine ( a d d x y) ; x e t y da n s N ( if ( z e r o? x) y ; 0 + x = x ( add1 ( a dd (sub1 x) y)))) ; x + y = [(x -1)+y]+1  E st-c e   une itération ?

Peano

 D o n n e z une version itérativ e ( addi t x y).  Me s u rons la complexité de   l a f on c t i on ré c ur siv e.  Choisisso ns comme granula r it é l e s o p é ra ti o n s de bas e add1, sub1. (i.e. ces o p é ra ti o n s coûte « 1 »)  Soit C x ,y le coût de (add x y)  On se pro pose de chercher u n   é q u iv a l e n t d e   cette q u antité C x,y

Peano

 E n  re lis ant laddition, on dé dui t  l e s   é q u a ti o n s suivantes :  C 0 , y = 0  C x,y = C x -1,y + 2  O n   e n   déduit aisément que C x , y e s t   p ro p o r ti onnel à x et indépe ndant de y  C x y = k x . ,  L a c o mp lexité reflète souve nt   l e te m p s   de c a lc u l, ma i s   dépend   de   l un i t é de m e s u r e.







Généralis ez

E n  p a ss ant à « l ordre  sup ér i eu r » ! L e s ma t héma t i c i ens   on t co mmencé à d é mo n t rer   des   t héorèmes   de géo m ét r i e en d i me n si on   2 , pu i s   en   d i me ns i on 3,   pui s…   e n   d i me nsion n. L a   g é n éralisation étant une   a c t i v i t é i mp o r t ante de la démarche sc i ent i f i que,   p o u rq u o i ne pas sen servir   en p ro g ra m mation ?