2017-2018 / MATH0470-1

Combinatorics on words

Durée

30h Th, 20h Pr

Nombre de crédits

 Master en sciences mathématiques, à finalité8 crédits 
 Master en sciences mathématiques8 crédits 

Enseignant

Julien Leroy, Michel Rigo

Coordinateur(s)

Michel Rigo

Langue(s) de l'unité d'enseignement

Langue anglaise

Organisation et évaluation

Enseignement au deuxième quadrimestre

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

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 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 comptant le nombre de facteurs de longueur n présents dans ce mot est bornée par une constante. Thèmes abordés : périodicité, fonction de complexité, mots sturmiens, suites automatiques, suites morphiques, substitutions, équivalence abélienne,  ...

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

L'étudiant maîtrisera des notions fondamentales exposées lors du cours, ainsi que les preuves et raisonnements sous-jacents. Il sera capable de les présenter clairement et de façon synthétique. Il pourra également les appliquer pour résoudre des exercices.

Savoirs et compétences prérequis

Connaissances mathématiques de base acquises en bachelier.

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 sur machine

Mode d'enseignement (présentiel ; enseignement à distance)

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. On pourra envisager d'implémenter certains algorithmes lors de ces séances d'exercices (par exemple, dans un logiciel du type Mathematica ou Sage). L'horaire des cours et des séances d'exercices sera communiqué en début d'année.

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. 2, 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).
  • 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).
  • J. Shallit, A second course in formal languages and automata theory, Cambridge University Press (2008).

Modalités d'évaluation et critères

Un examen oral dédié à la théorie (énoncés et preuves de résultats, avec discussion) mais aussi aux applications directes de celle-ci sera organisé. Les éventuels travaux personnels réalisés pendant l'année pourront être pris en compte pour la note finale.

Stage(s)

Remarques organisationnelles

Le cours se donne en anglais. Ce cours est organisé les années académiques débutant une année impaire (par ex. 2017-2018).

Contacts

J. Leroy, M. Rigo Institut de Mathématique (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 ; (04) 366.94.87 - E-mail : j.leroy@ulg.ac.be ; M.Rigo@ulg.ac.be