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-16 [2019/02/01 12:26]
colcombet
cours:c-2-16 [2019/09/06 12:55] (current)
colcombet
Line 8: Line 8:
     Responsable : <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe/">Thomas     Responsable : <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe/">Thomas
       Colcombet</a>       Colcombet</a>
-    <p>Équipe pédagogique : <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe">Thomas +    <p>Équipe pédagogique : 
-        Colcombet</a>, <a href="http://www.irif.univ-paris-diderot.fr/%7Epicantin/">Matthieu +         <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe">Thomas Colcombet</a>, 
-        Picantin</a>, <a href="https://www.pouly.fr/">Amaury Pouly</a>et <a +         <a href="https://www.irif.fr/~petrisan/">Daniela Petrisan</a>, 
-        href="http://www.enst.fr/%7Ejsaka/">Jacques +         <a href="http://www.irif.univ-paris-diderot.fr/%7Epicantin/">Matthieu Picantin</a> 
-        Sakarovitch</a>. </p>+         et <a href="https://www.pouly.fr/">Amaury Pouly</a>. </p>
     <h2>Table des matières </h2>     <h2>Table des matières </h2>
     <div class="twikiToc">     <div class="twikiToc">
Line 62: Line 62:
       </ul>       </ul>
       <h3><a name="Plan"></a> Plan du cours et intervenants prévus pour       <h3><a name="Plan"></a> Plan du cours et intervenants prévus pour
-        2018-2019</h3>+        2019-2020</h3>
       <ol>       <ol>
-        <li>Fonctions régulières de coût (12h + 3h TD, <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe">Thomas+        <li>Fonctions régulières de coût (15h + 3h TD, <a href="http://www.irif.univ-paris-diderot.fr/%7Ecolcombe">Thomas
             Colcombet</a>) </li>             Colcombet</a>) </li>
         <li>Semi-groupes et automates (9h + 3h TD, <a href="http://www.irif.univ-paris-diderot.fr/%7Epicantin/">Matthieu         <li>Semi-groupes et automates (9h + 3h TD, <a href="http://www.irif.univ-paris-diderot.fr/%7Epicantin/">Matthieu
             Picantin</a>) </li>             Picantin</a>) </li>
-        <li><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/mpri.html">Automates 
-            finis à multiplicité et transducteurs</a> (15h + 3h TD, <a href="http://www.enst.fr/%7Ejsaka/">Jacques 
-            Sakarovitch</a>) </li> 
         <li><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (9h + 3h TD, <a href="https://www.pouly.fr/">Amaury         <li><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (9h + 3h TD, <a href="https://www.pouly.fr/">Amaury
             Pouly</a>)<br>             Pouly</a>)<br>
         </li>         </li>
 +        <li>Automates finis à multiplicité et transducteurs (15h + 3h TD, <a href="https://www.irif.fr/~petrisan/">Daniela Petrisan</a>) </li>
       </ol>       </ol>
       <h3><a name="Plan"></a>Planning</h3>       <h3><a name="Plan"></a>Planning</h3>
-      <p> Le cours a lieu les <strong>mercredi</strong> de <em style="font-weight: bold;">16h15</em> +      <p> Le cours a lieu les <strong>mardi</strong> de <em style="font-weight: bold;">12h45</em> 
-        à <em><strong>19h15</strong></em> en <em>salle <span style="font-weight: bold;">1004</span></em>+        à <em><strong>15h45</strong></em> en <em>salle <span style="font-weight: bold;">1013</span></em>
         du bâtiment Sophie Germain. </p>         du bâtiment Sophie Germain. </p>
       <p> Chaque séance de cours comprendra (en gros) 2 heures de cours et 1       <p> Chaque séance de cours comprendra (en gros) 2 heures de cours et 1
Line 127: Line 125:
           </tr>           </tr>
           <tr>           <tr>
-            <td>12 Sept. </td>+            <td>10 Sept. </td>
             <td>Fonctions régulières de coût (1)</td>             <td>Fonctions régulières de coût (1)</td>
             <td>Colcombet</td>             <td>Colcombet</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>19 Sept. </td>+            <td>17 Sept. </td>
             <td>pas de cours</td>             <td>pas de cours</td>
             <td><br>             <td><br>
Line 138: Line 136:
           </tr>           </tr>
           <tr>           <tr>
-            <td>26 Sept. </td>+            <td>24 Sept. </td>
             <td>Fonctions régulières de coût (2)</td>             <td>Fonctions régulières de coût (2)</td>
             <td>Colcombet</td>             <td>Colcombet</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>Oct.</td>+            <td>Oct.</td>
             <td>Fonctions régulières de coût (3)</td>             <td>Fonctions régulières de coût (3)</td>
             <td>Colcombet</td>             <td>Colcombet</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>10 Oct. </td>+            <td>Oct. </td>
             <td>Fonctions régulières de coût (4)</td>             <td>Fonctions régulières de coût (4)</td>
             <td>Colcombet</td>             <td>Colcombet</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>17 Oct.</td>+            <td>15 Oct. </td> 
 +            <td>Fonctions régulières de coût (5)</td> 
 +            <td>Colcombet</td> 
 +          </tr> 
 +          <tr> 
 +            <td>22 Oct. </td>
             <td>Semi-groupes et automates (1)</td>             <td>Semi-groupes et automates (1)</td>
             <td>Picantin</td>             <td>Picantin</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>24 Oct. </td>+            <td>29 Oct. </td>
             <td>Semi-groupes et automates (2)</td>             <td>Semi-groupes et automates (2)</td>
             <td>Picantin</td>             <td>Picantin</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>31 Oct. </td> +            <td>5 Nov. </td> 
