Td corrigé Devoir 1 automne 2005; 8INF805 - UQAC pdf

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 l’expression ci-dessous qui détermine les coefficients de  EMBED Equation.3 , où  EMBED Equation.3 .
 EMBED Equation.3 
Écrivez le pseudo-code de l’algorithme implantant d’une manière récursive l’expression 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 l’inefficacité de votre algorithme.
Écrire une version itérative (c’est-à-dire non récursive) de l’algorithme 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 l’algorithme suivant :
void mystere (int *A, int k) {
if (k != 1) {
mystere(k-1);
int i= k-1; int temp = A[k];
while (i