Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Controle de Mathématiques Discrètes du 13 Janvier 2005

Nom : Prénom : Groupe:

Durée : 1 heure

1 2 3 4 5

1

Que signifie la notation f(n) = O(n) ? Que signifie la notation f(n) = Θ(n) ?

2

Quelles sont toutes les solutions de l’équation u_{n} = 5u_{n−1} − 6u_{n−2} ?

– Question 1 : Montrer par induction que la méthode sum suivante retourne ∑_{i=min}^{i=max} A[i] .

– Question 2 : Déterminer la complexité de cette méthode.

//On suppose que  0  <= min  <= max < A.length
public static int sum(int[] A, int min, int max){
int mid;
if(min == max) {
return A[min];
}
if (max-min == 1) {
return A[min] + A[max];
}
  // dans les autres cas
mid = (min + max)/2;
return sum(A,min,mid) + sum(A,mid+1,max);
}

Donner l’ordre de grandeur des solutions des équations suivantes: u_{n} = 5u_{n−1} − 6u_{n−2} + 3^{n},u_{0} = 0 v_{n} = 5v_{n−1} − 6_{n−2} + 5^{n},u_{0} = 0 On considère une variante des tours de Hanoï avec trois piquets A,B,C et n disques.

– les n disques sont de tailles différentes

– initialement les n disques sont rangés sur le piquet A, du plus grand en bas, au plus petit en haut

– on désire amener les n disques dans le même ordre sur le piquet C

– on ne peut déplacer qu’un seul disque à la fois

– on ne peut pas poser un disque sur un disque de taille inférieure

– tous les mouvements de disques doivent se faire via le piquet central (un déplacement direct

de A vers C ou de C vers A est interdit) Déterminer et prouver l’équation de récurrence correspondant au nombre minimum de déplacements de disques.