 | | |
| MATH0470-1 | Combinatoire des mots
|
|
| Durée : | 30h Th, 10h Pr, 20h TD |
|
| Nombre de crédits : |
|
|
| Nom du professeur : | Michel Rigo |
|
Langue(s) du cours :
|
| Langue française |
|
Organisation et évaluation :
|
| Enseignement durant l'année complète |
|
Contenus du cours :
|
| D'une manière générale, la combinatoire est la branche des mathématiques qui étudie les "configurations" d'un ensemble "discret" (et généralement fini). On s'intéresse alors au dénombrement ou à l'énumération effective des objets de cet ensemble, à la structure (éventuellement algébrique) de celui-ci ou encore à ses propriétés extrémales (éléments maximaux, ...). Comme son nom l'indique, la combinatoire des mots s'intéresse plus spécialement aux mots (finis ou infinis), i.e., aux suites de symboles ou de lettres appartenant à un alphabet fini. En guise d'illustration, énonçons un résultat typique de cette branche, le théorème de Morse-Hedlund : un mot infini indexé par N est ultimement périodique (périodique à partir d'un certain rang) si et seulement si la fonction p(n) comptant le nombre de facteurs de taille n présents dans ce mot est bornée par une constante. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| L'objectif principal est de préparer les étudiants à aborder au mieux certaines questions de la recherche
actuelle en mathématiques discrètes ou en informatique théorique. Les problèmes liés à la représentation des nombres et au caractère reconnaissable (par automate fini) des ensembles correspondants servent alors de support à la présentation de certains concepts de combinatoire des mots. A titre indicatif et sans être exhaustif, voici divers thèmes qui pourront être abordés au cours : numération en base entière et ensembles reconnaissables d'entiers (lacunes bornées, syndéticité, ...), premières propriétés des mots infinis (caractère périodique, récurrent,...), théorème(s) de Cobham, suites p-automatiques (noyau, fibre, problème de Prouhet, ...), mots morphiques (i.e., suites engendrées par morphisme itéré), normalisation, ensembles définissables dans l'arithmétique de Presburger étendue, rudiments de bêta-numération (bêta-shift, théorème de Bertrand-Schmidt, nombres de Parry,...), numérations linéaires (théorèmes de Shallit, Hollander, Hansel, ...), nombres de Pisot et numérations associées (numérations de Bertrand), mots de retour, suites sturmiennes et fractions continues, liens avec la géométrie discrète, ...
Au terme de ce cours, l'étudiant devra avoir acquis une autonomie suffisante pour adopter une posture de chercheur en mathématique. Il sera à même de synthétiser un thème actuel de recherche donné, de produire un document (article et/ou exposé) s'y rapportant et d'évoquer des perspectives de travaux. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Une connaissance de base en théorie des automates et en théorie des langages formels est nécessaire (par exemple, avoir suivi avec fruit INFO0213-2 "Automates et langages formels"). Des connaissances en théorie des graphes et en calculabilité ainsi que des rudiments en théorie des nombres peuvent s'avérer utiles mais ne sont pas indispensables. |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| Lecture d'articles de recherche et d'ouvrages de référence, participation active et passive à des séminaires, cours "sur mesure". |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Ce cours, préparant à la recherche, nécessite une participation active de l'étudiant. Pour s'approprier au mieux les concepts, le tutorat, le travail personnel et les présentations orales réalisées par les étudiants seront mises en avant. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Livres de référence :
- M. Rigo, Formal languages, automata and numeration systems, vol. 1, Introduction to combinatorics on words, ISTE-Wiley (2014).
- M. Rigo, Formal languages, automata and numeration systems, vol. 1, Applications to recognizability and decidability, ISTE-Wiley (2014).
Ce cours se base essentiellement sur une sélection d'articles de recherche et d'ouvrages scientifiques. Quelques exemples :
- M. Lothaire, Combinatorics on words, Cambridge University Press (1997).
- M. Lothaire, Algebraic combinatorics on words, Cambridge University Press (2002).
- V. Berthé, M. Rigo (Eds.), Combinatorics, Automata and Number Theory, Cambridge University Press (2010).
- J. Sakarovitch, Elements de théorie des automates, Vuibert (2003)
- V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. (1994).
- J.-P. Allouche, J. Shallit, Automatic sequences, Theory and applications, Cambridge University Press (2003).
- Thomas S. Ferguson, Game Theory, UCLA.
- J. Shallit, A second course in formal languages and automata theory, Cambridge University Press (2008).
- E. Bach, J. Shallit,Algorithmic Number Theory, volume 1: efficient algorithms, MIT Press (1996).
- A. de Luca, S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer (1999).
|
|
Modalités d'évaluation et critères :
|
| Les travaux réalisés durant l'année académique (présentations orales, discussions, rapports, résolutions d'exercices, ...) interviendront en grande partie dans la cote finale de l'examen. L'examen en session est composé d'un exposé (sur un thème défini au préalable) et d'une interrogation orale sur une partie limité du cours et ses applications directes (on pourra par exemple demander de résoudre au tableau un petit exercice). |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| |
|
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 |
|
|
| |
