[PDF] Algorithmes et structures de données : TD 5 Corrigé





Previous PDF Next PDF



Complexité Corrigé

12 mars 2012 Comme la boucle s'exécute n fois le temps d'exécution du programme est alors en Θ(n). 2 Correction de l'exercice 1.2. Le programme étudié est ...



Exercice 1 : Complexité des algorithmes (8 points) DIU Enseigner l

4 juil. 2019 Déterminer ensuite par la méthode du Master Theorem



TD1.1 Analyse dalgorithmes calculs de coûts TD1.1 Analyse dalgorithmes calculs de coûts

comparer des algorithmes selon leur complexité; évaluer la qualité d'un algorithme selon sa complexité. Exercice 1 : Itérations emboîtées (30 min). Compter 



TD : Complexité des algorithmes

Quelles conséquences peut-on en tirer ? Page 2. PROPOSITION DE CORRIGE. Durée Exercice 2 Revoir poly transparents 33



SUJET + CORRIGE SUJET + CORRIGE

Exercice 2 : Algorithmes de rang. (14 points). Le probl`eme de la sélection complexité en O(n × (n − r)). Ainsi la complexité dans le pire des cas est en ...



Algorithmes et structures de données : TD 5 Corrigé

Exercice 5.1 Temps d'un algorithme T(n). Pour chacun des fonctions Ti(n) Déterminer la complexité asymptotique des deux algorithmes dans la notation Grand-O.



Travaux Dirigés Algorithmique no3 - Complexité fonctions usuelles

Pour montrer qu'un algorithme est correct on écrit une propriété P qui est conservée à chaque étape de boucle que l'on appelle invariant de boucle. Exercice 1.



TD 01 – Introduction à lalgorithmique (corrigé)

Exercice 1. Grand Saut Nous allons montrer que la complexité exacte est 3n − ⌊log n⌋ − 3 en exhibant un algorithme ayant cette complexité ainsi qu'en.



TD dalgorithmique avancée Corrigé du TD 2 : récursivité

5. Qu'elle est la complexité (en nombre d'additions) de cet algorithme? La complexité de l'algorithme Fib-Paire en 



Algorithme correction

https://pnp.mathematik.uni-stuttgart.de/igt/eiserm/enseignement/mae/mae-chap08.pdf



Complexité Corrigé

12 mars 2012 Comme la boucle s'exécute n fois le temps d'exécution du programme est alors en ?(n). 2 Correction de l'exercice 1.2. Le programme étudié est ...



TD : Complexité des algorithmes

Conclure en donnant la complexité temporelle pour chaque algorithme PROPOSITION DE CORRIGE ... Exercice 2 Revoir poly transparents 33



SUJET + CORRIGE

Dans cet exercice nous allons adapter des algorithmes de tri vus Rappel : La complexité



TD1.1 Analyse dalgorithmes calculs de coûts

évaluer la qualité d'un algorithme selon sa complexité. Exercice 1 : Itérations emboîtées (30 min). Compter le nombre d'opérations Schtroumpfer exécutées 



Algorithmes et structures de données : TD 5 Corrigé

Exercice 5.1 Temps d'un algorithme T(n). Pour chacun des fonctions Ti(n) suivant déterminer sa complexité asymptotique dans la.



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

Quelle est la complexité de l'algorithme ? 21. Page 22. Exercice 2.6.2. Plus grand et deuxi`eme plus grand de 



Calculs de complexité dalgorithmes

?Complexité des algorithmes ?Un algorithme à partir d'une donnée établit un résultat . ... Exercice. ?Chaque jour pour mon goûter



Algorithmique et complexité de calcul

Exercice : Faire la trace pour l'exemplaire (1753). Modifier cet algorithme pour avoir une seule boucle et en utilisant seulement des variables scalaires. Page 



Algorithme correction

https://pnp.mathematik.uni-stuttgart.de/igt/eiserm/enseignement/mae/mae-chap08.pdf



TD 01 – Introduction à lalgorithmique (corrigé)

TD 01 – Introduction à l'algorithmique (corrigé). Exercice 1. Grand Saut La complexité en O(log2(n)) qui est indiquée nous aiguille vers une dichotomie.



Exercice 1 : Complexité des algorithmes (8 points)

Exercice 1 : Complexité des algorithmes (8 points) Question 1 1: On considère le code suivant comportant deux « tant que » imbriqués On cherche à mesurer la complexité de cette imbrication en fonction de n Pour cela on utilise la variable compteur qui est incrémentée à chaque passage dans le « tant que » interne def procedure(n) :



Travaux Pratiques Méthodes Numériques

Exercice 1 : Complexité des algorithmes On considère la fonction suivante réalisant la fusion de deux listes triées passées en paramètres La fonction retourne la liste fusionnée elle-même triée def fusion(liste1liste2) : 1 i1i2 = 00 2 resultat = [] 3 while i1 < len(liste1) and i2 < len(liste2) : 4 if liste1[i1] < liste2[i2] :



