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:2012-2013-c-2-15 [2013/07/09 11:15]
hubertcomon created
cours:2012-2013-c-2-15 [2013/07/09 11:23] (current)
hubertcomon
Line 1: Line 1:
  
 +===== Analyse d'algorithmes (48h, 6 ECTS) =====
 +
 +**Premier cours : Mercredi 19 septembre 2012,  de 16h15 à 19h15** (Chevaleret)
 +
 +Responsable : Michèle Soria
 +
 +==== Plan du cours et intervenants prévus pour 2012-2013 ====
 +
 +Partie 1
 +  -  Modèles réguliers : Michèle Soria
 +  - Familles simples d'arbres : Cyril Nicaud
 +  -  Arbres et Graphes fonctionnels :   Brigitte Vallée
 +
 +Partie 2
 +  -  Automates et analyse d'algorithmes : Frédérique Bassino
 +  -  Modèles d'arbres et analyse d'algorithmes: Nicolas Broutin 
 +  -  Graphes aléatoires et analyse d'algorithmes : Vlady Ravelomanana
 +
 +voir [[#planning| plan détaillé  ]] ci-dessous.
 +
 +==== Objectifs ====
 +
 + La première partie de ce cours vise à mettre en place les bases de l'étude des modèles combinatoires 
 +//quantitatifs// de l'analyse d'algorithmes.
 +Ceci met en jeu la théorie générale de la combinatoire analytique, où
 + interviennent des méthodes de combinatoire énumérative (par fonctions génératrices) 
 +conjuguées à des méthodes d’analyse asymptotique. Cette approche permet l’évaluation des principaux algorithmes et structures de données de l’informatique. Le cours est étayé de nombreux 
 +exemples. Divers types d’applications sont traitées en seconde partie, particulièrement en liaison 
 +avec les structures digitales, l’algorithmique probabiliste, la recherche multidimensionnelle, et la 
 +recherche de motifs dans les arbres.  
 + 
 +==== Contenu  ====
 +
 +<html>
 +<ol style="list-style-type: upper-roman">
 +<li><b>Socle </b>
 +<ul>
 +<li> Généralités sur
 +les modèles probabilistes discrets: moyennes, variances, lois de
 +probabilité discrètes. Liens entre dénombrements, analyse
 +asymptotique, et analyse d'algorithmes. Inégalités de Chebyshev.
 +Exemple élémentaire:
 +sélection des <i>k</i> premiers, tables d'inversion, nombre de Stirling,
 +comparaison de deux stratégies de sélection.  </li>
 +<li> Dénombrements exacts par séries génératrices ordinaires et
 +exponentielles. Modèles de base pour les mots et langages, 
 +familles d'arbres, permutations, graphes contraints, allocations
 +(modèles d'urnes). Pour les modèles rationnels: liens entre
 +automates, séries rationnelles,
 +systèmes linéaires, et matrices de transfert.
 +Pour les modèles algébriques et leurs variantes: inversion de
 +Lagrange, théorème de Cayley (arbres étiquetés), applications
 +aux fonctions finies (<em>mappings</em>). </li>
 +<li> Notions sur les fonctions génératrices à plusieurs
 +variables: calculs explicites de moments et de lois de probabilité.</li>
 +<li> Dénombrements asymptotiques. Utilisation des propriétés
 +analytiques des séries génératrices: pôles des fractions
 +rationnelles, bornes sur les rayons de convergence
 +(bornes de col), les singularités
 +et leur influence sur les coefficients de séries
 +(bases de l'analyse de singularité). </li>
 +</ul>
 +Le traitement est élémentaire en ce qui concerne la manipulation
 +algébrique de séries génératrices. Il reste pragmatique 
 +sur les aspects liés à l'analyse complexe (détection des
 +singularités positives grâce au théorème de Pringsheim). 
 +Il est demandé peu de connaissances préalables à l'étudiant
 +mais l'acceptation d'une théorie par nature assez
 +mathématisée. 
 +Les applications traitables à ce niveau sont par exemple:
 +<ul>
 +<li> Tri rapide (<em>Quicksort</em>); Sélection rapide (<em>Quickfind</em>);
 +Variantes avec
 +médiane; Tris (<em>Bubble-sort</em>, etc); Caractéristiques principales
 +des arbres
 +binaires de recherche (longueur de cheminement, pagination). 
 +Hachage avec chainage séparé et allocations aléatoires:
 +paradoxe des anniversaires, collectionneur de coupons, loi
 +de Poisson des remplissage, linéarité en moyenne. Mots et
 +motifs: polynômes d'autocorrelation, linéarité en moyenne de la
 +recherche naïve de motifs. Arbres de Catalan,
 +objets bijectivement reliés (chemins de Dyck, triangulations),
 +et leurs principales caractéristiques probabilistes. 
 +Arbres de Cayley et application 
 +aux générateurs aléatoires ainsi qu'à la factorisation entière
 +(méthode <em>rho</em> de Pollard). </li>
 +</ul>
 +</li>
 +
 +<li><b>Applications avancées.</b> 
 +<ul>
 +<li> <em>Lois limites en combinatoire analytique</em>: 
 +au delà des moyennes et variances, comment caractériser 
 +par l'analyse les lois probabilistes qui décrivent le comportement
 +des principales structures discrètes aléatoires et des
 +principaux algorithmes associés? Contenu: théorème des
 +quasi-puissances, méthodes de moments. Applications aux mots et
 +motifs, aux tris, à la factorisation de polynômes, à la recherche
 +multidimensionnelle (arbres quadrants), à l'algorithmique
 +arithmétique (factorisation de Pollard).</li>
 +<li> <em>Analyse dynamique des algorithmes</em>: il s'agit de considérer 
 +un algorithme comme un système dynamique, l'opérateur de transfert
 +jouant alors le rôle de <em>super</em> série
 +génératrice. Unification
 +des principaux modèles de source d'information
 +(sans mémoire ou Bernoulli, Markov, fractions continues, etc)
 +et applications à l'algorithmique du texte et 
 +aux statistiques de motifs.
 +Structure d'arbre digital (<em>trie</em>) et applications à la gestion de
 +dictionnaires; applications à la compression
 +(de type Lempel&ndash;Ziv); algorithmes arithmético-géométriques fondés sur
 +les fractions continues.</li>
 +<li> <em>Algorithmique aléatoirisée</em>: Cf <em>Randomized algorithms</em>
 +de Motwani &amp; Raghavan. Une direction récente est l'algorithmique de
 +la fouille de données: algorithmes de comptage probabiliste,
 +extraction des mots fréquents, extraction des contenus communs à
 +des corpus distincts. Quelques applications à l'optimisation
 +combinatoire ou aux structures de données (<em>skip lists</em>). </li>
 +<li> <em>Algorithmique et modèles probabilistes de la
 +bio-informatique</em>. 
 +Statistique des motifs simples et généralisés: facteurs,
 +sous-séquences, motifs approchés, alignements, etc.
 +Ce qui est visé ici est l'articulation entre les analyses
 +combinatoires et probabilistes d'une part, les problèmes issus de la
 +bio-informatique d'autre part.</li>
 +</ul></li>
 +</ol>
 +
 +<a name="planning"></a>
 +<h3>Contenu des cours </h3>
 +
 +
 +<h3> Examens </h3>
 +<html> <ul>
 +<li> Examen Partiel : Mercredi 5 Décembre 2012, de 16hh15 à 19h15
 +<br> Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.</li> 
 +<li>  Examen Final: Mercredi 6 Mars 2013, de 16hh15 à 19h15
 +<br> Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.</li> 
 +<li>  Note finale  = (EFinal+EPartiel)/2 </li> 
 +</html>
 +
 +==== Langue du cours  ====
 +Le cours aura lieu en français, mais les documents servant de support sont, pour la plupart, en anglais.
 +
 +==== Supports de cours  ====
 +Des supports de cours existent, sous forme de résumés détaillés, de notes de cours rédigées et d'annales:
 +vous pouvez par exemple accéder à la page du [[http://algo.inria.fr/flajolet/Teach/mpri05.html|cours de 2005]].
 +Ce cours s'appuie par ailleurs très fortement sur l'ouvrage cité dans la bibliographie.
 +
 +====  Exercices et Annales  ====
 +       
 +       
 +       ====  Cours liés  ====
 +Ce cours est très lié au cours [[http://mpri.master.univ-paris7.fr/C-2-10.html|2.10]], qui couvre des thématiques très proches  (mais on peut aussi suivre un seul de ces deux cours).
 +
 +Dans des domaines de l'algorithmique voisins, il est recommandé de suivre des  cours comme 2.11.1, 2.11.2, [[http://mpri.master.univ-paris7.fr/C-2-17.html|2.17]], [[http://mpri.master.univ-paris7.fr/C-2-22.html|2.22]],  ou
 + [[http://mpri.master.univ-paris7.fr/C-2-29-1.html|2.29-1]]
 +
 +==== Pré-requis ====
 +
 +Ce cours relativement mathématisé 
 +doit bien convenir à des étudiants ayant une formation mixte en
 +mathématiques et informatique de bon niveau, comme il s'en rencontre
 +à l'École polytechnique et dans les Écoles normales
 +supérieures, ainsi que dans les parcours Math-Info des
 + cursus universitaires. 
 +Il peut aussi servir de passerelle vers l'informatique,
 +pour des étudiants dont la formation jusqu'à Bac+4 était 
 +principalement mathématique. Pour ceux qui ont suivi 
 +des filières plus informatiques, il propose un socle
 +méthodologique solide mais demande un certain investissement.
 +
 +==== Bibliographie ====
 +
 +Pour la première partie, 
 +le niveau de traitement est intermédiaire entre le livre de 
 +R. Sedgewick et Ph. Flajolet (//Introduction à l'analyse des
 +algorithmes//) et les Chapitres I-- V de //Analytic Combinatorics// (800p.)
 +de Ph. Flajolet et R. Sedgewick [[http://algo.inria.fr/flajolet/Publications/books.html|disponible en ligne]].
 +
 +====  Les années précédentes  ====
 +   * [[2011-2012-C-2-15|Année 2011-2012]]
 +   * [[2012-2013-C-2-15|Année 2012-2013]]
 +  
 +  ==== Équipe pédagogique ====
 +<html><table border="2">
 +<tr><td>F. Bassino</td>
 +<td>PU</td>
 +<td>Paris13</td>
 +<td>LIPN</td>
 +<tr><td>N. Broutin</td>
 +<td>CR</td>
 +<td>INRIA</td>
 +<td>Rocquencourt</td>
 +<tr><td>V. Ravelomanana</td>
 +<td>PU</td>
 +<td>Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td> C. Nicaud </td>
 +<td>PU</td>
 +<td>Marne-la-Vallée</td>
 +<td>IGM</td>
 +</tr>
 +
 +<tr><td>M. Soria</td>
 +<td>PU</td>
 +<td>UPMC</td>
 +<td>LIP6</td>
 +</tr>
 +<tr><td>B. Vallée</td>
 +<td>DR</td>
 +<td>CNRS</td>
 +<td>GREYC</td>
 +</tr></table></html>
  
 
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