Géométrie discrète et algorithmique
Michel Pocchiola, Ens-Paris, (48h).


Cours du 25 Février.
  • Présentation du cours : recherche simpliciale, partitions simpliciales, epsilon-nets, convexification d'un polygone simple, cônes et pseudotriangulations minimales, diagramme de Voronoi et polyèdres;
  • Probabilité sur les ensembles finis, permutations, combinaisons/échantillons, arbres binaires, arbres binaires de recherche, complexes cellulaires, graphes (relation d'Euler, borne sur le nombre de croisements);
  • Epsilon-nets de taille logarithmique, non planarité des graphes de Kuratowski, incidence point-droite;

    • Cours du 4 Mars.
  • Enveloppes convexes 2D et sequences de Davenport-Schinzel; Support de cours

    • Cours des 11 et 18 Mars.
  • Arrangements de droites; Support de cours

    • Cours du 25 Mars.
  • Triangulations et subdivisions; Support de cours

    • Cours des 1, 8 Avril.
  • Recherche orthogonale et simpliciale; Support de cours

    • Cours du 15 Avril : partiel

    Cours du 22 Avril
  • Recherche simpliciale

    • Cours des 13, 20 et 27 Mai.
  • Polyédres, cônes et polytopes : théorèmes de séparations, polarité, treillis des faces d'un polyèdre, polytopes simples/simpliciaux, polytopes cycliques, arrangement d'hyperplans, relation d'Euler-Poincaré, graphe d'un polytope, bonnes orientations acycliques, relation de Dehn-Sommervile, théorème de la borne supérieure, borne sous-exponentielle sur le diamètre du graphe d'un polyèdre, la méthode du simplexe pour la programmation linéaire. Support de cours

    • Cours du 03 Juin : examen.

    • Last modified: Fri Feb 25 18:54:32 CET 2005