Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

This is an old revision of the document!


Dynamique symbolique (24h, 3 ECTS)

Symbolic dynamics (24h, 3 ECTS)

Responsable: V. Berthé, Directrice de recherches au CNRS

Objectifs

Ce cours s'adresse à des étudiants possédant une grande curiosité, car il fait appel simultanément à plusieurs domaines des mathématiques (combinatoire, topologie, théorie de la mesure, théorie ergodique, etc.).

Cours 2014-2015 : intervenants

Intervenants :

- Valérie Berthé, Directrice de recherches au CNRS (12h)

- Olivier Carton, Professeur à Paris 7 (12h)

Autres cours complémentaires

  • 2-8-2 Vérification algorithmique des programmes
  • 2-10 Aspects algorithmiques de la combinatoire
  • 2-15 Analyse d'algorithmes
  • 2-16 Modélisation par automates finis
  • 2-17-1 Fondements sur la modélisation des réseaux

Cours 2014-2015 : Plan

Langues du cours :

Français ou Anglais suivant l'avis des étudiants. L'anglais sera choisi si au moins un étudiant ne connait pas le français.

Le sujet d'examen sera en français et en anglais.

Les étudiants seront autorisés à rédiger leur examen en français ou en anglais.

Description du cours

L’objet de ce cours est de présenter une introduction à la dynamique symbolique. Un système dynamique discret (c’est-à-dire à temps discret) est défini comme l’action d’une application T agissant sur un espace X. Il s'agit alors d’étudier l’évolution à long terme du système. La dynamique symbolique a pour objet l’étude de systèmes dynamiques discrets composés de suites infinies de symboles d’un alphabet fini. Ils apparaissent naturellement comme des codages de trajectoires de points d’un système dynamique défini sur un espace X, a priori de nature continue, selon une partition finie donnée.

Voici quelques thèmes abordés dans ce cours:

  • Système dynamique
  • Système sofique, système de type fini
  • Entropie
  • Complexité en facteurs, mots de Sturm, substitutions
  • Mesure de Parry
  • Normalité vs compressibilité par automates
  • Théorèmes ergodiques

Pré-requis

Théorie classique des automates finis.

Notes de cours

Bibliographie

  • M.-P. Béal, D. Perrin, Symbolic dynamics and finite automata, Handbook of formal languages, Vol. 2, 463–505, Springer, Berlin, 1997.
  • B. P. Kitchens, Symbolic Dynamics: One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag.
  • D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press.
  • N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, V. Berthé and S. Ferenczi and C. Mauduit and A. Siegel (eds), Lecture Notes in Mathematics, vol. 1794, Springer-Verlag,
  • Combinatorics, Automata and Number Theory, V. Berthé, M. Rigo (eds.). 2010, Encyclopedia Math. Appl., vol. 135, Cambridge University Press.

Équipe pédagogique

Les membres des équipes “Combinatoires” et “Automates et applications” de l'IRIF

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA