From ff0541e82e1a6a55fa7e29fa90fed0aa9c35639d Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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