X Informatique MP/PC 2010

Thème de l'épreuve Échangeurs de polynômes
Principaux outils utilisés boucles for et while, parcours de tableaux
Mots clefs polynômes, permutations

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

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


É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

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


 X Informatique MP/PC 2010 -- Corrigé Ce corrigé est proposé par Céline Chevalier (ENS Cachan) ; il a été relu par Guillaume Batog (ENS Cachan) et Arnaud Borde (École Polytechnique). Ce sujet s'intéresse à une famille de permutations. Pour les définir, on part d'une famille finie de polynômes deux à deux distincts. Au voisinage de 0+ d'une part, de 0- d'autre part, ces polynômes peuvent être ordonnés selon les positions relatives de leurs courbes. L'ordre des polynômes à gauche et à droite de 0 est le même si, par exemple, tous les polynômes de la famille sont pairs. Dans le cas général, on passe du classement en 0- au classement en 0+ par une permutation sur les polynômes ; une telle permutation est appelée un échangeur. Le problème est divisé en deux parties relativement indépendantes, dans le sens où la seconde utilise les notions et notations de la première, mais pas ses résultats. · La première partie, plus facile, a pour objectif de tester si une permutation est un échangeur pour une famille de polynômes donnée. Les polynômes sont représentés ici par des tableaux indicés de 1 à m, ce qui est bien adapté aux notations de Maple. La première question permet de se familiariser avec les notations, et les trois suivantes calculent la valuation de polynômes afin de comparer deux polynômes au voisinage de l'origine. Ceci permet alors de trier un tableau de polynômes, puis de vérifier si une permutation donnée est un échangeur pour ces derniers. · La seconde partie a pour objectif d'énumérer les échangeurs. Grâce à une caractérisation admise par l'énoncé, les deux premières questions permettent de tester si une permutation est effectivement un échangeur. L'énoncé admet alors la formule donnant le nombre de ces échangeurs, et la question suivante le calcule. Enfin, les deux dernières questions énumèrent la totalité des échangeurs parmi les permutations de {1, . . . , m}. Hormis la dernière question, ce problème ne présente pas de réelle difficulté mais permet d'aborder tous les thèmes classiques de l'épreuve (tableaux, boucles itératives et conditionnelles, tests) et constitue donc un bon sujet de révision. Indications Partie I 1 Si le polynôme P(X) = a1 X + a2 X2 + · · · + am Xm est représenté par le tableau t, chaque réel ai est représenté par t[i]. Il suffit d'effectuer une boucle ajoutant à chaque itération la valeur t[i] * v^i. 2 La fonction valuation parcourt le tableau représentant le polynôme P et renvoie l'indice du premier élément non nul. 4 Le polynôme P1 - P2 se comporte comme un certain monôme ak xk . Distinguer suivant la parité de la valuation de P1 - P2 . 5 On peut utiliser ici le tri à bulles, qui parcourt le tableau en échangeant deux éléments consécutifs s'ils sont dans le mauvais ordre. En cas d'échange, le parcours du tableau recommence à l'indice précédent. 6 Si la permutation est représentée par un tableau p, la fonction verifier_permute compare, pour tout i, t[p[i]] et t[p[i+1]] à l'aide de compare_pos et renvoie vrai si tous ces polynômes sont dans le bon ordre. Partie II 7 Tester la relation (1) sur tous les triplets (a, b, c) et renvoyer faux si elle n'est pas vérifiée pour l'un d'entre eux. Renvoyer vrai sinon. 8 Essayer la fonction de la question 7 pour tout entier d et renvoyer faux si cette dernière renvoie faux pour l'un d'entre eux. Renvoyer vrai sinon. 9 Exploiter la relation de récurrence donnée en stockant au fur et à mesure les valeurs a(i) dans un tableau a pour éviter de les recalculer. 11 À chaque itération sur k, décaler chaque échangeur du tableau t (qui vaut [1] initialement) d'une valeur v de 1 à k + 1 et regarder si la permutation obtenue est un échangeur. Si oui, la stocker dans un tableau temp. À la fin de l'itération, donner à t la valeur de temp. I. Permutation de n polynômes Le sujet demande d'utiliser des tableaux, et propose d'admettre qu'il existe une fonction allouer dans le langage utilisé afin de les déclarer. Sous Maple, il est possible d'implémenter ces tableaux par des objets de type list, qui se manipulent à l'aide de l'instruction t[i] pour accéder au i-ième élément du tableau t. Le type list évite les complications du type array (appels de procédures à l'intérieur de procédures, par exemple). La fonction allouer n'est pas indispensable en Maple ; elle est ici utilisée pour respecter l'énoncé. On peut en donner l'implémentation suivante : allouer := proc(m) local i; RETURN([seq(0,i=1..m)]); end; Quant à la fonction taille, on peut proposer le code suivant : taille := proc(t) RETURN(nops(t)); end; Enfin, les booléens sous Maple sont les variables true et false. 1 La fonction evaluation prend en argument un tableau [a1 ; . . . ; an ] représentant un polynôme P et un nombre flottant v. Le calcul de P(v) utilise une variable temporaire resultat pour stocker la réponse, et s'effectue à l'aide d'une boucle for pour ajouter ai v i à cette variable à chaque itération. Par souci d'efficacité, utilisons une variable temporaire w pour stocker les valeurs successives v i sans les recalculer à chaque fois. On obtient le code suivant : evaluation := proc(t,v) local resultat,w,i; resultat := 0; w := 1; for i from 1 to taille(t) do w := w * v; resultat := resultat + t[i] * w; od; RETURN(resultat); end; L'évaluation proposée ici est facile mais non optimale. Pour diminuer le nombre de multiplications, une solution serait d'utiliser l'algorithme de Hörner : P(v) = v a1 + v a2 + v · · · + v(an-1 + van ) . 2 La fonction valuation prend en argument un tableau [a1 ; . . . ; an ] représentant un polynôme P. Elle parcourt ce tableau et s'arrête à la première valeur non nulle rencontrée : l'indice correspondant est alors la valuation de P. Si le programme sort de la boucle while avant de rencontrer une telle valeur, c'est que le tableau (et le polynôme) est nul : il renvoie alors 0 comme indiqué par l'énoncé. valuation := proc(P) local m,i; i:=1; m := taille(P); while (i <= m and P[i]=0) do i := i+1; od; if i = m+1 then RETURN(0) else RETURN(i) fi; end; 3 La fonction difference prend en argument deux tableaux t1 et t2 représentant deux polynômes P1 et P2 . Puisque le degré d'une différence de polynômes est inférieur ou égal au plus grand des degrés de ces polynômes, elle alloue un tableau t de taille égale à la plus grande des tailles de ces deux tableaux pour représenter le polynôme différence. Elle parcourt alors ces trois tableaux en effectuant à chaque itération de la boucle for l'opération de différence t[i] := t1[i] - t2[i] lorsque c'est possible (c'est-à-dire si les indices sont compatibles). difference := proc(t1,t2) local m,n,p,i,t; m := taille(t1); n := taille(t2); p := max(m,n); t := allouer(p); for i from 1 to p do if (i <= m and i <= n) then t[i] := t1[i] - t2[i]; elif i <= m then t[i] := t1[i]; else t[i] := -t2[i]; fi; od; RETURN(t); end; Il faut faire attention dans cette question au fait que les tableaux n'ont aucune raison d'être de même taille. S'ils ne le sont pas, on les complète implicitement par des zéros pour faire la différence : c'est la raison du test conditionnel, indispensable sous peine d'obtenir une erreur d'indice inexistant à la compilation. En outre, remarquons que la condition elif i <= m signifie en fait elif (i <= m and i > n) puisque Maple n'évalue pas cette deuxième condition (elif) si la première (celle du if) est vérifiée. 4 Soit k la valuation de la différence P1 - P2 et ak le coefficient correspondant. Alors le polynôme P1 - P2 se comporte comme le monôme ak xk au voisinage de 0. On en déduit que P1 (x) - P2 (x) est du signe de ak si k est pair, et de -ak si k est impair. La fonction compare_neg effectue ce test utilisant la fonction a mod b qui retourne le reste de la division euclidienne de a par b.