X Informatique MP/PC 2010

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

CONCOURS D'ADMISSION 2010

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.

Échangeurs de Polynômes
Dans ce problème on s'intéresse à des polynômes à coefficients réels qui 
s'annulent en 0. Un tel
polynôme P s'écrit donc P (x) = a1 x + a2 x2 + · · · + am xm . Le but de ce 
problème est d'étudier
la position relative autour de l'origine de plusieurs polynômes de ce type.
Dans tout le problème, les polynômes sont représentés par des tableaux de 
nombres flottants
de la forme [a1 ; a2 ; · · · ; am ]. Le nombre am peut être nul, par conséquent 
un polynôme donné
admet plusieurs représentations sous forme de tableau. Ces tableaux sont 
indexés à partir de 1
et les éléments d'un tableau de taille m sont donc indexés de 1 à m. On suppose 
qu'il existe
également une primitive allouer(m) pour créer un tableau de m cases. La taille 
m d'un tableau
t est renvoyée par la primitive taille(t). L'accès à la ième case d'un tableau 
t est noté t[i].
Par ailleurs, on suppose que les tableaux peuvent être passés en argument ou 
renvoyés comme
résultat de fonction, quel que soit le langage utilisé par le candidat pour 
composer. Enfin, les
booléens vrai et faux sont utilisés dans certaines questions de ce problème. Le 
candidat est libre
d'utiliser les notations propres à ces booléens dans le langage dans lequel il 
compose.
Le problème est découpé en deux parties qui peuvent être traitées de manière 
indépendante.
Cependant, la partie II utilise les notions et notations introduites dans la 
partie I.
I. Permutation de n polynômes
Question 1 Afin de se familiariser avec cette représentation, écrire une 
fonction evaluation
qui prend en arguments un polynôme P , représenté par un tableau, et un nombre 
flottant v, et
qui renvoie la valeur de P (v).
Nous commençons notre étude par quelques observations. Voici des exemples de 
graphes de
polynômes autour de l'axe des abscisses.
1

2x2 + x4

-2x3 + 2x5

y=0

y=0

x + 3x4

-3x4 + 2x5

y=0

y=0

On remarque que le comportement au voisinage de l'origine est décrit par le 
premier monôme
ak xk dont le coefficient ak est non nul (les coefficients a1 , . . . , ak-1 
étant donc tous nuls). En
effet, quand x est petit, le terme ak+1 xk+1 + . . . + am xm est négligeable 
devant le terme ak xk .
Cet entier k est la valuation du polynôme à l'origine. Par exemple, la 
valuation du polynôme
-2x3 - 3x5 + 4x7 est 3. On remarque alors les deux règles suivantes au 
voisinage de l'origine :
­ Si la valuation k est paire, le graphe du polynôme reste du même côté de 
l'axe des abscisses.
­ Si la valuation k est impaire, le graphe du polynôme traverse l'axe des 
abscisses.
Question 2 Écrire une fonction valuation qui prend en argument un polynôme P et 
renvoie
sa valuation. Par définition, cette fonction renverra 0 si P est le polynôme 
nul.
On s'intéresse maintenant aux positions relatives autour de l'origine des 
graphes de deux
polynômes P1 et P2 . La figure suivante montre les graphes de polynômes autour 
de l'origine.

x2
2

x2 + 6x4

x

x2 + 3x3

On remarque que le comportement de ces graphes dépend de la parité de la 
valuation de la
différence P1 - P2 :
­ Si la valuation de P1 - P2 est paire, les deux graphes se touchent mais ne se 
traversent pas
à l'origine.
­ Si la valuation de P1 - P2 est impaire, les deux graphes se traversent à 
l'origine.
Question 3 Écrire une fonction difference qui prend en arguments deux polynômes 
P1 et P2
(dont les tailles peuvent être différentes) et qui renvoie la différence des 
polynômes P1 - P2 .
Question 4 Écrire une fonction compare_neg qui prend en arguments deux 
polynômes P1 et
P2 et qui renvoie :
­ un entier strictement négatif si P1 (x) est plus petit que P2 (x), pour x 
négatif assez petit
­ 0 si les deux polynômes P1 et P2 sont égaux
­ un entier strictement positif si P1 (x) est plus grand que P2 (x), pour x 
négatif assez petit.
On admettra sans démonstration que la fonction compare_neg définit une relation 
d'ordre.
Enfin, passons à l'étude des graphes de trois polynômes. Les figures ci-après 
montrent les
positions relatives de trois polynômes P1 , P2 et P3 autour de l'origine, avec 
la légende suivante :

P1 (x)

P2 (x)

2

P3 (x)

P1 (x) = x2

P2 (x) = 0 P3 (x) = -x2

P1 (x) = 0 P2 (x) = x3

P3 (x) = -x2

P1 (x) = x2

P2 (x) = -x3

P1 (x) = -x P2 (x) = x2

P1 (x) = x2

P1 (x) = -x P2 (x) = 0 P3 (x) = x

P2 (x) = -x2

P3 (x) = 0

P3 (x) = -x2

P3 (x) = x