TD : Complexité des algorithmes - LIMSI

PROPOSITION DE CORRIGE Durée prévue : une séance Exercice 1 a) tableau à deux dimensions algo : somme := 0 pour cptL := 1 à n faire {pour chaque ligne} pour cptC := 1 à n faire {pour chaque colonne} somme := somme + tab[cptL cptC] 1 complexité spatiale : n * n 2 complexité temporelle : n* n sommes b) tableau à une dimension



TD11 Analyse d'algorithmes calculs de coûts - GitLab

comparer des algorithmes selon leur complexité; évaluer la qualité d'un algorithme selon sa complexité Exercice 1 : Itérations emboîtées (30 min) Compter le nombre d'opérations Schtroumpfer exécutées par chacun des algorithmes suivants 1 (1) pour i = 1 à n faire (2) pour j = 1 à n faire (3) Schtroumpfer() 2 (1) pour i = 1 à n faire



Complexité Corrigé

3 Correction de l’exercice 1 3 Cet exercice ressemble beaucoup à l’exercice 1 2 avec une di?érence fondamentale dans la boucle interne En e?et dans l’exercice 1 2 la boucle interne réalise un nombre constant d’opé-rationsalorsquedansleprésentexercicelenombred’opérationsdépenddescaractéristiquesdes

Quelle est la complexité des algorithmes?

Nous les présentons dans l’ordre de complexité croissante des algorithmes. Dans le cas de la méthode de dichotomie, la seule information utilisée est le signe de la fonction f aux extrémités de sous-intervalles, tandis que pour les autres algorithmes on prend aussi en compte les valeurs de la fonction et/ou de ses dérivées. I.2.

Quelle est l’existence d’un algorithme de résolution de complexité polynomiale?

La question de l’existence d’un algorithme de résolution de complexité polynomiale nous amène à définir des classes de complexité : intuitivement on aimerait avoir une classe des programmes que l’on peut résoudre en temps polynomial, une classe de problème plus compliqués, et un moyen de déterminer à quelle classe appartient un problème.

Quelle est la théorie de la complexité?

La théorie de la complexité a commencé en adaptant les méthodes de la calculabilité au cas du temps de calcul borné. Par exemple, on retrouve de nombreux ingrédients issus de la calculabilité dans la démonstration du théorème 3-AK de Ladner datant de 1975.

Qu'est-ce que la classe de complexité P?

Définition 14 (Classe de complexité P).La classe de complexité P est l’ensemble des problèmes concrets de décision qui sont résolubles en temps polynomial. Pour quoi s’embêter avec des codages plutôt que de définir directement la complexité d’un problème abstrait?

Universit´e Bordeaux 2 Licence MASS/Scico 5`eme semestre (2006/2007) Algorithmes et structures de donn´ees : TD 5 Corrig´e

Temps d"un algorithme T(n) - Notation Grand-O

Exercice 5.1Temps d"un algorithme T(n)

Pour chacun des fonctionsTi(n) suivant, d´eterminer sa complexit´e asymptotique dans la notation Grand-O. Exemple :T0(n) = 3n?O(n).

1.T1(n) = 6n3+ 10n2+ 5n+ 2?O(n3)

2.T2(n) = 3log2n+ 4?O(logn)

3.T3(n) = 2n+ 6n2+ 7n?O(2n)?O(an)

4.T4(n) = 7k+ 2?O(1)

5.T4(n) = 4log2n+n?O(n)

6.T5(n) = 2log10k+kn2?O(n2)

Exercice 5.2Temps d"un algorithme T(n)

Consid´erer les deux algorithmes A1 et A2 avec leurs temps d"ex´ecutionT1(n) = 9n2et T

2(n) = 100n+ 96 respectives.

1. D´eterminer la complexit´e asymptotique des deux algorithmes dans la notation Grand-O.

Quel algorithme a la meilleure complexit´e asymptotique? •T1(n) = 9n2?O(n2) •T2(n) = 100n+ 96?O(n) C"est l"algorithme A2 qui a la meilleure complexit´e asymptotique.

2. Montrer que vos solutions sont correctes en sp´ecifiant uncet unn0par algorithme afin

que la relation suivante soit satisfaite : 10n2 A2p.ex.c= 101 etn0= 100 pourf(n) =O(n) etg(n) =T2(n) = 100n+ 96 car?n≥100 : T Remarque : Bien sur, il y a d"autres choix possibles pourcetn0

3. Calculer les temps maximales d"ex´ecution des deux algorithmesTi(n) pourn= 1,n=

3,n= 5,n= 10,n= 14.

n T1T2 19196
3 81396
5

225596

10

9001096

14

17641496

4. Ebaucher les graphes des deux fonctionsTidans un mˆeme syst`eme de coordonn´e (abscisse

n, ordonn´eTi(n)).

