algorithme avancé

7/25/2019 algorithme avanc

1/70

Alg Avance H. Jamoussi Elkamel , FSM 1

Analyse et complexit des

algorithmes


2/70

Alg Avance H. Jamoussi Elkamel , FSM

La question aborde dans ce chapitre est la suivante:Comment choisir parmi les di!!rentes approches"mthodes de rsolution# pour rsoudre un

problme?

Exemple$Approche itrative ou rcursive?

Algorithme de tri : par insertion, bulle, tri fusion outri rapide?

%ntroduction


3/70

Alg Avance H. Jamoussi Elkamel , FSM &

%ntroduction

Pour comparer des solutions dun problme, plusieurs

points peuvent !tre pris en considration Exactitude des algorithmes : prouver que le rsultat de

limplantation est celui escompt"

Simplicitdes algorithmes"

'on(ergence et sta)ilit des algorithmes: que nos solutions convergent vers la solution e#acte $estimation de la

solution e#acte% "

que la perturbation des donnes ne change pas dune manire drastiquela solution obtenue

E!!icacit des algorithmes : que nos solutions ne soient paslentes et ne prennent pas despace mmoire considrable&

'ans ce chapitre, on sintresse ( l*analyse de l*e!!icacitdes algorithmes.


4/70

Alg Avance H. Jamoussi Elkamel , FSM +

%ntroduction

Lanal)se dalgorithmes se veut un outil d*aide lacomparaison des per!ormances des algorithmes&

Lanal)se de la comple#it permet de* +avoir les limitations dun algorithme $un algorithme peut

se#cuter sur un eu# des donnes, mais pas sur un autre%"

* Choisir les machines appropries pour e#cuter convenablement unalgorithme"

* Comparer deu# algorithmes pour un m!me problme afin de choisirle plus efficace&

'ans le cadre danal)se dalgorithmes, il sagit de mesurerles ressources criti-ues $coteuses% utilises par lesalgorithmes& Ces ressources sont, essentiellement :* /*espace mmoire

* /e 0emps d*excution


5/70


%ntroduction

Dfinition: on appelle complexit de l*algorithmeApour la ressource 2la !onction

0"A, 2, n#-. ressource 2utilise par l*algorithme Alorsquilest e#cut sur un ensemble des donnes de taille n/

/a taille des donnes d*entredpend du problme( rsoudre, elle peut !tre dfinie comme tant

l*espace -ue les donnes en entres occupent en mmoire* 0#: dans le cas dalgorithme puissance : nom)re de )its reprsentant

l*entre n

3om)re d*lments constituants l*entre* 0#: algorithme de tri : le nom)re des lments trier


6/70


Dfinition : la complexit spatiale dun algorithmeest la taille de lespace mmoire utilis pourle#cution dun algorithme

0"A, espace, n# 0lle dpend : 'e la 1aille de donnes dentre

'u Choi# dune structure de donnes2 t)pe de donnes

La comple#it spatiale est un problme en moinsprimordial vu les capacits techniques actuelles desmmoires&

'omplexit Spatiale


7/70


'omplexit Spatiale

'ans le cadre dun algorithme itrati!, lespace utilis peutse rsumer ( celui ncessaire pour reprsenter les (aria)lesutilises.

Fonctionfact3ter$a: entier%: entier6ar res: entier

7e)ut res 45

0ant -ue$a 6 5% Faire res 4res a a 4$a75%

Fin0ant-ue 8etourner $res%

Fin

La comple#it spatiale dans

cet algorithme est constante8 la taille de la (aria)le res9 la taille de la (aria)le a


8/70

Alg Avance H. Jamoussi Elkamel , FSM :

'omplexit Spatiale

Fonctionfact8ec$a:entier%:entier

7e)ut Si$a - 9%alors

retourner$5%

sinon

retourner $a fact8ec$a75%% !insiFin

/a complexit spatiale 8

taille de la pile d*excution taille de la (aria)le a8a ; taille de

lenvironnement de#cution taille de la variable a

/a complexit spatialeestmultiple de a

'ans les algorithmes rcursi!s, il faut considrer en outre

l*espace re-uis pour grer lensemble des appels rcursi!s&Cette gestion est organise au travers dune pile d*excution,dont la taille est !onction du nom)re d*appels rcursi!s.


9/70

Alg Avance H. Jamoussi Elkamel , FSM ;

