Algorithmique Notion de complexité PDF

Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et algorithme qui demande un nombre de départ et qui calcule sa factorielle.

ALGO 1.1 œ Correction TD N°5.

Remarque : On ne s'occupe pas de la situation où l'utilisateur saisit un entier strictement négatif. Rappel : 0 ! = 1. Calcul de la factorielle d'un entier

Écologie factorielle et attributs géographiques

Nous verrons plus loin que cette précaution ne devait pas s'avérer inutile. II. DES ALGORITHMES INFORMATIQUES À L'ANALYSE GÉOGRAPHIQUE. La première étape

Informatique et Algorithmique avec le langage Python

gorithmes déjà vu en cours : calcul de la factorielle d'un nombre entier résolution d'une équation du second degré… Un algorithme peut aussi être

Algorithmique Récursivité

informatique : récursivité Moyen simple et élégant de résoudre certain problème. Définition ... Sortie : factorielle de N si N = 0 retourner 1.

livre-algorithmes EXo7.pdf

ALGORITHMES ET MATHÉMATIQUES. 4. LES RÉELS. 17. Cette réalité informatique fait que des erreurs de calculs peuvent apparaître même avec des opérations.

Lanalyse factorielle pour la modélisation acoustique des systèmes

Aug 29 2014 Laboratoire d'Informatique (EA 4128). L'analyse factorielle pour la modélisation acoustique des systèmes de reconnaissance de la parole.

Exercices corrigés

Écrire l'algorithme du calcul de : m3 = m1?m2 . ! BC v2.1. - 11 -.

Algorithmique Notion de complexité

n! la factorielle de n : Algorithme (calcul du plus grand diviseur (solution 0)) ... n non premier =? 2 ? ppd(n) ? pgd(n) ? n ? 1.

Premiers pas en C 1 Exercice 1 2 Exercice 2

Pour tous les exercices de cette feuille il vous est demandé d'écrire l'algorithme correspondant au probl`eme avant son impl ´mentation en langage C.

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 :

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 :

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. 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

21 de 38Analyse des algorithmes

Retenir

Sur une machine où les opérations sur les entiers s"effectuent en temps constant, le temps d"exécution est donc de la forme : aB(n) +b oùaetbsont des constantes.Borne maximale :

Pour les solution (0), (1) et (2)B(n)n2

Pour la solution (3)B(n) bpnc 1

Complexité temporelle maximale :

Pour les solution (0), (1) et (2)a0n+b0

Pour la solution (3)a0bpnc+b0

Évaluation des performances

21 de 38Analyse des algorithmes

Retenir

Sur une machine où les opérations sur les entiers s"effectuent en temps constant, le temps d"exécution est donc de la forme : aB(n) +b oùaetbsont des constantes.Borne maximale :

Pour les solution (0), (1) et (2)B(n)n2

Pour la solution (3)B(n) bpnc 1

Complexité temporelle maximale :

Pour les solution (0), (1) et (2)a0n+b0

Pour la solution (3)a0bpnc+b0

Évaluation des performances

22 de 38En pratique

Voici les temps d"exécution mesurés pour quelques nombres à la fois premiers et proches de puissances de 10 : nsolution 0 solution 1 solution 2 solution 3

111:261071:121071:011078:93108

10092:141062:261062:411061:55107

1000031:861041:961042:151041:05106

100000191:881021:951022:151029:26106

10000000071:851001:921002:081008:88105 100 100 100 100 10Théoriquean+b an+b an+b apn+b

Évaluation des performances

23 de 38Bilan

Retenir

Il est très difficile de prévoir le temps de calcul d"un programme.En revanche, on peut très bienp révoircomment ce temps de calcul augmente quand la donnée augmente.

Notion de complexité

24 de 38Notion de complexité

Notion de complexité

25 de 38Problématique :

On cherche à définir une notion de complexitérobuste, indépendantede l"ordinateur, du langage de programmation,quotesdbs_dbs46.pdfusesText_46

[PDF] 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

Outils mathématiques

5 de 38Outils mathématiques : arithmétique

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

Outils mathématiques

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

8 de 38Fonction Exponentielle et Logarithme

On en déduit (au moins pournentier) :

On défini donc, pourx>0 etaquelconque

Outils mathématiques

9 de 38Différents logarithmes

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

Évaluation des performances

10 de 38Évaluation des performances

Évaluation des performances

11 de 38Temps de calcul

Évaluation des performances

12 de 38Complexités

Évaluation des performances

13 de 38Un exemple

Problème (plus grand diviseur)

Évaluation des performances

13 de 38Un exemple

Problème (plus grand diviseur)

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

Évaluation des performances

14 de 38Algorithme (0)

1k n1vusà voir

Entrée : un entiernSortie : pgd(n)

Pourkde2àn1:

Évaluation des performances

14 de 38Algorithme (0)

1k n1vusà voir

Entrée : un entiernSortie : pgd(n)

Pourkde2àn1:

Évaluation des performances

14 de 38Algorithme (0)

1k n1vusà voir

Entrée : un entiernSortie : pgd(n)

Pourkde2àn1:

Évaluation des performances

15 de 38Algorithme (1)

1k n1à voirvus

Entrée : un entiernSortie : pgd(n)

Évaluation des performances

15 de 38Algorithme (1)

1k n1à voirvus

Entrée : un entiernSortie : pgd(n)

Évaluation des performances

15 de 38Algorithme (1)

1k n1à voirvus

Entrée : un entiernSortie : pgd(n)

Évaluation des performances

16 de 38Algorithme (2)

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Entrée : un entiernSortie : pgd(n)

Évaluation des performances

16 de 38Algorithme (2)

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Entrée : un entiernSortie : pgd(n)

Évaluation des performances

17 de 38Algorithme (3)

On peut maintenant tenir compte de ce que :

D"où il vient que :

Évaluation des performances

18 de 38Algorithme (3)