From ff0541e82e1a6a55fa7e29fa90fed0aa9c35639d Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 4 Nov 2016 17:32:35 +0100
Subject: Slight clarifications on proposed curriculum.
---
programme-inf105.tex | 15 +++++++++------
1 file 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.
--
cgit v1.2.3