diff options
| author | David A. Madore <david+git@madore.org> | 2017-01-30 17:29:22 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2017-01-30 17:29:22 +0100 |
| commit | 834717ef2c2ed8eb7c9c7384db92843257312b8b (patch) | |
| tree | 787d206b3277bced53bbd6beef9bd3c3737347e8 | |
| parent | a06f5fa43d0fc4b7e7663bc7fa370796209627cd (diff) | |
| download | inf105-834717ef2c2ed8eb7c9c7384db92843257312b8b.tar.gz inf105-834717ef2c2ed8eb7c9c7384db92843257312b8b.tar.bz2 inf105-834717ef2c2ed8eb7c9c7384db92843257312b8b.zip | |
Clarifications on curriculum.
| -rw-r--r-- | programme-inf105.tex | 21 |
1 files changed, 12 insertions, 9 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex index f6ae6d8..078715b 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -74,12 +74,14 @@ reconnaissables. \thingy Stabilité des langages reconnaissables par complémentaire, union, intersection ; stabilité par concaténation et étoile de Kleene. -Les langages rationnels sont reconnaissables. Automate de Thompson. +Les langages rationnels sont reconnaissables. Automate de Thompson +d'une expression rationnelle. 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). Équivalence entre langages rationnels et reconnaissables. +états =algorithme de Kleene). Équivalence entre langages rationnels +et reconnaissables. \thingy Énoncé et démonstration du lemme de pompage pour les @@ -91,7 +93,7 @@ DFA minimal\footnote{On conviendra d'utiliser la notion d'automate puits.} (=canonique). Algorithme de minimisation. -\thingy TD sur les automates finis. +\thingy TD sur les automates finis et langages rationnels. \thingy TP sur les expressions régulières et automates finis. @@ -118,14 +120,15 @@ algébrique (admis sans démonstration). (Selon le temps disponible.) L'appartenance d'un mot au langage défini par une grammaire hors contexte est algorithmiquement -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. +décidable\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) ?}. 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. +\thingy TD sur les grammaires hors contexte et langages algébriques. \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas |