AccueilLicence généraleInformatiqueEnseignementsLangages formels

Licence InformatiqueUE Langages formels

Contenu

  • Expressions régulières, langages rationnels
  • Clôture rationnelle des AFN (concaténation, étoile de Kleene)
  • Théorème de Kleene
  • Résiduels, automate canonique et lemme de l'étoile
  • Grammaire algébrique (modélisation des expressions arithmétiques) - algorithme CYK
  • 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

  • Automates finis

Volume des enseignements

  • Cours magistraux : 9 heures
  • Travaux dirigés : 15 heures
  • Travaux pratiques : 6 heures

Les formations qui utilisent cet enseignement