logo CNRS
logo Universite de Savoie

Programme de l'école

Cours

Responsable et intervenants

Cours

Laurent Vuillon (LAMA, Chambéry);
Jacques-Olivier Lachaud (LAMA);
Thomas Fernique (LIF, Marseille)

Combinatoire des mots et géométrie discrète

Philippe Elbaz-Vincent (Institut Fourier, Grenoble);
Marc Joye (Thomson R&D)

Ingénierie cryptographique: de la recherche académique à la pratique industrielle

Hugo Gimbert (LABRI, Bordeaux);
Laurent Doyen (LSV, ENS Cachan)

Jeux et vérification

Christophe Raffalli (LAMA, Chambéry);
Alexandre Miquel (LIP, ENS Lyon)

Réalisabilité: des preuves à la programmation

Philippe Flajolet (INRIA Rocquencourt);
Brigitte Vallée (GREYC, Caen)

Analyse d'algorithmes probabilistes: méthodes et applications (transparents 1, 2)

Programme indicatif

Horaires Lundi Mardi Mercredi Jeudi Vendredi
8h30 – 10h30 Combinatoire des mots et géométrie discrète Ingénierie cryptographique: de la recherche académique à la pratique industrielle Jeux et vérification Réalisabilité: des preuves à la programmation Analyse d'algorithmes probabilistes: méthodes et applications
10h30 – 11h Pause café
11h – 13h Combinatoire des mots et géométrie discrète Ingénierie cryptographique: de la recherche académique à la pratique industrielle Jeux et vérification Réalisabilité: des preuves à la programmation Analyse d'algorithmes probabilistes: méthodes et applications
Déjeuner
14h30 – 16h Exposés des participants Exposés des participants Exposés des participants Présentation du GDR IM
puis
Exposés des participants
16h – 16h30 Pause café Départ du bus à 16h30 précises Pause café
16h30 – 18h Exposés des participants Ski de fond + Restaurant Exposés des participants Exposés des participants

Lundi

14h30: Matthieu Simonet, Pavages dans les plans discrets
En combinatoire des mots, les plans discrets peuvent être représentés par des mots bidimensionnels qui sont la généralisation à 2 dimensions des mots sturmiens. L'étude et le pavage des mots sturmiens par les mots de retour peuvent-ils être transposé à la dimension 2 ?


15h00: Sébastien Labbé, Sur le nombre maximal de façons de paver le plan par translation
Nous présenterons la solution d'une conjecture de Brlek, Dulucq, Fédou, Provençal (2007) énonçant qu'une tuile possède au plus deux factorisations en carré, ou autrement dit, qu'elle ne peut paver le plan en plus de deux manières distinctes en ayant quatre voisins. Ce travail est commun avec Alexandre Blondin Massé et Ariane Garon.




15h30: Antoine Vacavant, Reconstruction géométrique et topologique d'objets irréguliers : algorithmes et applications
Les systèmes d'acquisition de données image en deux ou trois dimensions fournissent généralement des données organisées sur une grille régulière, appelées données discrètes. Que ce soit pour la visualisation ou l'extraction de mesures, la géométrie discrète définit les outils mathématiques et géométriques pour de nombreuses applications. Dans cet exposé, je présenterai comment adapter diverses notions de la géométrie discrète aux grilles irrégulières isothétiques. Ce modèle de grille permet de représenter de manière générique les structurations d'images en pixels ou voxels de taille et de position variables : les grilles anisotropes, très répandues en imagerie médicale, les décompositions hiérarchiques telles que quadtree/octree, les techniques de compression comme le run length encoding, etc. De plus, je présenterai l'extension à cette représentation d'une méthodologie largement étudiée pour analyser les formes discrètes: la reconstruction d'objets binaires complexes. Je montrerai enfin comment ces outils sont employés dans diverses applications : la distinction de caractères ambigus dans un outil de reconnaissance de plaques minéralogiques, l'approximation dynamique de courbes implicites planaires et l'analyse d'objets discrets bruités.


