[PDF] [PDF] TD : La complexité temporelle Exemple 1 : Fibonacci - Pascal

[PDF] Calculs de complexité

Complexité : Tmaximum(n) = O(n) def maximum(L): m=L[0] for i in range(1,len(L )): if L[i]>m: m=L[i] return m Exemple Python Le nombre d'apparitions d'un élé-

[PDF] Complexité et preuves dalgorithmes

11 mai 2020 · le temps de calcul nécessaire, directement lié au nombre d'opérations qu' effectue On parle respectivement de complexité temporelle et de complexité spatiale Et effectivement, 2−1075 est déclaré nul par Python 5 

[PDF] Chapitre 2 Complexité algorithmique - langage python

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 car ce 

[PDF] TD : La complexité temporelle Exemple 1 : Fibonacci - Pascal

24 nov 2017 · En Python, il est possible de déterminer le temps de calcul d'un algorithme grâce aux instructions suivantes : from time import clock t1 = clock()

[PDF] Calcul de complexité - CPGE du Lycée Montesquieu

Dans la suite, on note T(P) la complexité dans le pire cas d'un bloc d'instructions P II 1 Complexité d'une instruction simple On s'intéresse ici à la complexité d' 

[PDF] Complexité algorithmique - Aurélien Poiret

3 5 - Optimisation du produit matriciel sous Python Dans le calcul de complexité interviendra de temps en temps la fonction logarithme de base a On

[PDF] Rappels de complexité et programmation orientée objet en Python

À ces fins, on aura donc recours à une approximation de ce temps de calcul en fonction de la taille des données, représentée par la notation O(·) Définition 1 Une 

[PDF] Complexité : un exemple pour le lycée

Complexité au lycée Programme python Python def triangle (p) : L=[ ] Comparer les temps de calcul expérimentalement et expliquer FICHIER SAGE GA, JG 

[PDF] Complexité - Algo Prog Objet Python

Andrea G B Tettamanzi, 2018 4 Complexité • Tous les algorithmes ne sont pas équivalents • On les différencie selon au moins 2 critères : – Temps de calcul 

[PDF] masse et quantité de matière exercice

[PDF] l'alcool utilisé comme antiseptique local peut être

[PDF] production primaire nette

[PDF] productivité nette de l'écosystème

[PDF] productivité primaire définition simple

[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] numero ine eleve college

[PDF] affectation lycee secteur

[PDF] inscription lycée hors secteur

[PDF] nombre de mole formule

[PDF] nombre de mole d'un gaz

TD: La complexit´e temporelle

2 heures

R´edig´e par Pascal Delahaye

24 novembre 2017

Exemple 1 : Fibonacci

La suite de fibonnacci est d´efinie par : (un) telle que?u0= 0 u

1= 1et pour toutn?N?:un+2=un+1+un.

Pour calculer le termeun, nous disposons des 2 algorithmes suivants : def u1(n) : | def u2(n) :

S1, S2 = 0, 1 | if n == 0 : return 0

for i in range(2,n+1): | elif n == 1 : return 1 S1, S2 = S2, S1 + S2 | else : : return u2(n-1) + u2(n-2) return S2 | # Ceci est un algorithme r´ecursif #

Nous allons ´evaluer le temps de calcul de chacun des algorithmes de calcul pr´ec´edents de fa¸con exp´erimentale et

th´eorique.

1) Etude exp´erimentale

En Python, il est possible de d´eterminer le temps de calcul d"un algorithme grˆace aux instructions suivantes :

from time import clock t1 = clock() ... instructions du programme dont on veut ´evaluer la dur´ee ... t2 = clock() print(t2-t1)

1. Concevoir deux fonctionstp1(n)ettp2(n)donnant le temps d"ex´ecution des instructionsu1(n)etu2(n).

2. En d´eduire deux fonctionsgraphe1(N,p)etgraphe2(N,p)permettant de repr´esenter le temps d"ex´ecution de

chacune des deux fonctionsu1etu2pournallant de 0 `a N par pas dep?N?. Lancer alors les instructionsgraphe1(100,1)etgraphe2(35,3). 1 MPSI - 2017/2018 La complexit´e temporelle http://pascal.delahaye1.free.fr/

3. R´epondez alors aux questions suivantes :

Courbes de complexit´e des deux algorithmes

(a) Quel est le programme le plus rapide?

(b) Quelle conjecture peut-on faire sur la nature de la complexit´e de chacun des deux algorithmes?

(c) Comment interpr´eter : i. les valeurs qui semblent aberrantes? ii. les diff´erences obtenues lorsqu"on lance deux fois la mˆeme instruction? iii. les discontinuit´es qui apparaissent ´eventuellement?

2) Etude th´eorique

Donner sous la forme d"un "grand O" la complexit´e des deux algorithmes pr´ec´edents.

On consid`erera :

1. La taille de la donn´ee :n

2. L"op´eration significative : l"addition

Cette ´etude th´eorique vient-elle confirmer les conjectures pr´ec´edentes?

Exemple 2 : Polynˆomes

SoitP?R[X] etα?R. Les deux algorithmes suivants proposent deux m´ethodes de calcul deP(α). Nous repr´esenterons un polynˆomePpar la liste de ses coefficients : P=a0+a1X+···+anXnest alors rep´esent´e en machine par :P= [a0,...,an]

1. Echauffement

Construire une fonctionsomme(P,Q)qui renvoie la somme de deux polynˆomes.

