AccueilLicence généraleInformatiqueEnseignementsAutomates et langages

Licence InformatiqueUE Automates et langages

Contenu

Cette unité d'enseignement propose l'étude des automates et des langages qu'ils représentent, tant du point de vue de la modélisation que des algorithmes associés utiles pour traiter automatiquement ces objets.

  • Modélisation par automates finis (déterministes ou non déterministes) et par expressions régulières
  • Algorithmes de recherche de motifs
  • Déterminisation des automates finis - Clôtures booléennes (union, intersection, complémentaire) - Test du vide et équivalence/inclusion de langages
  • Clôtures rationnelles (concaténation, étoile de Kleene) - Théorème de Kleene
  • Minimisation
  • Résiduels et lemme de l'étoile
  • Reconnaissance par monoides
  • Grammaire algébrique (modélisation des expressions arithmétiques) : algorithme de Cocke-Younger-Kasami
  • Automates à pile
  • Evocation de la hiérarchie de Chomsky

Compétences visées

  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement.
  • Rédiger de manière synthétique et rigoureuse des preuves.
  • Être familiarisé avec les concepts fondamentaux de complexité et calculabilité.
  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation.
  • Évaluer la complexité et la correction d’une solution algorithmique.
  • Concevoir le traitement informatisé d’informations de différentes natures, telles que du texte, des images et des nombres.

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

  • Langages formels : calculabilité et complexité : cours et exercices corrigés / Olivier Carton : ISBN 978-2-311-01400-6

Pré-requis recommandés

  • Langage mathématique

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 30 heures
  • Travaux pratiques : 12 heures

Les formations qui utilisent cet enseignement