SIN4U06
UE Langages formels
Unité d'enseignement (UE) de 3 crédits
Langue(s) d'enseignement(s) : Français
DESCRIPTION
ORGANISATION
FORMATIONS
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 à acquérir
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(s) d'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
Volume total: 30 heures
Responsables pédagogiques:
LHOTE Nathan
STEFANINI Marie helene
Codes APOGÉE
SIN4U06L [ELP]
SIN4U06A [ELP]
Les formations qui utilisent cet enseignement
Rechercher...