Algorithmique Notion de complexité









LOGARITHME D'UNE SOMME ET D'UNE DIFFÉRENCE

Michel Petrovitch (Belgrade). Les logarithmes de Gauss out pour ohjet de faire trouver le logarithme de la somme et de la différence de deux nombres parle.


LOGARITHME NEPERIEN

Remarque : La fonction exponentielle transformant une somme en produit on peut penser que la fonction logarithme népérien qui est sa fonction réciproque
ln


Algorithmique Notion de complexité

somme des termes Uk où k vérifie p ≤ k ≤ q (entiers) ;. Convention utile en informatique log fonction logarithme sans base précise à une constante.
Complexite


1 Sujet : Etudier la somme des inverses des entiers. Création d'un

20 sept. 2017 Graphique résultant de l'algorithme précédent : On remarque une ressemblance avec le graphique de la fonction logarithme népérien. Les résultats.
abcompte rendu maths





FONCTION EXPONENTIELLE ET FONCTION LOGARITHME

Remarque : Cette formule permet de transformer une somme en produit et réciproquement. Corollaires : Pour tous réels x et y on a : a) exp(− ) =.
Texplog


FONCTION LOGARITHME DÉCIMAL

Remarque : La première formule permet de transformer un produit en somme. Ainsi celui qui aurait à effectuer 36 x 62
LogTT


Programme cahier de vacances

Propriétés fondamentales des logarithmes : somme produit


Correction TP de programmation no3 - Fonctions et procédures

logarithme réel void exit(int e) On utilisera une boucle et un accumulateur pour calculer les sommes ... la factorielle la puissance et la somme.
TP corr





Cours de mathématiques - Exo7

Pour un entier n fixé programmer le calcul de la somme Sn = 13 + 23 + 33 + ··· + Dans l'algorithme précédent nous avions utilisé le logarithme décimal ...
ch algo


Dérivées et différentielles des fonctions de plusieurs variables

La différentielle logarithmique df/f d'une fonction de plusieurs ou égale à la somme des valeurs absolues des différents termes.
melodelima christelle p


213975 Algorithmique Notion de complexité

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.

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.
12345 Next
  1. logarithmus summe
  2. logaritmen sommen
  3. somme logarithme népérien