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 [2014/03/25 12:26]
pin [Cours 2009-2010 : Plan]
cours:c-2-20-2 [2019/09/16 11:36] (current)
carton [Cours 2019-2020]
Line 1: Line 1:
  
-===== Fondations mathématiques de la théorie des automates (24h, 3 ECTS) ===== +===== Dynamique symbolique (24h, 3 ECTS) ===== 
-===== Mathematical Foundations of Automata Theory  (24h, 3 ECTS) ===== + 
-Responsable: J.-EPinDirecteur de recherches au CNRS+===== Symbolic dynamics (24h, 3 ECTS) ===== 
 +Responsable: VBerthéDirectrice de recherches au CNRS
  
 ==== Objectifs ==== ==== Objectifs ====
 Ce cours s'adresse à des étudiants possédant une grande curiosité, car il fait Ce cours s'adresse à des étudiants possédant une grande curiosité, car il fait
-appel simultanément à plusieurs domaines des mathématiques (combinatoire, algèbrelogiquetopologie, etc.), mais sous un angle parfois très éloigné des mathématiques "classiques".+appel simultanément à plusieurs domaines des mathématiques (combinatoire, topologie théorie de la mesure 
 +théorie ergodique, etc.).
  
-Introduits vers 1950, les automates finis constituent le modèle le plus élémentaire de machine. 
-Ils sont utilisés dans diverses branches de l'informatique (et plus récemment des mathématiques): compilation, traitement de texte, modélisation et vérification des systèmes, calculs distribués, traitement des langues naturelles, compression de données, codage, etc. 
  
-Ce cours se propose de donner les bases mathématiques de la théorie des automates dans les domaines suivants: 
  
-- nouveaux concepts mathématiques (parties rationnelles et reconnaissables, monoïdes syntactiques ordonnés, etc.) 
  
-algèbre non-commutative (monoïdes, semi-anneaux, théorie des variétés)+==== Cours 2019-2020 ==== 
 +Intervenants : 
  
-logique (premier ordresecond ordre monadique)+[[https://www.irif.fr/~berthe/|Valérie Berthé]]Directrice de recherches au CNRS (12h)
  
-théorie équationnelle et topologies profinies+[[https://www.irif.fr/~carton|Olivier Carton]], Professeur à Paris 7 (12h)
  
-L'objectif est de démontrer dans ce cours quelques grands résultats classiques qui permettront aux étudiants d'accéder aux développements les plus récents et aux applications dans des domaines très variés (langages formels, vérification, logique, complexité des circuits, complexité de communication, modèles finis, etc.). On insistera plus particulièrement sur les liens avec la logique. +Le cours a lieu en salle 1013 le lundi de 12h45 à 14h15.
-On ne traitera que le cas des automates travaillant sur des mots finis, mais les extensions aux mots infinis, aux arbres et à d'autres structures pourront être étudiées ultérieurement.+
  
- 
- 
-==== Cours 2014-2015 : intervenants ==== 
-Intervenants:  
- 
-- Olivier Carton, Professeur à Paris 7 (12h) 
- 
-- Jean-Eric Pin, Directeur de recherches au CNRS (12h) 
  
 ==== Autres cours complémentaires ==== ==== Autres cours complémentaires ====
  
-   * 2-8  Modélisation et vérification des systèmes temporisés, hybrides ou concurrents +   * 2-8-2  Vérification algorithmique des programmes 
-   * 2-9 Vérification de systèmes dynamiques et paramétrés +   * 2-10 Aspects algorithmiques de la combinatoire  
-   * 2-16 Techniques pour la modélisation par automates +   * 2-15        Analyse d'algorithmes  
-   * 2-20-1 Jeux pour la théorie des automates, la vérification et l'internet +   * 2-16 Modélisation par automates finis 
-   * 2-26-1 Logique, complexité descriptive et théorie des bases de données +   * 2-17-1      Fondements sur la modélisation des réseaux 
-   * 2-28-1 Automates d'arbres et applications+
  
  
-==== Cours 2014-2015 : Plan ==== +==== Langues du cours  ====
- +
-Le plan détaillé du cours sera précisé ultérieurement, mais on suivra plus ou moins +
-le plan du support de cours. +
-Cette année deux séances supplémentaires seront organisées sous forme de travaux dirigés. +
- +
- +
- +
-=== 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 59: Line 40:
 Les étudiants seront autorisés à rédiger leur examen en français ou en anglais. Les étudiants seront autorisés à rédiger leur examen en français ou en anglais.
  
-=== Supports de cours :  === 
-Les supports de cours seront accessibles aux adresses suivantes 
  
-URL: http://www.liafa.univ-paris-diderot.fr/~jep/MPRI/MPRI.html 
  
-URL: http://www.liafa.univ-paris-diderot.fr/~carton/Enseignement/MPRI/ 
 ==== Description du cours ==== ==== 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: Voici quelques thèmes abordés dans ce cours:
  
-   * Reconnaissance par morphismes +   * Système dynamique 
-   * Langages sans étoile et théorème de Schützenberger +   * Système sofique, système de type fini 
-   * Calcul séquentiel de Büchi; logiques du premier ordre et du second ordre +   * Entropie 
-   * Logique du successeurcaractérisation algébrique +   * Complexité en facteursmots de Sturm, substitutions 
-   * Logique temporelle +   * Mesure de Parry 
-   * Langages testables par morceaux +   * Normalité vs compressibilité par automates 
-   * Théorème des variétés d'Eilenberg +   * Théorèmes ergodiques 
-   * Topologies profinies, théorie équationnelles + 
  
 ==== Pré-requis ==== ==== Pré-requis ====
  
-Théorie classique des automates finis et quelques rudiments de logique.+Théorie classique des automates finis.
    
-Il est très vivement recommandé aux étudiants peu familiers avec les automates de suivre le cours de tronc commun //Automates//.+==== Notes de cours  ====
  
-==== Bibliographie ====+[[https://www.irif.fr/~carton/Enseignement/MPRI/|Some notes here]]
  
-   * Olivier Carton, [[http://www.liafa.jussieu.fr/~carton/Lfcc/|Langages formels, calculabilité et complexité]], Vuibert, 2008 +==== Bibliographie ====
-   * Dexter C. Kozen, Automata and Computability, Springer, 1997 +
-   * Gerard Lallement, Semigroups and Combinatorial Applications, 1979, John Wiley & Sons, Inc. +
-   * Leonid Libkin, Elements of finite model theory, Springer-Verlag, 2004 +
-   * Dominique Perrin et Jean-Éric Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004. +
-   * Jean-Éric Pin, Variétés de langages formels, Masson, Paris, 1984. +
-   * Jean-Éric Pin, Varieties of formal languages, North Oxford, London et Plenum, New-York, 1986. +
-   * Howard Straubing, Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA, 1994.+
  
 +   * 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.
  
-==== Les années précédentes ==== 
-   * [[2009-2010-C-2-20-2|Année 2009-2010]] 
-   * [[2008-2009-C-2-20-2|Année 2008-2009]] 
-   * [[2007-2008-C-2-20-2|Année 2007-2008]] 
-   * [[2006-2007-C-2-20-2|Année 2006-2007]] 
  
 ==== Équipe pédagogique ==== ==== Équipe pédagogique ====
-Les membres de l'équipe "Automates et applications" du LIAFA +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