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.
# GRRRRRR
Posté par Guillaume Knispel . En réponse au journal Oral d'informatique. É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.