7!inition $ la complexit temporelle dunalgorithme est le temps mis par ce dernier pours*excuter.

La comple#it temporelle dpend des paramtres

du problme ( rsoudre c7(7d la tailles desdonnes d*entres

La comple#it temporelle dun algorithme A

pour une donne7de taille nsera note 0"A, n#ou simplement 0"n#

'omplexit temporelle


10/70

Alg Avance H. Jamoussi Elkamel , FSM 1s une case d*un ta)leau "0Di#* 2etourner "rsultat# d*une mthode* prations arithmti-ues "9, =, G, #* Etc.


16/70


@ne primiti(e dans le modle 8A correspond (une instructiondans un langage de programmation&

'ans le modle 8A, on suppose que le temps

d*excution de toutes les primiti(es est le mImecest7(7dire une unit de temps&

Calculer la comple#it temporelle dun algorithme

revient ( comptabiliser le nom)re de primiti(esquil contient&

Mod>le de machine 2AM


17/70


lment de calcul de la complexit temporelle

1$opration lmentaire%- constante - 5

1$si$C % alors3 sinonE !insi% F 1$C % ma# $1$3%, 1$E%%

1$pouri dee5 eG !aire3 !inpour% -

-1$affectation% $eG7e55%;1$comparaison%

$eG7e5%; $1$affectation%1$incrmentation%% 1$3i% - 5$eG7e55%G$eG7e5% 1$3i%

-=$eG7e5%G1$3i% 1emps de calcul des mthodes rcursi(es est la solution

d*-uations de rcurrence&

Mod>le de machine 2AM


18/70

Alg Avance H. Jamoussi Elkamel , FSM 1:

'omplexit mathmati-ue

Exemple$Kro)l>me: 8echerche squentielle Entres : une squence de n

lments a5, aG, && andun

tableau 1 et un lment 0&

Sorties: i indice de llment 0dans le tableau 1 sil e#iste, 75sinon

Krincipe 'ans un tableau de taille n, on

commence au dbut du tableauet on considre chaque lment

usqu( ce que llmentcherch soit trouv ou soit ontermine le tableau&

Fonction8ech+eq$1:1ab" 0: element" n : entie: entier 6ar i: entier 7e)ut1 i45

0ant -ue $$i Fn % 01 $1HiIJ60%% Faire& i4i5 Fintant-ue+ Si$i6n%

Alorsretourner $75%4 Sinon 8etourner $i%!insi

Fin


19/70

Alg Avance H. Jamoussi Elkamel , FSM 1;

'omplexit mathmati-ue Kous attribuons un cot pour chaque instruction, et nous comptons le nombre

de#cutions de chacune des instructions& Pour chaque i H5,nI, nous notons tilenom)re d*excutionde la )oucle tant -uepour cette valeur de i&

%nstruction 'ot 3om)re d*excutions

5 c5- 5 affectation -5 5

G cG-G comparaisons Accs - = ti

= c=- addition affectation - G $ti75%

> c>- comparaison -5 5

M cM- retour - 5 9 ou 5

N cN- retour - 5 9 ou 5

0"n# 8 c19 cGti9 c&G"ti=1#9c+ 9max"c, c4#

0"n# 8 "c9 cGti9 c1=c& 9c+9max"c, c4#

0"n# 8 Gti 9 1 tidpend de la position de E dans le ta)leau


20/70

Alg Avance H. Jamoussi Elkamel , FSM tre n& Cest le nombre minimal dinstructionslmentaires e#cutes sur lensemble de donnes ' detaille n&

0min"n#8 0min"A,n#8min L0"A,d# pour tout donnes 7 de taille nN

La comple#it minimale : cest une borne minimale detemps de#cution

* na aucune utilit pratique* 3l se peut que cette comple#it ne soit atteinte -ue pour unensem)le tr>s rduit des donnes, donc non reprsentatif du

problme&

'omplexit minimale


22/70


/a complexit maximale reprsente la comple#it dunalgorithme A dans le pire casen fonction du paramtre n&Cest le nombre ma#imal dinstructions lmentairese#cutes sur lensemble de donnes ' de taille n&

0max"n#8 0max"A,n#8max L0"A,d# pour tout donnes d de taille nN

Le temps de#cution dans le pire de cas dun algorithmeA est )orne suprieure du temps d*excutionpour uneentre quelconque&

@n algorithme qui a de )onnes per!ormances dans lepire des cas, aura touours de bonne performances quelquesoit les donnes en entre

'omplexit maximale


23/70


/a complexit moyenne reprsente la comple#it dun algorithme

A dans le cas moyen en !onction du param>tre n.Cest le nombremo)en dinstructions lmentaires e#cuts sur lensemble dedonnes ' de taille n&

Cest7(7dire la moyenne de toutes les complexits, 1i$n%, pouvantapparaitre pour tout ensemble de donnes ' de taille n

0moy"n#8 0moy"A,n#8 p"d# G 0"A,d# d de taille n

'ans le cas oD lon connait la probabilit P ide ralisation de lavaleur 1i$n%, alors par dfinition, on a:

0moy"n# 8 p101"n# 9 p0"n# 9 p&0&"n# 9 ... 9pn 0n"n#0min"n# B0moy"n# B0max"n#

La comple#it mo)enne ncessite une ide prcise sur les donnesdu pro)l>me& 0lle est difficile ( utiliser en pratique&

'omplexit moyenne


24/70


'omplexit de la recherche s-uentielle

0"n# 8 Gti 9 1

Meilleur casLe cas favorable se prsente quand llmentE setrouveau d)ut du ta)leau

ti 81

0min"n# 8 4$une seule affectation = test un accs un retour de la fonction%Kire cas: Le cas dfavorable se prsente quand llment E ne se

trou(e pas du tout dans le ta)leau& 'ans ce cas, lalgorithmeaura ( e#aminer, en vain, tous les lments&

ti 8 n91

0max"n# 8 G ti91 8 "n91#918n 94


25/70


'omplexit de la recherche s-uentielle

'as moyen: le calcul de comple#it mo)enne se fait comme suit:

Pour plus de simplicit, on suppose que E existe dans leta)leau&n suppose aussi que sa pro)a)ilit de prsencedans lune des

