[PDF] Chapitre 2 Complexité algorithmique





Previous PDF Next PDF



Calcul de coût dalgorithme

Calcul de coût d'algorithme. Concepts : Analyse de coût. Méthodes : Décomposition du coût ordres de grandeur. Présentation. Le concept de coût associé à un 



Séance 3 : coût dun algorithme

1. les calculs (+ - * / %). 2. les tests ( < > <= >= == != ) 3. les boucles (boucle pour (for) boucle tant que (while)). 4. les fonctions ou comment 



L3 Info Cours 1 : notion de coût dun algorithme

Savoir comment évaluer la complexité d'une solution algorithmique : Le calcul du coût d'un algorithme s'obtient donc en composant les coûts.



Chapitre 2 Complexité algorithmique

22 oct. 2014 Evaluer la compléxité d'un algorithme. Des exemples de calculs de complexité ... Comment évaluer le coût d'exécution d'un algorithme donné ?



L3 Info Cours 2 : algorithmes récursifs analyse en moyenne

Algorithmique et Analyse d'Algorithmes Comment évaluer l'efficacité d'un algorithme plus finement que dans le pire cas ? ... Calcul de coût direct.





cours 2:Complexité des algorithmes récursifs

On parle alors de méthode récursive. Exemple : Le calcul de la factorielle de N. N != N*(N-1)*(N-2)* 



Coût de lalgorithme dEuclide et CAPES interne 2000

Cela nous mène à préciser comment l'estimation peut être affinée en 3) Un majorant du temps de calcul de l'algorithme d'Euclide avait déjà été donné.



Complexité des algorithmes : nombres_instructions élémentaires

Le coût final du conditionnel est : T (conditionnel)=1+max(22)=3. 18 / 51. Page 27. Calculer le nombre d'instructions ´el´ementaires.



TD1.1 Analyse dalgorithmes calculs de coûts

TD1.1 Analyse d'algorithmes calculs de coûts. Objectifs. À la fin de cette séance



[PDF] Calcul de coût dalgorithme

19 sept 2012 · Pour calculer le coût d'un algorithme on utilise les règles de composition suivantes : Le coût d'une itération est égal à la somme des coûts de 



[PDF] Séance 3 : coût dun algorithme

Le coût d'un algorithme est une estimation du nombre d'opérations élémentaires effectué par un algorithme Cette estimation dépend du nombre de ses entrées et 



[PDF] L3 Info Cours 1 : notion de coût dun algorithme

? Savoir démontrer la correction des algorithmes ? Savoir comment évaluer la complexité d'une solution algorithmique : - analyser la complexité au pire en 



[PDF] Calculs de complexité dalgorithmes

Complexités d'un algorithme ?Un algorithme à partir d'une donnée établit un résultat ?La taille de la donnée est mesurée par un entier n



[PDF] Algorithmique et complexité de calcul

Exercice : Décrire cet algorithme Montrer qu'il demande un espace dans O(k) et un temps dans O(nk) si on compte chaque addition à coût unitaire 



[PDF] Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale

2 1 Algorithme de Strassen Le coût de l'algorithme est alors : Question 2 3 Comment calculer le produit d'une matrice de Tœplitz n × n par un 



[PDF] ALGORITHMIQUE

Exemple de progression pour aborder l'algorithmique en seconde Voici l'algorithme qui correspond au programme de calcul Comment les définir ?



[PDF] cours_exemples_exercices algorithmiquepdf - fustel-yaoundenet

2 2 pour qu'il calcule l'expression 3N 2 2 Exercice III 3 Écrire un algorithme permettant de calculer l'expression xy x2 où x et y représentent deux 



[PDF] livre-algorithmespdf - Exo7 - Cours de mathématiques

Voyons comment l'écriture binaire des nombres peut nous aider L'écriture binaire d'un nombre c'est son écriture en base 2 Comment calculer un nombre qui 



[PDF] Arles– Info 1ère année – Matière AP (Module Algorithmique) TD 3

