CR-06 : Approximations : du symbolique au numérique, et applications.

Programme de l’UE

Nous passons en revue une partie de la théorie de l’approximation du point de vue du calcul effectif. Comment calculer des approximants polynomiaux ou rationnels, développer efficacement en série de Taylor ou sur des bases de polynômes orthogonaux, calculer des approximants de Padé, puis comment utiliser ces développements pour obtenir des approximations à précision donnée (algorithmes de Remez, modèles de Taylor et de Chebyshev). La puissance de ces techniques sera illustrée en développant trois applications, attachées à des domaines scientifiques différents : preuves d’irrationalité en théorie des nombres, évaluation efficace de fonctions numériques, problème des « Near-Earth Objects ».

Prérequis :

Calendrier prévisionnel : 19/09, 24/09, 26/09, 01/10, 08/10, 10/10, 15/10, 22/10, 24/10, 5/11, 7/11, 12/11.

Modalités d’examen : Examen écrit, et un travail à la maison noté.

Intervenants

  • Nicolas Brisebarre, CR CNRS (responsable)
  • Bruno Salvy, DR INRIA

ER 03 (2011) : Vision et apprentissage

Du 24 au 28 janvier 2011 — ENS Lyon

Les cours de cette école seront dispensés en anglais. Merci de consulter la version anglaise de cette page où vous trouverez de plus amples informations (descriptif du cours, emploi du temps, etc.).

Intervenants :

  1. Zaid Harchaoui (INRIA, LEAR, INRIA Rhône-Alpes)
  2. Ivan Laptev (INRIA, WILLOW, INRIA Rocquencourt)
  3. Cordelia Schmid (INRIA, LEAR, INRIA Rhône-Alpes)
  4. Josef Sivic (INRIA, WILLOW, INRIA Rocquencourt)

Correspondants locaux

Un certain nombre d’informations utiles se trouve sur la page principale des écoles de recherche en informatique fondamentale de l’ENS Lyon.

ER-01 (2010) : Algorithmes pour l’approximation géométrique

du 11 au 15 janvier 2010 — ENS Lyon

Objectifs

De plus en plus de domaines comme la biologie, l’analyse statistique ou l’apprentissage automatique, ont à traiter des données qui sont en fait des nuages de points dans des espaces de grandes dimensions. Ces données sont porteuses de caractéristiques topologiques et géométriques qui traduisent les propriétés des systèmes modélisés. Par exemple, la densité du nuage de points peut être concentrée autour d’une variété de dimension intrinsèque bien inférieure à celle de l’espace ambiant. Extraire une telle information n’est pas une tâche facile. Tout d’abord les données sont généralement bruitées, Ensuite, les structures et algorithmes de la géométrie algorithmique ont souvent des complexités exponentiellement croissantes en fonction de la dimension et passent mal à l’échelle pour ce type de données.

Ce cours propose une introduction à la géométrie algorithmique, axée sur les problématiques de l’approximation et de l’échantillonnage des objets géométriques. Il part de certains concepts classiques (enveloppe convexe, diagrammes de Voronoi) et aborde des méthodes récemment développées (core sets, persistance topologique) pour approcher les propriétés géométriques et topologiques des objets en dimensions supérieures, tout en évitant l’explosion exponentielle de la complexité, lié à la dimension.

Intervenants :

  1. Jean-Daniel Boissonnat
  2. Frédéric Chazal
  3. Mariette Yvinec

Plan du cours

Algorithmes pour l’approximation géométrique

  1. Structures métriques pour les ensembles de points
    • Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat)
    • Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal)
    • Algorithmes randomisés et core sets (M. Yvinec)
  2. Approximation simpliciale de variétés
    • Génération de maillage par raffinement de Delaunay (M. Yvinec)
    • Triangulation de Delaunay restreinte, epsilon-échantillons et génération
      de maillage de surfaces (J.-D. Boissonnat)
    • Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat)
  3. Inférence géométrique (F. Chazal)
    • Théorie de l’échantillonnage des compacts
    • Homologie persistante et analyse de données

Prérequis

Le cours ne suppose pas de prérequis. Toutes les notions fondamentales de géométrie algorithmique utilisées dans le cours seront exposées au préalable.

Bibliographie

  • M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
  • J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces, Springer-Verlag, 2006.
  • J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
  • F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled « Tesselations in the Sciences », November 2007.
  • F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compacts in Euclidean Space, Proceedings of the 22nd ACM Symposium on Computational Geometry 2006.
  • E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
  • K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
  • A. Zomorodian, Topology for Computing, Cambridge Monographs on Applied and Computational Mathematics, cambridge University Press, 2005.

Inscription

Il n’y a pas de frais d’inscription. Pour des questions d’organisation, il est toutefois nécessaire de s’inscrire en ligne ; [inscription fermée].

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal de la partie « sciences exactes » de l’ENS Lyon).

Un emploi du temps possible est le suivant:

  • Lundi 11 janvier
    • 14h-17h. Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat).
      Transparents disponibles ici puis ici.
  • Mardi 12 janvier
    • 8h30 – 11h30. Génération de maillage par raffinement de Delaunay (M. Yvinec).
      Transparents disponibles ici puis ici.
    • 13h30 – 16h30. Triangulation de Delaunay restreinte, epsilon-échantillons et génération de maillage de surfaces (J.-D. Boissonnat).
      Transparents disponibles ici.
  • Mercredi 13 janvier
    • 8h30 – 11h30. Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal).
      Transparents disponibles ici.
    • 13h30 – 16h30. Algorithmes randomisés et core sets (M. Yvinec).
      Transparents disponibles ici puis ici.
  • Jeudi 14 janvier
    • 8h30 – 11h30. Théorie de l’échantillonnage des ensembles compacts (F. Chazal).
      Transparents disponibles ici.
  • Vendredi 15 janvier
    • 8h30 – 11h30. Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat).
      Transparents disponibles ici.
    • 13h – 16h. Homologie persistante et analyse de données (F. Chazal).
      Transparents disponibles ici.

Correspondants locaux

Un certain nombre d’informations utiles se trouve sur la page principale des écoles de recherche en informatique fondamentale de l’ENS Lyon.