Durée
30h Th, 20h Pr
Nombre de crédits
| Master en sciences mathématiques, à finalité (années impaires, organisé en 2023-2024) | 8 crédits |
Enseignant
Langue(s) de l'unité d'enseignement
Langue anglaise
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
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, à 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. 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.
Le cours est organisé en présentiel. Le cas échéant, certaines parties de la matière pourront être dispensées sous forme de vidéos à regarder (podcasts). Les exercices se feront en partie à domicile.
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).
- 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 et modifications principales apportées au cours
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, 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 ;