Calcul de coût d’algorithme - imag
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 chaque terme de l’itération; Le coût d’une instruction conditionnelle est majoré par le maximum des coûts de chacune des
Chapitre 2 Complexité algorithmique
Le cout^ d’une op eration el ementaire est egale a 1 Exemple 1 : Que vaut le cout^ de l’algorithme A somme = n + 1 #instr1 somme = somme n#instr2 somme = somme=2#instr3 Cout(^A)=Cout(^inst1)+Cout(^instr2)+Cout(^instr3)=3 Programmation en Python{2 eme ann ee MP3{ CPGE GSR 2014-201510/ 30
Plan - xavierduprefr
3 coût de l'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 de leurs dimensions Un opération élémentaires est une affection, un calcul, une comparaison som = 0 pour i allant de 1 à n inclus
Problème du plus court chemin : Algorithmes et complexité
ALGORITHME de DIJKSTRA (Reaching ; label-setting) Trouver des plus courts chemins de s vers tout autre noeud (c-à-d un arbre des plus courts chemins) dans un réseau qui ne contient pas d’arc de coût négatif L’algorithme maintient une distance di pour chaque noeud i avec un statut permanent (=plus court chemin) ou temporaire (=borne sup sur
Optimisation linéaire - EPFL
Algorithme du simplexe Michel Bierlaire 21 Développement de la méthode du simplexe • On veut aller le plus loin possible le long de d, en restant admissible • On cherche θ* tel que θ* = max { θ≥0 ¦ x+ θd ∈P} • Comment calculer θ* ? • Comme d est admissible, la seule manière de
Algorithme de Dijkstra : terminaison, correction et complexité
plexité d’un algorithme 1 Présentation de l’algorithme 2 Preuve de sa terminaison 3 Preuve de sa correction 4 Étude de sa complexité Remarques sur le développement 2 Étude de l’algorithme de Dijkstra Présentation de l’algorithme a Objectif : chemin le plus court à origine unique Pour a 2V, on veut calculer d : V f+¥gtel que
COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE
• On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 MAP - UNS 17 EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC
zNotations asymptotiques : 0 et Θ zComplexité des algorithmes
Complexités d’un algorithme zUn algorithme à partir d’une donnée établit un résultat zLa taille de la donnée est mesurée par un entier n {complexité temporelle une fonction de n qui mesure le temps de calcul pour une donnée de taille n {complexité en mémoire une fonction de n qui mesure la place mémoire
Complexité Techniques de calcul et de réduction
Lilian BUZER version b année 2003-2004 Complexité
[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] calcul mental cm1 pdf
[PDF] progression calcul mental cm2
![Chapitre 2 Complexité algorithmique Chapitre 2 Complexité algorithmique](https://pdfprof.com/Listes/17/23521-17CoursComplexitePyhton.pdf.pdf.jpg)
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{
22 octobre 2014
Programmation en Python{2eme annee MP3{CPGE GSR 2014-20151/ 30Introduction
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/ 30Introduction
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 soitFalse).Analysons plusieurs solutions
1.Premi eresolution
def contienta1(chaine) : k = 0N = len(chaine)
result = False while (result == False and kNotion 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/ 30Introduction
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 algorithmeDenition
La complexite d'un probleme mathematique P est une mesure de la quantite deressources 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/ 30Introduction
Notion de complexite
Complexite et notationO
Comment mesurer la complexite d'un algorithme
Dierentes nuances de complexiteDenition de la complexite d'un algorithmeTypes 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/ 30Introduction
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 .Exemples1Exemple 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 doncbornee, 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 donneestraitees, 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 esteleve 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 est1GHz(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'operationsN51015201001000
log N3:109s4:109s5:109s7:109s108s3:109s2N10
8s2:108s3:108s4:108s2:107s2:106sN log N1;2:108s3:108s6:108s10
7s7:107s10
5sN22;5:108s10
7s2;3:107s4:107s10
5s10 3sN53:106s10
4s7;2:104s3:103s10s11jours2
N3;2:108s10
6s3;3:105s10
500sNN3: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/composeesEvaluer la complexite d'un algorithme
Des exemples de calculs de complexite
Le module timeitLe co^ut des instructions elementairesOperation 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#instr2somme=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/composeesEvaluer la complexite d'un algorithme
Des exemples de calculs de complexite
Le module timeitLe co^ut des instructions composeesOperation 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/ 30Introduction
Notion de complexite
Complexite et notationO
Comment mesurer la complexite d'un algorithme
Dierentes nuances de complexiteLe co^ut des instructions elementaires/composeesEvaluer la complexite d'un algorithme
Des exemples de calculs de complexite
Le module timeitLe co^ut des instructions composeesExemple 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/ 30Introduction
Notion de complexite
Complexite et notationO
Comment mesurer la complexite d'un algorithme
Dierentes nuances de complexiteLe co^ut des instructions elementaires/composeesEvaluer 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 tempsd'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.