info205 - Automates et Langages

Nombre de crédits

5

Pré-requis

Aucun

Parcours

• obligatoire pour la mention informatique de la licence
• proposée pour le parcours « Mathématique »

Objectifs

Apprendre des démarches d'abstraction et de formalisation pour la conception et l'analyse de systèmes à travers l'étude de trois modèles de calculs : un modèle de machine à mémoire bornée, un modèle de description et d'analyse syntaxiques et un modèle général de calcul (les machines de Turing).

Organisation

semaine

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (2h)

×

×

×

×

×

Volume de travail personnel étudiant estimé

environ 50h

Contrôle et validation des connaissances

• pour les UE sans TP : sup ( Ex, (2Ex + CC)/3)
• pour les UE avec TP obligatoires : (2TP + 3 sup(Ex, (2Ex + CC)/3))/5

Description du contenu

• Automates finis et expressions régulières : Opérations et algorithmes sur les automates. Déterminisation. Minimisation. Théorème de Kleene. Applications : Recherche de motif, modélisation de systèmes, analyse lexicale.
• Introduction aux grammaires non contextuelles : Notions de dérivation, d'arbre de dérivation, d'ambiguïté dans les grammaires algébriques. Grammaires régulières. Application : Conception de grammaires pour des langages typiques. Grammaires XML.
• Machines de Turing et calculabilité : Définition des machines de Turing. Notions de configurations et calculs. Calculabilité. Décidabilité. Application : Comprendre les limites de l'informatique. Indécidabilité de l'arrêt des programmes. Indécidabilité d'autres problèmes, en particulier sur les mots et les grammaires algébriques

Responsable(s)

Yves Roos

fichier source pour édition/modification