positions de ce tableau est de 1n "loi uni!orme#

+i 0 est dans la position idu tableau, la comple#it 1$n% delalgorithme est0i"n# 8 Gti91avec ti8 i

Par consquent, la comple#it mo)enne de notre algorithme est :

G

PM5

G

%5$M%

G

%5$M$

5%$

%5M$

55

%$%$55

+=+

+=+

+=

+== ==nn

nnn

nnT

innnTnT

moy

n

i

n

iimoy

' i i


26/70


'omplexit asymptoti-ue

Lanal)se de la comple#it selon le modle 8A est difficile (

appliquer sur des algorithmes de grande taille n a besoin dune mthode danal)se permettant de rendre le

calcul plus simple, et daboutir ( la mIme conclusionconcernantle comportement de l*algorithme&

/a complexit asymptoti-ue d*un algorithme dcrit lecomportement de celui7ci quand la taille ndes donnesdu problme trait devient de plus en plus grande, plutQtquune mesure e#acte du temps de#cution&

@ne notation mathmati-ue$notations de /andau%, permettantde reprsenter le comportement as)mptotique:* ?rand= "Oig=h# $ * ?rand=mga "Oig=mega# $

* ?rand=0hta "Oig=0heta# $

3 t ti P? d Q "Oi h#


27/70


3otation P?rand=Q "Oig=h#0#prime le fait quune fonction est R in!rieure ou galeS ( une autrefonction au sens asymptoti-ue&7!inition: +oient !"n#et g"n#deu# fonctions ( valeurs strictement positifs&

f, g : K; 8

!"n#est dite "g"n##ssi il e#iste une constante c>0et un entier n


28/70


0$n% - c est en $5%& c9-c et n9-5

0$n% - =nG7G est en $nG%& c9-= et n9-5

0$n% - >n= GnG7M est en $n=%& c9-N et n9-5

0$n% - MnGlog(n) est en $n%& c9- et n9-5

0$n% - Mn+n log(n) est en $nlog(n)%& c9-N et n9-5

0$n% - =nn= n log(n) est en $3n%& c9-G et n9-5

Trand7 permet de se concentrer sur les !acteursdominantsdans le#pression de la comple#it&

P?rand=Q$ Exemples

P? d Q 2> l d i li!i i


29/70


+oient e, f, g, et h quatre fonctions de K; 81. /es constantes sont ignores +i f$n% est $g$n%% alors k .f"n#est $g$n%%" oD k6 9,

