Combinatorics on words

Durée

30h Th, 20h Pr

Nombre de crédits

Enseignant

Julien Leroy

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

Langue anglaise

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

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).

• 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,  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 ; 

Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session de mai-juin

Méthodes d'apprentissage mises en œuvre : enseignement à distance

Le cours théorique se poursuit via la publication régulière de podcasts sur le site institutionnel de l'Université. Ces podcasts sont réalisés en français. Des listes d'exercices sont envoyées par mail aux étudiants. Par la suite, un correctif de ces exercices est également envoyé.

Matière de l'évaluation

L'examen portera sur toute la matière vue au cours théorique ou aux séances d'exercices. Les questions consisteront en des résolutions d'exercice ou en des applications directes de la théorie. Certaines démonstrations ou parties de démonstrations pourront être demandées.

Méthodes d'évaluation

L'évaluation consistera en un examen écrit à distance. Le titulaire du cours enverra un mail aux étudiants à l'horaire prévu. L'examen sera attaché à ce mail sous forme de document pdf. Il y aura plusieurs questionnaires différents. Les étudiants doivent envoyer leurs réponse électroniquement, sous la forme d'un scan ou de photos lisibles de leur copie à l'adresse j.leroy@uliege.be, avant la fin du temps imparti. L'étudiant qui enverrait sa copie en retard se verra proposé un examen oral à distance supplémentaire le surlendemain de l'évaluation écrite. Celui-ci portera sur la copie écrite de l'étudiant, mais pourra aussi inclure d'autres questions.

Contact

Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session août-sept

Matière de l'évaluation

Similaire à la session de juin.

Méthodes d'évaluation (et plateforme utilisée)

Similaire à la session de juin.

Contact(s)