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.

Dans ce problème on s'intéresse à des polynômes à coefficients réels qui s'annulent en 0 . Un tel polynôme s'écrit donc . 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 . Le nombre 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 sont donc indexés de 1 à . On suppose qu'il existe également une primitive allouer( ) pour créer un tableau de cases. La taille d'un tableau est renvoyée par la primitive taille . L'accès à la case d'un tableau est noté . 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.

Question 1 Afin de se familiariser avec cette représentation, écrire une fonction evaluation qui prend en arguments un polynôme , représenté par un tableau, et un nombre flottant , et qui renvoie la valeur de .

Nous commençons notre étude par quelques observations. Voici des exemples de graphes de polynômes autour de l'axe des abscisses.

On remarque que le comportement au voisinage de l'origine est décrit par le premier monôme dont le coefficient est non nul (les coefficients étant donc tous nuls). En effet, quand est petit, le terme est négligeable devant le terme . Cet entier est la valuation du polynôme à l'origine. Par exemple, la valuation du polynôme est 3 . On remarque alors les deux règles suivantes au voisinage de l'origine :

Question 2 Écrire une fonction valuation qui prend en argument un polynôme et renvoie sa valuation. Par définition, cette fonction renverra 0 si est le polynôme nul.

On s'intéresse maintenant aux positions relatives autour de l'origine des graphes de deux polynômes et . La figure suivante montre les graphes de polynômes autour de l'origine.

On remarque que le comportement de ces graphes dépend de la parité de la valuation de la différence :

Question 3 Écrire une fonction difference qui prend en arguments deux polynômes et (dont les tailles peuvent être différentes) et qui renvoie la différence des polynômes .

Question 4 Écrire une fonction compare_neg qui prend en arguments deux polynômes et et qui renvoie :

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 et autour de l'origine, avec la légende suivante :

Le choix de ces polynômes est fait pour qu'à chaque fois les inégalités soient vérifiées pour légèrement négatif. Maintenant, observons les positions relatives de ces graphes pour légèrement positif. On remarque que l'ordre des courbes est permuté : on passe de l'ordre à un autre ordre. La donnée des trois polynômes et définit donc une unique permutation de telle que , pour positif et assez petit. On note que les six permutations de sont possibles, comme le montrent les six exemples ci-dessus.

De manière générale, on dit qu'une permutation de permute les polynômes si et seulement si :

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 .

Dans la suite, les permutations de seront représentées par des tableaux d'entiers de taille , indexés à partir de 1 et contenant tous les entiers entre 1 et .

Question 5 Écrire une fonction tri qui prend en argument un tableau contenant polynômes et qui le trie en utilisant la fonction compare_neg, de telle sorte que l'on ait pour 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 et un tableau de même taille supposé trié par la fonction tri, et renvoie vrai si permute les polynômes contenus dans , et faux sinon. On pourra s'aider d'une fonction compare_pos, similaire à la fonction compare_neg, pour comparer deux polynômes pour positif assez petit.

Dans la suite, nous dirons qu'une permutation de est un échangeur s'il existe polynômes 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 est un échangeur si et seulement si il n'existe aucun entiers tels que et

Question 7 Écrire une fonction est_echangeur_aux qui prend en argument une permutation de et un entier tel que et qui renvoie vrai s'il n'existe aucun entier et tels que 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 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 de permutations de qui sont des échangeurs :

Question 9 Écrire une fonction nombre_echangeurs qui prend un entier en argument et renvoie le nombre d'échangeurs . Enfin, les deux questions suivantes ont pour but d'énumérer tous les échangeurs de .

Question 10 Écrire une fonction decaler qui prend en arguments un tableau de taille et un entier , et renvoie un nouveau tableau de taille tel que

L'algorithme que nous allons utiliser pour énumérer les échangeurs de consiste à énumérer successivement les échangeurs de , pour tout de 1 à , dans un tableau de taille . Si on suppose qu'un tableau contient les échangeurs de entre les cases et , on peut en déduire les échangeurs de de la manière suivante : pour tout entier entre 1 et et tout entier entre 1 et , on décale (à l'aide de la fonction decaler) l'échangeur avec 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 en argument et renvoie un tableau contenant les échangeurs de . On pourra utiliser un second tableau pour stocker temporairement les nouveaux échangeurs.

*
4