-            <td>Semi-groupes et automates (2)</td>+            <td>Semi-groupes et automates (3)</td>
             <td>Picantin</td>             <td>Picantin</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>7 Nov. </td> +            <td>12 Nov. </td>
-            <td>Fonctions régulières de coût (TD)</td> +
-            <td>Colcombet</td> +
-          </tr> +
-          <tr> +
-            <td>14 Nov. </td>+
             <td>Semi-groupes et automates (TD)</td>             <td>Semi-groupes et automates (TD)</td>
             <td>Picantin</td>             <td>Picantin</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>21 Nov.</td>+            <td>19 Nov.</td>
             <td>pas de cours</td>             <td>pas de cours</td>
             <td><br>             <td><br>
Line 184: Line 182:
           </tr>           </tr>
           <tr>           <tr>
-            <td>28 Nov.</td>+            <td>26 Nov.</td>
             <td>Examen (1)<br>             <td>Examen (1)<br>
             </td>             </td>
Line 200: Line 198:
           </tr>           </tr>
           <tr>           <tr>
-            <td>Déc.</td> +            <td>Déc.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#CoursI">Automates +            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (1)</td> 
-                à multiplicité (1): Rationalité et reconnaissabilité</a></td> +            <td>Pouly</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>12 Déc.</td> +            <td>10 Déc.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#CoursII">Automates +            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (2)</td> 
-                à multiplicité (2): Morphismes et conjugaison</a></td> +            <td>Pouly</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>19 Déc.</td> +            <td>17 Déc.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#CoursIII">Automates +            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (3)</td> 
-                à multiplicité (3): Réduction</a></td> +            <td>Pouly</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>Janv.</td> +            <td>Janv.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#CoursIV">Transducteurs +            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (TD)</td> 
-                (1): Automates à k bandes</a></td> +            <td>Pouly</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>16 Janv.</td> +            <td>14 Janv.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#CoursV">Transducteurs +            <td>Automates à multiplicité et transducteurs (1)</a></td> 
-                (2): Réalisation par représentations</a></td> +            <td>Petrisan</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>23 Janv.</td> +            <td>21 Janv.</td> 
-            <td><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/FLAT.html#TD">Automates +            <td>Automates à multiplicité et transducteurs (2)</a></td> 
-                à multiplicité &amp; Transducteurs (TD)</a></td> +            <td>Petrisan</td>
-            <td>Sakarovitch</td>+
           </tr>           </tr>
           <tr>           <tr>
-            <td>30 Janv.</td> +            <td>28 Janv.</td> 
-            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (1)</td> +            <td>Automates à multiplicité et transducteurs (3)</a></td> 
-            <td>Pouly</td>+            <td>Petrisan</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>Fév.</td> +            <td>Fév.</td> 
-            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (2)</td> +            <td>Automates à multiplicité et transducteurs (4)</a></td> 
-            <td>Pouly</td>+            <td>Petrisan</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>13 Fév.</td> +            <td>11 Fév.</td> 
-            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (3)</td> +            <td>Automates à multiplicité et transducteurs (5)</a></td> 
-            <td>Pouly</td>+            <td>Petrisan</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>20 Fév.</td> +            <td>18 Fév.</td> 
-            <td><a href="https://www.pouly.fr/teaching.html">Automates probabilistes et chaînes de Markov</a> (TD)</td> +            <td>Automates à multiplicité et transducteurs (TD)</a></td> 
-            <td>Pouly</td>+            <td>Petrisan</td>
           </tr>           </tr>
           <tr>           <tr>
-            <td>27 Fév.</td>+            <td>25 Fév.</td>
             <td>pas de cours</td>             <td>pas de cours</td>
             <td><br>             <td><br>
Line 262: Line 254:
           </tr>           </tr>
           <tr>           <tr>
-            <td>Mars </td>+            <td>Mars </td>
             <td>Examen (2)<br>             <td>Examen (2)<br>
             </td>             </td>