5. Pour quelles longueur de donn´eenquel algorithme est le plus efficace ? (Calculer

l"intersection ...)

Il faut poser :

T

1(n) =T2(n)<==>9n2-100n-96 = 0

Equation quadratique, la seule solution positive est n = 12.Donc : •n≥12 : L"algorithme A2 est plus efficace

6. Quelle est la complexit´e asymptotique de l"algorithme suivant ? Quelle r`egle avez vous

appliqu´e ? d´ebut appeler A1 {Ici l"algorithme 1 est ex´ecut´e. } appeler A2 {Ici l"algorithme 2 est ex´ecut´e. } fin

Il faut appliquer la r`egle des sommes :

T

1(n) +T2(n)?O(max(n2,n)) =O(n2)

La feuille continue au verso ..

2

Exercice 5.3Addition de matrices

Consid´erer les deux matrices quadratiques A et B de taillen:

A=((((a

11a12... a1n

a

21a22... a2n

a n1an2... ann)))) ,B=((((b

11b12... b1n

b

21b22... b2n

b n1bn2... bnn)))) L"addition de ces deux matrices donne la matrice C quadratique de taillen:

C=((((c

11c12... c1n

c

21c22... c2n

c n1cn2... cnn)))) avec c ij=aij+bij?i,?j

1. D´efinir le type des matrices quadratiques et d´eclarer les variables A,B, et C.

type t_matrix = array[1..n, 1..n] of real; var A,B,C : t_matrix;

2. Ecrire un algorithme qui effectue l"addition des deux matrices A et B et stocke les r´esultats

en C. pour i de 1 `a n {boucle exterieur} pour j de 1 `a n {boucle interieur}

C[i,j] := A[i,j] + B[i,j];

fin pour fin pour

3. D´eterminer la fonction de temps maximale ("worst case")T(n) pour des matrices de

taillen. •Dans la boucle int´erieur : Une affectation j:=j+1, une comparaisonj <=n, et une affectation C[i,j] := A[i,j] + B[i,j], le tout est r´ep´et´e n*n fois. ==>3n2 •Dans la boucle ext´erieur : Une affectation i:=i+1, une comparaisoni <=n, une affec- tation j := 1, le tout est r´ep´et´e n*n fois. ==>3n •uniquement une fois : Une affectation i:=1. ==>1

T(n) = 3n2+ 3n+ 1

4. D´eterminer la complexit´e Grand-O pour des matrices de taille n.

T(n) = 3n2+ 3n+ 1?O(n2)

Exercice 5.4Multiplication de matrices

3 La multiplication des deux matrices quadratiques de taillen donne la matrice C quadra- tique de taille n:

C=((((c

11c12... c1n

c

21c22... c2n

c n1cn2... cnn)))) avec c ij=n? k=1a ikbkj?i,?j

1. Ecrire un algorithme qui effectue la multiplication des deux matrices A et B et stocke les

r´esultats en C. pour i de 1 `a n {boucle i} pour j de 1 `a n {boucle j}

C[i,j] := 0;

pour k de 1 `a n {boucle k}

C[i,j] := C[i,j] + A[i,k] * B[k,j];

fin pour fin pour fin pour

2. D´eterminer la fonction de temps maximale ("worst case")T(n) pour des matrices de taille

n. •Dans la boucle k : Une affectation k:=k+1, une comparaisonk <=n, et une affectation C[i,j] := C[i,j] + A[i,k] * B[k,j], le tout est r´ep´et´e n*n*n fois. ==>3n3 •Dans la boucle j : Une affectation j:=j+1, une affectation C[i,j] := 0, une comparaison j <=n, une affectation k := 1, le tout est r´ep´et´e n*n fois. ==>4n2 •Dans la boucle i : Une affectation i:=i+1, une comparaisoni <=n, une affectation j := 1, le tout est r´ep´et´e n fois. ==>3n •uniquement une fois : Une affectation i:=1. ==>1

T(n) = 3n3+ 4n2+ 3n+ 1

3. D´eterminer la complexit´e O(n) pour des matrices de taillen.

T(n) = 3n3+ 4n2+ 3n+ 1?O(n3)

4quotesdbs_dbs21.pdfusesText_27
[PDF] examen algorithmique 1ere année

[PDF] examen d'algorithmique

[PDF] examen principe de gestion 1ére année

[PDF] examen principe de gestion ihec

[PDF] principe de gestion 2

[PDF] comptabilité générale exercices corrigés maroc

[PDF] examen comptabilité générale s1 corrigé pdf

[PDF] examen de comptabilité générale

[PDF] examen comptabilité générale s1 pdf maroc

[PDF] cours de comptabilité générale s1 pdf

[PDF] examen comptabilité générale corrigé

[PDF] examen de comptabilité générale s2 corrigé

[PDF] exercices corrigés sur le décodage d adresses

[PDF] examen algorithmique récursivité

[PDF] examen algorithmique avancée corrigé