Reorganize syllabus.

1 files changed, 21 insertions, 25 deletions

diff --git a/programme-inf105.tex b/programme-inf105.tex
index e4ab97a..909924c 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -59,35 +59,36 @@ et notions sur les mots : concaténation de deux mots, longueur d'un
 mot ; préfixe, suffixe, facteur, sous-mot et mot miroir.
 
 Opérations sur les langages : opérations booléennes (complémentaire,
-union, intersection), concaténation, étoile de Kleene.  Définition des
-langages rationnels.  Expressions rationnelles.
+union, intersection), concaténation, étoile de Kleene.
 
+\thingy  Définition des langages rationnels.  Expressions rationnelles.
 
-\thingy Automates finis : automates déterministes (DFA), automates
-déterministes à spécification incomplète, automates non déterministes
-(NFA), automates non déterministes à transitions spontanées
-($\varepsilon$-NFA).
+Automates finis : automates déterministes (DFA), automates
+déterministes à spécification incomplète (DFAi), automates non
+déterministes (NFA), automates non déterministes à transitions
+spontanées ($\varepsilon$-NFA).
 
-Équivalence entre ces différentes sortes d'automates.  Langages
-reconnaissables.
+\thingy Équivalence entre DFA, DFAi, NFA et $\varepsilon$-NFA.
+Langages reconnaissables.
 
-
-\thingy Stabilité des langages reconnaissables par complémentaire,
+Stabilité des langages reconnaissables par complémentaire,
 union, intersection ; stabilité par concaténation et étoile de Kleene.
+
 Les langages rationnels sont reconnaissables.  Automate de Glushkov
 \emph{ou} (au choix) automate de Thompson d'une expression
 rationnelle.
 
-Automates à transitions étiquetées par des expressions rationnelles
+\thingy Automates à transitions étiquetées par des expressions rationnelles
 (informellement), équivalence avec les autres sortes d'automates,
 équivalence avec les expressions rationnelles (par élimination des
 états =algorithme de Kleene).  Équivalence entre langages rationnels
 et reconnaissables.
 
-
-\thingy Énoncé et démonstration du lemme de pompage pour les
+Énoncé et démonstration du lemme de pompage pour les
 langages rationnels (=reconnaissables).
 
+\thingy Exemples d'utilisation du lemme de pompage.
+
 DFA minimal\footnote{On conviendra d'utiliser la notion d'automate
   déterministe \emph{complet}, et la première étape de minimisation
   sera de compléter l'automate en lui ajoutant éventuellement un
@@ -101,25 +102,21 @@ peut décider algorithmiquement si deux expressions rationnelles sont
 \thingy TD sur les automates finis et langages rationnels.
 
 
-\thingy TP sur les expressions régulières et automates finis.
-
-
 \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 de langage
-intrinsèquement ambigu).
+Ambiguïté (grammaires inambiguës et ambiguës, exemple sans
+démonstration de langage intrinsèquement ambigu).
 
-
-\thingy Stabilité des langages algébriques par réunion, concaténation
+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.
 
-L'intersection d'un langage algébrique et d'un langage rationnel est
-algébrique (admis sans démonstration).
+\thingy 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).
@@ -155,10 +152,9 @@ ensemble est décidable ssi lui et son complémentaire sont
 semi-décidables.  Un ensemble est semi-décidable ssi il est (vide ou)
 énuméré par une fonction calculable.
 
-Notion de machine universelle.  Indécidabilité du problème de l'arrêt.
-
+\thingy Notion de machine universelle.  Indécidabilité du problème de l'arrêt.
 
-\thingy TP sur les grammaires hors contexte avec JavaCC.
+Petit TD sur la calculabilité.
 
 
 %