v2.11.0 (5776)

Enseignement scientifique & technique - MITRO210 : Automates et données structurées

Domaine > Mathématiques.

Descriptif

Ce cours s'intéresse à des notions avancées de théorie des automates et langages réguliers, et présente un tour d'horizon de leurs connexions avec d'autres disciplines comme l'algorithmique et la logique, ainsi que leurs extensions aux arbres et aux classes structurées de graphe.

Dans un premier temps, le cours se concentre sur les automates de mots, avec notamment des variantes des formalismes d'automates classiques, des notions d'algèbre des semigroupes, et des applications à l'algorithmique du texte.

Dans un second temps, le cours présente le formalisme des automates d'arbres et son lien avec la logique monadique du second ordre, puis étend à la notion de largeur d'arbre et la programmation dynamique sur des décompositions arborescentes de graphes.

24 heures en présentiel (16 blocs ou créneaux)
réparties en:
  • Contrôle de connaissance : 3
  • Cours magistral : 21

Diplôme(s) concerné(s)

Parcours de rattachement

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

Vos modalités d'acquisition :

Examen écrit (note sur 20)

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS
  • Crédit d'UE électives acquis : 2.5

Pour les étudiants du diplôme Echange international non diplomant

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS

Mots clés

automates, semigroupes, langages formels, algorithmique du texte, logique, automates d'arbres, largeur d'arbre, graphes
Veuillez patienter