[PDF] Algorithmique Notion de complexité





Previous PDF Next PDF





Algorithmique Notion de complexité

n! la factorielle de n : Fonction Exponentielle et Logarithme exp(a) exp(b) = exp(a + b) ... On va comparer aux constantes près la vitesse de croissance.



FONCTION EXPONENTIELLE

que la fonction exponentielle est croissante. Mais sa croissance est très rapide ainsi exp(21) dépasse le milliard. Pour des valeurs de x de plus en plus 



Fiche aide-mémoire 2 : Croissances comparées 1 Exponentielles et

On retient en général que l'exponentielle l'emporte sur les puissances qui l'emportent sur le logarithme. 1 Exponentielles et puissances. Moralement : en cas 



Analyse Asymptotique 1 : - Les Relations de comparaison —

13 janv. 2018 Il s'agit ici de comparer les 2 fonctions au voisinage de a. Pour cela formons leur rapport ... Comparaison puissance et exponentielle :.



Analyse factorielle sphérique: Une exploration

l'analyse factorielle sph?rique. Supposons que nous d?sirions comparer deux tableaux fl3 et 9Ij9 et que nous choisissions deux distributions auxi.



Résumé des nouveaux programmes de Mathématiques du Lycée

Expression des coefficients binomiaux à l'aide de factorielles. Symétrie. Croissance comparée des puissances et de exponentielle en +?.



FONCTION EXPONENTIELLE ET FONCTION LOGARITHME

Rappelons que par exemple 5! se lit "factorielle 5" et est égal à 1 x 2 x 3 x 4 x 5. 2) Croissance comparée des fonctions exponentielles et puissances.



Leçon 265: Exemples détude et dapplication de fonctions usuelles

