X Informatique MP/PC 2005

Thème de l'épreuve Réduction et fusion de lignes d'horizon
Principaux outils utilisés boucles for et while, parcours de tableaux à une et deux dimensions, variables et procédures locales et globales

Corrigé

(c'est payant, sauf le début): - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
        

Rapport du jury

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2005/MP_INFO_X_2_2005.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


É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 &.

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP/PC 2005 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Walter Appel (Professeur en CPGE) et Vincent Puyhaubert (Professeur en CPGE).

Cette épreuve est réservée aux candidats de la filière MP n'ayant pas choisi
l'option informatique. Elle n'est comptabilisée que pour l'admission et est 
commune
avec la filière PC.
Le thème abordé est une étude très simplifiée d'un problème de géométrie 
algorithmique : étant donné un ensemble d'objets en trois dimensions, 
déterminer le contour
perçu par un observateur. En particulier, certains objets peuvent être 
partiellement
cachés.
Toutes les questions demandent d'écrire du code. Nous l'avons rédigé en Maple
car ce langage est le plus connu dans les filières MP et PC, même s'il est plus 
destiné
au calcul formel qu'à la programmation. D'autres langages sont autorisés pour 
cette
épreuve, parmi lesquels figurent Caml, C, C++, Java et Pascal. Les fonctions 
écrites
n'utilisant que la syntaxe de base, vous pourrez sans peine les réécrire dans 
votre
langage préféré.
Le sujet est assez difficile et parfois les questions ne sont pas suffisamment
détaillées. De plus, il y a peu de questions et les fonctions à écrire sont 
longues.
Il faut porter une attention particulière aux indices, à l'initialisation des 
variables,
aux conditions d'arrêt et à la mise à jour des variables.
· La première partie définit ce qu'est une ligne d'horizon et en construit une 
de
façon naïve puis un peu plus évoluée.
· La seconde manipule les lignes d'horizon de deux manières : mise sous forme
canonique et fusion de deux lignes.
Ce corrigé introduit les fonctions locales, qui ne sont pas indispensables pour 
faire
cette épreuve mais sont pratiques et permettent de gagner du temps.
Ce sujet est progressif et constitue une bonne préparation au concours, mais
au vu de sa difficulté il est préférable de ne l'aborder qu'une fois le cours 
maîtrisé
et après avoir pratiqué la programmation.

Indications
Pour chacune des questions, sauf la première, il y a plusieurs indications (une 
par
phrase). Nous vous conseillons de tenter à nouveau de résoudre la question 
avant de
toutes les lire.
1 Remplir la matrice E avec des 0 puis, pour chaque immeuble (donc avec une
boucle for), mettre des 1 dans toutes les cases couvertes par cet immeuble.
2 Pour chaque abscisse x, chercher la hauteur y de la ligne d'horizon à cet 
endroit
et écrire x et y dans le tableau résultat. Comme indiqué par l'énoncé, x est 
écrit
dans la case 2*x du tableau, y dans la case suivante.
3 Distinguer quatre cas :
· On est à l'intérieur d'un immeuble, et l'on monte jusqu'à en sortir, 
c'est-à-dire
jusqu'à rencontrer une case contenant 0.
· On est sur un immeuble, et l'on avance (vers la droite) jusqu'à rencontrer 
soit
un mur qui monte (c'est-à-dire que l'on est dans une case contenant 1), soit
la fin du toit (c'est-à-dire que la case en dessous contient 0).
· On est au sol et l'on avance jusqu'à rencontrer un mur qui monte.
· On descend le long d'un mur, jusqu'à soit rencontrer le sol (y = 0), soit
rencontrer un toit.
Créer une variable direction qui contient le cas courant et faire une boucle 
while
dans laquelle, suivant la direction courante, on met à jour x et y, on change 
éventuellement de direction, et l'on écrit éventuellement x et y dans le 
tableau résultat.
4 Tenir à jour la position x dans le tableau hor et k dans le tableau résultat. 
Utiliser
une boucle « while hor[2*x] < N do ... ». Recopier deux cases de hor dans le
tableau résultat chaque fois que la ligne d'horizon change de hauteur.
5 Créer toutes les variables locales proposées par l'énoncé : i, j, k, x, y, u, 
u , v, v  , et
les tenir à jour (chaque fois que l'on modifie i ou j). Distinguer les cas x < 
y, x > y
(qui est symétrique) et x = y. Ne pas s'attacher (au moins dans un premier 
temps)
à renvoyer une ligne d'horizon sous forme canonique. On peut utiliser la 
fonction
suivante qui renvoie la longueur d'un tableau :
longueur := proc(tableau)
local bounds;
bounds := op(2,eval(tableau));
op(2,bounds) - op(1,bounds) +1;
end;

I. Détermination de la ligne d'horizon
On suppose dans ce corrigé que la matrice E est également une variable
globale. On trouvera à la fin de ce corrigé un exemple d'utilisation de ces
fonctions, qui commence par définir toutes les variables globales nécessaires.

1 On commence par remplir la matrice E avec des 0, puis, pour chaque immeuble i
défini par g[i], d[i] et h[i], on « colorie » cet immeuble dans E avec des 1. 
C'est la
fonction trace_rect qui se charge de tracer un immeuble.
C'est l'occasion de montrer que l'on peut définir une fonction locale (ici
trace_rect) à l'intérieur de la fonction remplir. De même que la variable i
n'existe pas à l'extérieur de la fonction remplir (alors que E si), la fonction
trace_rect n'est utilisable que dans la fonction remplir. Une fonction locale 
n'était pas indispensable ici, mais cette construction sera très utile par
la suite.

remplir := proc()
global g,d,h,n,M,N,E;
local i,x,y,trace_rect;
#
On remplit E avec des 0:
for x from 0 to N-1 do
for y from 0 to M-1 do
E[x,y] := 0;
od;
od;
#
On définit la procédure locale trace_rect:
trace_rect := proc (i)
global E;
local x,y;
for x from g[i] to d[i] -1 do
for y from 0 to h[i] -1 do
E[x,y] := 1
od;
od;
end;
#
On l'utilise pour remplir les immeubles:
for i from 0 to n-1 do trace_rect(i) od;
end;

Pour toute fonction (remplir comme trace_rect) il faut préciser à Maple
les variables globales utilisées à l'aide du mot clé global.

2 L'idée est simple : pour chaque abscisse x, on cherche la hauteur y de la 
ligne
d'horizon à cet endroit, et l'on écrit x et y dans le tableau résultat.
On commence donc par créer un tableau resultat de longueur 2N + 1 comme
l'indique l'énoncé. Trouver la hauteur de la ligne d'horizon se fait en partant 
de y = 0
et en augmentant y jusqu'à ce que la case (x, y) contienne 0 ; c'est une boucle 
while.
Il suffit alors d'écrire x dans la case 2x du tableau, et y dans la case 
suivante.
L'énoncé indique en effet que x est dans la case 2x. Rappelons qu'une
ligne d'horizon est stockée dans un tableau de la manière suivante :
(x1 , y1 , x2 , y2 , x3 , y3 . . . )
L'horizon est alors constitué de l'ensemble des segments horizontaux de la
forme [(xi , yi ); (xi+1 , yi )].
Cette notation permet d'utiliser peu de place pour stocker une ligne
d'horizon lorsque N est grand devant le nombre de segments de la ligne.
Comme la complexité des fonctions des questions 4 et 5 est linéaire en la
longueur du tableau représentant la ligne d'horizon, ceci représente un gain
de temps par rapport à des tableaux de longueur linéaire en N. Ce gain
de place et de temps est rendu possible par la fonction canonique de la
question 4.
Ce que l'énoncé appelle « sentinelle » est une marque que l'on met dans la
dernière case contenant des données. Ici cette marque est N, qui est connue car
N est une variable globale. Le tableau peut avoir plus de cases, mais il ne faut
pas les lire : la sentinelle indique la fin de la partie intéressante. Cet 
artifice est
par exemple utilisé pour les chaînes de caractères en C : le dernier caractère
est nul.
La figure suivante montre un exemple d'immeubles et le chemin parcouru par la
fonction horizon1 :

horizon1 := proc()
global E,N;
local resultat,x,y;
resultat := array(0..2*N); #tableau de longueur l = 2N+1 éléments
for x from 0 to N-1 do
y := 0;
while E[x,y] = 1 do y := y+1 od;
resultat[2*x] := x; resultat[2*x+1] := y;
od;
resultat[2*N] := N;
resultat
end;
Cette fonction examine au plus une fois chacune des cases de E, sa complexité 
est
donc linéaire en MN.