Complexité et preuves dalgorithmes
May 11 2020 Pour n = 105
Cours 6 : Programmation et complexité
Oct 23 2018 Python et Sympy permettent de programmer et de faire de l'analyse ... tout la librairie qui permet de mesurer un temps de calcul :timeit.
Chapitre 2 Complexité algorithmique
Oct 22 2014 Des exemples de calculs de complexité. Le module timeit. 5 Différentes nuances de complexité. Programmation en Python–2`eme année MP3–.
Calculs de complexité
Exemple Python. Déterminer le maxi- mum des éléments d'une liste L non vide de taille n. Complexité : Tmaximum(n) = O(n) def maximum(L):.
Notion de complexité algorithmique
ment la quantité de mémoire requise) et le temps de calcul à prévoir. langage de programmation tel que Python pour illustrer un cours d'algorithmique ...
Complexité dun algorithme I Généralités
dans le cas d'algorithmes de nature arithmétique (le calcul de n! par exemple) Python. Certaines opérations se déroulent en temps constant (ou en temps ...
Informatique – TD7 : Complexité et structures de données
Quelle est la complexité du calcul d'un élément de la matrice C ? Écrire la fonction python matmult(AB)
Récursivité
Oct 4 2017 4 Complexité d'un algorithme récursif ... 4.4 Complexité exponentielle . ... Implémentation Python de la factorielle récursive :.
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)*
Complexité
Comme dans le cas de la correction nous décomposons le calcul de complexité sur des instructions atomiques : nous allons nous intéresser à la complexité d'une
[PDF] Cours 6 : Programmation et complexité
23 oct 2018 · La complexité en temps d'un algorithme compte le nombre d'opérations élémentaires effectuées par l'algorithme Cette complexité s'exprime en
[PDF] Calculs de complexité dalgorithmes
Calculs de complexité d'algorithmes ?Notations asymptotiques : 0 et ? ?Complexité des algorithmes ?Exemples de calcul de complexité
[PDF] Calculs de complexité
Étudier la complexité (en temps) d'une fonction f c'est déterminer son temps d'exécu- tion Tf en fonction de la taille des données En pratique :
[PDF] Complexité et preuves dalgorithmes
Ilya p additions 2p multiplications et un calcul de racine carrée def algo4(n): t = [] N = math floor(math sqrt(n)) for i
[PDF] Chapitre 2 Complexité algorithmique
22 oct 2014 · Des exemples de calculs de complexité Le module timeit 5 Différentes nuances de complexité Programmation en Python–2`eme année MP3–
[PDF] Notion de complexité algorithmique
ment la quantité de mémoire requise) et le temps de calcul à prévoir langage de programmation tel que Python pour illustrer un cours d'algorithmique
[PDF] Complexité dun algorithme I Généralités
complexité est grande plus le programme mettant en oeuvre l'algorithme aura dans le cas d'algorithmes de nature arithmétique (le calcul de n! par
[PDF] Rappels - IGM
rithmiques et Swinnen [3] pour la programmation en Python) Le calcul de la complexité d'un algorithme se base sur les hypothèses suivantes :
[PDF] Cours Complexité algorithmique (MBDS) Outline - Esentn
cours 1:Introduction à la complexité des algorithmes Dr Dhouha Maatar Razgallah 2017/2018 Application de calcul de complexité: produit de matrices
[PDF] Algorithmique et complexité de calcul
Algorithmique et complexité de calcul M Eleuldj EMI Avril 2008 Chapitre I : Préliminaires Contenu 1 Notion d'algorithme 2 Efficacité des algorithmes
Comment faire un calcul de complexité ?
Réaliser un calcul de complexité en temps revient à compter le nombre d'opérations élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par l'algorithme.Comment calculer la complexité en espace d'un programme ?
On définit la fonction de complexité en espace sM de M de la manière suivante. sM(n) = maxw=n sM(w). La valeur sM(n) représente l'espace maximal d'un calcul de M avec une entrée de taille n.Comment calculer la complexité moyenne ?
Complexité en moyenne Est la moyenne des complexités de l'algorithme sur des jeux de données de taille n : Tmoy(n) = ?{Pr(d) · C(d), d ? Dn} o`u Pr(d) est la probabilité d'avoir la donnée d en entrée de l'algorithme.- p = O(log n). La complexité temporelle dans le pire des cas de la fonction recherche_dichotomique, somme d'opérations en O(1) et d'une boucle en O(log n), est donc en O(log n).
![[PDF] Chapitre 2 Complexité algorithmique [PDF] Chapitre 2 Complexité algorithmique](https://pdfprof.com/Listes/17/24217-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.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/ 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 timeitDes exemples de calculs de complexiteExemple 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 constantComplexite :O(1)
.Exemple 2 : la fonction insertLe 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 constantComplexite :O(1)
Programmation en Python{2eme annee MP3{CPGE GSR 2014-201514/ 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 timeitDes exemples de calculs de complexiteExemple 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 tableau def RemplirTab(T) : for i in range(len(T)) : print(\T[",i,\]=\,end=") T[i]=int(input())Le parametre de complexite est la taille du tableau d'entree T.On xantion execute 3 operations : print, input et aectationNombre de fois d'execution de ces 3 operations est :len(n)Le nombre total d'operations est3len(n)Complexite :O(len(T))
Programmation en Python{2eme annee MP3{CPGE GSR 2014-201515/ 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 timeitDes exemples de calculs de complexiteEx. 5 : remplir une matrice
def RemplirMat(M,n,p) : for i in range(n) : for j in range(p) : print(\T[",i,\][\,j,"]=\,end=") T[i][j]=int(input())Co^ut pour saisir une valeur est 3Le nombre d'iteration de la boucle surjpouri
xe egal apLe nombre total pour lire toutes les valeurs pouri xe egal a 3pLe nombre total d'operations est p+p+:::+p|{z} n fois=nxpComplexite :O(np) .Ex. 6 : produit matriciel def ProduitMatriciel(A,B) : prod = [[0]*len(A) for i in range(len(A))] for i in range(len(A)) : for j in range(len(B[0])) : s = 0 for k in range(len(B)) : s= s + A[i][k] * B[k][i] prod[i].append(s) return prodOn suppose que A et B sont deux matrices carrees d'ordre n (len(A) =len(B) =n)Co^ut pour calculer une valeur desest 2 (produit et aectation)Le nombre d'iteration de la boucle surkpourj xe egal anLe nombre d'iteration de la boucle surjpouri xe egal anLe nombre total d'operations est 2+n(n(2+n(2))Complexite :O(n3) Programmation en Python{2eme annee MP3{CPGE GSR 2014-201516/ 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 timeitDes exemples de calculs de complexiteExemple 7 Tri par selection
def TriSelection(T,n) : for i in range(n-1) :Posmin=i
for j in range(i+1,n) : if T[j]T[i],T[Posmin]=T[Posmin],T[i]Co^ut des echanges : le tri pas selection surnnombres faitn1 echanges, ce
quit fait 3(n1) aectationsCo^ut des recherches de maximum : On recherche le maximum parminelements : au plus 4(n1) operations. (c'est le nombre d'iteration de la boucle surjpourixe egal an1) On recherche le maximum parmin1 elements : au plus 4(n2) operations. (c'est le nombre d'iteration de la boucle surjpourixe egal an2) On recherche ensuite le maximum parmin2 elements : 4(n3) tests. ...Le nombre total de tests est :4(1 + 2 + 3 +:::+ (n2) + (n1)) = 4(n1)n2Le nombre total d'operations est :3(n1) + 4(n1)n2Donc, la complexite est quadratiqueO(n2)Programmation en Python{2eme annee MP3{CPGE GSR 2014-201517/ 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 timeitDes exemples de calculs de complexiteEx. 8 : recherche sequentielle
defRechercheSeq(T;n;x) : i=0 while iLa boucle while contient 2 instructions :
incrementation et aectationLe nombre de fois d'execution de ces 2
instructions estnLe nombre d'operations apres while est 1 (un
test)Le nombre d'operations total est
1 +n(1 + 1) + 1
Complexite :O(n)
.Ex. 9 : Recherche dichotomique def RechDichotomique(T,x) : g,d=0,len(T)-1 while g<=d : m=(g+d)//2 if T[m]==x : return True if T[m]Donc : 2m1<=n<= 2m
on deduit quem<=log2(n) + 1Complexite :O(log2(n))
Programmation en Python{2eme annee MP3{CPGE GSR 2014-201518/ 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 timeitDes exemples de calculs de complexite Exemple 10 Recherche d'un mot dans une cha^ne de caracteresLe principe est le m^eme que pour la recherche d'un caractere dans une cha^ne mais ici il necessaire d'ajouter une
boucle "while" pour tester tous les caracteres du mot. def searchWord(mot,texte) : if len(mot)>len(texte) : return False for i in range(1+len(texte)-len(mot)) : j=0 whilejIntroduction
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 timeitDes exemples de calculs de complexiteExemple. 11 les tours de Hano
def hanoi(n,a=1,b=2,c=3) :quotesdbs_dbs28.pdfusesText_34[PDF] l'alcool utilisé comme antiseptique local peut être
[PDF] production primaire nette
[PDF] productivité nette de l'écosystème
[PDF] production primaire et secondaire
[PDF] productivité nette de l écosystème
[PDF] taux d'évolution calcul
[PDF] taux d'endettement entreprise
[PDF] numero ine sur internet
[PDF] inscription lycée hors secteur
[PDF] nombre de mole formule
[PDF] nombre de mole d'un gaz
[PDF] nombre d'oxydation exercices corrigés
[PDF] exercices priorités opératoires 5ème pdf
[PDF] joachim doit traverser une rivière avec un groupe d'amis correction