Journal Oral d'informatique

Posté par  .
Étiquettes : aucune
0
18
juil.
2008
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 !
  • # arf un 3/2

    Posté par  (site web personnel) . Évalué à 4.

    tu nous diras si tu décides de replonger pour 5/2 ?
    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  . Évalué à 4.

      Bin moi je lui souhaite plutôt de ne pas avoir à faire 5/2.
      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  . Évalué à 4.

        Ben moi j'ai adoré être 5/2 ...

        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  . Évalué à 0.

      ou est le problème certains c'est 6h20 le 14 juillet
  • # 1 et 2

    Posté par  . Évalué à 2.

    Pour 1:
    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  (site web personnel) . Évalué à 1.

      1/ par induction sur la taille du mot et listage exhaustif des "petits" mots, tu dois pouvoir montrer ça., non ?

      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  (site web personnel) . Évalué à 1.

        Pareil, un peu embêté pour le 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  . Évalué à 1.

          Les cas n=0 et n=1 sont pas très interessants, c'est vrai que log(1) et log(0) ça marche pas top mais on avait même pas regardé ça pendant l'oral (peut-être que dans l'énoncé réel c'était n>=2 d'ailleurs...)
          • [^] # Re: 1 et 2

            Posté par  (site web personnel) . Évalué à 1.

            C'est pas la première fois que j'ai des doutes sur un énoncé de ce genre. C'est d'ailleurs ce qui m'a toujours dérangé en maths, des fois ça à l'air de manquer de rigueur, ce qui est quand même très étonnant pour l'ENS.

            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  . Évalué à 1.

              Ca c'est le sujet que j'ai tappé moi même, de mémoire après l'oral, ce n'est pas celui que j'avais sous les yeux lors de l'oral... Donc c'est moi qui manque de rigueur ;o

              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  . Évalué à 2.

                Il me semble que l’esprit ENS, ce sont les sujets ouverts. Si la consigne mérite d'être précisée et que le candidat le voit, le dialogue qui peut s'engager sera alors très bien vu par l'examinateur.
                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  (site web personnel) . Évalué à 0.

              Les profs de math que j'avais en prépa étaient capable de faire la démonstration en moins de 10s dans leur tête (ils ont l'habitude :) )
              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  . Évalué à 1.

                J’aimais bien aussi le coup des 5/2 qui répondaient avant que l’énoncé ne soit écrit entièrement. Impressionnant, vu le nombre d’énoncés différents qui existent !
    • [^] # Re: 1 et 2

      Posté par  (Mastodon) . Évalué à 4.

      on peut compresser à l'infini (le truc classique de la compression que compresse toujours de au moins 1 bit).

      Bravo, tu viens de réinventer I2BP !
      • [^] # Re: 1 et 2

        Posté par  . Évalué à 3.

        Au cas où c'était pas clair, c'était une preuve par l'absurde ;)
    • [^] # Re: 1 et 2

      Posté par  . Évalué à -1.

      Moi je suis bloqué à la première question :D

      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  . Évalué à 6.

    C'est assez rigolo à lire comme énoncé.
    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  (site web personnel) . Évalué à 9.

      Juste après une prépa alors parce qu'après on oublie vite...très très vite même :)

      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  . Évalué à 1.

        Je confirme. Pas par le cursus prépa, mais par la seule école véritablement formatrice, je veux bien sûr parlé de l'Université.

        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  (site web personnel) . Évalué à 3.

          Je confirme. Pas par le cursus prépa, mais par la seule école véritablement formatrice, je veux bien sûr parléer de l'Université.

          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  . Évalué à 1.

            Je vois pas la différence au même endroit pour la fac / prépa (disont fac prépa + ingé)
            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  (Mastodon) . Évalué à 3.

              La prépa ne développe pas l'apprentissage brut puisqu'on oublie tout une fois les oraux de concours terminés. Pour moi, la prépa développe surtout l'efficacité dans l'apprentissage et développe un schéma de pensée adaptable à n'importe quel savoir. Un niveau meta d'apprentissage en quelque sorte. Ensuite, ça peut servir aussi bien à être ingénieur que dans la recherche (beaucoup de chercheurs ont fait prépa).
            • [^] # Ingé vers Fac

              Posté par  (site web personnel) . Évalué à 3.

              Je vois pas la différence au même endroit pour la fac / prépa (disont fac prépa + ingé)

              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  . Évalué à 2.

                « 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 »

                C'est bien ce que je dis la FAC, ça prépare à la recherche :D
                • [^] # Re: Ingé vers Fac

                  Posté par  . Évalué à 6.

                  > C'est bien ce que je dis la FAC, ça prépare à la recherche :D

                  La recherche d'emploi ? :)
                  • [^] # Re: Ingé vers Fac

                    Posté par  . Évalué à 3.

                    Ça mène à la recherche d'emploi, dans la plupart des cas, mais ça n'y prépare pas plus que ça en soit, justement ;)
              • [^] # Re: Ingé vers Fac

                Posté par  . Évalué à 2.

                "En entreprise, on veut que ça marche hier, pas dans 10 ans."
                Vive IPoT ;)
              • [^] # Re: Ingé vers Fac

                Posté par  . Évalué à 10.

                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.
                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  . Évalué à 1.

                Ton exemple le montre aussi, en entreprise c'est l'ingénieur qui sera le mieux formé. Dans un institue de recherche comme le CNRS et le CERN, ce sera sans doute le contraire et ils iront je pense plus prendre un DEA qu'un diplômé d'ingé.

                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  . Évalué à 3.

                  À mon avis ce n'est pas tant les grandes théories qui n'ont pas d'application pratiques immédiates qui sont le problème (c'est plutôt le travail de fond des instituts de recherche publics/universités, et de quelques grandes boîtes), mais plutôt l'interaction entre R&D et direction commerciale, en lien en effet avec la pression de la rentabilité.

                  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  . Évalué à 5.

            l'Université a pour but de te former à un métier
            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  . Évalué à 5.

              Oui il me semble que à la base, la fac c'est principalement de la transmission de savoir, ça ne préparait pas spécialement à un métier même si c'était plutot adapté pour les profs et les chercheurs.
              C'est relativement récent les formations professionalisantes à la fac.
              • [^] # Commentaire supprimé

                Posté par  . Évalué à 8.

                Ce commentaire a été supprimé par l’équipe de modération.

          • [^] # Re: Amusant

            Posté par  (site web personnel) . Évalué à 3.

            L'Ecole d'Ingé forme à un métier ? Ah bon ?

            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  (site web personnel) . Évalué à 2.

              L'Ecole d'Ingé forme à un métier ? Ah bon ?

              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  . Évalué à 1.

            Beaucoup trop théorique, beaucoup

            Ç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  (site web personnel) . Évalué à 1.

        Sauf quand on est accepté, justement :D
  • # Et la soluce svp...

    Posté par  . Évalué à 2.

    Merci
  • # Anal ou oral ?

    Posté par  . Évalué à -8.

    Y'a pas d'anal pour l'oral ?
  • # On est vendredi

    Posté par  (site web personnel) . Évalué à 1.

    On voit clairement que c'est Latex qui a été utilisé pour le pdf, mais avec quel éditeur de texte? Vi, non?
  • # La prépa évolue...

    Posté par  (site web personnel) . Évalué à 2.

    A mon époque (putain le vieux...), l'informatique était un mot inconnu des profs de prépa!
    Ca va vite (car je ne suis pas si vieux)
  • # Début de solution

    Posté par  . Évalué à 1.

    (Attention quand on dit que |x| c'est la taille du mot x c'est le nombre de lettres ! pas le log du nombre de lettre.)


    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  . Évalué à 4.

    J'avais posté quelques détails pour les 1, 2 et 3 mais Templeet m'a chié une erreur SQL :/ snif.

    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.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.