Devoir 1 automne 2005; 8INF805 - UQAC
24 sept. 2007 ... Déterminez la complexité temporelle de cet algorithme dans le pire cas. ...
Montrer que le calcul d'un carré peut être évité en utilisant les ...
part of the document
DIM, UQAC Lundi 24 septembre 2007.
8INF805
Devoir 1
À rendre au plus tard le 11 octobre
avant 18h45 (en classe) ou ma boite aux lettres
Exercice 1 (20pts): Considérons lexpression ci-dessous qui détermine les coefficients de EMBED Equation.3 , où EMBED Equation.3 .
EMBED Equation.3
Écrivez le pseudo-code de lalgorithme implantant dune manière récursive lexpression ci-dessus.
Déterminez la complexité temporelle de cet algorithme dans le pire cas.
Déterminez la complexité spatiale de cet algorithme.
Donnez la raison principale de linefficacité de votre algorithme.
Écrire une version itérative (cest-à-dire non récursive) de lalgorithme donné en 1 et dont la complexité spatiale doit être en O(n). Quelle est la complexité temporelle de votre algorithme.
N.B : Pour la résolution de la relation de récurrence, trouvée en 2, pour les grandes valeurs de n, vous pourriez supposer que (n-1)/2 ( n/2 1 et n ( n 1.
Exercice 2 (15pts) : Soit fait lalgorithme suivant :
void mystere (int *A, int k) {
if (k != 1) {
mystere(k-1);
int i= k-1; int temp = A[k];
while (i
