École Jeunes Chercheurs en Informatique Mathématique 2013

Perpignan, du 8 au 12 avril 2013

CNRS INRIA
GDR IM
LIRMM DALI ED305
UPDV et Fondation UPVD CG66

Programme

Accueil-inscription des participants

L'accueil-inscription des participants est prévu le dimanche 7 avril 2013 de 17h à 19h, à l'Hotel Ibis : Un apéritif de bienvenu sera servi à partir de 19h.

Programme de la semaine

Cette année, l'école permettra d'aborder les thèmes suivants.
  1. Complexité et algorithmes paramétrés - Christophe Paul
  2. Programmes, preuves et fonctions : le ménage à trois de Curry-Howard - Lionel Vaux et Emmanuel Beffara
  3. Analyse géométriques des données - Mariette Yvinec, Frédéric Chazal et Jean-Daniel Boissonnat
  4. Matroïdes et matroïdes orientés - Jorge Ramirez et Emeric Gioan
  5. Introduction à la théorie de l'interprétation abstraite et application à la validation de codes numériques - Matthieu Martel
  6. Sage pour les applications - Thierry Monteil
Les jeunes chercheurs seront également invités à exposer leurs travaux. Le programme est ici.

Une version non définitive du programme de l'école est accessible ci-dessous.






Complexité et algorithmes paramétrés
La théorie de la complexité paramétrée permet d'étudier la difficulté de problèmes algorithmiques de manière plus précise que la théorie de la complexité classique. Cette théorie permet ainsi d'expliquer pourquoi certains problèmes NP-Complet (e.g. Vertex Cover) sont plus faciles que d'autres (e.g. clique) à résoudre exactement. Pour cela, l'idée principale est d'analyser la complexité d'un problème en fonction de la taille de l'instance, dénoté n, et d'un (ou plusieurs) paramètre, dénoté k. Un problème est dit FPT (Fixed Parameter Tractable) pour un paramètre k, s'il peut être résolu par un algorithme de complexité f(k).poly(n).

La complexité et les algorithmes paramétrés constituent un champ de recherches très actif depuis leur formalisation dans les années 90 par Downey et Fellows. En particulier de nouvelles techniques algorithmiques ont été développées dans le contexte de la complexité paramétrée et les progrès observés ces dernières années sont impressionnants.

Dans ce cours, nous consacrerons la première partie (1h30) à une introduction générale du domaine et des techniques. Cette introduction sera accessible à tous les étudiants ayant les notions de bases en complexité classique, théorie des graphes et algorithmiques. Le reste du cours se concentrera sur deux branches importantes de la complexité paramétrée.
  1. Théorie de la kernelisation (borne inférieures et supérieures).
  2. Conséquences algorithmiques de la théorie des mineurs de graphes et décomposition arborescente.
Ces présentations seront complétées par des séances d'atelier-groupe de travail et des travaux pratiques d'implémentation en Sage.

Orateur Transparents de cours : [Partie 1] [Partie 2] [Partie 3]


Programmes, preuves et fonctions : le ménage à trois de Curry-Howard
La correspondance de Curry-Howard promeut le point de vue selon lequel démonstrations et programmes sont des objets de même nature, l'élimination des coupures étant le pendant logique de l'exécution. L'étude des invariants des processus de calcul est le but des sémantiques dénotationnelles: en interprétant les types (formules logiques) comme des espaces structurés et les programmes (démonstrations) comme des morphismes entre ces espaces, elles capturent des propriétés essentielles du calcul. Une lecture éclairée de telles sémantiques a permis l'introduction de systèmes de déduction jouissant à la fois de bonnes propriétés logiques et d'interprétations calculatoires fécondes.

La première partie sera une introduction à cette correspondance, à partir de la logique minimale (lambda-calcul, déduction naturelle, interprétation de Brouwer-Heyting-Kolmogorov...) qui en illustre les idées fondatrices. On introduira la sémantique dénotationnelle au moyen du modèle relationnel, modèle étonnamment simple qui révèle déjà une structure riche. En regardant de près cette sémantique et son rapport avec le comportement du lambda-calcul, on verra comment apparaissent la logique linéaire, ses règles de déduction et sa procédure de normalisation.

La deuxième partie présentera des idées plus récentes autour de la notion de sémantique quantitative. Celle-ci permet de renouer avec l'intuition à l'origine de la logique linéaire: les programmes fonctionnels sont des fonctions non seulement continues, mais même analytiques, c'est-à-dire, décomposables en séries entières. Cette idée n'est d'ailleurs pas sans rapport avec le modèle relationnel.

