L'utilisation des calculatrices n'est pas autorisée
Avertissement. On attachera une grande importance à la clarté, à la précision et à la concision de la rédaction.
On définit les arbres (binaires complets) de la façon suivante :
Une feuille est un arbre.
Si et sont deux arbres, le couple est un arbre.
Un arbre de la forme ( ) est un nœud interne, dont est le fils gauche et le fils droit. Par la suite, on note l'ensemble des arbres possédant feuilles ( ). Les feuilles d'un arbre de sont numérotées de 1 à dans l'ordre d'un parcours postfixe (dit aussi en profondeur d'abord) et de gauche à droite.
Un flot de taille est une suite de entiers égaux à 1,2 , ou 3 . Pour un arbre de fixé, cette suite définit une fonction des sous-arbres de dans les entiers, également notée . La fonction associe le -ème entier du flot à la -ème feuille de l'arbre , et elle s'étend récursivement aux nœuds internes, par la formule :
c'est-à-dire que si , alors est le reste de la division euclidienne par 4 de la somme . On note l'ensemble des flots de taille . Un flot de est dit compatible avec un arbre de si, pour tout nœud interne de , on a : . La figure suivante représente un arbre à 5 feuilles (dont les nœuds internes sont désignés par ), et deux flots. On notera que le premier flot est compatible avec , tandis que le second ne l'est pas, car .
Les arbres sont représentés en machine par la structure de donnée usuelle :
(* Caml *)
type arbre =
| Feuille
| Interne of arbre * arbre
{Pascal }
type
arbre = `cellule_arbre ;
cellule_arbre = record
gauche, droite : arbre
end ;
En Pascal, une feuille est représentée par nil et on pourra utiliser la fonction noeud, constructeur des nœuds internes :
function noeud (gauche:arbre ; droite:arbre) : arbre ;
var r:arbre ;
begin
new(r) ;
r^.gauche := gauche ; r^.droite := droite ;
noeud := r
end ;
Les flots sont représentés en machine par des tableaux d'entiers.
(* Caml *)
type flot = int vect
{Pascal }
const NMAX=... ;
type flot = array [1..NMAX] of integer ;
L'attention des candidats qui composent en Caml est attirée sur ce que les indices des tableaux commencent à zéro. Les candidats qui composent en Pascal pourront supposer que la constante NMAX est toujours plus grande que les valeurs de utilisées en pratique.
Note. La plupart des fonctions demandées dans ce problème sont valides sous certaines hypothèses portant sur leurs arguments, hypothèses qui sont énoncées à chaque question. Le code écrit ne doit jamais vérifier les hypothèses portant sur les arguments, il doit au contraire indiquer clairement comment il les utilise le cas échéant.
Partie I. Vérification de la compatibilité des flots.
Question 1. Écrire une fonction compte_feuilles qui prend un arbre en argument et renvoie le nombre de ses feuilles.
(* Caml *)
compte_feuilles : arbre -> int function compte_feuilles (a:arbre) : integer
Question 2. Écrire une fonction compatible qui prend en arguments un arbre de et un flot de , et qui décide si est compatible avec . Cette fonction devra arrêter d'effectuer des additions modulo 4 dès qu'un noeud interne vérifiant est découvert.
(* Caml *)
compatible :
arbre -> flot -> bool
{ Pascal }
function
compatible(a:arbre ; f:flot) : boolean
Question 3. Dans cette question et la suivante, désigne un arbre de et un flot de .
a) Montrer que possède nœuds internes.
b) On suppose que n'est pas réduit à une feuille et on l'écrit . Soit un flot compatible avec . Donner les valeurs possibles du couple ( ) selon les valeurs possibles de .
c) Soit un entier égal à 1,2 ou 3. Calculer , nombre de flots compatibles avec et tels que . En déduire le nombre de flots compatibles avec .
Question 4. Pour un et un donnés, la fonction compatible de la question 2 effectue additions modulo 4 (avant de trouver un nœud interne tel que ou de revenir à la racine de ). Sur l'exemple du préambule, on a et . Pour tout entier , avec , on définit comme étant le nombre de flots incompatibles avec et tels que .
a) Calculer . Sa valeur dépend elle de la forme de l'arbre ?
b) Montrer qu'il existe un arbre possédant feuilles et tel que, pour tout , on a . En déduire l'expression de dans le cas général.
c) On admet que est une bonne mesure de la complexité de l'appel de compatible sur et . En considérant une distribution équiprobable des flots, la complexité moyenne de cette fonction pour fixé est définie comme
où parcourt l'ensemble des flots de taille . Calculer cette complexité moyenne, ainsi que sa limite lorsque .
Note. On pourra utiliser sans la démontrer la formule suivante :
Partie II. Triangulation des polygones.
Soit un polygone convexe à côtés ( ), dont les sommets sont numérotés de 1 à en suivant le sens trigonométrique. Une corde est un segment qui joint deux sommets non-contigus du polygone. Une subdivision de est un ensemble de segments qui comprend au moins les côtés de plus un certain nombre de cordes. Une subdivision est dite propre lorsque toutes ses cordes sont non-sécantes (sauf éventuellement en leurs extrémités). Une subdivision propre définit un ensemble de faces, qui sont les polygones (nécessairement convexes) formés à l'aide de ses segments et dont l'intérieur ne contient aucun autre segment.
Une triangulation de est une subdivision propre dont les faces sont des triangles. Voici par exemple une triangulation de :
En revanche, les deux dessins suivants ne décrivent pas des triangulations : le premier parce que la corde qui relie les sommets 4 et 8 coupe trois autres cordes; le second parce que la face dont les sommets sont et 6 n'est pas un triangle.
Un segment quelconque reliant deux sommets de est codé par le couple de ses extrémités, et un ensemble de segments par la liste de ses éléments. On notera que les éléments d'une liste qui représente un ensemble sont supposés deux à deux distincts.
(* Caml *)
{Pascal}
type
segment = record
debut,fin : integer
type segment == int * int
end ;
and segments == segment list
segments = ^cellule_segments ;
cellule_segments = record
tete : segment ;
suite : segments
end ;
En Pascal, on pourra utiliser le constructeur des cellules de liste cons :
function cons(tete:segment ; suite:segments) : segments ;
Ainsi, la triangulation donnée en exemple peut être codée par ; , tandis que l'ensemble de ses cordes peut être codé par .
Question 5. Montrer que le nombre de cordes d'une triangulation de est une fonction de et donner son expression .
Question 6. On admet qu'un ensemble de cordes non-sécantes (sauf éventuellement en leurs extrémités) définit une triangulation de . Écrire une fonction triangulation, de
complexité , qui prend en arguments un entier et un ensemble de cordes de , et qui décide si définit une triangulation de .
Conformément à la note préalable, il n'appartient pas à la fonction triangulation de vérifier que c est bien une liste de segments distincts, dont chaque élément est bien une corde de .
Question 7. On dessine une triangulation en représentant les côtés ( ), , du polygone, sous forme d'un segment de longueur , et chaque corde , ainsi que le côté , comme un arc reliant à . Voici le dessin représentant la triangulation donnée en exemple :
a) Utiliser cette représentation de l'exemple de triangulation pour lui associer un arbre à 7 feuilles et dont les nœuds internes et les feuilles correspondent aux segments de la triangulation.
b) Généraliser le procédé en décrivant comment on peut associer un arbre de à une triangulation de . On raisonnera en termes de polygones, il pourra être utile de remarquer que le côté est particulier.
c) Écrire une fonction triangle_arbre, qui prend en arguments un entier et une triangulation de et renvoie un arbre qui représente .
(* Caml *) {Pascal }
triangle_arbre : function
int -> segments -> arbre | triangle_arbre(n:integer ; t:segments):arbre
Question 8. Écrire la fonction inverse de la fonction de la question précédente. C'est-à-dire, programmer la fonction arbre_triangle qui prend en argument un arbre de et renvoie la triangulation de représentée par .
Note. On ne cherchera pas à prouver que les fonctions arbre_triangle et triangle_arbre sont inverses l'une de l'autre.
Partie III. Les quatre couleurs.
Le problème des quatre couleurs consiste à colorier une carte géographique avec au plus quatre couleurs, de telle sorte que deux pays voisins soient coloriés différemment. Le théorème des quatre couleurs affirme qu'une telle coloration est possible pour toute carte dessinée sur une sphère.
On admettra que la coloration d'une carte se ramène à la coloration d'une double triangulation d'un polygone , qui à son tour se ramène à la construction d'un flot compatible avec deux arbres donnés de . Le théorème des quatre couleurs exprime qu'un tel flot existe toujours. L'objet de cette partie est de vérifier expérimentalement ce théorème.
Étant donné un ensemble fini , de cardinal , une génération de est une bijection de l'intervalle entier dans .
Question 9. Soient et , deux ensembles finis, générés respectivement par et .
a) Donner une génération du produit cartésien .
b) On suppose que et sont disjoints. Donner une génération de l'union .
c) On suppose que et sont disjoints et de même cardinal. Donner une autre génération de l'union , qui n'utilise pas la valeur du cardinal de .
Question 10. On note le nombre d'arbres à feuilles ( est le cardinal de ).
a) Exprimer sous forme d'une récurrence faisant intervenir les avec . En déduire une fonction (procédure en Pascal) calcule_na qui prend un entier en argument et range les avec , dans un tableau global d'entiers na réputé de taille suffisante.
(* Caml *) {Pascal}
calcule_na : int -> unit | procedure calcule_na(n:integer)
b) Construire une génération de , c'est-à-dire écrire une fonction int_arbre qui prend en arguments un entier et un entier compris entre zéro et et renvoie un arbre à feuilles.
(* Caml *) {Pascal}
int_arbre : int -> int -> arbre | function int_arbre (n,k:integer) : arbre
Question 11. Étant donnés , un arbre à feuilles, et , un entier égal à 1,2 ou 3 , il est rappelé (cf. question 3) que est le cardinal de l'ensemble des flots compatibles avec et tels que .
Construire une génération de cet ensemble, c'est-à-dire écrire une fonction int_flot qui prend en arguments un entier , un arbre à feuilles, un entier compris entre 1 et 3 et un entier compris entre 0 et , et qui renvoie un flot de taille tel que . En Caml on se conformera au type suivant :
int_flot : int -> arbre -> int -> int -> flot
En Pascal, le flot sera renvoyé par le truchement d'un argument supplémentaire passé par variable.
procedure int_flot (n:integer ; a:arbre ; v,k:integer ; var f:flot)
Question 12.
a) Écrire une fonction (procédure en Pascal) trouve_compatible qui prend en arguments un entier et deux arbres à feuilles et , et qui renvoie un flot compatible à la fois avec et . La terminaison de trouve_compatible doit être garantie.
b) Écrire une fonction (procédure en Pascal) quatre_couleurs qui prend en argument un entier , tire au hasard deux arbres à feuilles et renvoie un flot compatible avec ces deux arbres.
(* Caml *)
quatre_couleurs : int -> flot
{ Pascal }
procedure
quatre_couleurs (n:integer ; var f:flot)
On pourra utiliser la fonction random_int qui prend un entier max en argument et renvoie un entier aléatoire compris entre zéro et max-1.
Polytechnique Option Informatique MP 2001 - Version Web LaTeX | WikiPrépa | WikiPrépa
