Scribd
Importer
557 vues2 pages

Complexité des algorithmes et récursivité

Le document contient plusieurs exercices sur la complexité des algorithmes récursifs et itératifs, notamment sur les problèmes de tour de Hanoï, de calcul de suite de Fibonacci et de recherche de maximum dans une liste.

Transféré par

Amrouch Jridi
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
557 vues2 pages

Complexité des algorithmes et récursivité

Le document contient plusieurs exercices sur la complexité des algorithmes récursifs et itératifs, notamment sur les problèmes de tour de Hanoï, de calcul de suite de Fibonacci et de recherche de maximum dans une liste.

Transféré par

Amrouch Jridi
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

Année universitaire 2020-2021

GL3

TD 4 : Complexité des algorithmes

Exercice 1 :

Le problème connu des tour de HANOI à n rondelles(et 3 piquets), noté P(n,3), peut-être résolu avec
un algorithme récursif de complexité C(n,3)= 2n-1 (mouvements). Il s’agit d’étudier ici le problème
général P(n,p)où l’on dispose de p>3 piquets.

1. Montrer que C(n, n+1)=an-b, a et b entiers positifs à déterminer et que C(n,p)>C(n,n+1) pour
tout p<n+1.
2. Calculer C(n,n)
3. Montrer que C(n,4)=c C(n-2,4)+d, c et d entiers positifs à déterminer. En déduire la valeur de
C(n,4) pour n≥3. Discuter selon la parité de n.

Exercice 2

Quelle est la complexité de l'algorithme suivant ?

float f(float x, int n)


{
int i; float S;
if (n < 1)
return n;
S = 0;
for(i=0;i<n;i++)
S = S + x/(i+n);
return S + f(x,n/2);
}

Exercice 3 - 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.
Année universitaire 2020-2021

GL3

Exercice 4 :

Concevoir un algorithme récursif m-aire (m≥2) calculant le maximum d’une liste de taille n.
Déterminer sa complexité. Comparer avec l’algorithme itératif classique. Conclure.

Exercice 5 :

On considère deux algorithmes récursifs AR1(n,m), de complexité C1(n,m) et AR2(m) de complexité


C2(m) vérifiant les relations de récurrence suivantes :

• C1(n,m)=C1(n/2,m)+C2(m/2)
• C2(m)=2 C2(m-1)+O(1)

Déterminer C2(m) puis C1(n,m), sachant que C1(1,n)=C2(1)=1 et en supposant que n=2 k (k>1) et
m=2r (r>1). Simplifier l’expression de C1(n,m)lorsque m= O(logn) et m=O(n).

Vous aimerez peut-être aussi