Scribd
Importer
13 vues2 pages

TD Complexité - Des Algorithmes

Le document présente un examen sur la complexité des algorithmes, comprenant des exercices sur le tri bulle, son analyse de complexité dans différents cas, et une version optimisée de l'algorithme. Il aborde également des calculs de temps d'exécution pour divers algorithmes et leur applicabilité dans des contextes spécifiques. Enfin, il demande de tracer des courbes pour comparer des fonctions de complexité.

Transféré par

Jean Bosco
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
13 vues2 pages

TD Complexité - Des Algorithmes

Le document présente un examen sur la complexité des algorithmes, comprenant des exercices sur le tri bulle, son analyse de complexité dans différents cas, et une version optimisée de l'algorithme. Il aborde également des calculs de temps d'exécution pour divers algorithmes et leur applicabilité dans des contextes spécifiques. Enfin, il demande de tracer des courbes pour comparer des fonctions de complexité.

Transféré par

Jean Bosco
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Examen

Etude des complexités et algorithme

TRAVAUX DIRIGES1 : COMPLEXITE DES ALGORITHMES


Master 1 MIAGE/GI
Durée : 02 h

Exercice 1 ( 10 points)

La procédure ci-dessous est une procédure de tri bulle d’un tableau.


PROCEDURE Tribulle ( TAB[1….N])
Var i , j : ENTIER
i n
TANTQUE i>1 FAIRE
j 1
TANTQUE j<i FAIRE
SI TAB[ j+1] <TAB[j] ALORS
ECHANGE (TAB[ j+1] , TAB[ j] )
FINSI
j 1+1
FINTANQUE
i i-1
FIN TANQUE

A)-En considérant les opérations de comparaisons d’ échanges. Réponds aux questions


suivantes
1) Complexité dans le pire des cas ( Worst case)
a) Evaluer le nombre de comparaisons
b) Evaluer le nombre d’échanges
c) En déduire la complexité Worst case
2) Complexité dans le cas le plus favorable ( Best case)
a) Evaluer le nombre de comparaisons
b) Evaluer le nombre d’échanges
c) En déduire la complexité Best case
B) Si à l’itération (𝑛 −i) aucun échange n’est effectué, on peut en déduire que le tableau est
trié. En se basant sur ce constat l’on vous demande :

3) Ecris une version optimisée du tri-bulle par modification de l’algorithme ci-dessus


proposé.
4)Complexité de la version optimisée dans le Worst case
a) Evaluer le nombre de comparaisons
b) Evaluer le nombre d’échanges
c) En déduire la complexité dans le Worst case
5)Complexité de la version optimisée dans dans le Best case
a) Evaluer le nombre de comparaisons
b) Evaluer le nombre d’échanges
c) En déduire la complexité Best case

Exercice 2

On suppose qu’on travaille sur une machine capable d’effectuer environ un milliard d’opérations
par seconde.
1) Calculer ( sans calculatrice) le temps nécessaire approximatif pour exécuter des
programmes dont les coûts sont données ci-dessous, avec des données de différents
tailles en entrée :
2) Lesquels de ces algorithmes sont utilisables :
a) À chaque chargement d’une page web ?
b) A chaque démarrage d’une machine ?
c) Pour produire les plans d’une usine ?
d) Quelle(s) conclusion(s) plus générale(s) en tirez-vous sur les ordres de grandeurs
respectifs de ces coûts.
3 ) Tracer sur une même figure les allures des courbes :
a) des fonctions log2 (𝑛) et √𝑛 sur une échelle assez grande ( n= 10 000 par exemple)
b) des fonctions 1010 × 𝑛3 et 2𝑛 avec 𝑛 compris entre 0 et 50

Vous aimerez peut-être aussi