Journée des deux fédérations

Le pôle SN et les deux fédérations (NormaSTIC et NorMath) organisent
une journée commune le 18 octobre au Havre Les présentations auront lieu en salle de conférences de l’ISEL, quai Frissard. Le repas aura lieu au PIL (Pôle Ingénieur et Logistique) qui jouxte l’ISEL. Le programme prévisionnel est le suivant:

9h-12h: Demis journée des deux fédérations avec deux exposés
scientifique de chercheurs invités.
Détail:

• 9h-9h30 accueil et présentation journée
• 9h30-10h30 Isomorphisme de sous-graphes : théorie vs pratique (Christine Solnon)

  Le problème d’isomorphisme de sous-graphes (SIP) consiste à décider s’il existe une copie d’un graphe « motif » dans un graphe « cible ». En théorie, le SIP est NP-complet et ne peut être résolu par un algorithme polynomial (à moins que P=NP). En pratique, il existe des algorithmes capables de résoudre très rapidement le SIP pour de « gros » graphes contenant plusieurs milliers de sommets. Aussi pouvons-nous nous demander s’il existe encore des instances réellement difficiles du SIP. Dans cet exposé, nous apporterons des éléments de réponse à cette question.
  Dans un premier temps, nous montrerons comment générer de façon aléatoire des instances du SIP dont on peut contrôler et prédire la difficulté. En particulier, nous montrerons comment générer de petites instances (avec 30 sommets dans le motif et 200 dans la cible, par exemple) qui ne sont résolues par aucun algorithme existant en un temps raisonnable. Nous comparerons les performances de différents algorithmes sur ces instances. Nous étudierons tout particulièrement les performances de deux familles d’algorithmes : les algorithmes développés dans la communauté « pattern recognition », tels que VF2, VF3 et RI, et les algorithmes développés dans la communauté « Constraint Programming », tels que LAD et Glasgow.
  Nous élargirons ensuite cette étude en considérant des instances provenant de 8 benchmarks différents. Nous montrerons que le temps de résolution d’une instance ne dépend pas de sa taille et que certaines petites instances provenant d’applications réelles ne sont résolues par aucun algorithme. Nous montrerons également que si VF2, VF3 et RI sont capables de résoudre très rapidement un grand nombre d’instances faciles, pour lesquelles LAD et Glasgow sont plus lents, ils ne sont pas capables de résoudre certaines instances qui sont rapidement résolues par LAD et Glasgow. Enfin, nous montrerons que nous pouvons facilement combiner plusieurs algorithmes afin de tirer partie de cette complémentarité.

• 10h30-11h pause café
• 11h-12h Hommage à Patrick Dehornoy (Gérard Grancher et Victoria Lebed)
• 12h-14h: Buffet repas pendant une session poster présentant les travaux
  des doctorants en 2ème et 3ème années financés par la Région.

14h-17h: Demis journée du pôle SN. Les projets RIN Recherche financés en 2017 et 2018 seront présentés.

Détail:

• 14h-14h30 : présentation des projets RIN 2017
• 14h30-15h30 : présentations de projets RIN 2018 (partie I)
• 15h30-16h: pause café
• 16h-17h : présentations de projets RIN 2018 (partie II)

Les déplacements sont pris en charge par les fédérations et des co-voiturages seront organisés. Nous comptons sur votre présence pour cette journée importante pour notre communauté.
Lien Qwant Maps vers l’ISEL