16h30: Pascal Vanier, Périodes dans les pavages
Les pavages sont un modèle qui apparait à la fois comme un système dynamique et comme un modèle de calcul. Nous caractérisons les ensembles de périodes qu'un jeu de tuiles peut donner et prouvons qu'ils correspondent exactement aux langages dans la classe de complexité NSPACE(n).


17h00: Bruno Grenet, Difficulté du résultant multivarié
La résolution de systèmes polynomiaux, en particulier homogènes, est utile dans de nombreux domaines de l'informatique. La version décisionnelle du problème (les polynômes ont-ils une racine commune non nulle ?) est NP-difficile. Cependant, s'il y a strictement moins de polynômes que de variables, il existe toujours une racine non nulle et le problème est trivial. Un cas intéressant est donc celui d'un système carré, avec autant de polynômes que de variables. Dans ce cas, la théorie de l'élimination fournit un outil pour étudier l'existence de racines, le résultant multivarié, qui pourrait aider à résoudre le problème. Cependant, nous verrons que dans ce cas aussi, le problème reste NP-difficile, que les polynômes soient à coefficients entiers ou dans un corps fini.


17h30: Yann Strozecki, Interpolation de polynômes : le point de vue de l'énumération
L'étude de problème d'énumération conduit à s'intéresser au délai entre deux solutions comme mesure de complexité, car le temps total est généralement exponentiel. On revisite le problème d'interpolation de polynômes multivariés donnés comme des boites noires avec ce point de vue, c'est à dire qu'on veut énumérer tous les monômes d'un polynôme avec un délai "raisonnable" entre deux monômes. On propose pour ce faire deux algorithmes aux caractéristiques différentes qui résolvent ce problème quand les polynômes sont multilinéaires. Pour les degrés supérieurs, il existe des algorithmes mais qui ne sont pas aussi performants.


Mardi

14h30: Tarik Kaced, Comment partager un secret
Une introduction au partage de secret (secret sharing). Un schéma de partage de secret est une méthode de distribution de parts d'un secret à un ensemble de participants. Les groupes de participants autorisés peuvent retrouver le secret en réunissant leurs parts, tandis que les autres groupes ne peuvent obtenir aucune information. Par exemple, le schéma de Shamir réalise une structure d'accès dite à seuil ou les groupes autorisé sont les sous-ensembles d'au moins m participants. Les principales techniques et problèmes ouverts seront abordées ainsi que des exemples.


15h00: Laurent Vallet, Protection d'Identités par Anonymat
Aujourd'hui l'émergence des réseaux sociaux et du tout numérique mine notre capacité à protéger notre vie privée. Ainsi nous faisons appel à des techniques d'anonymisation des communications pour donner une réponse efficace à ces problèmes de sécurité dans les réseaux de communication. Nous commencerons par décrire le monde de l'anonymat dans les systèmes communiquants pour préserver les identités des acteurs et nous verrons que les outils cryptographiques sont utilisés. Ensuite nous présenterons notre solution qui garanti l'anonymat grâce à la combinaison de protocoles de routage correctes, de sélections de chemins de routage et de diffusions de clés hiérarchiques sur ces chemins.


15h30: Thu-Hien To, Restricted-level phylogenetic networks are constructable from a dense triplet set in polynomial time
Let X be a taxon set and T be a set of triplets on X, we want to construct phylogenetic networks which are consistent with all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in each of its biconnected component. There are polynomial algorithms to construct level-0,1,2 networks. In this paper, we show that it is possible to construct level-k networks, even the ones which contain the minimum number of hybrid vertices, for any k fixed in polynomial time.


Mercredi

