Info-maths ens 2018

Un problème, une question, un nouveau théorème ?

Modérateurs : JeanN, Michel Quercia

Répondre
Avatar du membre
noro
Messages : 96
Enregistré le : mar. févr. 13, 2018 5:41 pm
Classe : MP*

Info-maths ens 2018

Message par noro » ven. avr. 27, 2018 2:42 am

Voici l'epreuve info-maths 2018:
Personnellement la question qui m'a posé le plus de difficultés est la 11 parce-que la surjectivité ou non surjectivité était vraiment difficile à prouver, j'ai finalement écrit que phi était surjectif et que psi ne l'était pas avec une pseudo justification de la surjectivité de phi.
infomaths.zip
(4.66 Mio) Téléchargé 180 fois
Nothing happened.
-------------------------------------------
ENS PS Maths/Info 2018

Almar
Messages : 62
Enregistré le : lun. juin 27, 2016 11:03 pm

Re: Info-maths ens 2018

Message par Almar » ven. avr. 27, 2018 7:07 am

J'ai trouvé que ça allait.
Pour la surjectivité de Phi on pouvait prendre une configuration et en donner un antécédent. Par exemple un antécédent de \( b \) pouvait être construit de la sorte :
\( a_0 = b_0 \), \( a_1 = a_{-1} = 0 \) et \( \forall n > 0 \), \( a_{n+1} = a_{n-1} + a_{n} + b_n \) et \( a_{-n-1} = a_{-n + 1} + a_{-n} + b_{-n} \). (On utilise le terme le plus extérieur pour corriger les deux précédents, le tout est evidemment modulo 2).
Pour la non surjectivité de Psi, on pouvait montrer que \( 1^{\mathbb{Z}} \) n'avait pas d'antécédents on retardant les 4 possibilités sur \( (a_{-1}, a_0, a_1) \), puis ce que ça entraîne sur \( a_2, a_3 \) et montrer qu'au bout d'un moment on a forcément un \( 0 \).
Modifié en dernier par Almar le dim. avr. 29, 2018 9:08 am, modifié 1 fois.
2016-2017 : MPSI (Lycée Pierre de Fermat)
2017-2018 : MP*
2018-20XX : ENS de Lyon

matmeca_mcf1
Messages : 1001
Enregistré le : mar. févr. 13, 2018 10:22 am

Re: Info-maths ens 2018

Message par matmeca_mcf1 » ven. avr. 27, 2018 3:13 pm

J'ai annoncé sur le fil de X maths B (l'épreuve annulée) que je ferai un commentaire culturel sur ce sujet s'il était posté. Malheureusement, je n'ai pas grand chose à dire d'un point de vue culturel sur l'épreuve car c'est de l'info théorique et j'ai arrêté l'info théorique après mon cours d'info en L3 au dpt math info de Cachan (avant la scission des deux départements). Mais chose promise, chose due même si ça va être court et limité à la partie math (topologie).

