summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--programme-inf105.tex15
1 files changed, 9 insertions, 6 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex
index 59b34c0..450ece8 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -115,14 +115,17 @@ grammaire à un DFA ou NFA.
(Selon le temps disponible.) L'appartenance d'un mot au langage
défini par une grammaire hors contexte est algorithmiquement
-décidable. Quelques idées sur l'analyse syntaxique en pratique :
-notion d'analyseurs descendants et ascendants.
+décidable\footnote{Par ex., esquisser comment on peut mettre la
+ grammaire sous forme normale de Chomsky et utiliser l'algorithme de
+ programmation dynamique (CYK) ?}. Quelques notions sur l'analyse
+syntaxique en pratique : notion d'analyseurs descendants et
+ascendants.
\thingy TD sur les grammaires hors contexte.
-\thingy Notions de calculabilité\footnote{Mieux vaut sans doute ne pas
+\thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
perdre de temps à introduire un modèle de calculabilité particulier
(machine de Turing ou fonctions générales récursives, par exemple) :
insister sur le fait que tout langage de programmation raisonnable,
@@ -131,9 +134,9 @@ d'un algorithme, thèse de Church-Turing.
Ensembles/langages\footnote{Souligner qu'ici contrairement au reste du
cours, on peut indifféremment considérer des ensembles d'entiers
- naturels ou de mots.} décidables (=récursifs) et semi-décidables
-(=récursivement énumérables). Notion de machine universelle.
-Indécidabilité du problème de l'arrêt.
+ naturels ou de mots.} décidables (=calculables, =récursifs) et
+semi-décidables (=semi-calculables, =récursivement énumérables).
+Notion de machine universelle. Indécidabilité du problème de l'arrêt.
\thingy TP sur les grammaires hors contexte avec JavaCC.