Les journaux sont destinés à des informations qui ne sont pas suffisamment intéressantes
pour être validées en dépêche (sinon n'hésitez pas à proposer votre information en
dépêche), qui sont sans rapport avec Linux ou le libre, ou simplement pour donner votre
avis. Si vous désirez poser une question, merci d'utiliser Journal : Oral d'informatique
Posté par Nénuphare Rose () le 17 juillet 2008concours, 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 !
> Lire le journal (47 commentaires, moyenne: 2,6).
arf un 3/2
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 mats (page perso, ) le 17/07/2008 à 23:34. (lien). É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 chicha () le 18/07/2008 à 09:57. (lien). É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
1 et 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 Axioplase Ashi (page perso, ) le 18/07/2008 à 08:40. (lien). É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 Ontologia (page perso, ) le 18/07/2008 à 10:49. (lien). É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 ;)-
[^]Re: 1 et 2
Posté par Nénuphare Rose () le 18/07/2008 à 10:59. (lien). É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 Ontologia (page perso, ) le 18/07/2008 à 11:15. (lien). É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 ?-
[^]Re: 1 et 2
Posté par Nénuphare Rose () le 18/07/2008 à 11:22. (lien). É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 Aldoo (Jabber id, ) le 18/07/2008 à 13:43. (lien). É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 Zenitram (page perso, ) le 18/07/2008 à 12:50. (lien). É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
-
-
-
-
-
-
[^]Re: 1 et 2
Posté par Thierry Boudet (page perso, ) le 18/07/2008 à 10:01. (lien). É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
-
-
[+] [^]Re: 1 et 2
Posté par PuRPLeHaZe () le 18/07/2008 à 11:05. (lien). É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
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.
-
[^]Re: Amusant
Posté par Infernal Quack (Jabber id, page perso, ) le 18/07/2008 à 00:39. (lien). Évalué à 9.Juste après une prépa alors parce qu'après on oublie vite...très très vite même :)
-
[^]Re: Amusant
Posté par seginus () le 18/07/2008 à 08:10. (lien). É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 Zenitram (page perso, ) le 18/07/2008 à 09:26. (lien). É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 seginus () le 18/07/2008 à 09:54. (lien). É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 rewind () le 18/07/2008 à 10:05. (lien). É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 Zenitram (page perso, ) le 18/07/2008 à 10:57. (lien). É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 seginus () le 18/07/2008 à 12:38. (lien). É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 Jak () le 18/07/2008 à 15:46. (lien). Évalué à 6.> C'est bien ce que je dis la FAC, ça prépare à la recherche :D
La recherche d'emploi ? :)--
« Le savoir, n'est-ce pas, est un bien précieux. Trop précieux pour ne pas être partagé. »
- Battologio d'Epanalepse, in De Cape et de Crocs, Acte VII (Ayroles & Masbou)-
[^]Re: Ingé vers Fac
Posté par Thomas Douillard () le 18/07/2008 à 15:54. (lien). É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
-
[^]Re: Ingé vers Fac
Posté par 2PetitsVerres () le 18/07/2008 à 17:58. (lien). É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...
-
[^]Re: Ingé vers Fac
Posté par seginus () le 18/07/2008 à 19:38. (lien). É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 khivapia () le 18/07/2008 à 21:24. (lien). É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 2PetitsVerres () le 18/07/2008 à 10:05. (lien). É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, ...)-
[^]Re: Amusant
Posté par ribwund () le 18/07/2008 à 10:14. (lien). É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.-
[^]Re: Amusant
Posté par alenvers () le 18/07/2008 à 13:54. (lien). Évalué à 8.>la fac c'est principalement de la transmission de savoir,
Je suis entièrement d'accord :
https://linuxfr.org//comments/364179.html#364179
Re: aah ! les écoles d'ingénieurs !
Posté par alenvers (envoyer un message privé) le 08/03/2004 à 10:08. (lien). Évalué à 5.
Il ne faut pas oublier qu'on ne va pas à l'université/école sup pour apprendre à utiliser tel ou tel produit ou encore apprendre un métier.
On y va pour acquérir des connaissances, être capable de les maitriser et éventuellement d'en creer des nouvelles (ou en avoir la capacité).
Quand j'étais à l'univ., on a appris un premier langage Pascal en première. Mais beaucoup plus important, on a aussi appris à d'écrire des algorithmes dans des langages informels ce qui permet de penser indépendament de tout langage. En 2ème, on a appris un paquets langages en 4 mois (C, C++, java, ada, dephi, cobol, fortran et j'en oublie surement). Après c'était plutot, voila le projet vous avez 3 semaines et vous le faite dans tel langage inconu au bataillon.
Le pillier central de l'informatique pour moi c'est l'algorithmique. Le reste n'est qu'outils : Math, langages (c'est un peu l'histoire de l'oeuf et la poule), Matos, méthodologie... Tout cursus qui se prétend être un cursus informatique doit être dans cette optique. On utilise des outils pour produire des algorithmes exprimmé dans des langages sur du matos pour résoudre un problème.
Pour ce qui est du boulot, quand on me demande si je connais tel langages/produits, je dit : "oui, mais il faut que je me rafraichisse un peu la mémoire". C'est terrible ce qu'un décideur pense qu'il est compliqué d'apprender un langage, un produit. Quand on a les concepts théoriques déja assimilés c'est tellement simple et rapide...
-
-
-
[^]Re: Amusant
Posté par Infernal Quack (Jabber id, page perso, ) le 18/07/2008 à 10:48. (lien). É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.-
[^]Re: Amusant
Posté par Zenitram (page perso, ) le 18/07/2008 à 10:59. (lien). É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 auve () le 18/07/2008 à 13:23. (lien). É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 Axioplase Ashi (page perso, ) le 18/07/2008 à 08:42. (lien). Évalué à 1.Sauf quand on est accepté, justement :D
-
[+] Anal ou oral ?
On est vendredi
On voit clairement que c'est Latex qui a été utilisé pour le pdf, mais avec quel éditeur de texte? Vi, non?
"Le jour où tu découvres le Libre, tu sais que tu ne pourras jamais plus revenir en arrière..."
-
[^]Re: On est vendredi
Posté par FreeB5D () le 18/07/2008 à 17:51. (lien). Évalué à 0."Vi, non?"
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>--
Linux çapu, mais quand Windows est concerné Linux c'est génial .-
[^]Re: On est vendredi
Posté par Axioplase Ashi (page perso, ) le 19/07/2008 à 07:08. (lien). Évalué à 1.Sous pas mal de BSD, par défaut, t'as vi.
-
La prépa évolue...
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
(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
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.
-
[^]Re: GRRRRRR
Posté par Guillaume Knispel () le 18/07/2008 à 21:50. (lien). Évalué à 2.Après avoir lu le commentaire https://linuxfr.org/comments/950880.html#950880, effectivement pour le 3) pas besoin de se prendre la tête autant que moi si on connaît le lemme de l'étoile. Je connaissait pas :/ (ou alors j'ai oublié :// )
Cette page a été générée par Templeet en 0.1494s (dont 0.014 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Faire un don !
Cette discussion est archivée, il n'est plus possible de laisser des commentaires.
Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.