2. Calcul na¨ıf

La premi`ere id´ee pour le calcul deP(α) est tout simplement de calculerP(α) =n? k=0a kαk`a l"aide d"une boucle FOR. 2 MPSI - 2017/2018 La complexit´e temporelle http://pascal.delahaye1.free.fr/

3. L"algorithme de Horner

Cet autre algorithme propose de calculerP(α) en proc´edant de la fa¸con suivante :

Siα?K, l"id´ee de l"algorithme d"H¨orner est de d´eterminerP(α) en effectuant les calculs suivants :

1.S=an(initialisation)

2.S=S×α+an-1=an.α+an-1(i=1)

3.S=S×α+an-1= (an×α+an-1)×α+an-2=an.α2+an-1.α+an-2(i=2)

4. ...etc ...

Apr`es la i`eme it´eration on obtient l"expression :S=anαi+an-1αi-1+···+an-i En poursuivant ainsi jusqu"`ai=n, on obtient la valeur deP(α). L"algorithme se pr´esente alors de la fa¸con suivante : Arguments : P : liste des coefficients du polyn^ome alpha : flottant Variables locales : S : flottant stockant les valeurs successives du calcul n : entier repr´esentant le degr´e du polyn^ome

Initialisation :

* n <- degr´e du polynome p ATTENTION au sens de n !! * S <- p[n] Boucle : Pour i allant de 1 `a n faire : S <- S * alpha + p[n - i]

Fin : retourner S

Travail

Etude exp´erimentale :

1. Construire une fonctionCALC(P,alpha)calculantP(α) selon la m´ethode na¨ıve.

2. Construire une fonctionHORNER(P,alpha)calculantP(α) avec l"algorithme de Horner.

3. En utilisant la fonctionclock()de Python, d´eterminer deux fonctionstp1(P,alpha)ettp2(P,alpha)qui

renvoient le temps de calcul deP(α) par chacune des deux fonctions pr´ec´edentes.

Vous appliquerez ces deux fonctions en prenant pour arguments un polynˆome de degr´e variable etα= 1000!

(oui, je sais : c"est tr`es grand!)

4. Construire une proc´eduregraphe(N,alpha)qui affiche le graphe donnant l"´evolution des temps d"execution des

deux algorithmes pr´ec´edents en fonction du degr´en?[[1,N]] de la fonction polynˆomiale.

Vous prendrez pour polynˆomesrange(1,n)o`unpourra varier de 1 `a N=30 et de nouveauα= 1000!.

Commenter les r´esultats obtenus.

Etude th´eorique :

A l"aide des deux courbes observ´ees exp´erimentalement, conjecturer la complexit´e des deux algorithmes.

Valider votre conjecture `a l"aide d"une ´etude th´eorique de complexit´e. 3 MPSI - 2017/2018 La complexit´e temporelle http://pascal.delahaye1.free.fr/ Comparaison exp´erimentale de la complexit´e de diff´erents algorithmes

Solutions

Python

# Comparaison de deux algorithmes de calcul de la suite de Fibonacci# def u1(n): # Algorithme usuel (complexit´e lin´eaire) u0 = 0 u1 = 1 for k in range(2,n+1): u0, u1 = u1, u0 + u1 return u1 def u2(n): # Algorithme r´ecursif (complexit´e exponentielle) if n == 0 : return 0 elif n == 1 : return 1 else : return u2(n-1)+u2(n-2) def tp1(n): from time import clock t1 = clock()

A = u1(n)

t2 = clock() return t2 - t1 def tp2(n): from time import clock t1 = clock()

A = u2(n)

t2 = clock() return t2 - t1 def G1(N,p):# Complexite de l"algorithme usuel from matplotlib.pylab import plot, arange

X = arange(1,N+1,p)

Y = [tp1(x) for x in X]

plot(X,Y) def G2(N,p):# Complexite de l"algorithme r´ecursif from matplotlib.pylab import plot, arange

X = arange(1,N+1,p)

Y = [tp2(x) for x in X]

plot(X,Y) 4 MPSI - 2017/2018 La complexit´e temporelle http://pascal.delahaye1.free.fr/

Python

# Comparaison de 2 algorithmes de calcul de P(alpha) # from sympy import factorial def alg1(P,alpha): # algorithme na¨ıf (complexit´e quadratique) n = len(P) S=0 for k in range(0,n):

S = S + P[k]*alpha**k

return S def alg2(P,alpha): # algorithme de Horner (complexit´e lin´eaire) n = len(P)

S = P[n-1]

for k in range(1,n):

S = S*alpha + P[n-1-k]

return S def tpalg1(n,alpha): # dur´ee d"execution de l"alg. na¨ıf from time import clock

P = range(2,n)

t1 = clock()

A = alg1(P,alpha)

t2 = clock() return t2 - t1 def tpalg2(n,alpha): # dur´ee d"execution de l"alg. de Horner from time import clock

P = range(2,n)

t1 = clock()

A = alg2(P,alpha)

t2 = clock() return t2 - t1 def graphe(N,p,alpha): # graphes de comparaison des deux complexit´e from matplotlib.pylab import plot, arange

X = arange(3,N+1,p)

Y1 = [tpalg1(x,alpha) for x in X]

Y2 = [tpalg2(x,alpha) for x in X]

plot(X,Y1) plot(X,Y2) 5quotesdbs_dbs4.pdfusesText_8