X Informatique MP/PC 2005

ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

CONCOURS 2005

FILIÈRE MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR FILIÈRE PC

COMPOSITION D'INFORMATIQUE

(Durée : 2 heures)

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.

***

Lignes d'horizon

On attachera une grande importance à la conctsion, a la clarté, et à la 
précision de la rédaction.
On précisera en tête de copie le langage de programmation utilisé.

Le temps d'exécution T ( f ) d'une fonction f est le nombre d'opérations 
élémentaires (addi-
tion, soustraction, multiplication, division, affectation, etc.) nécessaire au 
calcul de f. Lorsque
ce temps d'exécution dépend d'un paramètre n, il sera noté T n( f ) On dit que 
la fonction f
s'exécute :

-- en temps linéraire en n, s'il existe K > 0 tel que pour tout n, Tn( f ) 5 K 
n;

---- en temps quadratique en n, s'il existe K > 0 tel que pour tout n, Tn( f ) 
5 K n2.
I. Détermination de la ligne d'horizon

On cherche à calculer la ligne d'horizon engendrée par n beaux bâtiments 
modernes
(n > O), assimilés à des parallépipèdes verticaux. Pour simplifier, on se place 
dans l'espace
à deux dimensions; nos bâtiments sont de simples rectangles verticaux; la ligne 
d'horizon est
représentée par une suite de segments horizontaux, comme indiqué sur la figure 
suivante :

Dans trois tableaux globaux à valeurs entières 9, d et h de longueur n, on 
range respective--
ment l'abscisse de gauche, l'abcisse de droite et la hauteur du bâtiment 73 
vérifiant 0 < h[z'] < M et 0 £ g[i] < d[i] < N pour tout i (0 S 72 < n) où M et N sont deux constantes globales (comme d'habitude, les abcisses croissent de la gauche vers la droite, et les ordonnées du bas vers le haut). Dans l'exemple ci--dessus, les tableaux 9, d et h valent respectivement (2,3,0, 1,8, 9>,
(4,6,7,5,9,10> et (4,5,2,3,4,3).

On définit une matrice E = (e...--) (0 _<_ i < M, 0 5 j < N) de piæels (picture elements) dans laquelle on dessine les bâtiments; chaque élément c... vaut 0 ou 1; plus exactement 6... = 1 si et seulement si le point de coordonnées réelles ( j + 0,5, i+ 0,5) est a l'intérieur d'un bâtiment. Question 1. Écrire une fonction remplir() qui initialise la matrice E. La ligne d'horizon est représentée par un tableau hor de longueur EUR contenant une succession d'abcisses et de hauteurs : hor[2k] et hor[2k + 2] déterminent les abcisses de début et de fin d'un bout de ligne d'horizon à hauteur hor[2k+1] (0 _<_ k < £/2-- 1). Ainsi, dans l'exemple ci--dessus, la ligne d'horizon peut être représentée par le tableau (0, 2, 1, 3, 2, 4, 3, 5, 6, 2, 7, O, 8, 4, 9, 3, 10, O, N} avec N = 11. La << sentinelle >> N pourra ne pas être le dernier élément du 
tableau h0r; on
autorisera donc les lignes d'horizon contenues dans les seuls premiers éléments 
d'un tableau.

Dans un premier temps (questions 2 et 3), on se contente d'une ligne d'horizon 
où tous les seg--
ments horizontaux sont de longueur 1. Avec cette convention, on prend, pour 
représenter la ligne
d'horizon correspondant a la figure donnée en exemple, (0, 2, 1, 3, 2, 4, 3, 5, 
4, 5, 5, 5, 6, 2, 7, O, 8, 4, 9,
3, 10, O, N}. Alors la longueur EUR du tableau vérifie EUR = 2N + 1 et, pour 0 
5 k 5 N, hor[2k] = k:.

Question 2. Écrire une fonction horizonl() qui calcule, a partir de la matrice 
E, la ligne
d'horizon en temps linéaire par--rapport au produit MN.

On peut réduire le temps d'exécution de cette fonction en écrivant une fonction 
qui longe
la ligne d'horizon dans la matrice E. Le contour de l'horizon est la ligne 
continue formée d'une
succession de lignes horizontales et de verticales qui borde l'ensemble 
supérieur des bâtiments.
La longueur de ce contour est la somme des longueurs des segments verticaux et 
horizontaux
qui le composent.

Question 3. Écrire une fonction horizon2() qui calcule, a partir de la matrice 
E, la ligne
d'horizon en temps linéaire par rapport à la longueur L du contour de l'horizon.

II. Transformations de lignes d'horizon

Un tableau her, de longueur EUR, représentant une ligne d'horizon, est en forme 
canonique si,
pour tout lc, elle vérifie

hor[2k] < hor[2k + 2] (O 5 [EUR < (6 -- 1)/2) et hor[2k + 1]3£ hor[2k + 3] (O S [EUR < (EUR ---- 3)/2) . Question 4. Ecrire une fonction ca noniq ue(hor) qui retourne un tableau représentant hor en forme canonique, en temps linéaire par rapport a la longueur EUR de hor. On veut à présent fusionner deux lignes d'horizon comme indiqué sur la figure suivante : fusion(hon, how) ÆUÎ-- _ Les deux lignes d'horizon sont représentées par les tableaux hom et how de longueurs Ê1 et Êg. On peut effectuer cette fusion très facilement en examinant les deux tableaux de la gauche vers la droite, en maintenant la hauteur u' du dernier bâtiment rencontré dans hom et la hauteur U' du dernier bâtiment rencontré dans how, comme indiqué sur la figure suivante : hom how fusion(hon, how) Question 5. Écrire la fonction fusion (hom, how) qui retourne, en temps linéaire par rapport à fil + Kg, une ligne d'horizon fusionnant les lignes d'horizon hom et how de longueur & et &.