kconstante

+i f$n% est $g$n%% alors k 9 f"n#est $g$n%%" oD k6 9,k constante

. /a notation grand= est transiti(e+i f$n% est $g$n%% etg$n% est $h$n%% alors f$n% est$h$n%%&

=& +if$n% - $g$n%% et e$n% - $h$n%%, alorsf(n) e$n% est $g$n% h$n%%

f$n%;e$n% est $g$n% ; h$n%%

4. f$n% -a0+a1n+....+annk

est en $nk

% &

P?rand=Q$ 2>gles de simpli!ication

P? d Q


30/70

Alg Avance H. Jamoussi Elkamel , FSM &0et un entier n95 telle que nn9

c. g"n#

f"n#Signi!ication: la notation Trand7indique une )orne in!rieure sur letemps d*excution.T(n)est en $g$n%% Pour toutes les grandes entres $i&e&, nn9%, on estassur que lalgorithme ncessite au moins c.g"n#instructions lmentaires&

Oorne in!rieure.Exemple $ 0$n% - c5nG cGn3&c5n

G cGnV c5nGpour tout n6 5" donc 0$n% cnGpour c- c5et n9- 5&Ainsi, 0$n% - $nG%&

P? d 0hI Q


31/70

Alg Avance H. Jamoussi Elkamel , FSM &1

P?rand=0hItaQTrand7 0#prime quune fonction fest as)mptotiquement R galeS ( uneautre fonctiong&

7!inition: +oient f"n#etg"n#deu# fonctions ( valeurs strictement positifs&f,g: K; 8

f"n#est dite "g"n## ssi f"n#est "g"n## et f"n#est "g"n##

c7(7d : c1

>0, c2

>0et un entier n9

5 2 nn9

c1

.g"n# f"n# c

.g"n#

C i d f ti


32/70


Pour comparer deu# fonctions f et g, en termes dordre, on calcul

Comparaison de fonctions

%$%$lim

ngnfL

n =

Kroprits1.+i / 8 a


33/70

Alg Avance H. Jamoussi Elkamel , FSM &&

2emar-ue$ dans plusieurs cas, pour faciliter lescalculs, la r>gle de l*HRpital est souvent utilise&Cette rgle est pratique car, en gnral, la drive

dune fonction est facile ( valuer que la fonction

elle7m!me:

%$

%$lim

%$

%$lim

W

W

ng

nf

ng

nf

nn

=


34/70

Alg Avance H. Jamoussi Elkamel , FSM &+

'lasse de 'omplexit

Les algorithmes usuels peuvent !tre classs en un

certain nombre de grandes classes de comple#it:

*Comple#it constanteen $1%

*Comple#it logarithmi-ue$log"n#%

*Comple#it linaire en $n%*Comple#it -uadrati-ueen $n%

*Comple#it polynomialeen $nk% pour X 5*Comple#it exponentielleen $n%

*Comple#it super=exponentielle$nn% ou %G$G

n

O

E l


35/70


Exemple

$n%

$nG%

$n=%

$Gn%

$lg n%


36/70


0aux de croissance

> i i


37/70


2>gles pour dri(er la complexit 2>gle 1: la comple#it dun ensemble dinstructions est la

somme des comple#its de chacune delles&

2>gle : /es oprations lmentairestelles quelaffectation, test, accs ( un tableau, oprations logiques etarithmtiques, lecture ou criture dune variable simple &&&

etc, sont en "1# "ou en (1))

2>gle &: 3nstruction si: maximumentre le blocdinstructions de alorset celui de sinon

selon

: prendre le maximumparmi les comple#itsdes blocs dinstructions des diffrents cas de cetteinstruction&

2> l d i l l i


38/70

Alg Avance H. Jamoussi Elkamel , FSM &:

2>gles pour dri(er la complexit 2>gle +: 3nstructions de rptition:

5& la comple#it de la )oucle pour est calcule par lacomplexit du corps de cette boucle multiplie par lenom)re de !ois -u*elle est rpte&

G& 0n rgle gnrale, pour dterminer la comple#it dune

boucle tant que, il faudra avant tout dterminer le nom)rede !ois -ue cette )oucle est rpte, ensuite le multiplierparla complexit du corpsde cette boucle&

2>gle $Procdure et fonction: leur comple#it est dterminepar celui de leur corps&

Kotons quon fait la distinction entre les !onctions rcursi(eset celles -ui ne le sont pas: dans le cas de la rcursivit, letemps de calcul est e#prim comme une relation dercurrence&

E l


39/70

Alg Avance H. Jamoussi Elkamel , FSM &;

Exemples

Exemple 1:

a 4 b

1emps constant: $5%&

Exemple : somme 4 9 Kouri de5 n !aire

somme 4somme n"Fin pour

0emps$$n%

E l


40/70

Alg Avance H. Jamoussi Elkamel , FSM +s cha-ue itration, lataille de l*ensem)le de recherche est di(ise par deux&Au dpart, cet intervalle est gal ( !in* de)ut 5 - n&

2echerche d*un lment dans un ta)leau tri

2echerche d*un lment dans un ta)leau tri


45/70


%tration inter(alle de recherche

< n 1 n n+ & n:

................................................

k nkn arr!tera les itrations de la boucle tant -ue ds que la condition

suivante est vrifie $de)ut 8 !in% nk8 1 n8 kk 8 "logn#

Autrement dit, la comple#it de cet algorithme dansle pire cas est en"logn#&

Exercice: comple#it dans le cas moyen?

2echerche d un lment dans un ta)leau tri


46/70

Alg Avance H. Jamoussi Elkamel , FSM +4

Analyse d*algorithmes rcursi!s

Krincipe de l*analyse d*une mthode rcursi(e


47/70

Alg Avance H. Jamoussi Elkamel , FSM +5

Lanal)se dune mthode rcursive se fait sur deu#

tapes:

5& 'finition de la fonction de la complexittemporelle 0"n# ( laide dune -uation de

rcurrencequi dcrit le temps de#cution globalpour un problme de taille nen fonction de tempsde#cution pour des entres de taille moindre.

. 2soudre cet -uation de rcurrence pour endduire le comportement as)mptotique&