La troisième partie montrera comment l'approche s'étend au-delà du calcul fonctionnel et de la logique minimale. Le cas des mécanismes de contrôle en programmation impérative est assez établi, bien que la recherche y soit active. D'autres aspects sont plus exploratoires: effets, calcul concurrent, parallélisme; là les sémantiques existent (calculs de traces, structures d'événements) mais les logiques sont moins bien comprises. On évoquera les éclairages nouveaux qu'apportent les approches quantitatives à ces questions.

Orateurs Transparents de cours : [Parties 1, 2, 3 et 4]


Analyse géometrique des données
Dans les domaines scientifiques et techniques contemporains, les données pertinentes se présentent de plus en plus souvent sous la forme de nuages de points plongés dans des espaces de grande dimension. Dans ces espaces, les nuages de points s'organisent autour de structures géométriques qui reflètent les propriétés du système étudié. La détection et la compréhension de ces structures est devenue une composante essentielle de l'analyse des données. Une nouvelle approche, basée sur l'étude géométrique et topologique des nuages de points a récemment vu le jour. Il s'agit de développer en grande dimension des méthodes offrant des garanties analogues à celles qui ont fait le succès de la géométrie algorithmique. Cette approche est développée notamment dans le projet Européen CG-Learning (Computational Geometry Learning).

Ce cours présentera les bases théoriques et algorithmiques de l'analyse géométrique des données :
  • Structures de base et algorithmes approchés,
  • Fonction distance et théorie de l'échantillonage,
  • Reconstruction des variétés plongées dans des espaces de grandes dimensions,
  • Inférence topologique et persistence.

Orateurs Transparents de cours : [Partie 1] [Partie 2] [Partie 3]


Introduction à la théorie des matroïdes et des matroïdes orientés
Un matroïde - mot dérivé de "matrice" - peut être défini comme une structure combinatoire obtenue en retenant les principales propriétés ensemblistes de la dépendance linéaire dans les espaces vectoriels. Un matroïde est ainsi naturellement associé à un ensemble fini de points, ou à un ensemble fini (arrangement) d'hyperplans. Cependant les propriétés définissant les matroïdes ne caractérisent pas les espaces vectoriels : les matroïdes constituent une classe d'objets beaucoup plus vaste. D'autres exemples naturels de matroïdes peuvent être construits à partir des graphes, des groupes, des corps, des ensembles ordonnés, etc. donnant lieu à une grande variété d'applications, particulièrement en optimisation discrète.

Alors qu'un matroïde capture les relations d'incidence (alignement, coplanarité, etc.) entre des points de l'espace, un matroïde orienté est une structure combinatoire proche qui capture - en plus - les relations de convexité entre ces points, en prenant cette fois en compte les signes dans les relations de dépendance linéaire. Les matroïdes orientés forment ainsi un langage naturel pour décrire les positions relatives de points dans l'espace, ou de faces délimitées par des hyperplans, les relations entre cycles et cocyles dans les graphes orientés, etc.
Un théorème majeur indique que les propriétés définissant les matroïdes orientés caractérisent cette fois des objets topologiques : les arrangements de pseudohyperplans.

Les applications des matroïdes et matroïdes orientés ont d'abord été essentiellement situées en combinatoire et dans les domaines proches : graphes, optimisation discrète, programmation linéaire, polytopes...
Depuis une vingtaine d'années des applications apparaissent dans des domaines très divers : stratification des grassmanniennes en géométrie algébrique, triangulations en géométrie discrète...

Le premier exposé (Jorge Ramirez-Alfonsin, 2h) traiterait des matroïdes, en mettant a priori l'accent sur : définitions (indépendants, bases, rang...), propriétés fondamentales (algorithme glouton...), objets classiques (polytope des bases, polynôme de Tutte).

Le second exposé (Emeric Gioan, 2h) traiterait des matroïdes orientés, en mettant a priori l'accent sur : définitions (combinatoire et topologique), propriétés fondamentales de dualité (extensions de la dualité des graphes, et du lemme de Farkas en programmation linéaire réelle).

Orateurs Transparents de cours : [Partie 1] [Partie 2] [Parties 3 et 4 disponibles sur demande]


Introduction à la théorie de l'interprétation abstraite et application à la validation de codes numériques
L'interprétation abstraite est une théorie décrivant comment calculer automatiquement des invariants sur des programmes. Elle est notamment utilisée pour prouver l'absence de certaines erreurs dans des logiciels de grande taille dans des contextes industriels variés allant des applications .NET aux codes embarqués critiques de l'aéronautique. Les propriétés concernées sont nombreuses et concernent par exemple le comportement numérique des variables (domaines, trajectoires, relations numériques entre variables), le calcul de pires temps d'exécutions (WCET), la recherche d'alias (pointeurs vers une même référence) ou encore le calcul de propriétés sur des systèmes concurrents (topologie des communications, tailles de buffers, interblocages, etc.)

