oral ENS

Messages : 797

Inscription : 25 juin 2006 18:16

Profil de l'utilisateur : Élève de lycée

oral ENS

Message par sunmat » 16 janv. 2008 18:17

Bonjour,
je cherche des sujets d'oraux d'ENS, pour les épreuves d'info fondamentale et d'algorithmique. Un copain m'a dit en avoir trouvé, mais vu qu'il n'est pas connecté en ce moment et que je n'ai pas envie d'attendre demain pour avoir ces épreuves, ce serai sympa si vous pouviez me renseigner (j'ai cherché sur les sites des ENS, mais j'ai rien trouvé...)
Merci !
MPSI (Carnot, Dijon) -> MP* (idem) -> ENS (Info, Ker Lann) -> Doctorat (ENS Rennes, IRISA Rennes) -> Post-doctorat (Argonne National Lab, IL, USA)
http://people.irisa.fr/Matthieu.Dorier

Messages : 1832

Inscription : 01 août 2007 15:04

Profil de l'utilisateur : Élève de lycée

Message par gardener » 16 janv. 2008 18:48

J'en ai aucune idée, mais vu que j'ai passé un oral d'info fondamentale, je me permets une petite remarque : Les sujets sont vraiment proches des sujets d'écrit, donc t'entrainer pour les écrits t'entrainera pour les oraux ! Plus qu'en maths ou en physique, je pense.
Doctorant Maths-Info, ancien ENS Cachan.

Messages : 296

Inscription : 14 mars 2007 22:28

Profil de l'utilisateur : Élève de lycée

Message par Jean Starynkévitch » 16 janv. 2008 19:03

On trouve aussi certaines de ces épreuves annuellement dans la Revue de Mathématiques Spéciales (RMS).
Professeur de Mathématiques - MP* (Prytanée national militaire, la Flèche, 72).

cerise

Message par cerise » 17 janv. 2008 14:59

Je peux te donner ce sur quoi j'étais tombée...

On considère un groupe de personnes et une relation (non symétrique) "A connaît B". On dit qu'une personne du groupe est une "star" si tout le monde la connaît et qu'elle ne connaît personne.
1) Combien peut-il y avoir de stars dans un groupe ?
2) Étant donnés un groupe et les relations "connaître" entre les personnes du groupe, trouver un algorithme qui permet de trouver les stars du groupe.

omamar3131

Message par omamar3131 » 17 janv. 2008 16:34

Il y a peut-être une imprecision dans l'énoncé non? Concernant le cardinal du groupe..

Messages : 797

Inscription : 25 juin 2006 18:16

Profil de l'utilisateur : Élève de lycée

Message par sunmat » 17 janv. 2008 18:17

La question 1) est évidente, la réponse est 1, pour la question 2) la relation "connaitre" est-elle transitive ? On sait qu'elle n'est pas symétrique, on suppose qu'elle n'est pas réflexive sinon il n'y a aucune star dans le groupe.
On peut prendre le liste (finie) des individus du groupe, en supprimer tous les individus qui connaissent quelqu'un (algo en O(n)). Puis si la liste des individus ne connaissant personne est de longueur 0 ou supérieur ou égal à 2, il n'y a pas de star. Si elle est de longueur 1, on vérifie que l'individu en question est connu de tout le monde (à nouveau un algo en O(n) si on suppose que la vérification de connaissance est à temps constant).
MPSI (Carnot, Dijon) -> MP* (idem) -> ENS (Info, Ker Lann) -> Doctorat (ENS Rennes, IRISA Rennes) -> Post-doctorat (Argonne National Lab, IL, USA)
http://people.irisa.fr/Matthieu.Dorier

Messages : 797

Inscription : 25 juin 2006 18:16

Profil de l'utilisateur : Élève de lycée

Message par sunmat » 17 janv. 2008 18:46

MDR !
je comptais demander à mon prof de me faire passer des oraux d'info (avec des potes), je voulais voir des sujets avant pour savoir ce que ça donnais... j'aurais mieux fait de le lui demander tout de suite, j'aurais pas eu à chercher :lol:
Merci en tout cas !
MPSI (Carnot, Dijon) -> MP* (idem) -> ENS (Info, Ker Lann) -> Doctorat (ENS Rennes, IRISA Rennes) -> Post-doctorat (Argonne National Lab, IL, USA)
http://people.irisa.fr/Matthieu.Dorier

cerise

Message par cerise » 17 janv. 2008 18:49

sunmat a écrit :La question 1) est évidente, la réponse est 1,
0 ou 1 plus précisément. L'algo de la question 2 doit aussi déterminer s'il en existe.
sunmat a écrit :pour la question 2) la relation "connaitre" est-elle transitive ?
Non.

Par ailleurs, on n'a aucune information sur le cardinal du groupe.

Je ne me rappelle pas vers quel algorithme l'examinateur m'avait dirigée...

Messages : 1832

Inscription : 01 août 2007 15:04

Profil de l'utilisateur : Élève de lycée

Message par gardener » 17 janv. 2008 22:58

remarque : la structure sous-jacente est un graphe, orienté ici. Et là on recherche une "étoile" (parce que ça ressemble à une étoile quand on dessine)
Doctorant Maths-Info, ancien ENS Cachan.

Répondre