Après deux années de prépa (http://fr.wikipedia.org/wiki/CPGE ), j'ai passé des
concours, et depuis environ un mois, je passe des oraux, à peu près un par jour.
C'est très nerveux de passer ces oraux, et c'est pas toujours agréable. Mais
heureusement, vous, utilisateurs de linuxfr, vous avez fait preuve d'une
imagination débordante pour produire pendant cette période tout un tas de
dépêches/commentaires/trolls/réflexions (profondes)/... qui m'ont souvent permis
de me changer les idées.
Pour vous remercier, je viens donc vous proposer l'exercice que l'on m'a donné
lors de mon seul oral d'informatique (peut-être que vous n'en aurez rien à
faire, peut-être que ça vous rappelera des souvenirs, peut-être que ça vous fera
découvrir les automates et les langages rationnels...)
C'est un oral de l'ENS, ça porte sur la compression de mots sur l'alphabet {0;1}
à l'aide d'exposants. Il y a un peu de maths dans l'histoire, donc j'ai préféré
mettre l'énoncé dans un pdf...
http://pierroweb.free.fr/oral_info.pdf
N'hésitez pas à proposer des solutions, si ça en intéresse quelques uns je vous
raconterai comment on m'a fait traiter les trois premières questions...
Amusez-vous bien !
Journal Oral d'informatique
18
juil.
2008
# arf un 3/2
Posté par BAud (site web personnel) . Évalué à 4.
Bon courage, moi j'étais complètement stone à cette période, tellement d'ailleurs, que je me suis aperçu après coup du côté irréaliste de démarrer mes oraux un 14 juillet à 8h...
[^] # Re: arf un 3/2
Posté par mats . Évalué à 4.
J'espère qu'il va l'avoir son ENS :-)
Bonnes vacances. Dans tous les cas, elles sont méritées.
[^] # Re: arf un 3/2
Posté par Ririsoft . Évalué à 4.
J'ai eu l'impression de mieux maitriser les matières et ça fait du bien de ne plus nager en brasse coulée ! Et sur les résultats à l'intégration il n'y a pas photo !
En tout cas bravo à Nénuphare Rose pour son admissibilité à l'ENS (cachan ? ULM ? Lyon ?). Si tu es admissible en 3/2 je pense que tu n'as pas trop de soucis à te faire pour la suite ...
[^] # Re: arf un 3/2
Posté par modr123 . Évalué à 0.
# 1 et 2
Posté par ribwund . Évalué à 2.
on prend x = 0^{n/2}1^{n/2}
Pour 2:
À mon avis il faut encoder la forme compressée sous forme binaire (et que l'encodage soit de taille $\lbrqacket x \rbracket$), puis on montre qu'on peut compresser à l'infini (le truc classique de la compression que compresse toujours de au moins 1 bit).
Le reste j'ai la flemme, les automates et les langages ca date de y'a trop longtemps :)
[^] # Re: 1 et 2
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 1.
euh soudainement là...
n = 0, |x| = 0, <= c log(0)...
log(0)... ça marche pas ça ! Donc un tel x n'existe pas ! Les hypothèses sont fausses, on passe à la question suivante :D
2/ |y|, c'est log(nb_lettres(y))
log(|y|); c'est log(log((nb_lettres(y)))
montrer qu'on peut pas avoir <= c (log(log (nb_lettres(y)))
Hum.. pareil.. le mot vide. le log est pas défini dessus... (enfin, si le mot vide appartient à la fermeture par l'étoile de Kleene, je sais plus)
3/ Pareil que ribwund :D
4/ idem
Moi j'avais eu une preuve de NP-complétude d'un problème de graphes...
[^] # Re: 1 et 2
Posté par Ontologia (site web personnel) . Évalué à 1.
On pose x=1^n (on aurait pu prendre x=0^n)
Pour n>=2 tout va bien :
taille(x)=1+log2(n)= (1/log2(n)+1)log2(n) où 1/log2(n) +1 < 2
Donc là c'est bon.
Par contre pour n=1 :
taille(x)=1 et log2(1)=0 ...
De même pour n=0
Le reste à suivre :-)
Il est vraiment sympa ce sujet ;)
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: 1 et 2
Posté par Nénuphare Rose . Évalué à 1.
[^] # Re: 1 et 2
Posté par Ontologia (site web personnel) . Évalué à 1.
Ils les vérifient leur sujets ?
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: 1 et 2
Posté par Nénuphare Rose . Évalué à 1.
Et de toute façon, si tu as un doute sur l'énoncé l'examinateur pourra t'éclairer, et à mon avis ils vérifient leurs sujets et ils ont bien les problèmes en tête (en tout cas à l'ENS).
[^] # Re: 1 et 2
Posté par Aldoo . Évalué à 2.
On m’a parlé d'un sujet de physique du type « Combien de temps pour cuire une dinde au four ? ». Il s’agissait alors de faire des hypothèses raisonnables sur l'expérience.
[^] # Re: 1 et 2
Posté par Zenitram (site web personnel) . Évalué à 0.
Il y a eux pendant mes 2 ans des dizaines de cas du style "mais votre énoncé est bizarre, vous vous seriez pas trompé?". Deux réponses possible du prof après 10s : "ah oui, attendez (10s de plus), voila, vous pouvez continuer", ou "non, je ne me suis pas trompé" (et dans ce cas la on arrivait toujours à la fin de la démo, aidé par le prof).
Sur mes statistiques perso, environ 10% des doutes des élèves étaient justifiés (et bonjour la bâche du prof pour les 90% qui restaient...), mais comme mes profs étaient très compétents (du moins en prépa), on avait juste peur de la bâche assez gentille, on hésitait un peu avant de se lancer à dire que c'est faux (sachant qu'on avait 9 chances sur 10 de se faire bâcher :) ), mais on se lançait. C'était sympa (surtout quand c'est un autre qui pose la question 5s avant que tu te lance, et qui prend la bâche dans le figure :) )
[^] # Re: 1 et 2
Posté par Aldoo . Évalué à 1.
[^] # Re: 1 et 2
Posté par Tonton Th (Mastodon) . Évalué à 4.
Bravo, tu viens de réinventer I2BP !
[^] # Re: 1 et 2
Posté par ribwund . Évalué à 3.
[^] # Re: 1 et 2
Posté par PuRPLeHaZe . Évalué à -1.
Dans l'expression de la taille de la représentation, le log est arrondi à la valeur supérieure.
Par exemple sup(log(5)) = sup(2.3) = 3
Plus généralement :
sup(log(2^q + €)) = q+1 et sup(log(2^q))=log(2^q)=q
avec € une combinaison linéaire de 2^i de degré inférieur à n et telle que €>=1
C'est une bonne piste ?
# Amusant
Posté par yellowiscool . Évalué à 6.
Je pense qu'après une prépa, ça peut paraître moins abscons; mais là, c'est pire que les ingénieurs java qui utilisent 30 termes bizarres par phrase.
En tout cas, il y a de quoi s'amuser en été…
Bonne continuation.
Envoyé depuis mon lapin.
[^] # Re: Amusant
Posté par Infernal Quack (site web personnel) . Évalué à 9.
L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire
[^] # Re: Amusant
Posté par seginus . Évalué à 1.
Et bien quand on en sort, disont 2 ans après (mais même moins je pense), c'est juste si on arrive à lire les formules (je ne me souviens même plus vraiment de ce qui symbolise le ).
Sinon, merveilleux plan que tu as eu. Dire « j'ai un TD à faire pendant les vacances pouvez-vous m'aider » serait bien moins bien passé ;)
Aller bonnes vacances à toi et profite bien de tes vacances si tes examens sont enfin fini, tu vas maintenant pouvoir te préparer à travailler plus
[^] # Re: Amusant
Posté par Zenitram (site web personnel) . Évalué à 3.
Tu mélanges deux choses complètement opposées : l'Université a pour but de te former à un métier (et elle y arrive moyen... Beaucoup trop théorique, beaucoup.), la prépa a pour but de te préparer à l'école d'ingé, qui elle te formera à un métier.
Et bien quand on en sort, disont 2 ans après (mais même moins je pense), c'est juste si on arrive à lire les formules
Ca me rassure, je ne suis pas seul. Petit souvenir, 1 an pile après mes exams, chez un pote de l'école d'ingé :
- La soeur du pote : "je n'arrive pas a faire un exercice" (début math spé...)
- Le pote "débrouille toi, j'y comprend rien"
- Moi "bah... Ca fait un an seulement, ça devrait pas être la mer à boire, on a quand même fini ce putain de math spé... Montre"
(... Elle me montre le sujet...)
- Moi "bon, OK, j'ai compris un sigle sur deux, ça ne va pas le faire, vraiment pas, bon courage"
On oublie vite une langue comme celle de la prépa dès qu'on ne l'utilise plus :)
[^] # Re: Amusant
Posté par seginus . Évalué à 1.
La fac développe la créativité, là ou la prépa développe l'apprentisasage brut et le savoir.
La fac va donc être bien plus formatrice pour des aptitudes de recherches. Pour la prépa… et bien ça prépare à être ingénieur.
[^] # Re: Amusant
Posté par rewind (Mastodon) . Évalué à 3.
[^] # Ingé vers Fac
Posté par Zenitram (site web personnel) . Évalué à 3.
Euh... La on parlait Fac contre prépa, et j'ai bien précisé que l'équivalent de la Fac, si on veut comparer, c'est l'école d'ingé.
Comparer la Fac et la prépa, c'est comme comparer la Fac avec le lycée, c'est débile (d'ailleurs les prépas sont en Lycée...). Ca ne se compare pas, puisque en sortie de la Fac tu es "prêt", et pas en sorti de prépa.
La fac va donc être bien plus formatrice pour des aptitudes de recherches. Pour la prépa… et bien ça prépare à être ingénieur.
Le problème est qu'on fait 1000x plus de diplômés DEA que de postes de recherche, et que du coup 99.9% des diplômés DEA se retrouver à chercher un travail d'ingénieur. Et ils se plaignent de na pas être aussi bien payés que les ingés ("on est Bac+5 aussi" tout ça...)
Oui, je fais mon péteux d'ingé, mais j'ai eu à recruter des Bac+5, et à travailler avec les deux, est je sais pour quelle raison je paierai moins un DEA qu'un diplôme d'ingé si je devais le refaire : tu le dis toi-même, la Fac met en avant la partie créatrice, la recherche. En entreprise, on veut que ça marche hier, pas dans 10 ans.
[^] # Re: Ingé vers Fac
Posté par seginus . Évalué à 2.
C'est bien ce que je dis la FAC, ça prépare à la recherche :D
[^] # Re: Ingé vers Fac
Posté par Jak . Évalué à 6.
La recherche d'emploi ? :)
[^] # Re: Ingé vers Fac
Posté par Thomas Douillard . Évalué à 3.
[^] # Re: Ingé vers Fac
Posté par FreeB5D . Évalué à 2.
Vive IPoT ;)
[^] # Re: Ingé vers Fac
Posté par 2PetitsVerres . Évalué à 10.
Il y a des ingés chez qui on voit que, même dans dix ans, ça ne marchera pas...
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: Ingé vers Fac
Posté par seginus . Évalué à 1.
Le seul problème est qu'aujourd'hui, il y a bien plus de place pour des ingénieur que pour des chercheurs vu que ce qui compte, c'est la rentabilité à cours terme et de long travaux de recherches théoriques aux résultats incertains, on en veut pas.
Cependant, il me semble qu'à l'origine les nombres complexes sont sortis de l'esprit de chercheur en recherche théorique pur et à la base sans trop d'applications industrielles visibles. Et pourtant maintenant, imaginez bosser sans.
Ce sont les chercheurs qui créent les outils dont se serviront plus tard les ingénieurs.
[^] # Re: Ingé vers Fac
Posté par khivapia . Évalué à 3.
La recherche, même appliquée, ça ne se fait pas du jour au lendemain, on tombe sur une foultitude de petits problèmes qu'il faut régler les uns derrière les autres, ça coûte cher et on ne sait pas trop combien de temps ça prend. Le commercial, lui, sa question c'est plutôt "Est-ce que ce sera prêt pour Noël ?". Ben quand on recherche (même la recherche appliquée, par exemple un objet multimédia avec quelques nouvelles fonctionnalités), on ne sait pas, c'est tout. Il y a comme un hic...
Et encore, ça m'est arrivé de voir pire : la direction commerciale qui demande à la R&D "Ça, on saurait faire ?" R&D "Sans doutes." (mais elle n'a pas encore travaillé dessus).
Conclusion : la direction commerciale répond à un appel d'offre (et dans le matériel électronique, ils ne sont pas petits, et les retards se payent très cher), sans avoir la technologie sous la main encore. Ensuite, la R&D est priée de sortir le truc à l'heure pour que ce soit produit à temps...
[^] # Re: Amusant
Posté par 2PetitsVerres . Évalué à 5.
Je ne suis pas sur que l'université soit là pour former à un métier. Et les premières années de l'université (en tout cas en Belgique, j'ai fait l'université en Belgique et une école d'ingé en France) elles te préparent, tout comme la prépa, aux années suivantes (formation théorique, bases communes en math, physique, chimie, ...)
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: Amusant
Posté par ribwund . Évalué à 5.
C'est relativement récent les formations professionalisantes à la fac.
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 8.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Amusant
Posté par Infernal Quack (site web personnel) . Évalué à 3.
Perso, la prépa prépare surtout à être efficace et polyvalent. Par contre cela ne prépare pas aux Ecole d'Ingé mais aux concours d'entrée dans les Ecoles d'Ingé ce qui est très différents.
Et les Ecoles d'ingé, perso, j'ai plus vu ça comme un complément à la prépa. L'Ecole c'est plus l'ouverture à plein de sujets et le travail en équipe.
L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire
[^] # Re: Amusant
Posté par Zenitram (site web personnel) . Évalué à 2.
Oh que oui... Bien plus qu'un DEA ou un DESS...
Par contre cela ne prépare pas aux Ecole d'Ingé mais aux concours d'entrée dans les Ecoles d'Ingé ce qui est très différents.
On est d'accord sur ce point!
Perso, une fois passé l'exam, il y a eu un reboot de ma mémoire, et la dernière sauvegarde datait de 2 ans... (j'ai fait que 3/2).
[^] # Re: Amusant
Posté par auve . Évalué à 1.
Ça dépend des facs. Ça en dépend même très sévèrement. En informatique, la plupart de celles avec une partie théorique très solide voient malheureusement leurs effectifs s'effriter ces dernières années, et quand je vois le prix que payent en terme de niveau scientifique celles qui continuent à avoir un grand nombre d'étudiants, comme celle qui fut la mienne ces trois dernières années, je me demande si le jeu en vaut la chandelle...
(Ce n'est pas le monsieur à chapeau melon et pipe qui poste ailleurs dans ce journal qui me contredira, on a fait la même fac :-))
[^] # Re: Amusant
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 1.
# Et la soluce svp...
Posté par NickNolte . Évalué à 2.
[^] # Re: Et la soluce svp...
Posté par Snarky . Évalué à 10.
# Anal ou oral ?
Posté par libre Cuauhtémoc . Évalué à -8.
# On est vendredi
Posté par genma (site web personnel) . Évalué à 1.
[^] # Re: On est vendredi
Posté par FreeB5D . Évalué à 0.
Sous Linux, ce serait plutôt vim (encore qu'il y a elvis sous Slackware mais j'ai jamais vu vi autre part) .
<masochiste=on>Ou bien Emacs ?<masochiste=off>
[^] # Re: On est vendredi
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 1.
# La prépa évolue...
Posté par Zenitram (site web personnel) . Évalué à 2.
Ca va vite (car je ne suis pas si vieux)
# Début de solution
Posté par Nénuphare Rose . Évalué à 1.
Alors pour la question 1 vous avez déja trouvé, on avait considéré 1^n.
La question 2 c'est plus dur. En fait il faut trouver des mots pour lesquels on peut trouver la représentation la plus concise, c'est ça qui est psa évident.
On a considéré les préfixes du mot 010011000111000011110000011111... en fait, les préfixes de ce mot qui sont de taille k(k+1) pour que ça s'arrète après une séquence de 1.
A partir de ça il faut montrer que la représentation la plus concise, c'est celle à laquelle on pense naturellement, comme ça on peut exprimer \langle x\rangle avec une somme de log et d'entiers.
En minorant, on peut obtenir une inégalité sqrt(n)< c log(n), pour n=k(k+1) avec k aussi grand qu'on veut donc c'est absurde.
(mais on doit pouvoir considérer d'autres mots, il faut juste trouver des mots pour lesquels on peut minorer la taille de la représentation la plus concise...)
Indice pour la question 3, il faut utiliser le lemme de l'étoile, les mots de la forme u.v^k.w étant bien compressibles...
Pour la question 4 c'est un peu plus compliqué, on verra tout à l'heure. (Mais il faut considérer un automate qui reconnaît le langage et réfléchir avec des mots d'une taille énorme, pour les mots de petites tailles on peut prendre x=y et ajuster la constante à la fin pour que l'inégalité soit vraie.)
# GRRRRRR
Posté par Guillaume Knispel . Évalué à 4.
Donc je m'en tiens aux grandes lignes.
1) Trivial.
2) Par l'absurde. Montrer que si un tel d existait, à partir d'une certaine taille il n'y aurait pas assez de représentation pour couvrir l'ensemble des mots. Où alors si vous connaissez la théorie de l'information, prononcez simplement les mots "théorie de l'information" et passez au 3 avec un grand sourire (cette seconde approche n'est sans doute pas exploitable lors d'un oral, quoique...)
3) a) dans le cas où la longueur des mots de L admet un maximum, balayer le problème d'un revers de la main.
b) pas de max: Prendre un sous ensemble de L qui admet une représentation immédiate avec la notation à base d'exposants. Pour cela choisir arbitrairement une expansion des regex internes et de taille bornées, garder les externes qui peuvent être répétées jusqu'à l'infinie. Poser tous vos exposants variables restants égals entre eux et à n. Calculer la longueur mini d'un mot de votre sous ensemble. Calculer l'incrément de longueur lorsque n augmente de 1. Trouver un c qui fonctionne pour les premières longueurs possible (on ne cherche pas d'optimum, donc faire le bourrin avec les inéquations histoire de gagner du temps) puis démontrer qu'il fonctionne toujours pour toutes les valeurs. Un d qui fonctionne (toujours pas optimal mais on s'en fout) : d = max(longueur min d'un mot dans le sous-ensemble de L choisi, incrément de la longueur quand n augmente de 1)
4) c'est un truc de pervers :) j'ai pas d'idée après au moins 10 min de réflexion.
[^] # Re: GRRRRRR
Posté par Guillaume Knispel . Évalué à 2.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.