Krincipe de l*analyse d*une mthode rcursi(e

0ypes d*-uation de rcurrence


48/70

Alg Avance H. Jamoussi Elkamel , FSM +:

%$&&&&&%G$%5$%$ G5 knTnTnTnT k ++=

0ypes d*-uation de rcurrence

%$%$&&&&&%G$%5$%$ G5 nfknTnTnTnT k +++=

& types d*-uations: quation de rcurrence linaire

quations pour le paradigme R diviser pour rgner S

quation de rcurrence linaire sans second mem)re

+

= %$%$

d%$nsi

%$ nfbnaT

c

nT

cconstante reprsentant le cot dallerchercher une solution particuli>re

0"n)#La comple#it de rsolution dunsous=pro)l>me de taille n)

!"n#est le cot de di(iser le problmeoriginal en sous7problme et puis de

com)iner les solutions&

E-uations de rcurrence$ exemples


49/70

Alg Avance H. Jamoussi Elkamel , FSM +;


!onction !acto $n: entier %:entier

7e)ut Si$n J - 9%

alorsretourner $5% Sinon

retourner $n;!acto$n75%% FinSiFin

+i $n J- 9% on fait 5 test 5retour

+i $n69% on fait

5 test 5 multiplication 5 appel 5

soustraction 5 retour

+==

sinonM%5$

%9$nsiG%$nT

nT

Problme factorielle



50/70


===

5si%$%G$G

%5$ou9$si$5%%$

nnn

T

n)nnT

2solution de l*-uation de rcurrence


54/70


Pour rsoudre les quations de rcurrence plusieurs

approche sont possi)les$

1. Mthode de su)stitution

. Mthode itrati(e

&. Mthode de l*ar)re de rcursi(it "d*excution#

+. Application d*un 0hor>me

2solution de l -uation de rcurrence

Mthode par su)stitution


55/70



La mthode par substitution demande que la forme gnrale

de la solution soit d( pressentie et on utilise linductionmathmatique pour montrer que la solution est correcte et

trouver la constante&

Exemple:

>+

=

= 5nsi%G

$G

5nsi5

%$ nnTnT

ontrer que 0"n#8 "nlog"n## "1#

n suppose que

0t en substituant dans lquation de rcurrence&

%G

$logG

%G

$ GnncnT



56/70


Mthode par su)stitution 'monstration par 3nduction mathmatique

n suppose que la relation $5% est vrifie pour tout XJn eton la dmontre pour n

