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

2004–2005

Contrôle de Mathématiques Discrètes du 24 Janvier 2005

Nom : Prénom : Groupe:

Durée : 2 heures

1 2 3 4 5

Tous documents autorisés. Toutes vos réponses doivent être prouvées. Si vous pensez que le texte d’une question est ambigu, faites une hypothèsen raisonable et écrivez la sur votre copie.

1

On considère l’ensemble M des mots sur l’alphabet {a,b,c} tels que les suites (maximales) de c consécutifs soient toujours de longueur paire. Ainsi, le mot abccccbaaa est un mot de M , mais le mot aabbcccba n’est pas un mot de M. On considère l’ensemble E défini inductivement par :

– ϵ ∈ E

– Si m ∈ E, alors am ∈ E

– Si m ∈ E, alors bm ∈ E

– Si m ∈ E, alors ccm ∈ E

1. A-t-on M inclus dans E?

2. A-t-on E inclus dans M?

3. Le schéma définissant E est-il libre?

4. Trouvez et résoudre une relation de récurrence permettant de compter le nombres de mots de longueur n appartenant à E

2

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 un des piquets X, du plus grand en bas, au plus petit en haut.

– on désire amener les n disques dans le même ordre sur un autre piquet Y.

– 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 dentre les deux piquets no centraux est interdit)

On rappelle que si ni X ni Y ne sont des piquets centraux, le nombre minimum de déplacements pour transporter n disques entre X et Y est de 3^{n} − 1.

On suppose que Move_non_central_to_central(n,X) déplace de manière optimale une tour de hauteur n d’un piquet non central X vers le piquet central? et que Move_non_central_to_central(n,X) déplace de manière optimale une tour de hauteur n du piquet central vers un piquet non central X.

1. Déterminer, prouver et résoudre les équations de récurrence permettant de calculer la complexité de ces deux méthodes.

2. En déduire que l’algorithme suivant est optimal

Move_non_central_to_non_central (n, initial, final){
if (n>0){  Move_non_central_to_central(n-1, initial);
Move_central_to_non_central(n-1,final);
Move_disque(initial, central);
Move_non_central_to_central(n-1, final);
Move_central_to_non_central(n-1,initial);
Move_disque(central, final);
Move_non_central_to_central(n-1, initial);
Move_central_to_non_central(n-1,final)
}
}

On suppose connue la méthode Move_Hanoi(n,initial, final, intermediaire) qui déplace de manière optimale (c’est à dire avec 2^{n} − 1 mouvements de disques) une tour de Hanoi de hauteur n, d’un piquet initial vers un piquet final en utilisant un seul piquet intermédiare avec comme contraintes :

– les n disques sont de tailles différentes.

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

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

– 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. On suppose que l’on dispose d’un quatrième piquet. Pour chacune des stratégies suivantes, évaluer la compléxité en nombre de déplacements de disques, et déterminer la meilleure de ces stratégies.

– Stratégie 1 : Déplacer les n-2 plus petits disques vers l’un des piquets intermediaires, puis déplacer les 2 grands disques restant du piquet initial vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n-2 plus petits disques disques vers le piquet final.

– Stratégie 2 :Déplacer n-3 plus petits disques vers l’un des piquets intermediaires, puis déplacer les 3 grands disques vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n-3 disques vers le piquet final.

– Stratégie 3 :Déplacer n/2 disques vers l’un des piquets intermediaires, puis déplacer les n/2 grands disques vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n/2 petits disques vers le piquet final.

Question facultative : avez vous une meilleure stratégie ?

On considère des listes d’entiers L_{E}, définies inductivement par :

– liste_vide ∈ L_{E}

– Si l ∈ L_{E} et e ∈ E, alors cons(e,l) ∈ L_{E} On dit qu’une liste l est croissante, si elle est vide ou réduite à un seul élément ou sinon si car(l) est inférieur ou égal à tous les éléments de cdr(l), et cdr(l) est elle même une liste croissante.

Soit LC_{E} le sous ensemble de L_{E} constitué des seules listes croissantes, et LSC_{E} le sousensemble de LC_{E} constitué des listes strictement croissantes.

Donner une définition inductive des fonctions suivantes et déterminez la complexité de chacune de ses fonctions, en supposant que car, cdr et cons sont toutes en temps constant.

1. Croissante : L_{E} → {vrai,faux} Cette fonction retourne vrai si et seulement si la liste considérée est croissante

2. Simplifier : LC_{E} → LSC_{E} Cette fonction retourne une liste où les doublons ont été éliminés (donc une liste strictement croissante)

3. Fusion: LC_{E} × LC_{E} → LC_{E} Cette fonction fusionne deux listes triées en une seule.

4. Extraire : LSC_{E} × LSC_{E} → LSC_{E} Cette fonction extrait de la première liste les éléments qui sont à la fois dans la première et dans la seconde liste.

5

Donnez l’ordre de grandeur des solutions des équations de récurrences suivantes :

– u_{n} = 6u_{n−1} − 8u_{n−2} + 3^{n} – v_{n} = 6v_{n−1} − 8v_{n−2} + 4^{n} – w_{n} = 6w_{n−1} − 8w_{n−2} + 2^{n}

8