J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

E3A Option Informatique MP 2011

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo e3a
🔗 Explorer
Banque
E3A
Année
2011
Filière
MP
Matière
Info
E3A MPE3A 2011MP InfoInfo 2011
2025_08_29_e5403cc2d858f7bcbb8ag

CONCOURS ARTS ET MÉTIERS ParisTech - ESTP - ARCHIMEDE

Épreuve d'Informatique MP

Durée 3 h

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, d'une part il le signale au chef de salle, d'autre part il le signale sur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu'il est amené à prendre.

L'usage de calculatrices est interdit.

Indiquer en tête de copie le langage de programmation, Caml ou Pascal, choisi pour l'ensemble du sujet.
  • L'épreuve est constituée de trois problèmes totalement indépendants.
  • Dans toute la suite, on supposera que les éléments d'un tableau de longueur sont indexés de 1 à et ce, quel que soit le langage choisi en début de sujet.
  • Pour les candidats composant avec Pascal, on suppose disposer du type liste d'entiers Liste. La liste vide sera représentée par nil et on suppose disposer des fonctions suivantes :
  • cons prenant en argument un entier et une liste d'entiers et renvoyant une liste d'entiers dont la tête est et la queue ;
  • tete qui renvoie la tête d'une liste d'entiers;
  • queue qui renvoie la queue d'une liste d'entiers;

1 Décomposition de permutations

On note l'ensemble des permutations de l'ensemble où . On représente une telle permutation sous la forme d'un tableau de longueur où pour tout . Les tableaux considérés dans la suite sont supposés contenir des permutations et on ne vérifiera donc pas qu'ils représentent effectivement une permutation. Pour avec , la transposition est la permutation définie par:
Il est rappelé que toute permutation se décompose en produit de transpositions. Dans la suite, on représentera la transposition par le couple d'entiers .

1.1 Quelques fonctions auxiliaires

  1. Écrire une fonction swap prenant en argument deux entiers et et un tableau qui échange les éléments d'indice et du tableau .
  2. Écrire une fonction init prenant en argument un entier et renvoyant un tableau représentant la permutation .
  3. Écrire une fonction build prenant en argument un entier et une liste de transpositions et renvoyant un tableau de longueur représentant la permutation .

1.2 Un algorithme de décomposition

