Derniers contenus

Electrostatique : tout

Courants électriques : seulement j

Tout le chapitre de grammaires est au programme. Rien n'est exigible sur l'analyse syntaxique, mais on pourra proposer des exercices autour de méthode d'analyse syntaxique, avec un peu de guidage. Il faut savoir jouer avec l'ambiguïté d'une grammaire (montrer qu'elle ambiguë, et proposer sans nécessairement de justification formelle une grammaire non-ambiguë qui engendre le même langage, quitte à être guidé). Le plus important est de savoir rédiger des preuves par induction sur les arbres de dérivations des mots, par exemple pour montrer que le langage d'une grammaire est inclus dans un autre langage.

(rédigé rapidement par M. Besson)

Sur le chapitre sur les grammaires.

Tout le chapitre de séparation et évaluation a été fait, on pourra donner des exercices autour de ce thème. Il peut être attendu qu'on demande aux élèves de deviner la fonction d'évaluer à utiliser dans des cas simples. Dans des cas plus complexes, on leur donnera une fonction d'évaluation et on leur demandera de montrer qu'elle fournit bien une borne.

Ceci se couple bien avec le fait de faire montrer la NP-complétude d'un problème de décision associé à un problème d'optimisation au préalable.