14h30: Pierre Coucheney, Optimisation dans les jeux de potentiel
Les jeux de potentiel permettent de modeliser des systèmes distribués dans lesquels l'information locale des agents est corrélée avec la fonction de potentiel. Dans ces systèmes distribués, il arrive souvent que l'on cherche à maximiser ce potentiel (par exemple un débit global pour les réseaux). Dans le cas de jeux de potentiels finis, des dynamiques de type Gibbs sampling ont été proposées pour atteindre ce maximum. Cependant, cette technique nécessite: 1- De ne pas avoir de variations sur les valeurs du jeu (par exemple si celles ci sont des mesures). 2- D'être complètement désynchronisées. 3- Pour chaque agent, de tester toutes ses actions à chaque fois que c'est son tour. Nous proposons une méthode, basée sur des dynamiques continues de points intérieurs, qui s'affranchit de ces contraintes.


15h00: Mathieu Chapelle, Parameterized Complexity of Domination Problems on Bounded Tree-Width Graphs
Domination problems are amongst the classical types of problems well-studied in graph theory. This concept, introduced by J.A. Telle, generalizes several variants of graph domination problems. A generalized domination problem is characterized by two sets of integers which restrict the number of neighbors which can be in the dominating set, for any vertex of the input graph. In this presentation, we explore the boundary between fixed-parameter tractability and W-hardness of these problems on bounded tree-width graphs. In particular, we show that if the two sets are periodic, then the corresponding generalized domination problem is fixed-parameter tractable on bounded tree-width graphs.


15h30: Nicolas Gast, Une approche asymptotique pour l'étude des systèmes à grande échelle
La modélisation de systèmes informatiques complexes à l'aide de modèles probabilistes pose souvent un problème de dimension. Quand le nombre d'objets composant le système grandit, le nombre d'états nécessaires pour représenter le système explose. A travers cet exposé, nous verrons comment s'affranchir de cette explosion combinatoire en étudiant le "système limite" quand le nombre d'objets tend vers l'infini. Nous verrons comment ce système limite permet d'obtenir d'évaluer et d'optimiser les performance du système initial. Nous nous intéresserons en particulier à l'étude de la répartition de charge dans des clusters de calcul.


16h30: Xavier Pujol, Algorithmes de crible pour SVP
Un réseau est un sous-groupe discret de $\mathbb R^n$, qui peut être décrit comme l'ensemble des combinaisons linéaires entières d'une base d'au plus n vecteurs. Le problème du plus court vecteur (SVP) consiste à calculer un plus court vecteur non nul d'un réseau à partir d'une base de ce réseau. Ce problème est difficile, plus précisément NP-complet sous des réductions randomisées, et a de nombreuses applications en mathématiques et en informatique. En particulier, plusieurs primitives cryptographiques sont fondées sur la difficulté de résoudre SVP. Il existe aujourd'hui trois approches pour résoudre SVP. La première consiste à faire une recherche exhaustive de la solution, mais elle a un coût superexponentiel. La seconde est constituée des algorithmes de crible, non déterministes mais dont la complexité est simplement exponentielle. La dernière est basée sur le calcul de la cellule de Voronoï du réseau, son coût est exponentiel également mais elle ne semble pas utilisable en pratique. Le but de cet exposé est de présenter une amélioration de l'analyse des algorithmes de crible obtenues conjointement avec Damien Stehlé. Nous commencerons par décrire sommairement les différentes familles de méthode, en se concentrant sur les algorithmes de crible, en particulier AKS et ListSieve. Enfin, nous présenterons notre amélioration de l'analyse, reposant sur le paradoxe des anniversaires.


17h00: Maxime Senot, Construction géomètrique pour résoudre SAT en temps constant
Il est possible de mener des calculs complexes avec des particules se déplaçant à vitesse constante sur la droite euclidienne et leurs collisions. A partir de cela a été défini un modèle abstrait et géométrique du calcul, les machines à signaux. Après avoir introduit et défini ce modèle, nous montrerons comment il nous permet de résoudre SAT en temps et espace bornés. Nous proposerons également une notion de complexité pertinente pour ce modèle, qui sera en temps quadratique notre solution de SAT.


