Durée
30h Th, 20h Pr
Nombre de crédits
| Bachelier en sciences mathématiques | 5 crédits |
Enseignant
Langue(s) de l'unité d'enseignement
Langue française
Organisation et évaluation
Enseignement au premier quadrimestre, examen en janvier
Horaire
Unités d'enseignement prérequises et corequises
Les unités prérequises ou corequises sont présentées au sein de chaque programme
Contenus de l'unité d'enseignement
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) de l'unité d'enseignement
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.
Savoirs et compétences prérequis
Notions élémentaires vues dans les cours d'algèbre linéaire et de théorie des groupes. Avoir suivi des cours de théorie des graphes et/ou de calculabilité est un atout (mais n'est pas nécessaire).
Activités d'apprentissage prévues et méthodes d'enseignement
Cours théorique avec "tableau et craies" ou projection, en interaction avec les étudiants. Dans les séances d'exercices, les étudiants pourront être face à des exercices qu'ils doivent résoudre.
Mode d'enseignement (présentiel, à distance, hybride)
Combinaison d'activités d'apprentissage en présentiel et en distanciel
Explications complémentaires:
Le cours est consacré principalement aux aspects théoriques. Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou 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.
Le cours théorique sere donné en présenciel. Le cas échéant, certaines parties de matière pourront être dispensées sous forme de vidéos à regarder (podcasts).
Les séances d'exercices contiendront une partie de travail personnel à réaliser à domicile.
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/
Les notes de cours sont suffisantes. Quelques compléments pour approfondir :
- J. Sakarovitch, Elements de théorie des automates, Vuibert, Paris, (2003).
- T. A. Sudkamp, Languages and Machines, An Introduction to the Theory of Computer Science, second edition, Addison-Wesley (1997).
- J. Berstel, D. Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007).
- J. Shallit, A second course in formal languages and automata theory, Cambridge Univ. Press (2008).
- A. Mateescu, A. Salomaa, Formal Languages: an Introduction and a Synopsis, Handbook of Formal Languages, vol. 1, Springer, (1997).
- S. Yu, Regular Languages, Handbook of Formal Languagues, vol. 1, Springer, (1997).
- D. Perrin, Les débuts de la théorie des automates, Technique et Science Informatique14 (1995).
- G. Lallement, D. Perrin, Marcel-Paul Schützenberger (1920-1996), Semigroup Forum55 (1997).
- J.-M. Autebert, Langages algébriques, études et recherches en informatique, Masson (1987).
Modalités d'évaluation et critères
Toutes sessions confondues :
- En présentiel
évaluation écrite ( questions ouvertes ) ET évaluation orale
- En distanciel
évaluation écrite ( questions ouvertes )
- Si évaluation en "hybride"
préférence en présentiel
Explications complémentaires:
L'examen, en session, comporte une partie orale et une partie écrite. L'examen oral porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau ou sur feuille un petit exercice). L'examen écrit porte sur la matière des répétitions.
En cas d'impossibilité de faire l'examen en présentiel, celui-ci consistera en un examen écrit unique contenant des questions de théorie et d'exercice ou application de la théorie.
Stage(s)
Remarques organisationnelles et modifications principales apportées au cours
Contacts
J. Leroy, Institut de Mathématique (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 - E-mail : j.leroy@uliege.be