 | |
| MATH0470-1 | Combinatoire des mots
 |
|
| Durée : | 30h Th, 10h Pr, 20h TD |
|
| Crédits/ECTS : |
|
|
| Titulaire(s) : | Michel Rigo |
|
| Langue : | Langue française |
|
| Aperçu général : | 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. |
|
| Objectif 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, ... |
|
| Pré-requis : | 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. |
|
| Organisation : | Ce cours, préparant à la recherche, nécessite une participation active de l'étudiant. Pour s'approprier au mieux les concepts, le travail personnel et les présentations orales réalisées par les étudiants seront mises en avant. |
|
| Notes de cours : | Ce cours se base essentiellement sur une sélection d'articles de recherche et d'ouvrages scientifiques de référence. |
|
| Evaluation : | L'examen en session comporte une partie écrite et une partie orale. Cette dernière porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau un petit exercice). Il est à noter que les travaux réalisés durant l'année académique (présentations orales, rapports, ...) interviendront également dans la cote finale de l'examen. |
|
| 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 |
|
|
| |
