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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-20-2 [2019/09/10 12:25]
carton
cours:c-2-20-2 [2019/10/14 12:41] (current)
carton [Plan du cours]
Line 1: Line 1:
  
 ===== Dynamique symbolique (24h, 3 ECTS) ===== ===== Dynamique symbolique (24h, 3 ECTS) =====
 +
 ===== Symbolic dynamics (24h, 3 ECTS) ===== ===== Symbolic dynamics (24h, 3 ECTS) =====
 Responsable: V. Berthé, Directrice de recherches au CNRS Responsable: V. Berthé, Directrice de recherches au CNRS
Line 12: Line 13:
  
  
-==== Cours 2014-2015 : intervenants ====+==== Cours 2019-2020 ====
 Intervenants :  Intervenants : 
  
-- Valérie Berthé, Directrice de recherches au CNRS (12h)+[[https://www.irif.fr/~berthe/|Valérie Berthé]], Directrice de recherches au CNRS (12h)
  
-- Olivier Carton, Professeur à Paris 7 (12h)+[[https://www.irif.fr/~carton|Olivier Carton]], Professeur à Paris 7 (12h)
  
 +Le cours a lieu en salle 1013 le lundi de 12h45 à 14h15.
  
  
Line 30: Line 32:
  
  
-==== Cours 2014-2015 : Plan ==== +==== Langues du cours  ====
- +
- +
- +
- +
-=== Langues du cours ===+
 Français ou Anglais suivant l'avis des étudiants. L'anglais sera choisi si au moins Français ou Anglais suivant l'avis des étudiants. L'anglais sera choisi si au moins
 un étudiant ne connait pas le français. un étudiant ne connait pas le français.
Line 58: Line 55:
    * Théorèmes ergodiques    * Théorèmes ergodiques
    
 +==== Plan du cours ====
 +
 +   * Cours n° 1 : introduction
 +   * Cours n° 2 : shifts et sous-shifts ([3] p.1, [2] p.34)
 +       * espaces de suites, distance, topologie
 +       * équivalence avec l'ensemble des facteurs
 +       * entropie ([[https://fr.wikipedia.org/wiki/Lemme_sous-additif|existence]])
 +       * exemples
 +   * Cours n° 3 : sous-shifts de type fini et sous-shifts sofiques
 +       * définitions
 +       * automates locaux
 +       * décidabilité de la localité
 +   * Cours n° 4 : décidabilité du type fini
 +       * local implique de type fini
 +       * déterminisation d'automates
 +       * minimisation d'automates
 +   * Cours n° 5 : applications locales
 +       * Théorème de Perron-Frobenius ([[https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem|wikipedia]], [7], [3, chap 7.1])
 +       * définition
 +       * conjugaison
  
 ==== Pré-requis ==== ==== Pré-requis ====
Line 69: Line 86:
 ==== Bibliographie ==== ==== Bibliographie ====
  
-   M.-P. Béal,  D.  Perrin, Symbolic dynamics and finite automata, Handbook of formal languages, Vol. 2, 463--505, Springer, Berlin, 1997. +   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. +   - M.-P. Béal, Codage symbolique, Masson, 1993. 
-   D. Lind and  B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press. +   - B. P. Kitchens, Symbolic Dynamics: One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag. 
-   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,  +   D. Lind and  B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press. 
-   *  Combinatorics, Automata and Number Theory, V. Berthé, M. Rigo (eds.). 2010, Encyclopedia Math. Appl., vol. 135, 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. 
 +   - E. Senata, Non-negative matrices and Markov Chains, Springer Series in Statistics
  
 ==== Équipe pédagogique ==== ==== Équipe pédagogique ====
 Les membres des équipes "Combinatoires" et "Automates et applications" de l'IRIF  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