Bon, sinon voilà le sujet, pour les intéressés.
Je l’ai retapé, ça m’a fait découvrir des commandes LaTeX. Même pas du temps complètement perdu.
pikachuyann a écrit:
Bon, sinon voilà le sujet, pour les intéressés.
Je l’ai retapé, ça m’a fait découvrir des commandes LaTeX. Même pas du temps complètement perdu.
Le 1.2.b) a été mal tapé.
CayleyMimosa a écrit:
Le sujet parait intéressant à première vue mais je n’ai pas saisi le lien avec la physique.
C’est dommage que le sujet n’explique pas plus pourquoi il s’agit de diffusion. Je l’ai compris car mon TIPE en est assez proche, mais pour quelqu’un qui a jamais fait ce genre de truc, le rapport ne doit pas se voir facilement.
En gros, on prends un graphe à N sommets dont les arrêtes sont pondérées par des coefficients (l’arrête entre les sommets i et j est pondérée par p_{ij}).
Le graphe est non orienté (c’est l’hypothèse P symétrique), connexe (P irréductible), et la somme des poids des arrêtes partant d’un sommet vaut 1 (P bistochastique).
Ensuite, on va répartir une certaine quantité d’un truc sur les sommets du graphe, et le truc va se diffuser d’un sommet à l’autre à travers les arrêtes, avec un débit proportionnel au poids de l’arrête et à la quantité de truc sur l’arrête de départ. u_i(t) est en fait la quantité de truc sur le sommet i à l’instant t. Et par exemple, dans la partie 1, on montrait qu’on tendait vers une répartition uniforme du truc entre les sommets, ce qui paraît logique, mais en plus qu’on y tendait à une vitesse exponentielle dépendant du trou spectral (différence entre les plus grandes valeurs propres de P).
Pour le lien avec la physique, je n’y connais pas grand chose, mais je sais que l’opérateur P - Id est parfois appelé le laplacien, et l’équation différentielle étudiée dans le sujet devient alors \frac{\partial u}{\partial t}=\Delta u, qui est une équation de diffusion.
Ce qui me fait un peu peur, c’est que le sujet comportait quand même pas mal d’algèbre : est-ce que ça signifie qu’on risque d’avoir un sujet assez orienté analyse lundi matin ?
Que vient faire la rgf?
Transformée de fourier ? Caractères de Dirichlet ?
Nuhlanaurtograff a écrit:
Je peux bien passer pour une gourde mais bien qu’en essayant de passer par une inégalité je n’ai toujours pas trouvé comment prouver que la dim du sous ep était 1;
On suppose les p_i_j > 0. On note u_k = max (u_i). Alors u_k = somme des p_k_j*u_j <= u_k*(somme des p_k_j qui vaut 1 par hypothèse, donc l’inégalité utilisée u_j =< u_k est une égalité pour tout j, donc u est dans Vect(pi). Pour le cas où on peut avoir certains p_i_j nuls, il fallait faire de même mais en utilisant l’hypothèse d’irréductibilité : on prend j différent de k, on prend un chemin qui correspond et on en déduit que u_k = u_j_l =... = u_j.
Moi j’ai fait de la sorte :
Je prend un vecteur propre pour la valeur propre 1, je le note u=(u_i). L’idée est de montrer qu’il est colinéaire à \pi. Je note u_0=\min u_i.On a u-u_0 \pi est encore un vecteur propre. Montrons qu’il est nul : P(u-u_0 \pi)=u-u_0 \pi, dans la ligne de O-ème, on a : \displaystyle \sum_{j=0} p_{o,j} (u_j-u_0)=0, donc une somme de termes positifs qui est nulle, donc tous les termes sont nuls, comme les p_{i,j} ne le sont pas, alors u_j=u_0 CQFD.
La 1c, m’a fait perdre beaucoup de temps et je ne l’ai pas trouvé. Sinon, j’ai fait jusqu’à Partie II question 4b sauf 1c, 3 c et une partie de 2b. Pour la 1c, faut utiliser irréductibilité sinon l’identité serait un contre exemple sauf que je n’ai pas compris cette propriété >_<
C’est marrant, Feynman, on a eu exactement le même raisonnement. Oo Et j’ai pas non plus trouvé comment faire la 1c. 
Noé a écrit:
En gros, on prends un graphe à N sommets dont les arrêtes sont pondérées par des coefficients (l’arrête entre les sommets i et j est pondérée par p_{ij})
…
Pour le lien avec la physique, je n’y connais pas grand chose, mais je sais que l’opérateur P - Id est parfois appelé le laplacien, et l’équation différentielle étudiée dans le sujet devient alors \frac{\partial u}{\partial t}=\Delta u, qui est une équation de diffusion.
Merci pour l’explication bien intéressante
pikachuyann a écrit:
Pour Informatique A: Caml, mais ça déjà fait;
Pour Informatique B: Maple / Mathematica (épreuve aux ENS Cachan pour tout le monde y compris les infos, et pour les SI à l’X)
Déjà pour A, tu oublie le Pascal, mais aussi pour l’info B (je crois qu’il y avait aussi des candidats qui avaient composé en java précédemment…).
Hachino a écrit:
C’est marrant, Feynman, on a eu exactement le même raisonnement. Oo Et j’ai pas non plus trouvé comment faire la 1c.
lol au départ je n’ai pas compris leurs indications, donc leurs indication m’a plutôt fait perdre du temps que en gagner.. Pour l’inégalité avec le ln(a) et ln(b) idem, j’ai fait une autre méthode ^^ . C’était mon premier sujet ENS mdr
Pour la 1.c, on utilise exactement la preuve que tu viens de faire pour la 1.b, qui permet de montrer, cette fois, que u_j=u_0 pour tout état j connecté à l’état 0. Puis en réappliquant ce résultat une fois, tu vois que c’est vrai pour tout état j' connecté à un état j connecté à l’état 0… et ainsi de suite. Comme P est irréductible, pour tout j il existe une suite de sommets connectés les uns aux autres reliant j à 0, et voilà !
Je n’ai saisi cette propriété irréductibilité, donc en gros une matrice irréductible est à coeff strict positifs ? 
Non, c’est pas ça, c’est une matrice d’adjacence de graphe connexe. Après, je ne vois pas comment donner une idée plus simple de ce que c’est sans utiliser de graphe, et c’est vrai qu’en terme de pure algèbre linéaire je ne vois pas trop ce que ça peut représenter.
Pour l’épreuve d’algo, j’ai codé en CAML (je suis en info et je passais cette épreuve pr Cachan), quelqu’un sait si ce sera pénalisé ?
VictorVVV a écrit:
On pouvait aussi montrer que si P est irréductible, alors \forall i,j, P^{n!}_{i,j} >0. Du résultat sur P^{n!} on en déduit celui sur P.
Cela ne fonctionne pas avec la matrice \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}.
Perso j’ai fait 1b) et 1c) en même temps en considérant Uio le max des Ui … mais aussi Ui1 le max des Ui privés de Uio … donc Uio>=Ui1
En écrivant le système Pu=u et en prenant la ligne correspondant à Uio= …
On prouve par majorations que (1-Pioio)Uio <= (1-Pioio)Ui1
Dès lors Uio=Ui1 … et l’on repète ce procédé … tous les Ui sont égaux et u est colinéaire à Pi … et l’on se sert juste que les Pij sont >= 0 et que la matrice est bistochastique …
C’a avait l’air de pas mal marcher …
En tout c’est ce que j’ai écrit … 
yayathe a écrit:
Perso j’ai fait 1b) et 1c) en même temps en considérant Uio le max des Ui … mais aussi Ui1 le max des Ui privés de Uio … donc Uio>=Ui1
En écrivant le système Pu=u et en prenant la ligne correspondant à Uio= …
On prouve par majorations que (1-Pioio)Uio <= (1-Pioio)Ui1Dès lors Uio=Ui1 … et l’on repète ce procédé … tous les Ui sont égaux et u est colinéaire à Pi … et l’on se sert juste que les Pij sont >= 0 et que la matrice est bistochastique …
C’a avait l’air de pas mal marcher …
En tout c’est ce que j’ai écrit …
Il faut absolument utiliser l’irréductibilité, car sinon, tu prends la matrice identité qui vérifie toutes les autres hypothèses pourtant 1 est une valeur propre multiple. C’est comme un ami en sortant il m’a dit qu’il l’a réussi, je lui ai demandé s’il a utilisé l’irréductibilité, il m’a dit non, après je l’ai dégouté
Pour ceux qui ont passé l’info cette aprem, vous n’avez pas trouver que c’était long ? Et surtout beaucoup plus dur que celui de l’an dernier !
C’est vrai
C’est pour cela que cela … avait l’air … de bien marcher
Perso ces trois questions m’ont pris 40 minutes et j’ai fini par écrire cela … Je sais pas vous mais la fatigue arrive après 4 semaines d’épreuves …
Concernant l’info en effet c’était pas un cadeau …
Mdr désolé de te décevoir
C’est pas grave c’est pas la dernière erreur faite dans le sujet je pense …
yayathe a écrit:
Je sais pas vous mais la fatigue arrive après 4 semaines d’épreuves …
Pour moi c’est l’inverse, j’ai complétement raté les mines, centrale moyen, ccp bien à part la physique, l’x et l’ens mieux que les mines, ça reste moyen mais je pense que c’est pas assez pour être admissible (je prend cher en physique alors que c’est la matière que j’ai le plus travaillé avant les concours xD ).