CR-04 : Décompositions arborescentes et algorithmes FPT

Guillaume Hanrot

Programme de l’UE

Une grande majorité des problèmes en algorithmique des graphes sont NP-difficiles, comme par exemple le problème du voyageur de commerce. En revanche, la plupart de ces problèmes deviennent polynomiaux lorsque les graphes considérés sont acycliques, e.g. des arbres. Une manière de contourner la difficulté est de structurer le graphe en le décomposant de façon arborescente. L’objectif de ce cours est de présenter ces techniques, dont notamment la désormais incontournable notion de tree-width, ou largeur arborescente, introduite par Robertson et Seymour. Une introduction aux algorithmes FPT (fixed parameter tractable), qui découlent de cette théorie, sera aussi proposée.

  1. Introduction des notions de largeur arborescente (tree-width) et de ses nombreux dérivés, dont la path-width et la branch-width. Résultats de base, jusqu’au Grid-Minor Theorem.
  2. Programmation dynamique sur les graphes de largeur arborescente bornée.  Ce résultat est le point de départ du chapitre suivant.
  3. Introduction à la complexité paramétrée.
  4. Notion de Noyau et d’algorithme de compression.
  5. Le théoreme des mineurs de graphes. Avec son corollaire principal: Pour toute classe de graphe close par mineur, il existe un algorithme polynomial qui décide si un graphe appartient à cette classe ou pas. Nous présenterons ce résultat, certainement le plus difficile et le plus profond de la théorie des graphes. Une application directe est par exemple qu’il est polynomial de décider si un graphe se plonge sur une surface donnée. La largeur arborescente et le routage (linkage) sont les clés de ce résultat.
  6. Graph Searching. La notion de largeur arborescente est interprétable en termes de nombre minimum d’agents requis pour rechercher un fugitif dans un réseau. Les stratégies gagnantes des deux camps suggèrent une dualité.
  7. Certificat dual de la tree-width. Introduction de la notion de bramble et autres certificats des mesures de largeur arborescente.
  8. Introduction de la notion de clique-width de Courcelle. Une mesure de complexité qui capture plus de graphes que la tree-width, et stable par complémentation. Equivalence avec la notion de rank-width de Seymour et Oum.

Prérequis. Le cours s’adaptera au public.

Calendrier prévisionnel. 14/09, 17/09, 21/09, 24/09, 28/09, 01/10, 05/10, 12/10, 15/10, 26/10, 5/11, 9/11

Modalités d’examen. Examen écrit et oral.

Bibliographie

  • Une petite Introduction aux mineurs de graphes, de László Lovász.
  • Le Graph Theory, de Reinhard Diestel, est à conseiller. Le chapitre 12, traite de la ‘tree-width’.
  • Le Parameterized Complexity Theory, de Jorg Flum et Martin Grohe, est une bonne réference pour les algorithmes FPT.

Pour les plus courageux, la série des Graph Minors de I à XXIII, de Neil Robertson et Paul Seymour, est intéressante à parcourir, pour se rendre compte de la difficulté du résultat.

Lien sur la page du cours

Intervenant

  • Stéphan Thomassé, Pr ENS Lyon

CR-11 – Réseaux avancés : architectures et protocoles

Guillaume Hanrot

Programme du cours

  • Architecture de l’internet du futur (réseaux/équipements) : evals de perfs, simulation, modélisation
  • Introduction à la simulation à événements discrets (2 x 2h)
  • Cas pratique d’un routeur (2 x 2h)

Nouveaux protocoles réseaux : services/middleware, QoS, réseaux verts

  • Réseaux autonomes et programmables (2h)
  • Réseaux fiables (2h)
  • Réseaux verts (2 x 2h)
  • Communication entre processus (par message (socket), par mémoire partagée (RPC)) (3h)
  • Liens entre middleware (MPI), réseaux rapides et infrastructures (3h)

Planning prévisionnel :

20/09, 27/09, 4/10, 11/10, 18/10, 25/10

Intervenants

  • Thomas Begin, MCF UCBL
  • Laurent Lefèvre, CR INRIA

ER05 (2012) : algorithmique distribuée

Guillaume Hanrot

Intervenants : Maria Potop-Butucaru, Sébastien Tixeuil

Dates : 6 au 10 février 2012

Résumé de l’école de recherche :

L’algorithmique distribuée est l’algorithmique des réseaux et des systèmes distribués. Dans un algorithme distribué, les machines qui participent au calcul collaborent à une tâche commune malgré des informations qui ne peuvent s’échanger que localement, malgré des vitesses de calcul et de communication qui diffèrent parfois significativement, malgré des connaissances sur le système global qui ne sont que parcellaires, malgré des pannes de certaines de ces machines qui surviennent inopinément, malgré des attaques sur des machines critiques qui surviennent au pire moment, malgré des machines qui vont et qui viennent au gré de la volonté de leurs utilisateurs. En  somme, il s’agit pour ces machines de collaborer malgré l’adversité.

L’objectif du cours est de proposer un panorama des recherches récentes en algorithmique distribuée, tant du point de vue de la tolérance aux fautes et aux attaques (auto-stabilisation, comportements Byzantins, etc.), que de celui de la coordination distribuée (cohortes de robots, agents mobiles, etc.).