Ce cours constitue une introduction à la théorie de l'interprétation abstraite. Nous présenterons les concepts fondamentaux de la théorie : calcul de propriété et notion de domaine abstrait, correspondance entre les sémantiques concrètes et abstraites, calcul efficace de point fixe dans l'abstrait. Nous illustrerons ces notions par l'utilisation de domaines numériques simples, pas ou faiblement relationnels. Enfin, nous nous pencherons sur un domaine d'application particulier concernant la précision numérique des calculs en nombres flottants (détection des sources d'erreurs et techniques d'amélioration de la précision par réécriture d'expressions).

Orateur Transparents de cours : [Parties 1 et 2]


Présentations des jeunes chercheurs


Lundi 08/04/2013 de 14h à 16h - Graphes et ordonnancement
  • 14h00 Sur une généralisation des graphes excluant les configurations de Truemper, DIOT Émilie     [PDF]
  • 14h10 Clique-Stable séparation dans les graphes et conjecture d'Alon-Saks-Seymour, LAGOUTTE Aurélie     [PDF]
  • 14h20 Mise à jour locale de graphes aléatoires, DUVIGNAU Romaric     [PDF]
  • 14h30 Coloration localement irrégulière des arêtes d'un graphe, BENSMAIL Julien     [PDF]
  • 14h50 Isotopies de graphes sur les surfaces, DE MESMAY Arnaud     [PDF]
  • 15h10 On the complexity of scheduling checkpoints for computational workflows, ZAIDOUNI Dounia     [PDF]
  • 15h30 Energy-aware scheduling, AUPY Guillaume     [PDF]


Lundi 08/04/2013 de 17h35 à 18h45 - Logique, preuve et aléa
  • 17h35 Formal proof and Mathematics, LELAY Catherine     [PDF]
  • 17h55 La règle de coupure dans les preuves circulaires, FORTIER Jérôme     [PDF]
  • 18h15 An analysis of digital search trees for a general source, HUN Kanal     [PDF]
  • 18h35 A general framework for the realistic analysis of sorting and searching algorithms, NGUYEN THI Thu Hien     [PDF]


Mardi 09/04/2013 de 11h45 à 12h45 - Géométrie et cryptographie
  • 11h45 Knot Segmentation in 3D Images of Wood, KRÄHENBÜHL Adrien     [PDF]
  • 11h55 Robust and efficient homology inference, BUCHET Mickaël     [PDF]
  • 12h15 Alice au pays de non-linéarité, CAULLERY Florian     [URL]


Mercredi 10/04/2013 de 10h15 à 11h30 - Session posters
  • Concurrence efficace avec entrées/sorties asynchrones, BOUTIER Matthieu
  • Reconstruction garantie pour la super-résolution d'images, GRABA Fares
  • Synthesis of Arithmetic Expressions for the Fixed-Point Arithmetic : The Sardana Approach, IOUALALEN Arnault
  • 10h15 Génération aléatoire d'arbre unaire-binaire "à la Rémy", JACQUOT Alice
  • Étude de la propagation des erreurs d'arrondi dans un code d'hydrodynamique parallèle, MONTAN Sethy
  • État des lieux : attaques passives, courbes elliptiques, ROBERT Jean-Marc
  • Étude de stratégies pour de la synthèse de code avec compromis performances-précision, THÉVENOUX Laurent


Jeudi 11/04/2013 de 11h45 à 12h30 - Combinatoire
  • 11h45 Counting smaller trees in the Tamari order, CHATEL Grégory     [PDF]
  • 11h55 Génération aléatoire "uniforme" de mots avec motifs interdits et maximisation de l'entropie, MARCOVICI Irène     [PDF]
  • 12h15 Fonctions symétriques sur les mots et théorème de Pólya, CHOURIA Ali     [PDF]


Vendredi de 14h à 15h45 - Arithmétique
  • 14h00 Réduction des circuits arithmétiques, TAVENAS Sébastien     [PDF]
  • 14h10 Factorisation des polynômes lacunaires, GRENET Bruno     [PDF]
  • 14h30 Synthesis of fixed point programs: the case of matrix multiplication, NAJAHI Amnie     [PDF]
  • 14h50 Génération de nombres pseudo-aléatoires basée sur des fonctions chaotiques, FRANCOIS Michaël     [PDF]