:: Enseignements :: ESIPE :: E3INFO :: 2009-2010 :: Algorithmique ::
![[LOGO]](http://igm.univ-mlv.fr/ens/resources/mlv.png) | Complexité, récursivité |
On effectue quelques calculs de complexité pour se familiariser
avec les techniques élémentaires. Dans une seconde partie, on
détaille le fonctionnement de la pile de récursivité sur des
exemples.
Exercice 1 - Calcul de complexité
On considère l'algorithme suivant:
Sachant que
Algo1(n)
s'effectue en temps
O(log n),
Algo2(n)
en temps
O(n) et
Algo3(n) en temps
O(n2),
quelle est la complexité de
Algo(n)?
Exercice 2 - Calcul de complexité, bis
Quelle est la complexité de l'algorithme suivant?
Exercice 3 - Encore un peu de complexité
Quelle est la complexité de l'algorithme suivant?
Exercice 4 - Suite de Fibonacci
On veut calculer la suite de Fibonacci définie par
u0=u1=1
et, pour tout
n>=2
,
un= un-1+un-2
Proposez un algorithme récursif simple pour calculer
un
. Estimez, sans detailler, sa complexité. Montrez les différents appels récursifs
lors du calcul de
u4
. Comment améliorer l'algorithme?
Proposez une version itérative (non récursive) qui calcule
un
en temps linéaire.
Exercice 5 - Tours de hanoï
Le problème des tours de Hanoï est originaire d'Inde où une
légende raconte que, dans un temple où se trouvent trois poteaux sur lesquels
s'empilent 64 disques d'or de diamètres différents, les prêtres de Brahmâ déplacent
continuellement les disques d'un poteau de " départ " à un poteau d'" arrivée "
en passant par un poteau " intermédiaire " selon les règles suivantes :
- on ne peut déplacer plus d'un disque à la fois,
- on ne peut placer un disque que sur un autre disque plus grand que lui ou
sur un emplacement vide.
On suppose que cette dernière règle est également respectée dans la configuration
de départ. D'après cette même légende, le dernier déplacement de disque marquera la fin du monde.
- Comment peut-on déplacer une pile ordonnée de n disques du poteau de
" départ " au poteau d'" arrivée " ?
- Écrire la solution proposée.
- En supposant que les moines déplacent un disque par seconde, donner une estimation de la date de la fin du monde.
Devez-vous vous inquiéter ?
© Université de Marne-la-Vallée