Aux étudiants de la deuxième année, nous proposons ce module d'informatique fondamentale. Il est centré autour de l'étude des aspects mathématiques des langages. En passant par la définition des systèmes générateurs (grammaires) et reconnaisseurs (automates) de certains classes de langages (Hiérarchie de Chomsky), nous y prouvons également les principales propriétés d'équivalence (Kleene) et de fermeture. Cette théorie est indispensable à tout informaticien. Elle trouve des applications dans divers domaines (synthèse de circuits, vérifications de protocoles, recherche de motifs, différentes phases d'analyse dans les compilateurs, etc.)
Teacher: Slimane Oulad-Naoui
Teacher: Slimane Oulad-Naoui
----------------------------------------------
Présentation de la matière File
Volume + Évaluation
Plan & références
----------------------------------------------
Rappel File
Rappel de qlq notions élémentaires en Math.
Ensembles, relations, fonctions, logique
Graphes, Schémas de preuves
----------------------------------------------
Introduction aux langages
Alphabet et mots
Langages
Grammaires
----------------------------------------------
Langages réguliers
Automates finis déterministes
Automates finis non déterministes
Automates finis non déterministes avec epsilon-transitions File
Expressions régulières (rationnelles) File
Langages réguliers (reconnaissables) et théorème de kleene File
Propriétés de fermeture des langages réguliers et lemme de pompage
Minimisation
Vous pouvez signaler n’importe quel lien cassé