N.B. : Le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a été amené à prendre.
Préambule : Les deux parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Partie I : Automates et langages
Le but de cet exercice est l'étude des propriétés de l'opération de déterminisation d'un automate. Cette opération a été étudiée dans le cadre du cours. Malgré cela, les réponses aux questions doivent être complètes. Une simple référence au contenu du cours ne suffit pas.
1 Automate fini
Pour simplifier les preuves, nous nous limiterons au cas des automates finis semi-indéterministes, c'est-à-dire les automates finis non déterministes qui ne contiennent pas de transitions instantanées (ou -transitions). Les résultats étudiés s'étendent au cadre des automates finis quelconques.
1.1 Représentation d'un automate fini
Déf. I. 1 (Automate fini semi-indéterministe) Soit l'alphabet (un ensemble de symboles), soit le symbole représentant le mot vide ( ), soit l'ensemble contenant et les mots composés de séquences de symboles de (donc ), un automate fini semi-indéterministe sur est un quintuplet composé de :
Un ensemble fini d'états : ;
Un ensemble d'états initiaux : ;
Un ensemble d'états terminaux : ;
Une relation de transition confondue avec son graphe : .
Pour une transition ( ) donnée, nous appelons o l'origine de la transition, e l'étiquette de la transition et la destination de la transition.
Remarquons que est le graphe d'une application de transition dont les valeurs sont définies par :
La notation est plus adaptée que à la formalisation et la construction des preuves dans le cadre des automates indéterministes.
Déf. I. 2 (Automate fini déterministe) Soit un automate fini semi-indéterministe, est déterministe si et seulement si :
1.2 Représentation graphique d'un automate
Les automates peuvent être représentés par un schéma suivant les conventions :
les valeurs de la relation de transition sont représentées par un graphe orienté dont les nœuds sont les états et les arêtes sont les transitions;
un état initial est entouré d'un cercle (i);
un état terminal est entouré d'un double cercle (t);
un état qui est à la fois initial et terminal est entouré d'un triple cercle
une arête étiquetée par le symbole va de l'état à l'état si et seulement si .
Exemple I. 1 L'automate avec :
est représenté par le graphe suivant :
1.3 Langage reconnu par un automate fini
Soit l'extension de à définie par :
Soit un alphabet, un langage sur est un sous-ensemble de .
Le langage sur reconnu par un automate fini est :
Question I. 1 Donner sans la justifier une expression régulière ou ensembliste représentant le langage sur reconnu par l'automate de l'exemple I.1.
2 Déterminisation d'un automate
2.1 Relation de transition étendue
La relation de transition définie sur des états peut être étendue à des ensembles d'états de de la manière suivante :
Déf. I. 3 (Relation de transition étendue) Soit une relation de transition sur l'ensemble d'états et l'alphabet , la relation étendue à est définie par:
2.2 Définition
Soit l’opération interne sur les automates finis semi-indéterministes définie par :
Déf. I. 4 (Déterminisation d'un automate) Soit un automate fini semi-indéterministe, l'automate qui résulte de la déterminisation de est défini par :
Question I. 2 En considérant l'exemple I.1, construire l'automate (seuls les états et les transitions utiles, c'est-à-dire accessibles depuis les états initiaux, devront être construits).
Question I. 3 Donner sans la justifier une expression régulière ou ensembliste représentant le langage sur reconnu par l'automate .
2.3 Propriétés
Question I. 4 Montrer que : si est un automate fini semi-indéterministe alors est un automate fini déterministe.
Question I. 5 Montrer que :
Question I. 6 Soit un automate fini semi-indéterministe, montrer que :
Question I. 7 Quelle relation peut-on en déduire entre et ?
Partie II : Algorithmique et programmation en CaML
Cette partie doit être traitée par les étudiants qui ont utilisé le langage CaML dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, while, ...) ni de références.
Une image numérique est constituée de points disjoints discrets (abscisse et ordonnée dans ). De nombreuses techniques de traitements d'images reposent sur la construction du contour de l'enveloppe convexe d'un ensemble de points distincts. Les techniques les plus courantes reposent sur un parcours de tous les points de l'ensemble pour construire le contour. Ceci est coûteux en temps d'exécution. Nous allons étudier une approche qui permet de réduire le nombre de points parcourus lors de la reconstruction d'un contour après l'ajout ou le retrait d'un point ainsi que lors de la fusion de deux contours. Cette approche est dérivée de la structure d'arbre binaire de recherche adaptée à un espace à deux dimensions. Elle consiste à construire les arbres enveloppants inférieurs et supérieurs pour les points de l'ensemble puis à extraire la partie convexe de leurs contours.
Nous considérerons dans le sujet des ensembles de points dont les abscisses et les ordonnées sont toutes différentes. L'approche étudiée peut être généralisée à des ensembles quelconques. Cette contrainte de séparabilité se définit de la manière suivante :
Déf. II. 1 (Points séparables) Soit un ensemble de points , les points de sont séparables si et seulement si :
Tous les ensembles de points considérés par la suite sont séparables.
1 Représentation du problème
1.1 Notations
Nous nous plaçons dans un espace euclidien orienté de dimension 2 muni d'un repère ( ).
( ) représente la droite passant par les points et ,
représente le segment d'extrémités et et ,
est l'angle orienté entre les vecteurs et , également noté .
1.2 Rappels
Déf. II. 2 (Polygone simple) Un polygone simple est une suite ( ) d'au moins trois points appelés sommets. Ces points forment des segments (avec ) appelés arêtes tels que :
l'intersection de deux arêtes qui ne sont pas adjacentes est vide,
l'intersection de deux arêtes adjacentes est réduite à leur extrémité commune,
les extrémités de deux arêtes adjacentes ne sont pas alignées.
La réunion des arêtes du polygone s'appelle le contour de .
Déf. II. 3 (Intérieur d'un polygone) Un polygone simple sépare le plan en trois régions :
le contour de ,
une région bornée, l'intérieur de ,
une région non bornée, l'extérieur de ,
Le contour constitue la frontière entre l'intérieur et l'extérieur de .
Théorème II. 1 Soit un polygone simple, soient et deux points distincts du plan qui n'appartiennent pas au contour de et tels que le nombre d'intersections entre le segment [ ] et le contour de est fini, alors le nombre d'intersections entre et le contour de est pair si et seulement si et sont tous les deux dans la même région du plan délimitée par le contour de .
Déf. II. 4 (Enveloppe convexe) Soit un ensemble de points; l'enveloppe convexe de , notée , est le plus petit des ensembles convexes contenant . Dans le cas où est un ensemble fini, ce que nous supposons dans la suite, nous admettrons que est la réunion du contour d'un polygone convexe et de son intérieur; ce polygone convexe est caractérisé par ses sommets : une suite composée de points de , appelés par extension les sommets de . Les points de sont alors des barycentres à coefficients positifs des points de , c'est-à-dire :
Les points de la suite sont ordonnés de manière à ce que :
les segments sont les arêtes du polygone convexe (avec ), ils forment une ligne polygonale : le contour du polygone,
le contour du polygone est positif, c'est-à-dire orienté dans le sens direct.
Exemple II. 1 Le schéma suivant représente en hachuré l'enveloppe convexe d'un ensemble de points . Les sommets de sont .
1.3 Codage en CaML
Un point est représenté par un couple d'entiers :
type point == int * int;;
Un ensemble, une liste, une suite de points sont représentés par une liste de points :
type suite = point list;;
Exemple II. 2 L'ensemble de points de l'exemple II. 1 est représenté par la liste :
La suite des sommets de l'enveloppe convexe de est représentée par la liste :
[ (1,0);(6,1);(9,7);(4,9);(2,8);(0,3) ]
Question II. 1 Écrire en CaML une fonction comparer de type point -> point -> bool telle que l'appel (comparer p1 p2) renvoie la valeur vraie si p1 et p2 ont les mêmes composantes et faux sinon.
Question II. 2 Écrire en CaML une fonction taille de type suite -> int telle que l'appel (taille e) renvoie le nombre de points contenus dans la suite e.
1.4 Produit croisé et fonctions trigonométriques
Déterminer la convexité d'une figure repose sur des propriétés trigonométriques dont le calcul informatique est en général coûteux et source de nombreuses approximations. Pour éviter leurs utilisations, nous allons exploiter le produit croisé qui permet la comparaison d'angles entre vecteurs sans calculer effectivement ces angles.
Déf. II. 5 (Produit croisé) Le produit croisé de trois points , q et est égal au déterminant dans une base orthonormale directe des vecteurs et , c'est-à-dire : .
Question II. 3 Soient p, q et trois points distincts; montrer que :
,
,
, et sont alignés,
Question II. 4 Écrire en CaML une fonction croise de type
point -> point -> point -> int telle que l'appel (croise ) renvoie la valeur de .
1.5 Séparation du plan par une droite
Déf. II. 6 Soit une droite qui n'est pas parallèle à l'axe des ordonnées, soient et deux points de tels que l'abscisse de est strictement inférieure à l'abscisse de . L'ensemble des points audessus de la droite est , l'ensemble des points au-dessous de la droite est .
Théorème II. 2 Un polygone de sommets est convexe si et seulement si, pour toute arête , les autres sommets de sont, soit tous au-dessus, soit tous au-dessous par rapport à la droite ( ).
Question II. 5 Écrire en CaML une fonction separation de type point -> point -> suite -> (suite * suite * suite) telle que l'appel (separation ) renvoie un triplet de listes ( , a) composées de tous les points de l'ensemble e qui :
sont distincts de et ,
se trouvent au-dessus de la droite pour la liste ,
se trouvent au-dessous de la droite pour la liste ,
appartiennent à la droite pour la liste .
Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 6 Calculer une estimation de la complexité de la fonction separation en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2 Décomposition en sous-problèmes disjoints
Pour permettre la représentation d'un ensemble de points par un arbre pour construire efficacement le contour de l'enveloppe convexe , nous allons décomposer cet ensemble en deux sous-ensembles disjoints séparés par la droite reliant le point le plus à gauche et le point le plus à droite de l'ensemble. Nous construirons ensuite l'arbre enveloppant inférieur qui correspond aux points au-dessous de la droite et l'arbre enveloppant supérieur qui correspond aux points au-dessus de la droite.
Déf. II. 7 (Point le plus à gauche, le plus à droite) Dans les hypothèses de cette étude, le point le plus à gauche, respectivement le plus à droite, est celui dont l'abscisse est la plus petite, respectivement la plus grande.
Question II. 7 Écrire en CaML une fonction extremes de type suite -> (point * point) telle que l'appel (extremes e), sur un ensemble non vide de points séparables e, renvoie un couple de points de l'ensemble e. Le point , respectivement , doit être le point le plus à gauche, respectivement à droite, des points de e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 8 Soit un ensemble de points, soit , respectivement , le point le plus à gauche, respectivement à droite, de , montrer que et sont des sommets de l'enveloppe convexe .
Théorème II. 3 Soit un ensemble de points; soient :
, respectivement , le point le plus à gauche, respectivement le plus à droite, de ,
les points au-dessus de la droite ,
les points au-dessous de la droite ( ),
les points de ,
alors forme une partition de
et .
Exemple II. 3 L'ensemble de points de l'exemple II. 1 est partitionné en :
3 Structure d'arbres enveloppants
L'utilisation de la structure d'arbre enveloppant permet de réduire la complexité en temps de calcul de l'opération de construction du contour de l'enveloppe convexe d'un ensemble de points. Dans ce but, , respectivement , doit être organisé sous la forme d'un arbre enveloppant supérieur, respectivement inférieur. Nous ne traiterons par la suite que le cas inférieur car le cas supérieur s’obtient ensuite par symétrie.
3.1 Arbres binaires de points
Un ensemble de points peut être implanté par un arbre binaire en utilisant les étiquettes des nœuds pour représenter les points contenus dans l'ensemble.
3.1.1 Définition
Déf. II. 8 (Arbre binaire de points) Un arbre binaire de points a est une structure qui peut soit être vide (notée Ø), soit être un nœud qui contient un point comme étiquette (notée ), un sous-arbre gauche (noté ) et un sous-arbre droit (noté ) qui sont tous deux des arbres binaires de points. L'ensemble de tous les nœuds de l'arbre a est noté .
Exemple II. 4 (Arbres binaires de points) Voici deux exemples d'arbres binaires étiquetés par des points (les sous-arbres vides fils des nœuds ne sont pas représentés) :
3.1.2 Profondeur d'un arbre
Déf. II. 9 (Profondeur d'un arbre) Les branches d'un arbre relient la racine aux feuilles. La profondeur d'un arbre A est égale au nombre de nœuds de la branche la plus longue. Nous la noterons .
Exemple II. 5 (Profondeurs) Les profondeurs des deux arbres binaires de l'exemple II. 4 sont respectivement 3 et 4.
Question II. 9 Donner une définition de la profondeur d'un arbre a en fonction de , et .
Question II. 10 Considérons un arbre binaire de points représentant un ensemble contenant n points distincts. Quelle est la forme de l'arbre dont la profondeur est maximale? Quelle est la forme de l'arbre dont la profondeur est minimale? Calculer la profondeur de l'arbre en fonction de dans ces deux cas. Vous justifierez vos réponses.
3.1.3 Représentation des arbres binaires en CaML
Un arbre binaire de points est représenté par le type CaML : type arbre = Vide | Noeud of arbre * point * arbre;;
Dans l'appel Noeud( ), les paramètres et sont respectivement le fils gauche, l'étiquette et le fils droit de la racine de l'arbre créé.
est alors associé au premier arbre binaire représenté graphiquement dans l'exemple II.4.
3.1.4 Profondeur d'un arbre binaire de points
Question II. 11 Écrire en CaML une fonction profondeur de type arbre -> int telle que l'appel (profondeur a) renvoie la profondeur de l'arbre binaire de points a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.2 Arbres enveloppants inférieurs
Déf. II. 10 (Arbre enveloppant inférieur) Un arbre enveloppant inférieur est un arbre binaire de points tel que :
son fils gauche, s'il existe, est un arbre enveloppant inférieur,
son fils droit, s'il existe, est un arbre enveloppant inférieur,
les étiquettes de ses deux fils ont une ordonnée supérieure à celle de son étiquette,
les étiquettes de tous les nœuds de son fils gauche, s'il existe, ont une abscisse inférieure à celle de son étiquette,
les étiquettes de tous les nœuds de son fils droit, s'il existe, ont une abscisse supérieure à celle de son étiquette.
Exemple II. 7 (Arbre enveloppant inférieur) Le deuxième arbre de l'exemple II. 4 est un arbre enveloppant inférieur.
Question II. 12 Construire l'arbre enveloppant inférieur pour les points de l'ensemble correspondant à l'exemple II. 3
Question II. 13 Exprimer la définition II. 10 sous la forme d'une propriété (a) qui indique que a est un arbre enveloppant inférieur. Vous pouvez utiliser pour cela et les fonctions définies sur les arbres binaires de points et et .
4 Application au calcul d'une enveloppe convexe
Déf. II. 11 (Contour direct d'un arbre enveloppant) Le contour direct d'un arbre enveloppant est une suite de points composée des points de la branche la plus à gauche et des points de la branche la plus à droite. Ces points sont numérotés dans le sens direct. Pour un arbre enveloppant inférieur, le premier point est le point le plus à gauche, le dernier point est le point le plus à droite. La branche la plus à gauche est numérotée de haut en bas. La branche la plus à droite est numérotée de bas en haut.
Exemple II. 8 La suite de points suivante est le contour direct du second arbre de l'exemple II. 4 :
Soient et deux points, soit un ensemble de points tel que , respectivement , soit le point le plus à gauche, respectivement le plus à droite, de , et que tous les points de soient au-dessous de la droite ( ). Soit le contour direct de l'arbre enveloppant inférieur construit à partir de .
Question II. 14 Montrer que est un polygone tel que tous les points de soient à l'intérieur ou sur le contour de ce polygone.
Question II. 15 Écrire en CaML une fonction developper de type arbre -> suite telle que l'appel (developper a) renvoie le contour direct de l'arbre enveloppant inférieur a. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 16 Montrer que les sommets de l'enveloppe convexe de appartiennent au contour direct .
Question II. 17 Soient et points consécutifs du contour , montrer que si alors n'est pas un sommet de .
Question II. 18 Soit la sous-suite maximale de telle que pour tout triplet ( ) de points consécutifs de cette sous-suite, . Montrer que cette sous-suite est égale à la suite des sommets de .
Question II. 19 Écrire en CaML une fonction filtrer de type suite -> suite telle que l'appel (filtrer s) renvoie la suite des sommets de l'enveloppe convexe de , si désigne la suite des points constituant le contour direct . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
5 Opérations sur un arbre enveloppant inférieur
5.1 Recherche dans un arbre enveloppant inférieur
Une première opération consiste à déterminer si un arbre enveloppant inférieur contient un point particulier.
Question II. 20 Écrire en CaML une fonction contenir de type point -> arbre -> bool telle que l'appel (contenir a) renvoie la valeur vraie si l'arbre enveloppant inférieur a contient le point et la valeur faux sinon. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 21 Donner des exemples de valeurs des paramètres et a de la fonction contenir qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Donner une estimation de la complexité dans le meilleur et pire cas de la fonction contenir en fonction du nombre de points dans a. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
5.2 Ajout d'un point dans un arbre enveloppant
5.2.1 Scission d'un arbre enveloppant inférieur
Une deuxième opération consiste à scinder un arbre enveloppant inférieur en deux selon une abscisse tout en préservant cette structure. Elle produit deux arbres enveloppants inférieurs : celui dont les points ont des abscisses inférieures, celui dont les points ont des abscisses supérieures.
Question II. 22 Écrire en CaML une fonction scinder de type int -> arbre -> (arbre * arbre) telle que l'appel (scinder a) renvoie une paire d'arbres enveloppants inférieurs dont la première composante est la partie de l'arbre enveloppant inférieur a contenant les points dont les abscisses sont supérieures à et la seconde composante est la partie de l'arbre enveloppant inférieur a contenant les points dont les abscisses sont supérieures à x. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
5.2.2 Insertion d'un point
Une troisième opération consiste à insérer un élément dans un arbre enveloppant inférieur en préservant cette structure.
Question II. 23 Écrire en CaML une fonction ajouter de type point -> arbre -> arbre telle que l'appel (ajouter a) renvoie un arbre enveloppant inférieur contenant les mêmes points que l'arbre enveloppant inférieur a ainsi que le point . Nous supposons que a ne contient pas déjà p et qu'aucun point de a n'a la même abscisse ou la même ordonnée que p. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 24 Donner une estimation de la complexité dans le meilleur cas de la fonction ajouter en fonction du nombre de points contenus dans a. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
Partie II : Algorithmique et programmation en PASCAL
Cette partie doit être traitée par les étudiants qui ont utilisé le langage PASCAL dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, while, repeat,...).
Une image numérique est constituée de points disjoints discrets (abscisse et ordonnée dans ). De nombreuses techniques de traitements d'images reposent sur la construction du contour de l'enveloppe convexe d'un ensemble de points distincts. Les techniques les plus courantes reposent sur un parcours de tous les points de l'ensemble pour construire le contour. Ceci est coûteux en temps d'exécution. Nous allons étudier une approche qui permet de réduire le nombre de points parcourus lors de la reconstruction d'un contour après l'ajout ou le retrait d'un point ainsi que lors de la fusion de deux contours. Cette approche est dérivée de la structure d'arbre binaire de recherche adaptée à un espace à deux dimensions. Elle consiste à construire les arbres enveloppants inférieurs et supérieurs pour les points de l'ensemble puis à extraire la partie convexe de leurs contours.
Nous considérerons dans le sujet des ensembles de points dont les abscisses et les ordonnées sont toutes différentes. L'approche étudiée peut être généralisée à des ensembles quelconques. Cette contrainte de séparabilité se définit de la manière suivante :
Déf. II. 1 (Points séparables) Soit un ensemble de points , les points de sont séparables si et seulement si :
Tous les ensembles de points considérés par la suite sont séparables.
1 Représentation du problème
1.1 Notations
Nous nous plaçons dans un espace euclidien orienté de dimension 2 muni d'un repère ( ).
( ) représente la droite passant par les points et ,
représente le segment d'extrémités et et ,
est l'angle orienté entre les vecteurs et , également noté .
1.2 Rappels
Déf. II. 2 (Polygone simple) Un polygone simple est une suite ( ) d'au moins trois points appelés sommets. Ces points forment des segments (avec ) appelés arêtes tels que :
l'intersection de deux arêtes qui ne sont pas adjacentes est vide,
l'intersection de deux arêtes adjacentes est réduite à leur extrémité commune,
les extrémités de deux arêtes adjacentes ne sont pas alignées.
La réunion des arêtes du polygone s'appelle le contour de .
Déf. II. 3 (Intérieur d'un polygone) Un polygone simple sépare le plan en trois régions :
le contour de ,
une région bornée, l'intérieur de ,
une région non bornée, l'extérieur de ,
Le contour constitue la frontière entre l'intérieur et l'extérieur de .
Théorème II. 1 Soit un polygone simple, soient et deux points distincts du plan qui n'appartiennent pas au contour de et tels que le nombre d'intersections entre le segment [ ] et le contour de est fini, alors le nombre d'intersections entre et le contour de est pair si et seulement si et sont tous les deux dans la même région du plan délimitée par le contour de .
Déf. II. 4 (Enveloppe convexe) Soit un ensemble de points; l'enveloppe convexe de , notée , est le plus petit des ensembles convexes contenant . Dans le cas où est un ensemble fini, ce que nous supposons dans la suite, nous admettrons que est la réunion du contour d'un polygone convexe et de son intérieur; ce polygone convexe est caractérisé par ses sommets : une suite composée de points de , appelés par extension les sommets de . Les points de sont alors des barycentres à coefficients positifs des points de , c'est-à-dire :
Les points de la suite sont ordonnés de manière à ce que :
les segments sont les arêtes du polygone convexe (avec ), ils forment une ligne polygonale : le contour du polygone,
le contour du polygone est positif, c'est-à-dire orienté dans le sens direct.
Exemple II. 1 Le schéma suivant représente en hachuré l'enveloppe convexe d'un ensemble de points . Les sommets de sont .
1.3 Codage en PASCAL
Un point est représenté par le type de base POINT.
Un ensemble, une liste, une suite de points sont représentés par le type de base SUITE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION P_Creer(a,o:INTEGER):POINT; renvoie un point dont l’abscisse est a et l'ordonnée 0,
FUNCTION P_Abs(p:POINT): INTEGER; renvoie l'abscisse de p,
FUNCTION P_Ord(p:POINT): INTEGER; renvoie l’ordonnée de p,
NIL représente la suite vide de points,
FUNCTION S_Ajouter(p:POINT;s:SUITE):SUITE; renvoie une suite de points composée d'un premier point et du reste de la suite contenu dans ,
FUNCTION S_Premier (s:SUITE) :POINT; renvoie le premier point de la suite s,
FUNCTION S_Reste(s:SUITE):SUITE; renvoie le reste de la suite s privée de son premier point,
FUNCTION S_Juxtaposer(s1,s2:SUITE):SUITE; renvoie la suite composée de la suite s 1 suivie de la suite s 2 .
Exemple II. 2 L'ensemble de points de l'exemple II. 1 est représenté par la liste :
Question II. 1 Écrire en PASCAL une fonction comparer (p1, p2 : POINT) : BOOLEAN; telle que l'appel comparer(p1, p2) renvoie la valeur vraie si p1 et p2 ont les mêmes composantes et faux sinon.
Question II. 2 Écrire en PASCAL une fonction taille (e : SUITE) : INTEGER; telle que l'appel taille (e) renvoie le nombre de points contenus dans la suite e.
1.4 Produit croisé et fonctions trigonométriques
Déterminer la convexité d'une figure repose sur des propriétés trigonométriques dont le calcul informatique est en général coûteux et source de nombreuses approximations. Pour éviter leurs utilisations, nous allons exploiter le produit croisé qui permet la comparaison d’angles entre vecteurs sans calculer effectivement ces angles.
Déf. II. 5 (Produit croisé) Le produit croisé de trois points , et est égal au déterminant dans une base orthonormale directe des vecteurs et , c'est-à-dire : .
Question II. 3 Soient , et trois points distincts; montrer que :
,
,
, et sont alignés,
Question II. 4 Écrire en PASCAL une fonction croise( POINT) : INTEGER; telle que l'appel croise ( ) renvoie la valeur de [ ].
1.5 Séparation du plan par une droite
Déf. II. 6 Soit une droite qui n'est pas parallèle à l'axe des ordonnées, soient et deux points de tels que l'abscisse de est strictement inférieure à l'abscisse de . L'ensemble des points audessus de la droite est , l'ensemble des points au-dessous de la droite est .
Théorème II. 2 Un polygone de sommets est convexe si et seulement si, pour toute arête , les autres sommets de sont, soit tous au-dessus, soit tous au-dessous par rapport à la droite ( ).
Un triplet de suites de points est représenté par le type de base TRIPLET.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION T_Creer(s1,s2,s3:SUITE):TRIPLET; renvoie un triplet dont les éléments sont s1, s2 et s3,
FUNCTION T_Un(t:TRIPLET):SUITE; renvoie le premier élément de t ,
FUNCTION T_Deux(t:TRIPLET):SUITE; renvoie le deuxième élément de t ,
FUNCTION T_Trois( t :TRIPLET): SUITE; renvoie le troisième élément de t .
Question II. 5 Écrire en PASCAL une fonction
separation(p,q:POINT;e:SUITE):TRIPLET; telle que l'appel separation( ) renvoie un triplet de listes composées de tous les points de l'ensemble e qui :
sont distincts de et ,
se trouvent au-dessus de la droite ( ) pour la liste ,
se trouvent au-dessous de la droite ( ) pour la liste ,
appartiennent à la droite pour la liste a.
Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 6 Calculer une estimation de la complexité de la fonction separation en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2 Décomposition en sous-problèmes disjoints
Pour permettre la représentation d'un ensemble de points par un arbre pour construire efficacement le contour de l'enveloppe convexe , nous allons décomposer cet ensemble en deux sous-ensembles disjoints séparés par la droite reliant le point le plus à gauche et le point le plus à droite de l'ensemble. Nous construirons ensuite l'arbre enveloppant inférieur qui correspond aux
points au-dessous de la droite et l'arbre enveloppant supérieur qui correspond aux points au-dessus de la droite.
Déf. II. 7 (Point le plus à gauche, le plus à droite) Dans les hypothèses de cette étude, le point le plus à gauche, respectivement le plus à droite, est celui dont l'abscisse est la plus petite, respectivement la plus grande.
Un couple de points est représenté par le type de base COUPLE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
FUNCTION C_Creer(p1,p2:POINT):COUPLE; renvoie un couple dont les éléments sont p1 et p2,
FUNCTION C_Un(c:COUPLE):POINT; renvoie le premier élément de c,
FUNCTION C_Deux(c:COUPLE):POINT; renvoie le second élément de c .
Question II. 7 Écrire en PASCAL une fonction extremes(e :SUITE) : COUPLE; telle que l'appel extremes(e), sur un ensemble non vide de points séparables e, renvoie un couple de points C_Creer ( ) de l'ensemble e. Le point , respectivement , est le point le plus à gauche, respectivement à droite, des points de e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 8 Soit un ensemble de points, soit , respectivement , le point le plus à gauche, respectivement à droite, de , montrer que et sont des sommets de l'enveloppe convexe .
Théorème II. 3 Soit un ensemble de points; soient:
, respectivement , le point le plus à gauche, respectivement le plus à droite, de ,
les points au-dessus de la droite ( ),
les points au-dessous de la droite ( ),
les points de ,
alors forme une partition de
et .
Exemple II. 3 L'ensemble de points de l'exemple II. 1 est partitionné en :
3 Structure d'arbres enveloppants
L'utilisation de la structure d'arbre enveloppant permet de réduire la complexité en temps de calcul de l'opération de construction du contour de l'enveloppe convexe d'un ensemble de points. Dans ce but, , respectivement , doit être organisé sous la forme d'un arbre enveloppant supérieur, respectivement inférieur. Nous ne traiterons par la suite que le cas inférieur car le cas supérieur s'obtient ensuite par symétrie.
3.1 Arbres binaires de points
Un ensemble de points peut être implanté par un arbre binaire en utilisant les étiquettes des nœuds pour représenter les points contenus dans l'ensemble.
3.1.1 Définition
Déf. II. 8 (Arbre binaire de points) Un arbre binaire de points a est une structure qui peut soit être vide (notée Ø), soit être un nœud qui contient un point comme étiquette (notée ), un sous-arbre gauche (noté ) et un sous-arbre droit (noté ) qui sont tous deux des arbres binaires de points. L'ensemble de tous les nœuds de l'arbre a est noté .
Exemple II. 4 (Arbres binaires de points) Voici deux exemples d'arbres binaires étiquetés par des points (les sous-arbres vides fils des nœuds ne sont pas représentés) :
3.1.2 Profondeur d'un arbre
Déf. II. 9 (Profondeur d'un arbre) Les branches d'un arbre relient la racine aux feuilles. La profondeur d'un arbre est égale au nombre de nœuds de la branche la plus longue. Nous la noterons .
Exemple II. 5 (Profondeurs) Les profondeurs des deux arbres binaires de l'exemple II. 4 sont respectivement 3 et 4.
Question II. 9 Donner une définition de la profondeur d'un arbre a en fonction de , et .
Question II. 10 Considérons un arbre binaire de points représentant un ensemble contenant n points distincts. Quelle est la forme de l'arbre dont la profondeur est maximale? Quelle est la forme de l'arbre dont la profondeur est minimale? Calculer la profondeur de l'arbre en fonction de dans ces deux cas. Vous justifierez vos réponses.
3.1.3 Représentation des arbres binaires en PASCAL
Un arbre binaire de points est représenté par le type de base ARBRE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
Vide est une constante de valeur NIL qui représente un arbre ou une liste vide;
FUNCTION Noeud(fg:ARBRE;p:POINT;fd:ARBRE):ARBRE; est une fonction qui renvoie un arbre dont le fils gauche, l'étiquette et le fils droit de la racine sont respectivement et ,
FUNCTION Gauche(a:ARBRE):ARBRE; est une fonction qui renvoie le fils gauche de la racine de l'arbre a;
FUNCTION Etiquette(a:ARBRE):POINT; est une fonction qui renvoie l'étiquette de la racine de l'arbre a;
FUNCTION Droit(a:ARBRE) : ARBRE; est une fonction qui renvoie le fils droit de la racine de l'arbre a.
renvoie le premier arbre binaire de points représenté graphiquement dans l'exemple II.4.
3.1.4 Profondeur d'un arbre binaire de points
Question II. 11 Écrire en PASCAL une fonction profondeur(a :ARBRE) : INTEGER; telle que l'appel profondeur (a) renvoie la profondeur de l'arbre binaire de points a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.2 Arbres enveloppants inférieurs
Déf. II. 10 (Arbre enveloppant inférieur) Un arbre enveloppant inférieur est un arbre binaire de points tel que :
son fils gauche, s'il existe, est un arbre enveloppant inférieur,
son fils droit, s'il existe, est un arbre enveloppant inférieur,
les étiquettes de ses deux fils ont une ordonnée supérieure à celle de son étiquette,
les étiquettes de tous les nœuds de son fils gauche, s'il existe, ont une abscisse inférieure à celle de son étiquette,
les étiquettes de tous les nœuds de son fils droit, s'il existe, ont une abscisse supérieure à celle de son étiquette.
Exemple II. 7 (Arbre enveloppant inférieur) Le deuxième arbre de l'exemple II. 4 est un arbre enveloppant inférieur.
Question II. 12 Construire l'arbre enveloppant inférieur pour les points de l'ensemble correspondant à l'exemple II. 3
Question II. 13 Exprimer la définition II. 10 sous la forme d'une propriété (a) qui indique que a est un arbre enveloppant inférieur. Vous pouvez utiliser pour cela et les fonctions définies sur les arbres binaires de points et et .
4 Application au calcul d'une enveloppe convexe
Déf. II. 11 (Contour direct d'un arbre enveloppant) Le contour direct d'un arbre enveloppant est une suite de points composée des points de la branche la plus à gauche et des points de la branche la plus à droite. Ces points sont numérotés dans le sens direct. Pour un arbre enveloppant inférieur, le premier point est le point le plus à gauche, le dernier point est le point le plus à droite. La branche la plus à gauche est numérotée de haut en bas. La branche la plus à droite est numérotée de bas en haut.
Exemple II. 8 La suite de points suivante est le contour direct du second arbre de l'exemple II. 4 :
Soient et deux points, soit un ensemble de points tel que , respectivement , soit le point le plus à gauche, respectivement le plus à droite, de , et que tous les points de soient au-dessous de la droite ( ). Soit le contour direct de l'arbre enveloppant inférieur construit à partir de .
Question II. 14 Montrer que est un polygone tel que tous les points de soient à l'intérieur ou sur le contour de ce polygone.
Question II. 15 Écrire en PASCAL une fonction developper (a : ARBRE ) : SUITE; telle que l'appel developper(a) renvoie le contour direct de l'arbre enveloppant inférieur a. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 16 Montrer que les sommets de l'enveloppe convexe de appartiennent au contour direct .
Question II. 17 Soient et points consécutifs du contour , montrer que si alors n'est pas un sommet de .
Question II. 18 Soit la sous-suite maximale de telle que pour tout triplet ( ) de points consécutifs de cette sous-suite, . Montrer que cette sous-suite est égale à la suite des sommets de .
Question II. 19 Écrire en PASCAL une fonction filtrer(s : SUITE) : SUITE; telle que l'appel filtrer(s) renvoie la suite des sommets de l'enveloppe convexe de , si désigne la suite des points constituant le contour direct . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
5 Opérations sur un arbre enveloppant inférieur
5.1 Recherche dans un arbre enveloppant inférieur
Une première opération consiste à déterminer si un arbre enveloppant inférieur contient un point particulier.
Question II. 20 Écrire en PASCAL une fonction contenir ( : POINT; a : ARBRE ) : ARBRE; telle que l'appel contenir ( ) renvoie la valeur vraie si l'arbre enveloppant inférieur a contient le point et la valeur faux sinon. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 21 Donner des exemples de valeurs des paramètres et a de la fonction contenir qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Donner une estimation de la complexité dans le meilleur et pire cas de la fonction contenir en fonction du nombre de points dans a. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
5.2 Ajout d'un point dans un arbre enveloppant
5.2.1 Scission d'un arbre enveloppant inférieur
Une deuxième opération consiste à scinder un arbre enveloppant inférieur en deux selon une abscisse tout en préservant cette structure. Elle produit deux arbres enveloppants inférieurs : celui dont les points ont des abscisses inférieures, celui dont les points ont des abscisses supérieures.
Un couple d'arbre est représentée par le type de base PAIRE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION PA_Creer(a1,a2:ARBRE):PAIRE; renvoie un couple dont les éléments sont a1 et a2,
FUNCTION P_Un(p:PAIRE):ARBRE; renvoie le premier élément de p,
FUNCTION C_Deux ( :ARBRE) : ARBRE; renvoie le second élément de .
Question II. 22 Écrire en PASCAL une fonction scinder ( : INTEGER; a : ARBRE ) : PAIRE; telle que l'appel scinder ( ) renvoie une paire d'arbres enveloppants inférieurs dont la première composante est la partie de l'arbre enveloppant inférieur a contenant les points dont les abscisses sont supérieures à et la seconde composante est la partie de l'arbre enveloppant inférieur a contenant les points dont les abscisses sont supérieures à x. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
5.2.2 Insertion d'un point
Une troisième opération consiste à insérer un élément dans un arbre enveloppant inférieur en préservant cette structure.
Question II. 23 Écrire en PASCAL une fonction ajouter ( : POINT; : ARBRE) : ARBRE; telle que l'appel ajouter ( ) renvoie un arbre enveloppant inférieur contenant les mêmes points que l'arbre enveloppant inférieur a ainsi que le point . Nous supposons que a ne contient pas déjà et qu'aucun point de a n'a la même abscisse ou la même ordonnée que p. L'algorithme utilisé ne devra parcourir au plus qu'une fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 24 Donner une estimation de la complexité dans le meilleur cas de la fonction ajouter en fonction du nombre de points contenus dans a. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
CCINP Option Informatique MP 2007 - Version Web LaTeX | WikiPrépa | WikiPrépa