1.2.1 Résultats de croissance comparée . comparées o`u l'obtention de majorations. ... On définit sur C la fonction exponentielle définie par:.



Fiche PanaMaths (Terminale S) Croissances comparées

? Les principales règles de calcul des limites de fonctions ;. ? Les fonctions logarithme népérien et exponentielle. Ce que vous devez retenir. 1. Les limites 

1 de 38

Algorithmique

Notion de complexité

Florent Hivert

Mél :Florent.Hivert@lri.fr

Adresse universelle :http://www.lri.fr/˜hivert

2 de 38

1Outils mathématiques2Évaluation des performances3Notion de complexité

Outils mathématiques

3 de 38Outils mathématiques

Outils mathématiques

4 de 38Outils mathématiques : analyse élémentaire

(Uk)k2Nsuite de terme généralUk,k2N (Uk)k2Kfamille d"indexKN; suite extraite de(Uk)k2N q X k=pU ksomme des termesUkoùkvérifiepkq(entiers); Convention utile en informatiquelorsquep>q:la somme estvideet vaut 0,

Outils mathématiques

5 de 38Outils mathématiques : arithmétique

opérateurs usuels : + = Outils mathématiques

6 de 38Parties entières et égalités

Pour tout réelx, pour tout entiern:bxc=n()nxPour tout entiern:n=bn=2c+dn=2e:

Outils mathématiques

7 de 38Parties entières et inégalités

Pour tout réelx, pour tout entiern:bxcOutils mathématiques

8 de 38Fonction Exponentielle et Logarithme

exp(a)exp(b) = exp(a+b) exp(a) =1exp(a) exp(x) =y()x= ln(y) (poury>0) exp(ln(y)) =yln(exp(x)) =x ln(uv) = ln(u) +ln(v) ln1u =ln(u)

On en déduit (au moins pournentier) :

a n= exp(ln(a))n= exp(nln(a))

On défini donc, pourx>0 etaquelconque

x a:= exp(xln(a)):

Outils mathématiques

9 de 38Différents logarithmes

lnlogarithme népérien (ou naturel), de basee log alogarithme de basea:loga(x) =lnxlna logfonction logarithme sans base précise,à une constante multiplicative près log

2logarithme binaire, de base 2 :log2(x) =lnxln2

a x=y()x= loga(y) 2 x=y()x= log2(y)

Évaluation des performances

10 de 38Évaluation des performances

Évaluation des performances

11 de 38Temps de calcul

Sur les machines actuelles, le temps pris par un calcul esttrès

difficile à prévoir, avec une forte composante aléatoire :traduction (interprétation, compilation) code de haut niveau

vers code de bas niveau, microcode.forte dépendance à l"environement (mémoire, système

d"exploitation, multi-threading, hyper-threading...);nombreuses optimisations qui dépendent de l"historique

(caches, prédictions de branches...).Retenir On travaille avec un modèle de machine simplifiée.

Évaluation des performances

12 de 38Complexités

Définitions (complexités temporelle et spatiale)

complexité temporelle: (ouen temps) : temps de calcul;complexité spatiale: (ouen espace) : l"espace mémoire

requis par le calcul.Définitions (complexités pratique et théorique) Lacomplexité pratiqueest une mesure précise des complexités temporelles et spatiales pour unmodèle de machine donné.Lacomplexité (théorique)est unordre de grandeurde ces couts, exprimé de manière la plusindépendantepossible des conditions pratiques d"exécution.

Évaluation des performances

13 de 38Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que

lui-même d"un entiern2.Notonspgd(n)le plus grand diviseur en question.On a : 1pgd(n)n1;pgd(n) =1()nest premier.

Évaluation des performances

13 de 38Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que lui-même d"un entiern2.Notonspgd(n)le plus grand diviseur en question.On a :

1pgd(n)n1;pgd(n) =1()nest premier.

Évaluation des performances

14 de 38Algorithme (0)

On parcours les nombres de 2 àn1 et l"on note le dernier diviseur que l"on a trouvé :

1k n1vusà voir

Algorithme (calcul du plus grand diviseur (solution 0))

Entrée : un entiernSortie : pgd(n)

res 1

Pourkde2àn1:

sikdivisenalorsres k retournerres

Évaluation des performances

14 de 38Algorithme (0)

On parcours les nombres de 2 àn1 et l"on note le dernier diviseur que l"on a trouvé :

1k n1vusà voir

Algorithme (calcul du plus grand diviseur (solution 0))

Entrée : un entiernSortie : pgd(n)

res 1

Pourkde2àn1:

sikdivisenalorsres k retournerres

Évaluation des performances

14 de 38Algorithme (0)

On parcours les nombres de 2 àn1 et l"on note le dernier diviseur que l"on a trouvé :

1k n1vusà voir

Algorithme (calcul du plus grand diviseur (solution 0))

Entrée : un entiernSortie : pgd(n)

res 1

Pourkde2àn1:

sikdivisenalorsres k retournerres

Évaluation des performances

15 de 38Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme (calcul du plus grand diviseur (solution 1))

Entrée : un entiernSortie : pgd(n)

k n1 tant quenmodk6=0:k k1 retournerk

Évaluation des performances

15 de 38Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme (calcul du plus grand diviseur (solution 1))

Entrée : un entiernSortie : pgd(n)

k n1 tant quenmodk6=0:k k1 retournerk

Évaluation des performances

15 de 38Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme (calcul du plus grand diviseur (solution 1))

Entrée : un entiernSortie : pgd(n)

k n1 tant quenmodk6=0:k k1 retournerk

Évaluation des performances

16 de 38Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entiernSortie : pgd(n)

k 2 tant quenmodk6=0:k k+1 retournern=k

Évaluation des performances

16 de 38Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entiernSortie : pgd(n)

k 2 tant quenmodk6=0:k k+1 retournern=k

Évaluation des performances

17 de 38Algorithme (3)

On peut maintenant tenir compte de ce que :

nnon premier=)2ppd(n)pgd(n)n1:

D"où il vient que :

nnon premier=)(ppd(n))2n:Proposition Sinne possède pas de diviseur compris entre2etbpnc, c"est qu"il est premier;Cece permet d"améliorerle temps de calcul pour les nombres premiers : il est donc inutile de chercher en croissant entre bpnc+1 etn.

Évaluation des performances

18 de 38Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entiernSortie : pgd(n)

k 2 tant quenmodk6=0etkn=k:k k+1 sik>n=kretourner1sinon retournern=k

Évaluation des performances

18 de 38Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entiernSortie : pgd(n)

k 2 tant quenmodk6=0etkn=k:k k+1 sik>n=kretourner1sinon retournern=k

Évaluation des performances

19 de 38Analyse des algorithmes

Calcul des complexités

temporelles pratiques des solutions (0), (1), (2) et (3) :

Les algorithmes ont la même

structures : A 1 tant queC:A2 A 3

Hypothèse : boucle compilée par

un branchement conditionnel et un branchement inconditionnel.A 1C A 2A

3vraifaux

Évaluation des performances

19 de 38Analyse des algorithmes

Calcul des complexités

temporelles pratiques des solutions (0), (1), (2) et (3) :Les algorithmes ont la même structures : A 1 tant queC:A2 A

3Hypothèse : boucle compilée par

un branchement conditionnel et un branchement inconditionnel.A 1C A 2A

3vraifaux

Évaluation des performances

19 de 38Analyse des algorithmes

Calcul des complexités

temporelles pratiques des solutions (0), (1), (2) et (3) :Les algorithmes ont la même structures : A 1 tant queC:A2 A

3Hypothèse : boucle compilée par

un branchement conditionnel et un branchement inconditionnel.A 1C A 2A

3vraifaux

Évaluation des performances

20 de 38Analyse des trois algorithmes

Calcul des complexités temporelles pratiques des différentes solutions : Les quatres algorithmes ont la même structures (for = tant que) : A 1 tant queC:A2 A 3 Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécution respectifs des actionsA1,C,A2etA3. Temps branchement conditionnel et inconditionnel :tBCettBI.

Le temps d"exécution est :

t

1+ (tC+tBC+t2+tBI)B(n) +tC+tBC+t3;

oùB(n)est le nombre de boucles exécutées.

Évaluation des performances

20 de 38Analyse des trois algorithmes

Calcul des complexités temporelles pratiques des différentes solutions :Les quatres algorithmes ont la même structures (for = tant que) :

A 1 tant queC:A2 A

3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécution

respectifs des actionsA1,C,A2etA3. Temps branchement conditionnel et inconditionnel :tBCettBI.

Le temps d"exécution est :

t

1+ (tC+tBC+t2+tBI)B(n) +tC+tBC+t3;

oùB(n)est le nombre de boucles exécutées.

Évaluation des performances

20 de 38Analyse des trois algorithmes

Calcul des complexités temporelles pratiques des différentes solutions :Les quatres algorithmes ont la même structures (for = tant que) :

A 1 tant queC:A2 A

3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécution

respectifs des actionsA1,C,A2etA3.quotesdbs_dbs21.pdfusesText_27
[PDF] croissance comparée n factorielle

[PDF] croissance économique france 1er trimestre 2019

[PDF] croissance exponentielle en arabe

[PDF] crossfit flooring australia

[PDF] crossfit flooring canada

[PDF] crossfit flooring home

[PDF] crossfit flooring ideas

[PDF] crossfit flooring nz

[PDF] crossfit flooring uk

[PDF] crossfit rubber flooring

[PDF] crossword puzzles pdf with answers

[PDF] crossword the basics of music

[PDF] crossword the basics of music answer key

[PDF] crossword the basics of music answers

[PDF] crs report f 35