English 2 (2nd semester, 3 ECTS)

Eric Thierry

Cours : Véronique Rancurel, Hélène Windish, Karen Rizo, David Alzapiedi (Veronique.Rancurel)

Ce module  est centré sur l’expression orale et la compréhension orale. Présentation orale, avec transparents, d’un article scientifique (simulation de colloque), apprentissage des techniques et stratégies de communication, anglais du quotidien . Entraînement à la prise de notes à partir de documents vidéo authentiques avec compte rendu écrit.

Performance evaluation

Eric Thierry

Description :

This course presents basic tools for qualitative and quantitative performance evaluation of communication and computing systems. It is a
theoritical course but some real systems will be analyzed such as communication networks. This course will also present an introduction to
statistics and some discussions about the experimental method.

Plan of the course :

  1. Short refresher about probability prerequisites
  2. Simulation schemes and random generation
  3. Discrete time Markov chains
  4. Continuous time Markov chains and queuing theory
  5. Markovian decision process
  6. Petri nets
  7. Statistics

Prerequisites :

A classical but strong background in probability is necessary (like some knowledge about finite state Markov chains or convergence of random  variables).

People in charge of the course:

  • Eric Thierry (a web page dedicated to the course will be made available from E. Thierry’s page).
  • Julien Herrmann

ER-02 : Graphs and Combinatorial Optimization

Eric Thierry

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

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 du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

  • méthodes inductives (Thomassen)
  • déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

  • constructions
  • méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

  • méthodes algébriques (Borsuk-Ulam)
  • méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

  • Introduction du concept de graphes parfaits
  • Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
  • utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
  • Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
  • Exemples de graphes triangulés: graphes d’intervalles, graphes “splits”.

Cours 2 (Vendredi 9h30-12h45):

  • Relation entre nombre chromatique et orientation (Gallai-Roy)
  • graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
  • théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

  • Flot maximum
  • Algorithme “Push-Relabel” et flots paramétriques.
  • Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

  • Flot de coût minimum.
  • Les k-flots non nuls.
  • Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

  • Quelques modèles d’optimisation combinatoire.
  • Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

  • Algorithme de l’intersection de deux matroïdes.
  • Applications.

Cours 3 (Mercredi 14h-16h)

  • Algorithme de couplage de cardinalité maximum (Edmonds).
  • Théorème de caractérisation lié (Tutte-Berge).
  • Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)