Cet article est en construction.

Vous trouverez dans cet article toutes les données à propos de l'option informatique en classe préparatoire MPSI, MP, PCSI, PC, PSI pour réussir les concours Polytechnique, ENS, Centrale, Mines :

• Tous mes conseils pour les différentes périodes de l'année
• Mes sujets d'écrits avec mes ressentis pour comprendre le fonctionnement des écrits
• Mes sujets d'oraux avec mes ressentis et ma correction pour comprendre le fonctionnement des oraux

Conseils pour l'année de sup (MPSI)

Conseils pour l'année de spé (MPSI)

Conseils pour les écrits (Polytechnique, ENS, Mines, Centrale)

Conseils pour les oraux (ENS)

Mes planches d'oral

ENS

Info LCR (40 mns de passage + 5 mns de question sur l'info aux ENS)

Enoncé
Soit \(G = (V, E)\) un graphe. Un plongement de \(G\) est une représentation de \(G\) dans \(R^2\) (une manière de dessiner le graphe dans le plan). \(G\) est planaire si il existe un plongement où les arêtes ne se coupent qu'aux sommets. Une face est une composante connexe de \(R^2\) privé de l'image du graphe.

1) Montrer que le graphe complet à 4 sommets est planaire (donner une représentation avec des segments).
2) En utilisant cette inégalité (théorème d'Euler, je crois) pour un graphe planaire : \(|V| - |E| + |F| = 1 + c(G)\) où \(c(G)\) est le nombre de composantes connexes de \(G\), montrer que pour un graphe connexe et planaire, \(|E| \leq 3|V| - 6\).
3) Donner un graphe non planaire
4) Montrer que pour tout graphe acyclique connexe (un arbre), on peut enlever un sommet tel que chaque composante connexe de ce nouveau graphe a moins de \(\frac{2}{3} |V|\) sommets.

Indications données pendant l'oral
2) Montrer que \(3|F| \leq 2|E|\)
4) Essayer d'enlever des arêtes

Commentaire à chaud
Examinateur sympathique, très calme, qui aide quand il le faut. 40 minutes de passage. 5 minutes de question sur les ENS. Le sujet comportait plus de 10 questions... J'ai perdu beaucoup de temps sur la question 2. Je me suis bloqué sur cette question.

Note obtenue
10

Info Ulm (1h de passage)

Enoncé
On définit \(L_n = L_{n-1} + L_{n-2} + 1\) et \(L_0 = L_1 = 1\).
1) Résoudre la récurrence.
2) Montrer que pour tout n entier, il existe \((x_0, ..., x_p)\) tels que :
- \(x_i < x_{i+1}\)
- pour \(i > 0\), \(x_i + 1 < x_{i+1}\)
- si \(x_0 = 0\), alors \(x_1 = 1\)
et \(n = L_{x_1} + ... + L_{x_p}\).

On définit récursivement \(T_n\) comme l'arbre ayant \(r\) pour racine, pour sous arbre-gauche \(T_{n-1}\) et sous-arbre droit \(T_{n-2}\).
3) Donner une manière d'encoder \(T_n\) avec au plus \(k\) valeurs où \(k\) est la taille de \(T_n\).
4) Définir les files de priorités.
5) Donner une implémentation de file de priorité (ajout, suppression) sous forme d'une liste \([T_{x_0}, ..., T_{x_p}]\) tels que \(x_{i} + 1 > x_{i+1}\) pour \(i < p\), la racine de \(T_{x_i}\) est strictement inférieure à la racine de \(T_{x_(i+1)}\). Les \(T_{x_i}\) doivent être des tas.

Indications données pendant l'oral
1) Introduire une constante pour la solution particulière. Finalement, on ne retient à la fin de la question qu'un \(O(L_n)\).
2) Faire une récurrence sur n et faire un disjonction sur le fait que \(x_0 + 1 = x_1\).
5) Pour l'ajout, utiliser la preuve de la récurrence de la question 2) pour gérer la reconstruction de la liste des \(T_n\), puis trier les racines et les arbres pour lesquels on a modifié la racine.

Commentaire à chaud
Examinatrice très très gentille (j'ai de la chance pour l'instant...). Elle est venue à côté de moi au tableau. J'étais moins stressé et plus relaché. Je suis allé un peu plus vite, avais de bonnes idées pour les premières questions puis ai patiné sur la question 5 pendant longtemps. Le sujet ne comportait que 7 questions et l'oral durait 1h.

Note obtenue
11