n suppose que $5% est vrifie pour tout k ncest7(7dire0"k#8 "k.log"k##

%$logW%$log%5$%$log%$log%$donc

%$loget%$log%G$log%$log%G

$log:aonor

%G$log%%G$log%G$$G%G$G%$

GGGG

GGGGG

GG

nncnncnnnncnT

nnnnnn

nn

ncnnn

cnn

TnT

++

=

+++=

0tant donne que $n2G% J n donc

0n substituant dans lquation de rcurrence&

%G

$logG

%G

$29 Gnn

cn

Tc >%$log%$2n"9%%$log$%$ G9G kckkT'ckkOkT >=

Mthode itrati(e


57/70


Mthode itrati(e Lide est de dvelopper la rcurrence et de le#primer sous la forme dune

sommation de termes dpendant uniquement de n et des conditions initiales&

>+=

=5nsi%

G$G

5nsi5%$

nn

TnT

%G

$G%$ n

TnnT +=

%%$log$%$log%5$G%5$

%5$G

G

G&&&&&

5N

G

Z

G

>

G

G

G

%%&&&%%%%5$GG

$G&&&&&&&&5N

$GZ

$G>

$GG

$G

%%%

Z

$G

>

$G

G

$G%%

>

$G

G

$G

GG

%$log5%$log

9

%$log

5%$log

5%$log>=G5

5%$log

G

G

G

G

G

G

nnOnnnTn

Tnnnnn

n

Tnnnnn

n

nT

nnn

nT

nn

nn

i

n

n

n

n

=+=+=

++++++=

+++++++=

+++=++=

=

Se sou(enir -ue (a)(n)in

i

i bb na##

##

loglog5

9

queet5si,5

5=

=+

=

Exemple:

Mthode de l*ar)re de rcursi(it


58/70


Mthode de l ar)re de rcursi(it Larbre de rcursivit est un mo)en pratique pour calculer le

cot dune mthode rcursive&

>+=

=5nsi%

G$G

5nsi5%$ Gn

nT

nT

nG

$n2G%G $n2G%G

$n2>%G $n2>%G $n2>%G$n2>%G

Gn

G

G

5n

G

>

5n

/ogG"n#91

Exemple:

p-9

p-5

p-G

p-logG$n%

..

%5$G%$logG T

n

p-logG$n%75G

5%$logGG

5n

n

Mth d d l* ) d i it


59/70


Mthode de l*ar)re de rcursi(it%5$G%

G

5&&&

Z

5

>

5

G

55$%$

%$log

5%$log

G G

GTnnT

n

n ++++++=

GG

%$log

G

%$log

G

5%$log

G

G

G

55G

5G

5

5

G

5

%G

5&&&

Z

5

>

5

G

55$

G

G

G

ncnn

nn

nn

nn

n

n

n

+

+

=

+

=

++++++=

Se sou(enir -uele nombre de n[uds dun arbre complet ( uneprofondeur p est p

%$%$ GnnT =

0hor>me gnral


60/70

Alg Avance H. Jamoussi Elkamel , FSM 4me gnral

+oient a 1 et ) C 1deu# constantes, soient ! "n# et

0"n#deu# fonctions dfinies sur les entiers positi!spar lquation de rcurrence

>+=

dnsi%$%$

%$nsi%$

nfb

naT

"cnT

comme tant ou

b

n

b

noD lWon interprte

b

n

0hor>me gnral


61/70


0hor>me gnral

%$%$%$log = abnnf

%$%$%$log abnnT =

0"n#peut alors !tre )orne asymptoti-uementde la fa\onsuivante:

pour une certaine constante 6 9, alors1.si

%%$log$%$ G%$log

nnnf kab=

%%$log%$$%%$log$%$ G5

G

%$lognnfnnnT

kab == +alors.si

%$%$ %$log = abnnf

%%$$%$ nfnT =

pour une certaine constante 6 9,&.siet si a.f(n/b)

.f(n) pour une certaine constante J 5 etpour n suffisamment grand, alors

0hor>me gnral$ signi!ication


62/70


0hor>me gnral$ signi!ication

'ans chacun de trois cas on compare!"n# ( la fonction

3ntuitivement, la solution de la rcurrence est dterminepar la plus grande de deu# fonctions&

'as 1: est la plus grande, alors

'as &: la fonctionf(n)est la plus grande, alors T(n)

(f(n)) 'as : les deu# fonctions ont la m!me taille, on multipliepar un facteur logarithmique, et

Remarque :

Les trois cas ne couvrent pas toutes les possibilits pourf(n)& 3l )a untrou entre le cas 5 et G, quand f$n% est plus petit que mais pas

pol)nQmialement& 'ans ce, on ne peut pas appliquer le thorme&

'e m!me, si la condition de rgularit du cas = ne tenait pas&

%$log abn

%$log abn %$%$%$log abnnT =

%%$log%$$%$ G nnfnT =

%$log abn

0hor>me gnrale$ exemples


63/70

Alg Avance H. Jamoussi Elkamel , FSM 4&


%

=

$]%$ nn

TnT +=

a-] , b- =

