 | | |
| INFO0213-2 | Automates et langages formels
|
|
| Durée : | 30h Th, 10h Pr, 20h TD |
|
| Nombre de crédits : |
| Master en sciences mathématiques, à finalité approfondie, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité didactique, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en gestion, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en statistiques, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée, 1re année | | Premier quadrimestre | | 8 |
|
| Master en sciences mathématiques | | Premier quadrimestre | | 8 |
|
|
|
| Nom du professeur : | Michel Rigo |
|
Langue(s) du cours :
|
| Langue française |
|
Contenus du cours :
|
| On présente quelques notions fondamentales de la théorie des langages formels et de combinatoire des mots. Le cours débute par quelques résultats classiques en combinatoire des mots finis et infinis (mots engendrés par morphisme itéré, topologie sur les mots infinis, mot de Thue-Morse sans chevauchement,...). Ensuite, on étudie les langages réguliers et algébriques en insistant sur les aspects théoriques fondamentaux et les structures algébriques sous-jacentes, mais aussi algorithmiques (automate fini, théorie de l'automate minimal, fonction de croissance, monoïde syntaxique, automate à pile). Ces concepts trouvent en particulier de nombreuses applications en informatique (théorique) comme par exemple l'analyse syntaxique, la vérification ou encore la compilation mais aussi en mathématiques : systèmes de numération et théorie des nombres, logique, théorie des graphes, combinatoire, ... |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| Au terme de ce cours, l'étudiant maîtrisera les principaux concepts issus de la combinatoire des mots et de la théorie des langages formels. L'étudiant disposera d'un ensemble de résultats théoriques pour lesquels il sera capable d'en fournir des preuves, le plus souvent constructives. En particulier, ceci lui permettra de fournir des expressions régulières respectant un critère syntaxique donné, construire des automates finis déterministes ou non, obtenir l'automate minimal d'un langage donné, expliciter la congruence de Nerode et le monoïde syntaxique d'un langage, minimiser des automates, décider si un langage régulier est sans étoile. En outre l'étudiant sera capable d'exploiter des théorèmes de stabilité ou de gonflement pour prouver la (non)-régularité d'un langage. Il/elle sera à même d'étudier la fonction de croissance (ou de complexité) d'un langage et d'en tirer des renseignements asymptotiques. Pour les langages algébriques, l'étudiant sera capable de construire des grammaires hors contexte, des arbres de dérivation, tirer parti du théorème de Parikh, appréhender les ensembles semi-linéaires, mettre une grammaire sous diverses formes normales (en particulier, la forme normale de Chomsky), contruire des automates à pile, démontrer et utiliser le théorème de Chomsky-Schützenberger. Enfin, les outils acquis doivent pouvoir être appliqués en algorithmique du texte ou en compilation, mais aussi en arithmétique par l'intermédiaire des systèmes de numération. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Notions élémentaires vues dans les cours d'algèbre linéaire, de théorie des graphes, de calculabilité et de théorie des groupes. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Le cours est consacré principalement aux aspects théoriques des langages formels. Les séances de répétition permettent de présenter la résolution d'exercices mais surtout l'illustration et la concrétisation des concepts vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. La réalisation de travaux personnels en cours d'année peut être envisagée. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Des notes de cours seront distribuées aux étudiants lors du premier cours. Elles sont aussi téléchargeables sur http://www.discmath.ulg.ac.be/ (http://) |
|
Modalités d'évaluation et critères :
|
| L'examen en session comporte une partie orale (énoncés et preuves de résultats, avec discussion) et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. La cote finale pourra également prendre en compte les travaux personnels. |
|
Remarques organisationnelles :
|
| Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ |
|
Contacts :
|
| M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
|
|
| Notes en ligne : |
|
| Notes de cours |
| Syllabus (théorie et énoncés d'exercices) |
|
|
|
| |