17h30: Thibaut Balabonski, Filtrage et causalité
Le filtrage (certains disent "pattern matching") est un des piliers de la programmation fonctionnelle en ce qu'il permet de définir des fonctions en raisonnant par cas sur la structure des arguments. Cependant, dans la compilation comme dans la théorie ce mécanisme est généralement traité à part. En réintégrant le filtrage au coeur des langages, nous verrons comment une petite analyse des relations de causalité entre les différentes étapes d'évaluation d'un programme permet de déduire un modèle d'exécution nouveau et efficace.


Jeudi

14h30: Brigitte Vallée, Présentation du GDR IM
GDR Informatique Mathématique


15h00: Guillaume Munch-Maccagnoni, Valeurs et polarités en réalisabilité classique
La logique classique intéresse l'informaticien en ce qu'elle peut être vue, contrairement au lambda-calcul, comme un langage de programmation dans lequel la notion d'ordre d'évaluation est primordiale. La théorie développée depuis 20 ans, notamment la logique classique de Girard, correspond donc mieux aux langages de programmation avec des effets en style direct, comme ML. La réalisabilité classique s'étend à ce cadre, et on fera quelques remarques sur les phénomènes propres à l'appel par valeur de ML que la réalisabilité permet de décrire.


15h30: Fabien Givors, Forcing et degrés Turing
En calculabilité, on étudie la structure des degrés de difficulté du calcul, par exemple des degrés Turing. En théorie des ensembles, le forcing est une méthode permettant de créer des modèles possédant des propriétés particulières. Nous verrons comment faire des preuves en calculabilité grâce au forcing.


16h30: Vincent Siles, Tout ce que vous avez toujours voulu savoir sur les PTS
Les Systèmes de Types Purs (ou PTS) définissent des systèmes de typages "génériques" permettant de raisonner sur plusieurs systèmes à la fois (Lambda-Calcul Simplement Typé, Systeme F,...). Ainsi, tout les résultats que l'on peut prouver pour un PTS sont directement validés sur toutes ses instances. Outre l'intéret évident de pouvoir travailler sur une famille de systèmes et non plus au cas par cas, les PTS permettent aussi de s'abstraire des particularités inhérentes à chaque système et de se focaliser sur l'essentiel. Dans cette introduction, je vous presenterai les principaux résultats connus sur l'ensemble des PTS, puis des propriétés plus avancées qui ne sont valables que sur certaines sous-classes de PTS.


17h00: Khalil Ghorbal, Inferring automatically invariants on numerical variables of a program
We aim at proving automatically the correctness of numerical behaviour of a program by inferring invariants on numerical variables. Said differently, given inputs range of some piece of code (with tests, loops etc.), we tightly over-approximate the outputs while giving in addition precise input/output relations. First, we briefly present the abstract interpretation framework. We then introduce the affine forms-based abstract domain : numerical variables are abstracted by an extended affine form, called "constrained perturbed affine form". We focus on Set-Theoretic operators over these special affine forms. We finally show some experiments and benchmarks using our implementation of such an abstract domain, called Taylor1+.


17h30: Vonjy Rasendrahasina, MAX-2-XORSAT : approches analytiques
Nous présentons une approche analytique du problème d'optimisation MAX-2-XORSAT basée sur la combinatoire analytique et énumérative. Dans cet exposé, nous étudions les séries génératrices liées aux configurations optimales de MAX-2-XORSAT. En combinant ces outils avec ceux d'analyse complexe, nous quantifions alors le nombre maximum de clauses satisfaisables des instances aléatoires de MAX-2-XORSAT.


"Social Event"

Skieur
Sortie ski de fond suivie d'une dégustation de mets savoyards qui réchauffent. Cette activité est comprise dans les frais d'inscription.
N.B. : la météo peut nous amener à modifier le programme de cette sortie.