On va comparer aux constantes près la vitesse de croissance cubique Θ(nk ), k ∈ N, k ≥ 2 polynomiale Θ(an), a > 1 exponentielle Θ(n) factorielle Exemple
Previous PDF | Next PDF |
[PDF] Analyse 1 – Croissances comparées
Rappelons que la version "suites" de l'exponentielle s'appelle "géométrique" Aux protagonistes précédents, s'ajoute la factorielle On a le théorème suivant : Pour
[PDF] Croissances comparées Exemples - capes-de-maths
Fonctions logarithme et exponentielle, limites ; – Théorèmes : de 55 1 3 Suite factorielle Théorème 4 : La général an,nb et n 55 2 Croissance comparée
[PDF] Croissance comparée des fonctions logarithmes, puissances et
La fonction réciproque de la fonction logarithme de base a est x → ax = ex ln a, la fonction exponentielle de base a • Les fonctions puissances sont toutes les
[PDF] Fiche aide-mémoire 2 : Croissances comparées 1 Exponentielles et
l'exponentielle l'emporte sur les puissances, qui l'emportent sur le logarithme Déterminer les limites suivantes, en vous basant, le cas échéant, sur les croissances comparées (CC) suites, la factorielle, qui l'emporte sur (presque) tout
[PDF] Algorithmique Notion de complexité - Laboratoire de Recherche en
On va comparer aux constantes près la vitesse de croissance cubique Θ(nk ), k ∈ N, k ≥ 2 polynomiale Θ(an), a > 1 exponentielle Θ(n) factorielle Exemple
[PDF] FONCTION EXPONENTIELLE - maths et tiques
Définition : On appelle fonction exponentielle l'unique fonction dérivable sur ℝ telle que et Mais sa croissance est très rapide, ainsi exp(21) dépasse le milliard II Etude de la Rappelons que par exemple 5 se lit "factorielle 5" et est égal à 1 x 2 x 3 x 4 x 5 Par cette formule Limites et croissances comparées Propriétés
[PDF] Analyse Asymptotique 1 : - Les Relations de - Pascal Delahaye
13 jan 2018 · Il s'agit ici de comparer les 2 fonctions au voisinage de a Pour cela, formons leur Comparaison puissance et exponentielle : • en +∞ : xα
[PDF] Cours de MPSI - MPSI La Martinière Monplaisir
11 août 2020 · 6 4 Croissances comparées 23 ce cas f(x) < f(x ) par croissance stricte de f, ou x>x , dans ce cas f(x) On appelle fonction exponentielle notée exp la réciproque appelle factorielle n, notée n le nombre n = n ∏
[PDF] ETUDE DES FONCTIONS EXPONENTIELLES DE BASE a
Terminales ES Ch11 Les fonctions exponentielles Année 2010–2011 1 ETUDE DES Croissances comparées : 1) Comparaison de la croissance de la fonction ln et des fonctions puissances au voisinage de + : Si n > 0 lim x + ln x x n = 0
[PDF] ECE3 2011-2012 : Un an de maths - Normale Sup
10 juil 2012 · Les régles de calcul avec la fonction exponentielle sont les mêmes que les règles de calcul sur Croissance comparée des fonctions usuelles en +∞ On appelle factorielle de l'entier naturel n, et on note n, le nombre n =
[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
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 : + =6 de 38Parties entières et égalités
Pour tout réelx, pour tout entiern:bxc=n()nxOutils mathématiques
7 de 38Parties entières et inégalités
Pour tout réelx, pour tout entiern:bxc8 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 log2logarithme 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èsdifficile à 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èmed"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 quelui-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 1Pourkde2à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 1Pourkde2à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 1Pourkde2à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 3Hypothèse : boucle compilée par
un branchement conditionnel et un branchement inconditionnel.A 1C A 2A3vraifaux
É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 A3Hypothèse : boucle compilée par
un branchement conditionnel et un branchement inconditionnel.A 1C A 2A3vraifaux
É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 A3Hypothèse : boucle compilée par
un branchement conditionnel et un branchement inconditionnel.A 1C A 2A3vraifaux
É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 :
t1+ (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 A3Pour 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 :
t1+ (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