L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Médians et Convexité
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.
Les deux problèmes sont indépendants.
Premier problème : Sélection
Un médian d'un ensemble de nombres entiers distincts est un nombre dans tel que les nombres d'éléments strictement plus petits et strictement plus grands que dans diffèrent d'au plus de . Si est impair, le médian est unique ; si est pair, il y a deux médians possibles.
Le problème de la sélection consiste à trouver l'élément de rang dans , c'est-à-dire l'élément se trouvant en -ième position quand est trié en ordre croissant ( ).
Nous supposerons l'ensemble représenté par la liste de ses éléments, c'est-à-dire par le type ensemble défini par :
(* Caml *)
type ensemble == int list;;
{ Pascal }
type
ensemble = `cellule;
cellule = record contenu:integer;
suivant:ensemble; end;
En Pascal, la liste vide est nil et l'on pourra utiliser la fonction suivante pour construire les listes :
function cons(x:integer; s:ensemble) : ensemble;
var r:ensemble;
begin new(r); r^.contenu := x; r^.suivant := s; cons := r end;
Cette fonction est applicable pour construire les listes du type ensemble.
Question 1. Écrire la fonction card qui prend un ensemble en argument et retourne son nombre d'éléments.
Quelle est la complexité en temps de cette fonction par rapport à ?
Soit un entier quelconque, on sera amené à partitionner l'ensemble en éléments plus grands, égaux ou plus petits que .
Question 2. Écrire la fonction nPetits qui prend en arguments un entier et l'ensemble ; et qui retourne le nombre d'éléments strictement inférieurs à dans . Caml
nPetits : int -> ensemble -> int
Quelle est la complexité en temps de cette fonction par rapport à ?
Pour sélectionner le -ième élément de , on prend un nombre bien choisi dans , appelé pivot , et on effectue une partition de par rapport à .
Question 3. Écrire la fonction partitionP qui prend en arguments un entier et l'ensemble ; et qui retourne l'ensemble de tous les éléments de strictement plus petits que .
(* Caml *)
partitionP : int -> ensemble -> ensemble
function partitionP
(p:integer; X:ensemble) : ensemble;
Modifier cette fonction pour obtenir la fonction partitiong qui retourne l'ensemble de tous les éléments de strictement plus grands que . Quelles sont les complexités en temps de ces fonctions par rapport à ?
Question 4. Écrire la fonction récursive elementDeRang qui prend en arguments un nombre entier naturel et l'ensemble ; et qui retourne l'élément de rang dans , en choisissant comme pivot le premier élément de la liste représentant .
(* Caml *)
elementDeRang : int -> ensemble -> int
{ Pascal }
function elementDeRang
(k:integer; X:ensemble) : integer;
Le nombre d'opérations pris par la fonction précédente varie en fonction du choix du pivot.
Question 5. Donner un ordre de grandeur, par rapport à , du nombre maximum d'opérations pris par la fonction précédente.
En supposant équiprobables tous les rangs possibles pour le pivot choisi dans , on peut démontrer que le temps moyen pris par elementDeRang est borné supérieurement par où est une fonction croissante, vérifiant et la formule de récurrence suivante :
( est une constante indépendante de et ).
Question 6. En déduire une constante , qu'on déterminera en fonction de , telle que, pour tout entier naturel, on a .
On s'intéresse à présent à optimiser le coût dans le cas le pire . Considérons d'abord les sousensembles de 5 éléments consécutifs dans pour . Soit l'ensemble des médians des .
Question 7. Écrire une fonction medians qui prend en arguments l'ensemble ; et qui retourne l'ensemble .
Quelle est la complexité en temps pris par cette fonction par rapport à ?
Pour améliorer la vitesse de la fonction de sélection, on prend à présent comme pivot le médian de l'ensemble .
Question 8. Écrire la fonction elementDeRangBis qui prend en argument un entier naturel et l'ensemble ; et qui retourne l'élément de rang dans , en prenant comme pivot le médian de l'ensemble .
Question 9. Montrer que son temps maximum vérifie la formule :
où est la partie entière de , et est une constante que l'on ne cherchera pas à expliciter. En déduire que, pour suffisamment grand, on a où est une constante à déterminer en fonction de .
Question 10. Expliquer pourquoi l'ordre de grandeur du nombre maximal d'opérations pris par la fonction de sélection serait différent si on avait regroupé les éléments de par groupes de 3 , plutôt que par groupes de 5.
Second problème : Localisation dans un polygone convexe
Dans un repère cartésien, les points sont représentés par des enregistrements de type point défini par
Question 11. Écrire la fonction orientation qui prend comme arguments trois points ; et qui retourne ou -1 selon que l'angle formé par les demi-droites et vérifie soit , soit , soit .
(*Caml *)
orientation :
point -> point -> point -> int
{Pascal}
function orientation
( :point; :point, :point) : integer;
La région , encore appelée région à droite du zigzag , est définie par trois éléments :
la demi-droite partant de l'infini et finissant en de vecteur directeur ,
le segment de droite ,
la demi-droite partant de et de vecteur directeur .
La région se situe donc à droite de ces trois éléments pour un observateur les parcourant dans le sens indiqué.
Question 12. Écrire la fonction aDroiteDe qui prend comme arguments les points , ; et qui teste si le point est à droite du zigzag .
(*Caml *)
aDroiteDe :
point -> point ->
point -> point -> point -> bool
{Pascal}
function aDroiteDe
( : point; : point; :point; :point; :point): boolean;
À présent, on se donne un polygone convexe de côtés ( ), et on cherche à déterminer si un point quelconque est à l'intérieur de ce polygone, en décomposant le plan par rapport au polygone de la façon suivante :
L'extérieur du polygone est composée des secteurs délimités par les demi-droites et pour tout vérifiant (les calculs d'indice se feront toujours dans l'arithmétique modulo ). L'intérieur du polygone est décomposé en triangles en considérant la construction arborescente suivante :
La racine est un nœud spécial représentant tout le plan. Tout nœud interne représente la région à droite du zigzag . Remarque : est la réunion des secteurs et de l'intérieur du polygone . Les feuilles sont les secteurs déterminés par les trois points comme expliqué précédemment.
Dans cette construction arborescente, chaque nœud (sauf la racine) est découpé en trois parties disjointes, deux de ces parties correspondent aux régions associées aux deux fils, et la troisième est le triangle intérieur au polygone (où est le nouveau point apparaissant dans la définition des fils, en 4ème position dans le fils gauche et en 2ème dans le fils droit).
Le polygone est représenté par la liste de ses sommets (dans l'ordre). L'arbre précédent de décomposition du plan est représenté par des éléments du type arbre défini par :
(* Caml *)
{ Pascal }
type listePoints == point list;; type arbre = Racine of arbre*arbre
| Noeud of point*point pointpoint arbrearbre
| Feuille of point*point *point;;
type listePoints = ^cellule; cellule = record contenu:point; suivant:listePoints; end;
tNoeud = (Racine, NoeudInterne, Feuille); arbre = ^noeud; noeud = record case indicateur of Racine: (gauche:arbre; droite:arbre); NoeudInterne: (q1:point; q2:point; r1:point; r2:point; gauche:arbre; droite:arbre); Feuille: (q1:point; q2:point; q3:point); end;
L'arbre est équilibré si, pour chacun de ses nœuds, la différence de hauteur entre ses deux fils a une valeur absolue inférieure ou égale à 1 .
Question 13. Écrire la fonction construire qui prend en argument la liste ; et qui retourne un arbre équilibré représentant sa décomposition arborescente. Donner la complexité en temps pris par cette fonction en fonction de .
Question 14. Avec quels arguments peut-on appeler la fonction aDroiteDe pour tester si le point est dans le secteur ?
Question 15. Écrire la fonction aLInterieurDe qui prend en argument un arbre équilibré et un point ; et qui teste si est dans le polygone représenté par . Donner la complexité en temps de cette fonction par rapport à .
(* Caml *)
aLInterieurDe :
arbre -> point -> bool
{ Pascal }
function aLInterieurDe
(a:arbre; T:point) : boolean;
Si est un point à l'extérieur du polygone, les tangentes à partir de par rapport au polygone convexe sont les deux droites issues de qui touchent le polygone sans couper son intérieur. La tangente de gauche se trouve à gauche pour un observateur en faisant face au polygone; l'autre tangente est la tangente de droite.
Question 16. Écrire la fonction tangenteG qui prend en arguments un arbre équilibré et un point ; et qui retourne un sommet du polygone , représenté par l'arbre , point de contact de la tangente de gauche issue d'un point à l'extérieur du polygone. Donner la complexité en temps de cette fonction par rapport à .
(* Caml *) { Pascal }
tangenteG : arbre -> point -> point function tangenteG (a:arbre; T:point) : point;
Question 17. Donner une idée de modification des fonctions ou des structures de données précédentes pour obtenir également un point de contact de la tangente de droite.
Polytechnique Option Informatique MP 2004 - Version Web LaTeX | WikiPrépa | WikiPrépa
