Durée
30h Th, 20h Pr
Nombre de 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.
Supports de cours, lectures obligatoires ou recommandées
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
Examen(s) en session
Toutes sessions confondues
- En présentiel
évaluation écrite ( questions ouvertes ) ET évaluation orale
Travail à rendre - rapport
Informations complémentaires:
L'évaluation finale pourra prendre l'une des deux formes suivantes :
- un examen classique, comprenant une partie orale portant sur la théorie et une partie écrite portant sur les exercices et les applications directes de la théorie ;
- une évaluation combinée, comprenant une interrogation orale portant sur la théorie, un court exercice écrit ainsi qu'une présentation de projets.
Dans tous les cas, les modalités retenues auront pour objectif d'évaluer à la fois la maîtrise des connaissances théoriques, la capacité à les mobiliser dans la pratique et la qualité du travail réalisé au cours de l'année.
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
Manon Stipulanti
Institut de Mathématique (B37)
Allée de la découverte 12
Sart Tilman, 4000 Liège
E-mail : m.stipulanti@uliege.be