'as 1 donc, (n)! (n")

%$%$, GG%]$log%$log = ==== nnnfnnn ab

Exemple 1$

%log$%G

$G%$ nnn

TnT +=

a-G , b- G

'as donc, (n)! (n.log""(n))

%log$%$,5%G$log%$log G nnnfnnn

ab ===

Exemple $



64/70

Alg Avance H. Jamoussi Elkamel , FSM4+


%log$%>

$=%$ nnn

TnT +=

a-= , b- >

f(n) (n0+)cas &

%log$%$,P],9%=$log%$log > nnnfnnn

ab ===

Exemple &$

5>

=donc,n&log$n%

>

=%

>log$

>=%$


65/70

Alg Avance H. Jamoussi Elkamel , FSM4

-mem)re

+oit une quation de rcurrence linaire dordre X sans second

mem)re: %$&&&&&%G$%5$%$ G5 knTnTnTnT k ++=

k

kkk ####, = &&&&%$ GG5

5

n ) associe son polynRme caractristi-ue:

La rsolution de ce pol)nQme donne k*B k racines ride multiplicit Ti La solution de lquation est alors :

D i"n#sont des pol)nQme de degr Ti=1&

Les coefficients de chaque ^isont dtermins gr_ce au# k premierstermes "0"


66/70


-second mem)re

Exemple$

+==

=

%G$%5$%$

G%5$

G%9$

nTnTnT

T

T

( )nn

nn

!nT

ab!!

!!###,

5

G5

G5

G

G

M5%$

"M

5Mb"

M

5Maveca1$n%

G

M5

"G

M5

donc5%$

=

+=

=

+=+=

=

+==

2solutions des -uations linaires d*ordre 1 a(ecd )


67/70


-second mem)re

La solution dune quation linaire d*ordre 1de la forme:

%$%5$%$ nfnTanT += est

+=

=

n

i

i

n

a

ifTanT

5

%$%9$%$

2solutions des -uations linaires d*ordre 1


68/70

Alg Avance H. Jamoussi Elkamel , FSM4:

-a(ec second mem)re

+=

=

5%5$G%$

5%9$

nTnT

T

5G5

G

5

5G

5

GG

5

GG

5

5G%$5

5

95 =

=

=

+=

+

+

== n

n

nn

ii

nn

ii

n

nT

G

5=#

Exemple

@tiliser l*-uation ci=dessous a(ec

5 #,5

55

9

=

+

=

#

##

nn

i

i

so ut on es -uat ons na res or red )


69/70

Alg Avance H. Jamoussi Elkamel , FSM4;

-a(ec second mem)re

A une quation linaire d*ordre de la forme :

%$%G$%5$%$ nfnTbnTanT ++=

%G$%5$%$ += nbnan n ) associe l*-uation homog>ne

Puis on rsout C$n% qui est une quation linaire sans secondmembre&

n sait ensuite que 0"n#8 '"n#9g"n#oD g"n# est unesolution particuli>rede lquation dordre G avec secondmembre&

%$%G$%5$%$ nfngbngang ++=

2solution des -uations linaires d*ordre


70/70

-

Exemple$

++==

=

5%G$%5$%$5%5$

5%9$

nTnTnTT

T

%G$%5$%$ += n.n.n.

WaWC$n% G5nn !b! +=

0quation homogne associe

n trouve $les conditions initiales ont chang, a et b sontdiffrents de a et b%

5%G$%5$%$ ++= ngngng

n sait que g$n%C$n%1$n% +=

0t que g$n% est une solution particulire cest7( dire

n trouve que g$n%- fonctionne : -5 0t donc - 5

Documents

algorithme avancé