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, ...
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 : Cest -à -d i re q u o n c o n si d è r e q uune 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 lordre de ( n *l o g² (n )). Doù : 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 du 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 laddition, 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 sen servir en p ro g ra m mation ?