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 [2020/02/26 15:30] (current)
berthe
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.+
  
 +**Examen :** 24 février 12h45-14h45 Salle 1013
  
- 
-==== 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 42:
 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 facteurs, mots de Sturmsubstitutions 
-   * 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+  
 +==== 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
 +   * Cours n° 6 : conjugaison de systèmes
 +       * définition et résultats connus (mots infinis)
 +       * invariants: entropie et fonction zêta
 +       * rationalité de la fonction zêta
 +   * Cours n° 7 : mots sturmiens
 +       * équilibre
 +       * équilibre et mots sturmiens
 +       * mots mécaniques
 +   * Cours n° 8 : normalité
 +   * Cours n° 9 : substitutions
 +       * mots et décalages engendrés
 +       * exemples : Fibonacci, Thue-Morse
 +       * complexité en facteurs
 +   * Cours n° 10 : substitutions primitives
 +       * Uniforme récurrence
 +       * Complexité linéaire
 +   * Cours n° 11 : fréquences et équilibre
 +       * Notion de féquences uniformes 
 +   * Cours n° 12 : discrépance symbolique
 +   * Cours n° 13 : théorème ergodique
 +       * mesures invariantes
 +       * unique ergodicité
 +   * Cours n° 14 : mots sturmiens
 +       * Graphe des mots
 +   * Cours n° 15 : mots sturmiens
 +       * Fréquences et théorème des 3 longueurs
 +   * Cours n° 16 : théorème de Fine et Wilf
 +   
  
 ==== 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  ==== 
 + 
 +[[https://www.irif.fr/~carton/Enseignement/MPRI/|Some notes here]]
  
 ==== Bibliographie ==== ==== Bibliographie ====
  
-   * Olivier Carton, [[http://www.liafa.jussieu.fr/~carton/Lfcc/|Langages formelscalculabilité et complexité]]Vuibert2008 +   - M.-PBéal,  D PerrinSymbolic dynamics and finite automataHandbook of formal languagesVol2463--505, Springer, Berlin, 1997. 
-   * Dexter CKozenAutomata and Computability, Springer, 1997 +   - M.-P. BéalCodage symboliqueMasson1993
-   * Gerard LallementSemigroups and Combinatorial Applications1979John Wiley & Sons, Inc+   - B. P. KitchensSymbolic Dynamics: One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag. 
-   * Leonid LibkinElements of finite model theory, Springer-Verlag, 2004 +   - D. Lind and  B. MarcusAn Introduction to Symbolic Dynamics and CodingCambridge University Press
-   * Dominique Perrin et Jean-Éric PinInfinite words, Pure and Applied Mathematics Vol 141Elsevier, 2004+   - N. Pytheas FoggSubstitutions in DynamicsArithmetics and CombinatoricsVBerthé and S. Ferenczi and C. Mauduit and A. Siegel (eds)Lecture Notes in Mathematicsvol. 1794Springer-Verlag,  
-   * Jean-Éric PinVariétés de langages formelsMasson, Paris1984. +   - CombinatoricsAutomata and Number TheoryV. BerthéMRigo (eds.)2010Encyclopedia Math. Appl.vol. 135Cambridge University Press
-   * Jean-Éric PinVarieties of formal languagesNorth OxfordLondon et Plenum, New-York1986. +   - E. Senata, Non-negative matrices and Markov Chains, Springer Series in Statistics
-   * Howard StraubingFinite automataformal logicand circuit complexityProgress in Theoretical Computer ScienceBirkhäuser Boston Inc., BostonMA1994. +
- +
- +
-==== 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