Le choix de ces polynômes est fait pour qu'à chaque fois les inégalités P1 (x) 
> P2 (x) > P3 (x)
soient vérifiées pour x légèrement négatif. Maintenant, observons les positions 
relatives de ces
graphes pour x légèrement positif. On remarque que l'ordre des courbes est 
permuté : on passe
de l'ordre P1 (x) > P2 (x) > P3 (x) à un autre ordre. La donnée des trois 
polynômes P1 , P2 et P3
définit donc une unique permutation  de {1, 2, 3} telle que P(1) (x) > P(2) (x) 
> P(3) (x), pour
x positif et assez petit. On note que les six permutations de {1, 2, 3} sont 
possibles, comme le
montrent les six exemples ci-dessus.
De manière générale, on dit qu'une permutation  de {1, 2, . . . , n} permute 
les polynômes
P1 , P2 , . . . , Pn si et seulement si :
pour x négatif assez petit

P1 (x) > P2 (x) > . . . > Pn (x)

et P(1) (x) > P(2) (x) > . . . > P(n) (x) pour x positif assez petit
Ce qui était vrai pour trois polynômes ne l'est plus à partir de quatre 
polynômes : il existe des
permutations qui ne permutent aucun ensemble de polynômes P1 , P2 , . . . , Pn .
Dans la suite, les permutations de {1, 2, . . . , n} seront représentées par 
des tableaux d'entiers
de taille n, indexés à partir de 1 et contenant tous les entiers entre 1 et n.
Question 5 Écrire une fonction tri qui prend en argument un tableau t contenant 
n polynômes
et qui le trie en utilisant la fonction compare_neg, de telle sorte que l'on 
ait t[1](x) > t[2](x) >
· · · > t[n](x) pour x négatif et assez petit. Le candidat ne pourra pas 
utiliser pour cette question
de fonction de tri prédéfinie dans la bibliothèque du langage qu'il utilise 
pour composer.
Question 6 Écrire une fonction verifier_permute qui prend en argument une 
permutation
 de {1, 2, . . . , n} et un tableau t de même taille supposé trié par la 
fonction tri, et renvoie
vrai si  permute les n polynômes t[1], t[2], . . ., t[n] contenus dans t, et 
faux sinon. On pourra
s'aider d'une fonction compare_pos, similaire à la fonction compare_neg, pour 
comparer deux
polynômes pour x positif assez petit.
3

II. Échangeurs de n polynômes
Dans la suite, nous dirons qu'une permutation  de {1, 2, . . . , n} est un 
échangeur s'il existe
n polynômes P1 , P2 , . . . , Pn tels que  permute ces polynômes. Nous allons 
maintenant écrire
des fonctions qui répondent aux questions suivantes : Une permutation  est-elle 
un échangeur ?
Peut-on dénombrer les échangeurs ? Peut-on énumérer les échangeurs ?
Une condition nécessaire et suffisante pour qu'une permutation soit un 
échangeur est la
suivante : une permutation  de {1, 2, . . . , n} est un échangeur si et 
seulement si il n'existe aucun
entiers a, b, c, d tels que n  a > b > c > d  1 et
(b) > (d) > (a) > (c)

ou (c) > (a) > (d) > (b)

(1)

Question 7 Écrire une fonction est_echangeur_aux qui prend en argument une 
permutation
 de {1, 2, . . . n} et un entier d tel que 1  d  n et qui renvoie vrai s'il 
n'existe aucun entier
a, b et c tels que n  a > b > c > d et vérifiant (1), et faux sinon.
Question 8 En utilisant la fonction est_echangeur_aux, écrire une fonction 
est_echangeur
qui prend en argument une permutation  de {1, 2, . . . , n} et renvoie vrai si  
est un échangeur,
et faux sinon.
On admet sans démonstration que la relation de récurrence suivante permet de 
compter le
nombre a(n) de permutations de {1, 2, . . . , n} qui sont des échangeurs :
a(1) = 1,

a(n) = a(n - 1) +

n-1
X

a(i) × a(n - i)

i=1

Question 9 Écrire une fonction nombre_echangeurs qui prend un entier n en 
argument et
renvoie le nombre d'échangeurs a(n). Enfin, les deux questions suivantes ont 
pour but d'énumérer
tous les échangeurs de {1, 2, . . . , n}.
Question 10 Écrire une fonction decaler qui prend en arguments un tableau t de 
taille n et
un entier v, et renvoie un nouveau tableau u de taille n + 1 tel que

 u[1] = v

u[i] = t[i - 1]

 u[i] = 1 + t[i - 1]

si t[i - 1] < v et 2  i  n + 1 si t[i - 1]  v et 2  i  n + 1 L'algorithme que nous allons utiliser pour énumérer les échangeurs de {1, 2, . . . , n} consiste à énumérer successivement les échangeurs de {1, 2, . . . , k}, pour tout k de 1 à n, dans un tableau t de taille a(n). Si on suppose qu'un tableau t contient les m échangeurs de {1, . . . , k} entre les cases t[1] et t[m], on peut en déduire les échangeurs de {1, . . . , k + 1} de la manière suivante : pour tout entier v entre 1 et k + 1 et tout entier i entre 1 et m, on décale (à l'aide de la fonction decaler) l'échangeur t[i] avec v puis on teste si le résultat est un échangeur (avec la fonction est_echangeur_aux). Question 11 Écrire une fonction enumerer_echangeurs qui prend un entier n en argument et renvoie un tableau contenant les a(n) échangeurs de {1, 2, . . . , n}. On pourra utiliser un second tableau pour stocker temporairement les nouveaux échangeurs. 4