|
Premier cours : Vendredi 25 septembre 2020, de 12h45 à 15h45 (Bat. Sophie Germain, 2001)
Responsable : Vlady Ravelomanana
Partie 1
Petite introduction : Vlady Ravelomanana
Modèle rationnel : Frédérique Bassino
Familles simples d'arbres et analyse de singularités : Olivier Bodini
Structures étiquetés: permutations, graphes: Vlady Ravelomanana
Partie 2
Graphes aléatoires et combinatoire analytique : Elie de Panafieu
Algorithmes de comptage probabiliste et estimation de cardinalité : Vincent Jugé
voir plan détaillé ci-dessous.
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. La seconde partie est dédiée à l'étude de divers types d’applications (différentes selon les années), particulièrement en liaison
avec les structures arborescentes, l’algorithmique probabiliste, la recherche multidimensionnelle, et les
graphes aléatoires.
- Socle
- 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 k premiers, tables d'inversion, nombre de Stirling,
comparaison de deux stratégies de sélection.
- 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 (mappings).
- Notions sur les fonctions génératrices à plusieurs
variables: calculs explicites de moments et de lois de probabilité.
- 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é).
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:
- 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 rho de Pollard).
- Tri rapide (Quicksort); Sélection rapide (Quickfind);
Variantes avec
médiane; 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.
- Applications avancées.
- Problèmes difficiles en optimisation et combinatoire analytique : apports de la Combinatoire Analytique dans les problèmes difficiles d'optimisation, les graphes
aléatoires et les transitions de phase dans les formules du type SAT.
- Algorithmique aléatoirisée. Une direction récente est l'algorithmique de
la fouille de données: algorithmes de comptage probabiliste et estimation de cardinalité,
extraction des mots fréquents, extraction des contenus communs à
des corpus distincts.
- 25/09 : introduction
- 25/09, 02/10 : structures non étiquetées (Frédérique Bassino)
- 09/10, 16/10 et 23/10 : familles d'arbres (Olivier Bodini)
- 30/10, 06/11 et 13/11 : structures étiquetées (Vlady Ravelomanana)
- 20/11 : séance d'exercices
- 27/11 : examen partiel
- 08/01, 15/01 et 22/01 : graphes aléatoires (Elie de Panafieu)
- 29/01, 05/02 et 12/02 : algorithmes (Vincent Jugé)
- 19/02 : séance d'exercices
- 26/02 : examen
- Examen Partiel : Vendredi 27 Novembre 2020, de 12h45 à 15h45
Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.
- Examen Final : Vendredi 26 Février 2020, de 12h45 à 15h45
Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.
- Note finale = (EFinal+EPartiel)/2.
Le cours aura lieu en français, mais les documents servant de support sont, pour la plupart, en anglais.
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 cours de 2005.
Ce cours s'appuie par ailleurs très fortement sur l'ouvrage cité dans la bibliographie.
Des exercices sont proposés chaque semaine (et corrigés au début du cours suivant). Deux séances d'exercices précèdent les examens.
Ce cours est très lié au cours 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, 2.17.1, 2.22, ou
2.29-1
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.
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 disponible en ligne. Pour la seconde partie, les articles de références seront donnés par les enseignants.
F. Bassino |
PU |
Paris 13 |
LIPN |
O. Bodini |
PU |
Paris 13 |
LIPN |
E. de Panafieu |
Chercheur |
Nokia Bell Labs |
https://www.bell-labs.com/ |
V. Jugé |
MCF |
Gustave Eiffel |
LIGM |
V. Ravelomanana |
PU |
Paris |
IRIF |
|