affichage digital effectue un calcul semblable toutes les minutes) Exercice V : Ecrire un algorithme qui permet de calculer le prix d'un troupeau

  • Comment savoir le coût d'un algorithme ?

    Méthode de calcul de coût Le calcul du coût d'un algorithme s'obtient donc en composant les coûts des différentes opérations composant l'algorithme. On écrit f = O(g) pour f ? O(g). On dit que g est une borne supérieure asymptotique pour f .

  • Quel est le coût d'un algorithme de recherche du maximum d'un tableau de nombres ?

    le coût d'un algorithme A(T) est son nombre d'affectation. Ainsi, pour chaque cas de Pn,k, l'algorithme effectue k affectations. On obtient donc ainsi que le coût d'un algorithme A(T) est de kPn,k. coutA(T) = 1 n

  • Comment faire un algorithme PDF ?

    Un algorithme, ou code "bien écrit" doit avoir les propriétés suivantes :

    1Être facile à lire, pas soi-même mais aussi par les autres.2Avoir une organisation logique et évidente.3Être explicite, montrer clairement les intentions du développeur.4Être soigné et robuste au temps qui passe.

  • Résumé des étapes de la méthode

    1Lisez bien le sujet, et reformulez-le.2Faites la liste des dimensions du sujet.3Cherchez une bonne représentation visuelle du problème.4Générez des exemples, et résolvez-les entièrement à la main.5Décrivez la solution naïve, puis essayez de l'améliorer.
Chapitre 2 Complexité algorithmique

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteChapitre 2

Complexite algorithmique