Dans le sujet, on définit une notion de distance et une topologie. En prépa, la topologie est limitée aux espaces vectoriels normés. Ici, on introduit une distance. Les distances permettent de définir ce que l'on appelle des espaces métriques. En général pour un ensemble \( E \), une distance est une application \( d \) de \( E\times E \) dans \( \mathbb{R}^+ \) qui vérifie l'inégalité triangulaire
$$
\forall x\in E,\,\forall y\in E,\,\forall z\in E \; d(x,z)\leq d(x,y)+d(y,z),
$$
est symétrique
$$
\forall x\in E,\,\forall y\in E\; d(x,y)= d(y,x),
$$
et la propriété de séparation
$$
\forall x\in E,\,\forall y\in E\; (d(x,y)=0\iff x=y.
$$
Une fois la notion de distance définie, on définie les boules ouvertes comme dans le sujet \( B(x,r)=\{y\in E:d(x,y)<r\} \). Et toutes les notions de topologies (ouverts, fermés, limites de suite, compacité) fonctionnent comme avec les evn. J'avoue que je ne vois pas vraiment l'intérêt de limiter l'étiude de la topologie aux evn, les espaces métriques ne sont pas fondamentalement plus difficiles à manipuler que des evn d'un point de vue topologique.

Bizarrement, le sujet ne demande pas de vérifier qu'il s'agit d'une distance, ni ne définit la notion de distance. La symétrie et la propriété de séparation sont évidentes. Quand on essaie d'établir l'inégalité triangulaire, on se rend compte que la distance définie est même une distance ultra-métrique, i.e., vérifie:
$$
\forall x\in E,\,\forall y\in E,\,\forall z\in E \; d(x,z)\leq \max(d(x,y),d(y,z)).
$$
ce qui est une propriété plus forte que l'inégalité triangulaire. À partir du moment où \( d_A \) est une distance, la réponse à la question 3
est automatique de par les propriétés des espaces métriques (évidemment on n'a pas le droit d'écrire cela sur sa copie puisqu'il faut rester dans le cadre du programme de prépa).

Sinon, en ce qui concerne la partie info, je ne connaissais pas ces constructions, j'avais vu le concept d'alphabet en 1A à Cachan (très courant en info). Et nous avions vu la théorie des grammaires (pas dans le détail) et les machines de Turing où on utilisait un alphabet. Et on avait vu les langages mais dans \( A^\mathbb{N} \). Je n'avais pas vu les langages bilatéraux. Par contre, il y a suffisamment de vocabulaire pour qu'une recherche sur internet permette de découvrir de la littérature sur le sujet: https://ejcim2017.sciencesconf.org/data ... im2017.pdf page 9 du pdf (pavages et automates cellulaires).

EDIT: correction propriété de séparation \( \implies \) remplacée par \( \iff \).
Modifié en dernier par matmeca_mcf1 le ven. avr. 27, 2018 8:56 pm, modifié 1 fois.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'enseirb-matmeca.
Les opinions exprimées ci-dessus n'engagent que moi et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

MATHADOR
Messages : 1132
Enregistré le : dim. août 14, 2011 3:14 pm
Classe : M P *

Re: Info-maths ens 2018

Message par MATHADOR » ven. avr. 27, 2018 8:53 pm

Je n'ai pas regardé le sujet mais dans la définition de distance rappelée ci-dessus, contrairement au cas de la norme, la propriété de séparation (avec l'inégalité triangulaire et la symétrie) ne suffit pas. Autrement dit, il faut remplacer l'implication par une équivalence (ou alors garder l'implication et ajouter l'annulation sur la diagonale). Afin d'obtenir une définition encore plus satisfaisante, il convient de supposer la distance à valeurs réelles, la positivité étant alors une conséquence de la définition.

Quant à l'absence des espaces métriques au sein du programme, c'est effectivement une aberration (tout comme l'oubli de l'étude des limites supérieure et inférieure, que n'importe quel utilisateur des probabilités manipule au quotidien après la prépa). Heureusement que certaines classes continuent de voir ça. Dans tous les cas, ce sera vu en L3 ou dans les 1A d'écoles sérieuses.
2011-2012 : M P S I
2012-2013 : M P *
X2013

matmeca_mcf1
Messages : 1001
Enregistré le : mar. févr. 13, 2018 10:22 am

Re: Info-maths ens 2018

Message par matmeca_mcf1 » ven. avr. 27, 2018 9:07 pm

J'ai corrigé l'implication. Bien vu.
MATHADOR a écrit :
ven. avr. 27, 2018 8:53 pm
Afin d'obtenir une définition encore plus satisfaisante, il convient de supposer la distance à valeurs réelles, la positivité étant alors une conséquence de la définition.
Je ne suis pas d'accord que ce soit plus satisfaisant. Oui, on enlève une hypothèse mais on rend aussi la définition moins lisible, et en pratique, la positivité est évidente pour toutes les distances, et cela prend moins de 5 secondes de la vérifier la positivité. Le travail le plus dur quand on doit vérifier qu'on a bien une distance est la vérification de l'inégalité triangulaire. Ce sera toujours bien plus dur de vérifier l'inégalité triangulaire que de vérifier la positivité. Je préfère laisser \( \mathbb{R}^+ \) et avoir une définition plus lisible. Les définitions les plus succintes ou avec le moins d'hypothèses ne sont pas nécessairement meilleures.

Sinon, je suis aussi d'accord que l'étude de la \( \limsup \) et de la \( \liminf \) simplifieraient bien des exercices en prépa. Mais c'est un peu HS donc je vais en rester là.

EDIT: Je propose de déplacer le débat sur l'intérêt de la minimalité des hypothèses dans une définition ou un théorème vers un autre fil et de laisser ce fil à ceux qui veulent discuter de l'épreuve de maths infos des ENS.
Modifié en dernier par matmeca_mcf1 le sam. avr. 28, 2018 1:10 am, modifié 1 fois.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'enseirb-matmeca.
Les opinions exprimées ci-dessus n'engagent que moi et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

MATHADOR
Messages : 1132
Enregistré le : dim. août 14, 2011 3:14 pm
Classe : M P *

Re: Info-maths ens 2018

Message par MATHADOR » ven. avr. 27, 2018 11:31 pm

C'est de toute façon une affaire de goût et d'esthétique, mais je suis d'accord qu'ici, ça ne sert à rien en pratique, ce qui n'empêche pas la chose d'être appréciable. J'ai toujours préféré les cours dont les définitions et énoncés des théorèmes sont minimaux. L'un de mes professeurs de prépa avait cette habitude. En vrac : ne pas préciser que le groupe est abélien dans la définition d'un espace vectoriel, prendre une partie dénombrable et utiliser la dérivée à droite dans le TAF, avoir en tête le théorème de Mertens en parallèle de celui sur les produits de Cauchy, l'inégalité de Taylor-Lagrange reste valable avec une fonction de classe C^n et seulement n+1 fois dérivable, ne pas inutilement préciser qu'un temps d'arrêt est une variable aléatoire, remarquer en général les pléonasmes dans les définitions lorsqu'il y en a, \( etc. \) Même si bien souvent, ça ne sert pas forcément en pratique, c'est au final un réflexe (certains diront trouble) obsessionnel qu'il est bon d'avoir.
2011-2012 : M P S I
2012-2013 : M P *
X2013

BobbyJoe
Messages : 152
Enregistré le : lun. oct. 16, 2017 10:49 pm

Re: Info-maths ens 2018

Message par BobbyJoe » sam. avr. 28, 2018 12:53 am

Comme pour étudier les variations d'une fonctions dérivable sur un intervalle, il est suffisant de regarder les annulations de la dérivée (et de tester des valeurs) car tout le monde sait que la dérivée satisfait le TVI.... Bof.... La minimalité, c'est bien! Mais le caractère praticable (surtout lorsqu'on apprend) est plus audible.

Avatar du membre
oty20
Messages : 618
Enregistré le : dim. avr. 30, 2017 1:48 am

Re: Info-maths ens 2018

Message par oty20 » sam. avr. 28, 2018 1:37 am

Bonsoir @BobbyJoe , je ne sais pas si vous vous en rappelez , il y a un moment déjà , vous avez mis en relation le sujet des Mines 2017 maths 2 , avec la probabilité alors qu'il s'agissait d'une épreuve centrée sur la topologie . Pourriez-vous donner plus de détails ? Merci .
-sup: public -> Spé:chez moi.
-2018-??? Ecole Central Casablanca.

''L’ennemi du savoir , n'est pas l'ignorance , mais l'illusion du savoir '' all within the four seas are brothers .

BobbyJoe
Messages : 152
Enregistré le : lun. oct. 16, 2017 10:49 pm

Re: Info-maths ens 2018

Message par BobbyJoe » sam. avr. 28, 2018 3:22 am

Le théorème démontré dans cette épreuve (un cas particulier du théorème de Kakutani) permet de prouver l'existence d'une mesure invariante pour des chaines de Markov homogène et d'états finis.
Tu peux voir cette application sur ce lien : https://imgur.com/a/YCwroAP

Desert
Messages : 104
Enregistré le : mar. août 08, 2017 11:42 pm

Re: Info-maths ens 2018

Message par Desert » sam. avr. 28, 2018 4:03 am

BobbyJoe a écrit :
sam. avr. 28, 2018 12:53 am
Comme pour étudier les variations d'une fonctions dérivable sur un intervalle, il est suffisant de regarder les annulations de la dérivée (et de tester des valeurs) car tout le monde sait que la dérivée satisfait le TVI.... Bof.... La minimalité, c'est bien! Mais le caractère praticable (surtout lorsqu'on apprend) est plus audible.
Très bien dit je trouve

Avatar du membre
noro
Messages : 96
Enregistré le : mar. févr. 13, 2018 5:41 pm
Classe : MP*

Re: Info-maths ens 2018

Message par noro » sam. avr. 28, 2018 6:59 pm

Almar a écrit :
ven. avr. 27, 2018 7:07 am
J'ai trouvé que ça allait.
Pour la surjectivité de Phi on pouvait prendre une configuration et en donnet un antécédent. Par exemple un antécédent de \( b \) pouvait être construit de la sorte :
\( a_0 = b_0 \), \( a_1 = a_{-1} = 0 \) et \( \forall n > 0 \), \( a_{n+1} = a_{n-1} + a_{n} + b_n \) et \( a_{-n-1} = a_{-n + 1} + a_{-n} + b_{-n} \). (On utilise le terme le plus extérieur pour corriger les deux précédents, le tout est evidemment modulo 2).
Pour la non surjectivité de Psi, on pouvait montrer que \( 1^{\mathbb{Z}} \) n'avait pas d'antécédents on retardant les 4 possibilités sur \( (a_{-1}, a_0, a_1) \), puis ce que ça entraîne sur \( a_2, a_3 \) et montrer qu'au bout d'un moment on a forcément un \( 0 \).
C'est stylé comme démonstration, perso j'ai calculer les 8 valeurs de phi, puis j'ai dis qu'on pouvais toujours choisir le terme suivant de a pour atteindre b avec Phi.
Nothing happened.
-------------------------------------------
ENS PS Maths/Info 2018

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Exabot [Bot] et 6 invités