SIN4U06
UE Langages formels
Unité d'enseignement (UE) de 3 crédits
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
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
Dernière modification éffectué le 05/12/2022 à 12:51