Site des Oraux

Théorie des langages et de la compilation 2005 (1) :: post
Années :: Toutes

Post nº1 (id992) envoyé par arnaud  le 16 May 2005, 15:27
Bien que ce ne soit plus d'actualité cette année, je mets toujours un compte-rendu de qq oraux ici (www.cerkinfo.be). On ne sait jamais qu'il change d'avis d'ici une session ou deux.

Ps: Sur ce lien il y a aussi des cours pirates qui ont pas l'air mal du tout: http://www.cerkinfo.be/cours/licence.php

--------------------------
Conseils pour Th‚orie des langages/T.Massart !!!!!
--------------------------------------------------

L'examen se d‚roule de la fa‡on suivante:

20 minutes de pr‚paration sur tableau AVEC le syllabus de Massart (SON exemplaire !!!!!)

AprŠs il vient voir... il suffit alors d'exposer la question.
Ensuite sans les notes, il pose quelques petites questions et petites d‚monstrations (genre culture g‚n‚rale pour voir si on a compris kekchose au cours !!!)

Il n'est pas si m‚chant pour la cotation...

Exemples de questions principales

- Machine Turing: montrer que Le n'est pas r‚cursif le nec plus ultra c'est de faire toutes les d‚monstrations … partir de Ld (compris) --> donc 1 dem par diagonalisation pour Ld, 1 par r‚duction pour Lu et pour finir une r‚duction pour Le .....(c'est dans le cours et dans les notes prises aux cours (Lu...)) Le tout c'est d'un peu enrichir la version du cours, histoire de montrer qu'on a pig‚ .....

Ne pas oublier de pr‚ciser qu'on fait des raisonnements par l'absurde !!!!!

- Grammaires recu … droite: ‚liminer recu … droite et faire d‚monstration pour prouver qu'on peut faire ‡… ....

- Delta(p,aw) plut“t que Delta(p,wa) : d‚finir, d‚montrer .....

- Trouver 2 d‚monstrations dans le cours o— contradictions .....

- Imaginez un algorithme qui minimise le nombre de non terminaux dans une grammaire. Id‚e: algo sur graphe (de d‚rivation), supprimer cycles ....

........

Exemples petites questions th‚oriques:

- qu'est-ce qu'un pr‚ordre ?? -> rel r‚flexive, transitive
qu'est-ce qu'une ‚quivalence ?? rel r‚fl, trans, sym‚trique
montrez que si R est un pr‚ordre alors R inter R^(-1) est une ‚quivalence
suffit d'utiliser les d‚finitions et d‚velopper et on voit ....

- qu'est-ce qu'une d‚rivation ? montrez lui une d‚riv … gauche par ex....

- pumping lemma sur ensemble de fini string -> r‚gulier.
hyp fausse donc conclusion vraie !!!!
........


R‚f‚rences:

-syllabus T.Massart
-Introduction to Automata Theory, Languages and Computation
John E.Hopcroft
Jeffrey D.Ullman

-> excellent !!!! r‚f du cours (on y trouve mˆme les calculs qui sont pas dans les notes (du genre la d‚m Lnr pour les mach de Turing !!!)

il doit y avoir un exemplaire au cercle... ou du moins … la biblio info ...


------------------------------------------------------------------------------

Voil….... c'est pas un tuyau mais juste de quoi vous donner des id‚es ....

A quand les tuyaux pour Florine ??????? euh ben en fait ....


oraux.pnzone.net - infos - 40ms