Voir la page de l’école de recherche.

Correspondant local : Eddy Caron

ER06 (2012) : Introduction à l’image de synthèse

Guillaume Hanrot

Intervenants : Sylvain Lefebvre (INRIA Nancy-Grand Est), Bruno Lévy (INRIA Nancy Grand-Est).

Thème :Ce cours introduit les algorithmes fondamentaux utilisés en synthèse d’images, avec un accent en particulier sur le calcul rapide pour l’affichage temps réel (simulateurs, pré-visualisation, jeux). Les techniques de lancer de rayon et rendu projectif seront abordées, avec quelques excursions vers des domaines actifs de recherche comme la modélisation géométrique, le placage de texture et la génération procédurale de contenu. Le cours comprend également une introduction à la programmation des cartes graphiques parallèles via OpenGL et OpenCL.

Date : 13/02-17/02/2012

Emploi du temps :

Lundi 13/02 : 14h-17h30 cours

Mardi 14/02 9h-12h30 cours, 14h-16h cours

Mercredi 15/02 14h-17h30 cours

Jeudi 16/02 9h-13h TD

Vendredi 9h-12h30 cours, 14h-18h TD

Correspondant local : Guillaume Hanrot

Poste de professeur 27ème section

Guillaume Hanrot

Campagne d’emploi Département Informatique / Laboratoire LIP ENS 2011

Poste de professeur 27ème section

Octobre 2010

Le DI et le LIP recrutent une, ou un, professeur en informatique pour la rentrée 2011.

Contact enseignement : eric.fleury@ens-lyon.fr
Contact recherche : gilles.villard@ens-lyon.fr

Recherche. La, ou le, professeur viendra conforter les activités de recherche du LIP dans le cadre du projet élaboré pour le quadriennal du laboratoire. Ce projet s’inscrit dans l’étude et l’anticipation du monde numérique futur et de ses fondements théoriques, dans l’optique d’inventer de nouveaux concepts et méthodes informatiques et de devancer leurs répercussions sur les autres sciences. Les recherches s’organisent selon deux axes complémentaires et transverses aux huit équipes :

  • modèles et méthodes en informatique mathématique ;
  • défis des futures architectures de calcul et de communication.

La machine (ordinateur, infrastructure), aussi bien entité abstraite qu’objet physique, est le centre des études. Depuis toujours au LIP les recherches s’étendent du fondamental au développement, ce qui est une source majeure d’invention. Les ouvertures du laboratoire, qui sont riches et traditionnelles vers les mathématiques, vont en outre vers les industries de communication et de semi-conducteurs, les sciences numériques, la modélisation et les sciences du vivant. La candidate ou le candidat se rapprochera d’une des équipes du laboratoire, et pourrait amener une nouvelle thématique, en harmonie avec celles du projet du laboratoire. Les candidates et candidats brillants de tous profils sont encouragés à candidater ; le choix final sera dicté en premier lieu par la qualité du dossier. Ce recrutement est très largement ouvert ; les candidatures externes françaises et étrangères seront privilégiées.

Enseignement. Le service d’enseignement s’effectuera au sein du Département Informatique de l’ENS de Lyon au sein de la licence (L3) et du master (M1 et M2) dans la spécialité Informatique Fondamentale. L’une des caractéristiques emblématiques reste que cette formation dispensée à l’ENS Lyon est résolument une formation par et pour la recherche en informatique. Cet engagement dans la formation à la recherche d’excellence se reflète dans l’organisation des enseignements. Les priorités du campus Mérieux amènent par ailleurs des enjeux et défis stratégiques importants autour de la complexité et de la modélisation, le Département Informatique de l’ENS de Lyon s’inscrit dans ce contexte local en soutenant des formations inter-disciplinaires.
On s’attachera à ce que les enseignements soient connexes au projet/thématique de recherche des candidats et se placent dans l’un des trois parcours de la spécialité informatique fondamentale / informatique mathématique ,  algorithmique,  modèles et optimisations pour les infrastructures émergentes  ou en lien avec le parcours  modélisation des systèmes complexes . La spécialité Informatique Fondamentale est une formation complète avec d’une part des enseignements donnant les bases des fondamentaux d’une solide culture généraliste en informatique et d’autre part des enseignements plus spécialisés offrant une réelle introduction à la recherche. Le parcours systèmes complexes s’appuie à la fois sur les masters d’informatique fondamentale, de mathématiques et de physique de l’ENS Lyon. Les capacités à apporter des compétences complémentaires de celles existant actuellement au sein du département d’informatique et à proposer la création de nouveaux enseignements seront particulièrement appréciées.
La, ou le, professeur recruté devra faire valoir des capacités de gestion d’organisation et prendre des responsabilités administratives dans la gestion du département Informatique de l’ENS de Lyon.

Rappel.  La procédure de recrutement en France inclut une étape préliminaire de qualification, qui doit être accomplie avant que le poste ne soit effectivement ouvert. Tous les candidats intéressés, même potentiellement, devraient commencer ce processus dès que possible. Voir la version anglaise de cette page pour les détails sur la procédure.