On considère l'algorithme suivant :
[decompose p=
    n:=longueur (p)
    l:= []
    k:=1;
    tant que (k<=n) faire
        si p[k]=k alors k:=k+1 sinon
            temp:=p[k]; swap temp k p; add (k,temp) l
        fin si
    fin faire
    renvoyer(l)
où la fonction add permet d'ajouter un élément en tête d'une liste et où [] désigne la liste vide.
  1. Expliciter le déroulement de l'algorithme sur le tableau . On donnera les valeurs de et à fin de chaque exécution de la boucle. (On pourra vérifier sur cet exemple que si la valeur finale de est , on a bien : .)
  2. On note et les valeurs de et à la fin de la -ième exécution de la boucle. On convient que et . On note le nombre de points fixes de et le nombre d'éléments présents dans la liste .
    (a) Prouver que la suite est strictement croissante.
    (b) Démontrer que l'algorithme termine toujours et, plus précisément, que la boucle est exécutée au plus fois, en notant la longueur du tableau .
    (c) On note le nombre d'éléments contenus dans la liste lorsque l'exécution s'achève, montrer que:
(d) Démontrer que le programme est correct (i.e. si la liste renvoyée est : , alors .
3. Si et si , l'orbite de est : . L'ensemble des orbites forme alors une partition de l'ensemble . Par exemple, si , on a :
On a donc la partition suivante : .
On note le nombre d'orbites distinctes de . Prouver que .

2 Le jeu de Marienbad

Soit . Sur une table sont disposés tas d'allumettes : le premier tas contient allumettes, le second , et le dernier tas contient allumettes. On suppose les strictement positifs. Le jeu se joue à deux. Le premier joueur retire un nombre strictement positif d'allumettes d'un tas, le second joueur fait de même, puis le premier, etc. La partie s'arrête lorsque toutes les allumettes ont été retirées; le joueur gagnant étant celui qui a pris la ou les dernières allumettes présentes sur la table, l'autre étant déclaré perdant.

2.1 Préliminaires

La table du vérité du «ou exclusif», noté est :
0 1
0 0 1
1 1 0
On rappelle que définit une structure de groupe commutatif sur . Soient et des entiers naturels. Leurs décompositions en base 2 s'écrit :
où les et les sont à valeurs dans . On définit alors une loi de composition interne sur , noté abusivement , par :
et on admet que ( ) est un groupe commutatif.
  1. Déterminer l'élément neutre de ( ).
  2. Si , quel est l'inverse de ?
  3. Soient et des entiers naturels tels que . Soit et soit avec . On pose : si et . Prouver que :
  1. Soient et des entiers naturels tels que . Prouver qu'il existe et avec de sorte que si on pose : si et , on a :
(Si est le développement binaire de , on pourra considérer :
Montrer que pour un tel , on a nécessairement .
5. Écrire une fonction xorb prenant en argument deux entiers et et renvoyant si et sont dans et renvoyant -1 sinon.
6. Écrire une fonction tobin prenant en argument un entier naturel et renvoyant une liste telle que :
  1. Écrire une fonction frombin prenant en argument une liste d'entiers de et renvoyant l'entier défini par :
(On supposera ne pas disposer de fonction calculant et on veillera à réaliser un minimum de multiplications.)
8. Écrire une fonction xor prenant en argument deux entiers naturels et et renvoyant . (On prendra garde au fait que les listes renvoyées par la fonction tobin sur et n'ont pas nécessairement la même longueur.)

2.2 Stratégie gagnante

Une configuration du jeu est entièrement caractérisée par la donnée du nombre d'allumettes de chacun des tas. On code donc une configuration par un -uplet d'entiers naturels ( ). On dit d'une configuration qu'elle est favorable lorsque ; sinon on dit qu'elle est défavorable. On note et les deux joueurs.
  1. (a) Décider si la configuration est favorable. Si c'est le cas, déterminer tous les coups qu'il est possible de jouer et qui placent le jeu dans une configuration défavorable.
    (b) Même question avec .
  2. Le joueur récupère la main et le jeu est dans une configuration favorable. Comment doit jouer pour être certain de gagner la partie?
  3. Le joueur récupère la main et le jeu est dans une configuration défavorable. Que peut-il faire?
  4. Écrire une fonction coupSuivant qui prend en entrée un tableau contenant une configuration non finale du jeu et qui modifie le tableau de sorte que celui-ci contienne la configuration obtenue après avoir joué un des coups correspondant à la stratégie détaillée lors des deux questions précédentes.

3 Résiduels d'un langage

Soit un alphabet fini et non vide. Si et si , on pose :
Un tel ensemble est un résiduel du langage . On se propose de montrer qu'un langage est rationnel si et seulement si celui-ci n'a qu'un nombre fini de résiduels et, si c'est le cas, de construire un automate déterministe le reconnaissant ayant un nombre minimal d'états.
  1. Soient et . Comparer et en justifiant votre réponse.
  2. Dans cette question, on suppose que et on considère le langage .
    (a) Représenter graphiquement un automate déterministe reconnaissant le langage .
    (b) Calculer pour et .
    (c) Décrire sans justification les différents résiduels de .
  3. On revient au cas général et on se donne un langage . On suppose que l'ensemble des résiduels de est fini :
On considère alors un automate où est l'ensemble fini des résiduels et où est définie par:
(a) En choisissant judicieusement l'état initial et l'ensemble des états finals, démontrer que l'automate ainsi construit reconnaît exactement et conclure.
(b) Représenter graphiquement l'automate obtenu si est le langage de la question 2.
4. Réciproquement, on se donne un langage rationnel et un automate déterministe reconnaissant . Si , le langage reconnu par , noté est le langage reconnu par l'automate .
(a) Soit . On note l'état de l'automate obtenu après lecture du mot . Établir et prouver un lien entre et .
(b) Démontrer finalement que n'a qu'un nombre fini de résiduels.
5. Si et si sont deux automates déterministes sur l'alphabet , un morphisme d'automates de dans est une application vérifiant :
(a) Si est un morphisme de dans , comparer les langages reconnus par et .
(b) Un morphisme d'automate est dit surjectif lorsque est surjective et lorsque . Reprendre la question précédente en supposant le morphisme surjectif.
(c) Soit un langage rationnel. On se donne un automate déterministe reconnaissant et on note l'automate construit à la question 3.(a). Construire un morphisme d'automates de dans et en déduire que le nombre d'états de est supérieur ou égal au nombre d'états de .
(d) Que dire de plus lorsque et ont le même nombre d'états?
E3A Option Informatique MP 2011 - Version Web LaTeX | WikiPrépa | WikiPrépa