:: Enseignements :: ESIPE :: E3INFO :: 2009-2010 :: Algorithmique ::
Ce TD a pour objectif d'introduire la notion de complexité d'un algorithme, d'apprendre à estimer la complexité d'un algorithme et à interpréter le résultat obtenu.
![[LOGO]](http://igm.univ-mlv.fr/ens/resources/mlv.png) | Notions de base |
Ce TD a pour objectif d'introduire la notion de complexité d'un algorithme, d'apprendre à estimer la complexité d'un algorithme et à interpréter le résultat obtenu.
Exercice 1 - Mon Pentium IV 2Ghz et l'âge du soleil
On dispose d'un ordinateur capable d'effectuer
2.109
opérations par seconde qui exécute un programme de
complexité
2n
depuis la création du système solaire (il y a
6.109
années). Estimez grossièrement le nombre de données qu'il a
pu traiter pendant ce laps de temps.
Exercice 2 - Estimation des temps d'exécution de différents algorithmes
On dispose d'un processeur pouvant effectuer
109
opérations par seconde. On utilise cinq algorithmes dont les
complexités (en nombre d'opérations à effectuer) sont
respectivement de
n
,
log2n
,
n2
,
n log2n
,
n3
. Indiquez combien de temps utilise chaque algorithme pour
des données de tailles
1000
,
106
et
109
Exercice 3 - Minimum d'un tableau
Écrivez un algorithme en C ou en pseudo-code qui trouve
le plus petit élément puis le deuxième plus petit élément d'un tableau d'entiers.
Indiquez la complexité de chaque fonction.
Exercice 4 - Tableau trié, recherche d'éléments
Écrivez un algorithme en C ou en pseudo-code qui indique si
un élément
x
est présent dans un tableau trié par ordre croissant.
Indiquez sa complexité.
Exercice 5 - Puissance d'un nombre
Écrivez un algorithme en C ou en pseudo-code qui calcule
xn
,
x
étant un flottant et
n
un entier passés en arguments. Indiquez sa complexité.
Exercice 6 - Fonction récursive
Que fait la fonction suivante ? Quelle est sa complexité ?
© Université de Marne-la-Vallée