Programmation en Python{2eme annee MP3{

E-mail

mlahby@gmail.com

22 octobre 2014

Programmation en Python{2eme annee MP3{CPGE GSR 2014-20151/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexitePlan

1Introduction

2Notion de complexite

Denition de la complexite d'un algorithme

Types de complexite

3Complexite et notationOLa notationOClasses de complexite les plus usuelles

Comparaison de temps d'execution

4Comment mesurer la complexite d'un algorithme

Le co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeit

5Dierentes nuances de complexite

Programmation en Python{2eme annee MP3{CPGE GSR 2014-20152/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteIntroduction

Exercice

Ecrire en python une fonction qui prend en argument une cha^ne de caracteres et determine si le caractere 'a' est present dans la cha^ne (on retourne soit True soit

False).Analysons plusieurs solutions

1.

Premi eresolution

def contienta1(chaine) : k = 0

N = len(chaine)

result = False while (result == False and kIntroduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteIntroduction

2.

Deuxi emesolution :

def contienta2(chaine) : for i in range(len(chaine)) if chaine[i] == 'a' : return True return False 3.

T roisiemeso lution:

def contienta3(chaine) : n = chaine.count('a') return bool(n) 4.

Quatri emesolution :

def contienta4(chaine) : return ('a' in chaine)Quelques questions :

1que remarquez vous concernant cet exercice?

2Le code le plus court! Est-il meilleur?

3Comment peut-on designer le meilleur code parmi ces quatre solutions?

Programmation en Python{2eme annee MP3{CPGE GSR 2014-20154/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteDenition de la complexite d'un algorithme Types de complexiteDenition de la complexite d'un algorithme

Denition

La complexite d'un probleme mathematique P est une mesure de la quantite de

ressources necessaires a la resolution du probleme P.Cette mesure est basee sur une estimation du nombre d'operations de base

eectuees par l'algorithme en fonction de la taille des donnees en entree de l'algorithme.Generalement, pour le m^eme probleme P, on peut trouver plusieurs algorithmes (Alg1;Alg2;::;Algn).L'objectif de la complexite est d'evaluer le co^ut d'execution de chaque algorithme an de choisir le meilleur. .Probleme : Comment evaluer le co^ut d'execution d'un algorithme donne? Programmation en Python{2eme annee MP3{CPGE GSR 2014-20155/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteDenition de la complexite d'un algorithme

Types de complexiteTypes de complexite

En fonction des ressources utilisees pour evaluer la complexite d'un algorithme, on sera amene a dsitinguer deux types de complexite : complexite temporelle et complexite spatiale.Complexite temporelle (en temps) La complexite temporelle d'un algorithme est le nombre d'operations elementaires

(aectations, comparaisons, operations arithmetiques) eectuees par un algorithme.Complexite spatiale (en espace)

La complexite en memoire donne le nombre d'emplacements memoires occupes lors de l'execution d'un programme.Remarque Dans ce cours, nous nous interessons uniquement a la complexite temporelle. Programmation en Python{2eme annee MP3{CPGE GSR 2014-20156/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLa notationO

Classes de complexite les plus usuelles

Comparaison de temps d'executionLa notationODenition Soit T(n) une fonction qui designe le temps de calcul d'un algorithme A. On dit que T(n) est en grand O de f(n) :T(n) =O(f(n)) si et seulement si :9(n0;c) telle queT(n)<=cf(n)8n>=n0 .Exemples

1Exemple 1 :

siT(n) = 3n+ 6 alorsT(n) =O(n)

Demonstration :

En eet, pourn>= 2, on a 3n+ 6<= 9n; la quantite 3n+ 6 est donc bornee, a partir d'un certain rang, par le produit denet d'une constante.2Exemple 2 : siT(n) =n2+ 3nalorsT(n) =O(n2)

Demonstration :

En eet, pourn>= 3, on an2+ 3n<= 2n2; la quantiten2+ 3nest donc

bornee, a partir d'un certain rang, par le produit den2et d'une constante.Programmation en Python{2eme annee MP3{CPGE GSR 2014-20157/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLa notationO

Classes de complexite les plus usuelles

Comparaison de temps d'executionClasses de complexite les plus usuelles On voit souvent appara^tre les complexites suivantes :

ComplexiteNom courantDescription

O(1)constanteLe temps d'execution ne depend pas des donnees

traitees, ce qui est assez rare!O(log(n))logarithmiqueaugmentation tres faible du temps d'execution quand

le parametre croit.O(n)lineaireaugmentation lineraire du temps d'execution quand le parametre croit (si le parametre double, le temps double).O(nlog(n))quasi-lineaireaugmentation un peu superieure a O(n) O(n2)quadratiquequand le parametre double, le temps d'execution est multiplie par 4. Exemple : algorithmes avec deux boucles imbriquees.O(nk)polyn^omialeici,nkest le terme de plus haut degre d'un polyn^ome en n; il n'est pas rare de voir des complexites enO(n3) ouO(n4).O(kn)exponentiellequand le parametre double, le temps d'execution est

eleve a la puissancekaveck>1.O(n!)factorielleasymptotiquement equivalente annProgrammation en Python{2eme annee MP3{CPGE GSR 2014-20158/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLa notationO

Classes de complexite les plus usuelles

Comparaison de temps d'executionComparaison de temps d'execution Prenons un ordinateur (tres rapide), dont la vitesse du microprocesseur est

1GHz(cad il execute un milliard d'operations par seconde), et imaginons des

algorithmes qui eectuent un traitement donne dans un tempsT(N)Nous donnons ci-dessous tableau des ordres de grandeur des temps d'execution

que l'on peut esperer pourNelements suivant la complexite de l'algorithme. .ComplexiteTemps d'execution en fonction du nombre d'operations

N51015201001000

log N3:109s4:109s5:109s7:109s10

8s3:109s2N10

8s2:108s3:108s4:108s2:107s2:106sN log N1;2:108s3:108s6:108s10

7s7:107s10

5sN

22;5:108s10

7s2;3:107s4:107s10

5s10 3sN

53:106s10

4s7;2:104s3:103s10s11jours2

N3;2:108s10

6s3;3:105s10

500sN

N3:106s10s13ans3:109ans3:10183ans10

300sTab.:Ordres de grandeur des temps d'ex ecutionProgrammation en Python{2eme annee MP3{CPGE GSR 2014-20159/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitLe co^ut des instructions elementaires

Operation elementaire

On appelle operation de base, ou operation elementaire, toute :

1Aectation;

2Test de comparaison :==;<;<=;>=;! =;3Operation de lecture (input) et ecriture (print);

4Operation arithmetique :+;;;=;%;5Operation d'incrementation :a=a+1,(pas 1) a=a+n (pas n);

6Operation de decrementation :a=a-1,(pas 1) a=a-n (pas n);

Le co^ut d'une operation elementaire est egale a 1.

Exemple 1 :Que vaut le co^ut de l'algorithmeA

somme=n+ 1 #instr1 somme=sommen#instr2

somme=somme=2#instr3Co^ut(A)=Co^ut(inst1)+Co^ut(instr2)+Co^ut(instr3)=3Programmation en Python{2eme annee MP3{CPGE GSR 2014-201510/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitLe co^ut des instructions composees

Operation composee

On appelle operation composee, toute instruction contenant :

1L'execution d'un instruction conditionnelle : SiPest une instruction

conditionnelle du type SibalorsQ1 sinonQ2 nsi, le nombre d'operations est :

Co^ut(P)<= Co^ut(test) + max(Co^ut(Q1), Co^ut(Q2))2L'execution d'une boucle : le temps d'une boucle est egal a la

multiplication de nombre de repetition par la somme du co^ut de chaque instructionxidu corps de la boucle;

Co^ut(boucle for) =PCo^ut(xi)

Co^ut(boucle while) =P(Co^ut(comparaison) + Co^ut(xi))3L'appel d'une fonction : Lorsqu'une fonction ou une procedure est

appelee, le co^ut de cette fonction ou procedure est le nombre total d'operations elementaires engendrees par l'appel de cette fonction. Programmation en Python{2eme annee MP3{CPGE GSR 2014-201511/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitLe co^ut des instructions composees

Exemple 2 :Que vaut le co^ut de l'algorithmeB

if i%2==0 : Texte n=i//2 else : Texte i=i+1 Texte n=i//2 Co^ut(B)=Co^ut(i%2 == 0)+ max(Co^ut(n=i==2),Co^ut(i=i+ 1;n=i==2)) =1+max(1,2) =3Exemple 3 :Que vaut le co^ut de l'algorithmeC whilei<=n: Texte somme=som me+i Texte i=i+1 Co^ut(C)=Co^ut(i<=n)+Co^ut(somme=somme+i)+Co^ut(i=i+ 1) =n+n+n =3n Programmation en Python{2eme annee MP3{CPGE GSR 2014-201512/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitComment mesurer la complexite d'un algorithme Principe pour calculer la complexite d'un algorithme La mesure de complexite d'un algorithme consiste a evaluer le temps

d'execution de cet algorithme.Dans l'evaluation de ce temps d'execution (co^ut), on sera amene a suivre les

etapes suivantes :1Determiner les operations elementaires (OE) a prendre en consideration : co^ut T(OE).2Calculer le nombre d'instructions eectuees par les operations composees (OC) : co^ut T(OC).3Preciser les instructions a negliger.

4Le co^ut de l'algorithme T(Alg) est la somme des deux co^uts T(OE) et

T(OC).

T(Alg) =T(OE) +T(OC)

Programmation en Python{2eme annee MP3{CPGE GSR 2014-201513/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitDes exemples de calculs de complexite

Exemple 1 : la fonction append

Le code ci-dessous consiste a

programmer la fonction append def AjoutFin(L,a) :

L=L+[a]

return LExemple >>>L= [1;2] >>>AjoutFin(L;3) [1;2;3]Le nombre d'operations est : 3 (concatenation, aectation et return);Quelque soit la taille de liste, le nombre d'operations est constant;Temps de calcul est constant

Complexite :O(1)

.Exemple 2 : la fonction insert

Le code ci-dessous consiste a

programmer la fonction insert : def AjoutElement(L,a,i) :

L[i :i]=[a]

return LExemple >>>L= [1;2] >>>AjoutElement(L;3;1) [1;3;2]Le nombre d'operations est : 2 (aectation et return);Quelque soit la taille de liste, le nombre d'operations est constant;Temps de calcul est constant

Complexite :O(1)

Programmation en Python{2eme annee MP3{CPGE GSR 2014-201514/ 30

Introduction

Notion de complexite

Complexite et notationO

Comment mesurer la complexite d'un algorithme

Dierentes nuances de complexiteLe co^ut des instructions elementaires/composees

Evaluer la complexite d'un algorithme

Des exemples de calculs de complexite

Le module timeitDes exemples de calculs de complexite

Exemple 3 : boucle simple

for i in range(n) : print(\Bonjour")#une instruction sDans la boucle for,on a une seule instruction : printTemps de calcul de print :Tsest constantTs=CNombre de fois d'execution de cette instruction estnLe nombre total d'operations est n1 =nTemps de calcul total :T(n) =nTsComplexite :O(n) .Exemple 4 : remplir un tableauquotesdbs_dbs28.pdfusesText_34
[PDF] taux de rendement production trp

[PDF] trp production definition

[PDF] taux de rendement de production

[PDF] calcul trp production

[PDF] trp calcul

[PDF] faire des statistiques sur excel 2010

[PDF] calculer les cotés d'un triangle rectangle avec les angles

[PDF] longueur mediane triangle equilateral

[PDF] calcul mental 5eme

[PDF] séquence mesure de longueur cm1

[PDF] grandeurs et mesures cm1

[PDF] calcule mentale rapide

[PDF] calcul mental cm1 ? imprimer

[PDF] fiches calcul mental cm2

[PDF] calcul mental cm1 pdf