Line 379: Line 371:
              
              
-      <h3><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/mpri.html">Automates +      <h3>Automates finis à multiplicité (Daniela Petrisan)</h3> 
-          finis à multiplicité</a> (Jacques Sakarovitch)</h3> +      <p> Les automates à multiplicité sont un modèle de calcul très riche.  
-      <p> Aprés la généralisation des définitions de base des automates aux +        Si les automates classiques acceptent des mots, les automates à 
-        automates à multiplicité, on traitera successivement des points +        multiplicité examinent le nombre de façons pour accepter ou les ressources 
-        principaux suivants: </p> +        nécessaires pour accepter des motsPlus généralementles automates à 
-      <ul> +        multiplicité sont des automates possédant une sortie dans un semi-anneau 
-        <li>Rationalité et reconnaissabilité.<br> +        arbitraireCette génralisation permet de couvrir de nombreux modèles d'automates tels que 
-          Equivalence automates--expressions. Equivalence +        les automates Min-Plus, les transducteurs ou des automates à pile.</p
-          automates--représentations pour les automates sur le monoïde libre. +      <p
-          Produit de Hadamard.</li> +        Dans ce coursnous introduisons les automates à multiplicité et les 
-        <li>Conjugaison et morphismes.<br> +        notions de rationalité et reconnaissabilitéAprès avoir discuté la 
-          Morphismesquotients et revêtements d'automates à multiplicité +        relation entre ces notions et le théorème de Kleene-Schutzenberger
-          (bisimulation des systèmes de transitions). Conjugaison et équivalence +        nous considérons les notions de bisimulation et les morphismes des 
-          pour les automates sur Z et N.</li> +        automates et nous fournissons une approche algébrique pour la 
-        <li>Réduction.<br> +        minimisation
-          Espace des états et déterminisation; bases de l'espace des états et +      </p
-          représentations; réduction des représentations sur un corps. +      <p
-          Applications à l'équivalence des transducteurs.</li+        Dans une deuxième partie, nous étudions plus particulièrement les transducteurs, 
-      </ul> +        c'est-à-dire les automates avec des mots en sortie. En particulier
-      <h3><a href="http://www.enst.fr/%7Ejsaka/ENSG/MPRI/mpri.html">Transducteurs</a+        nous étudierons les relations rationnelles et le 
-        (Jacques Sakarovitch) </h3> +        théorème de composition assiciéEnfin, nous 
-      <p> Les transducteursou automates avec sortie (dans un monoïde libre) +        présenterons une approche algébrique pour la minimisation des 
-        peuvent être vus comme des cas particuliers des automates à +        transducteurs sous-séquentielsbasée sur une notion de 
-        multiplicité. La spécificité de cette "multiplicité" donne lieu à des +        congruence syntaxique pour les fonctions introduite par Choffrut, et 
-        développements bien particuliers</p> +        une généralisation aux fonctions rationnelles due à Reutenauer et 
-      <ul> +        Schutzenberger. 
-        <li>Uniformisation.<br> +      </p> 
-          Revêtement de Schützenbergerrevêtement lexicographique. + 
-          Uniformisation des relations rationnelles. Théorème de structure des +
-          fonctions rationnelles.</li> +
-        <li>Séquentialisation<br> +
-          Algorithme général de séquentialisation. Décidabilité et +
-          non-décidabilité de la séquentialitéCharactérisation des fonctions +
-          séquentielles. </li+
-        <li> Synchronisation<br+
-          Les transducteurs synchronesou lettre-à-lettresont le modèle qui +
-          sera utilisé en particulier dans la partie «Semi-groupes et +
-          automates»</li> +
-      </ul> +
-      <h4>Bibliographie</h4> +
-      <ul> +
-        <li>Jean-Eric PinPoly de l'X. </li> +
-        <li> Jacques Sakarovitch, <a href="http://www.enst.fr/%7Ejsaka/ETA/eta.html"><i>Éléments +
-              de théorie des automates</i></a>, Vuibert, 2003. <br> +
-          Il est fortement conseillé de télécharger la <a href="http://www.enst.fr/%7Ejsaka/ETA/eta.html#Errata">liste +
-            d'errata</a>, malheureusement assez longue.<br> +
-          Une version anglaise, et corrigée: <i>Elements of Automata Theory</i>, +
-          Cambridge (2009), est également disponible. <br> +
-          <!-- +
-    | Des exemplaires de cet ouvrage, en fran&ccedil;ais, ou en anglais, pourront    | &ecirc;tre pr&ecirc;t&eacute;s aux &eacute;tudiants pour l'ann&eacute;e.   --> +
-        </li> +
-      </ul>+
       <br>       <br>
       <h3>Automates probabilistes et chaînes de Markov (Amaury Pouly)</h3>       <h3>Automates probabilistes et chaînes de Markov (Amaury Pouly)</h3>
Line 463: Line 431:
             <td> CNRS </td>             <td> CNRS </td>
             <td> IRIF </td>             <td> IRIF </td>
 +          </tr>
 +          <tr>
 +            <td> D. Petrisan </td>
 +            <td> MC </td>
 +            <td> Paris 7 </td>
 +            <td> IRIF</td>
           </tr>           </tr>
           <tr>           <tr>
Line 475: Line 449:
             <td> CNRS </td>             <td> CNRS </td>
             <td> IRIF </td>             <td> IRIF </td>
-          </tr> 
-          <tr> 
-            <td> J. Sakarovitch </td> 
-            <td> DR Émérite </td> 
-            <td> CNRS </td> 
-            <td> IRIF &amp; Télécom </td> 
           </tr>           </tr>
         </tbody>         </tbody>
 
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