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.
Sandwich au jambon
Le problème dit du sandwich au jambon ou bien encore appelé théorème de Stone-Tukey s'énonce de la manière suivante : un ensemble de points en dimension peut toujours être séparé en deux parties de cardinal au plus par un hyperplan de dimension (certains points peuvent être dans l'hyperplan), où désigne la partie entière de . De manière concrète, un ensemble de points dans l'espace peut être séparé en deux parties quasi-égales par un plan. De même un ensemble de points dans le plan peut être séparé en deux par une droite et même en 4 à l'aide de deux droites. Ce sujet porte sur la résolution algorithmique de ce problème et de problèmes connexes selon différentes méthodes.
Dans tout le problème, les tableaux sont indicés à partir de 1 . L'accès à la -ème case d'un tableau tab est noté . Quel que soit le langage utilisé, on suppose que les tableaux peuvent être passés comme arguments des fonctions. En outre, il existe une primitive allouer pour créer un tableau de taille dont chaque case contient à l'origine, ainsi qu'une primitive taille qui renvoie la taille d'un tableau . Enfin, on disposera d'une fonction floor( ) qui renvoie la partie entière pour tout réel .
La complexité, ou le temps d'exécution, d'un programme (fonction ou procédure) est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc...) nécessaires à l'exécution de . Lorsque cette complexité dépend d'un paramètre , on dira que a une complexité en , s'il existe tel que la complexité de est au plus , pour tout . Lorsqu'il est demandé de garantir une certaine complexité, le candidat devra justifier cette dernière si elle ne se déduit pas directement de la lecture du code.
Partie I. Grand, petit et médian
Dans cette partie, nous supposerons donné un tableau tab contenant nombres réels. Les indices du tableau vont de 1 à . Nous dénoterons par tab[a..b] le tableau pris entre les indices et c'est-à-dire les cellules . Nous supposerons dans l'énoncé que .
Nous utiliserons le tableau de taille 11 suivant pour nos exemples :
3
2
5
8
1
34
21
6
9
14
8
Question 1 Écrire une fonction calculeIndiceMaximum( ) qui renvoie l'indice d'une case où se trouve le plus grand réel de . Sur le tableau précédent avec et , la fonction renverra 6 car la case 6 contient la valeur 34 .
Question 2 Écrire une fonction nombrePlusPetit( ) qui renvoie le nombre d'éléments dans le tableau tab [a..b] dont la valeur est plus petite ou égale à val. Sur le tableau exemple, pour une valeur de val égale à 5 , et , la fonction devra renvoyer la valeur 4 car seuls les nombres sont inférieurs ou égaux à 5 .
Nous allons maintenant calculer un médian d'un tableau. Rappelons qu'une valeur médiane d'un ensemble de nombres est un élément de tel que les deux ensembles (les nombres de strictement plus petits que ) et (les nombres de strictement plus grands que ) vérifient et . Notez que le problème du médian est une reformulation de problème dit du sandwich au jambon pris en dimension 1 . Une méthode naïve consiste donc à parcourir les éléments de l'ensemble et à calculer pour chacun d'eux les valeurs de et mais il est possible de faire mieux comme nous allons le voir dans la partie suivante.
Partie II. Un tri pour accélérer
Une méthode plus efficace serait de trier le tableau par ordre croissant tout en prenant la cellule du milieu dans le tableau trié. Cette méthode certes rapide requiert opérations. Il existe une méthode optimale en temps linéaire pour trouver le médian d'un ensemble de éléments. Cette partie a pour but d'en proposer une implémentation.
Une fonction annexe nécessaire pour cet algorithme consiste à savoir séparer en deux un ensemble de valeurs. Soit un tableau tab et un réel appelé pivot , il s'agit de réordonner les éléments du tableau en mettant en premier les éléments strictement plus petits que le pivot , puis les éléments égaux au pivot , et en dernier les éléments strictement plus grands . Sur le tableau exemple, en prenant comme valeur de pivot 8 on obtiendra le tableau résultat suivant :
Notez que dans le résultat les nombres plus petits que le pivot peuvent être dans n'importe quel ordre les uns par rapport aux autres.
Question 3 Écrire une fonction partition(tab, , indicePivot) qui prend en paramètre un tableau d'entiers tab[a..b] ainsi qu'un entier indicePivot . Soit tab indicePivot . La fonction devra réordonner les éléments de comme expliqué précédemment en prenant comme pivot le nombre . La fonction retournera le nouvel indice de la case ou se trouve la valeur .
Dans cette question, on suppose que les modifications effectuées par la fonction sur le tableau tab sont persistantes, même après l'appel de la fonction.
Remarquons que le -ème élément dans l'ordre croissant d'un tableau de taille est un élément médian du tableau considéré. Nous allons donc non pas programmer une méthode pour trouver le médian mais plus généralement pour trouver le -ème élément d'un ensemble. Nous allons utiliser l'algorithme suivant :
On cherche le -ème élément du tableau .
Si et alors renvoyer
Sinon, soit . Partitionner le tableau en utilisant le pivot en mettant en premier les éléments plus petits que . Soit l'indice de dans le tableau résultant.
Si chercher le -ème élément dans et renvoyer cet élément.
Si renvoyer le pivot.
Si chercher le ( )-ème élément dans et renvoyer cet élément.
Question 4 Écrire une fonction elementK qui réalise l'algorithme de sélection du -ème élément dans le tableau décrit précédemment et renvoie cet élément.
Question 5 Supposons que dans l'algorithme précédent nous voulions rechercher le premier élément mais qu'à chaque étape le pivot choisi est le plus grand élément, quel est un ordre de grandeur du nombre d'opérations réalisées par votre fonction?
L'algorithme précédent ne semble donc pas améliorer le calcul du médian. Le problème vient du fait que le pivot choisi peut être mauvais c'est-à-dire qu'à chaque étape un seul élément du tableau a été éliminé. En fait, si l'on peut choisir un pivot dans tel qu'il y ait au moins éléments plus petits et plus grands alors on peut montrer que l'algorithme précédent fonctionne optimalement en temps .
Pour choisir un tel élément dans , on réalise l'algorithme choixPivot suivant où chaque étape sera illustrée en utilisant le tableau donné en introduction en prenant et .
On découpe le tableau en paquets de 5 éléments plus éventuellement un paquet plus petit.
On calcule l'élément médian de chaque paquet.
S'il n'y a qu'un paquet on renvoie son médian. Sinon on place ces éléments médians au début du tableau.
5
9
2
8
1
34
21
6
On réalise choixPivot sur les médians précédents. Dans notre exemple on recommence donc les étapes précédentes en prenant et .
Question 6 Écrire la fonction choixPivot qui réalise l'algorithme précédent et renvoie la valeur du pivot.
Partie III. De la 1D vers la 2D, des nombres aux points.
Pour un réel , on note dans cette partie la partie entière supérieure de , c'est-à-dire, le plus petit entier qui est plus grand ou égal à : . On supposera disposer d'une fonction ceil( ) qui renvoie la partie entière supérieure pour tout réel .
Dans la partie précédente, nous avons étudié le problème du médian en dimension 1 . On supposera donc que vous disposez maintenant d'une fonction indiceMedian(tab, ) qui calcule un élément médian du tableau tab[ ] et renvoie l'indice de cet élément. Vous supposerez de plus que cette fonction ne modifie pas l'ordre des éléments du tableau tab.
Dans cette partie, nous généralisons l'algorithme de manière à trouver deux droites dans le plan séparant un ensemble de points en 4 parties de cardinal plus petit que , Soit un ensemble de points tel qu'il n'existe pas trois points alignés. Nous allons chercher deux lignes et séparant cet ensemble de points en 4 parties comme le montre la troisième figure ci-dessous. En effet, dans cette figure chaque partie est composée d'exactement 2 points, les points situés sur les lignes n'étant pas pris en compte. Nous supposerons donnés dans cette partie deux tableaux tabX et tabY de taille contenant les coordonnées des points. Ainsi le point a comme abscisse et comme ordonnée .
La première étape est de séparer les points en deux ensembles de même cardinal. Il suffit de remarquer que l'on peut toujours effectuer cette séparation par une ligne horizontale notée passant par un point d'ordonnée médiane comme le montre le second schéma ci-dessus.
Question 7 Écrire une fonction coupeY( ) qui renvoie l'ordonnée d'une ligne horizontale séparant les points en deux parties de cardinal au plus .
La seconde ligne est plus difficile à trouver. Nous allons en réalité trouver le point d'intersection des deux lignes et .
Soit un point sur la droite horizontale précédente de coordonnées . On veut vérifier si ce point peut être le point d'intersection des deux lignes et . Nous allons trouver dans un premier temps l'angle entre et en utilisant le fait que doit séparer en deux parties de cardinal proche les points au dessus de . Ensuite nous allons vérifier si la droite ainsi devinée sépare les points en dessous de en deux parties presque égales.
Concrètement on considère les demi-droites partant de et joignant les points de au dessus strictement de comme indiqué sur le schéma ci-dessus. On calcule ensuite les angles entre et ces demi-droites. Remarquez alors que toute demi-droite d'angle médian partage en deux parties de cardinal les points au dessus de .
Nous supposerons donnée une fonction angle( ) qui calcule et renvoie l'angle formé par une demi-droite horizontale partant de et allant vers la droite et le segment . La valeur retournée sera comprise dans l'intervalle .
Question 8 Écrire une fonction demiDroiteMedianeSup qui calcule et renvoie un angle médian entre et les segments reliant avec les points de dont l'ordonnée est supérieure à .
Pour un point donné, nous avons déterminé l'angle que doit prendre pour couper les points au dessus de en 2 parties de taille au plus moitié. Il faut maintenant vérifier que cette droite coupe aussi les points en dessous de en 2 parties quasi-égales. Il suffit de vérifier que l'angle de partitionne les angles formés entre et les points en dessous de en deux parties de cardinal .
Question 9 Écrire une fonction verifieAngleSecondeDroite , theta) qui calcule les angles formés entre et les points strictement au dessous de . Votre fonction devra renvoyer : si theta est une médiane des angles. si le nombre d'angles strictement plus petits que theta est si le nombre d'angles strictement plus grands que theta est
Si min est l'abscisse minimale des points de et xmax l'abscisse maximale, alors il est évident que l'intersection entre et ait une abscisse entre min et max . Nous allons donc rechercher cette abscisse en utilisant l'algorithme suivant :
Trouver d'ordonnée .
Soit et .
On calcule le point au milieu de et .
On calcule l'angle possible de la droite par la fonction demiDroiteMedianeSup.
Soit la valeur donnée par la fonction verifieAngleSecondeDroite avec l'angle trouvé précédemment. Si alors on a trouvé . Si on recommence à partir du point 3 en prenant l'abscisse de à la place de . Si on recommence mais en prenant l'abscisse de à la place de .
Question 10 Écrire la fonction secondeMediane qui à partir d'un ensemble de points donnés par leurs coordonnées et de l'ordonnée de la droite calcule et renvoie un tableau contenant dans la première case l'abscisse du point d'intersection de et de ainsi que l'angle de dans la seconde case.
X ENS Informatique Commune MP PC 2012 - Version Web LaTeX | WikiPrépa | WikiPrépa
