Revised syllabus for 2022-2023.

1 files changed, 10 insertions, 25 deletions

diff --git a/programme-inf105.tex b/programme-inf105.tex
index 909924c..a65fc55 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -102,39 +102,23 @@ peut décider algorithmiquement si deux expressions rationnelles sont
 \thingy TD sur les automates finis et langages rationnels.
 
 
-\thingy Grammaires hors contexte\footnote{Je propose pour gagner du
-  temps de ne faire que mentionner au passage le fait qu'il existe des
-  grammaires plus générales, sans entrer dans les détails.}, langages
-algébriques (=définis par une grammaire hors contexte).  Dérivations,
-dérivations gauches et droites.  Arbre d'analyse (=de dérivation).
-Ambiguïté (grammaires inambiguës et ambiguës, exemple sans
-démonstration de langage intrinsèquement ambigu).
+\thingy Grammaires hors contexte, langages algébriques (=définis par
+une grammaire hors contexte).  Dérivations\footnote{On pourra même
+  sauter complètement la notion de dérivation et définir le langage
+  engendré par une grammaire à travers les arbres d'analyse.}.  Arbre
+d'analyse (=de dérivation).  Ambiguïté (grammaires inambiguës et
+ambiguës).
 
 Stabilité des langages algébriques par réunion, concaténation
 et étoile de Kleene.  Les langages rationnels sont algébriques :
 d'après ce qu'on vient de dire et directement en associant une
 grammaire à un DFA ou NFA.
 
-\thingy L'intersection d'un langage algébrique et d'un langage
+L'intersection d'un langage algébrique et d'un langage
 rationnel est algébrique (admis sans démonstration).
 
-Lemme de pompage pour les langages algébriques (admis sans
-démonstration, mais on peut esquisser l'idée).
-
 L'appartenance d'un mot au langage défini par une grammaire hors
-contexte est algorithmiquement décidable (l'énoncer et éventuellement
-expliquer une approche possible\footnote{Par ex., en montrant qu'on
-  peut trouver une grammaire monotone équivalente ; ou bien esquisser
-  comment on peut mettre la grammaire sous forme normale de Chomsky et
-  utiliser l'algorithme de programmation dynamique (CYK) ?} si le
-temps le permet).
-
-Selon le temps disponible : quelques notions sur l'analyse syntaxique
-en pratique : notion d'analyseurs descendants et ascendants (sans
-entrer dans les détails).
-
-
-\thingy TD sur les grammaires hors contexte et langages algébriques.
+contexte est algorithmiquement décidable (admis sans démonstration).
 
 
 \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
@@ -154,7 +138,8 @@ semi-décidables.  Un ensemble est semi-décidable ssi il est (vide ou)
 
 \thingy Notion de machine universelle.  Indécidabilité du problème de l'arrêt.
 
-Petit TD sur la calculabilité.
+\thingy TD sur les grammaires hors contexte / langages algébriques, et
+sur la calculabilité.
 
 
 %