Conférences de rentrée 2015

Manuel Serrano

Le 2/9, 14h-17h

Le Web est en passe de devenir la plateforme d'exécution la plus riche jamais existante. Sa force vient de trois éléments: des navigateurs modernes qui sont capables de produire des interfaces graphiques sophistiquées, des services distants qui permettent le développement de composants indépendants et interchangeables, une masse de ressources utilisables qui ne cesse de grandir chaque jour (multimédia, scientifiques, statistiques, sociétales, ...).

La combinaison de des trois éléments a déjà donné lieu à l'apparition d'applications révolutionnaires telles que Google Maps, les podcast radio ou encore les réseau sociaux. L'étape suivante sera probablement l'intégration du monde physique dans les applications connectées. Une difficulté majeure subsiste: les techniques de programmation que nous employons ont principalement été inventées du temps où les programmes étaient faiblement connectées et elles sont mal adaptées à ces applications nouvelles. Dans ce cours nous présenterons un nouveau langage de programmation nommé Hop.js qui constitue une première étape vers cet objectif à atteindre d'une programmation diffuse évoluée.

Pierre-Alain Fouque

Le 3/9, 14h-17h

Aspects Algorithmiques de Cryptanalyse

Dans cette conférence, je présenterai quelques algorithmes importants en cryptanalyse au travers d'exemples issus de cryptographie symétrique et asymétrique comme par exemple: les attaques génériques sur les fonctions de hachage, les algorithmes de factorisation ou du logarithme discret, les schémas de signature construit sur la difficulté à résoudre des systèmes quadratiques en plusieurs variables ou la difficulté à résoudre des systèmes linéaires avec du bruit.

Edmond Boyer

Le 4/9, 14h-17h

Modélisation des formes en mouvement

Les progrès en vision par ordinateur rendent désormais possible la construction de modèles numériques de formes en mouvement à partir de vidéos. Ces modèles sont des objets graphiques, définis dans l'espace et dans le temps (des modèles 4D). Ils sont constitués d'informations géométriques et photométriques sur les formes et sur leurs apparences. Ils permettent de reproduire et d'analyser les scènes dynamiques telles que des mouvements humains. Ils ouvrent ainsi la voie à de nouvelles applications dans les jeux, dans la production de contenus médiatiques ou encore dans le domaine médical. Dans cet exposé je préciserai l'état de l'art dans ce domaine et discuterai des méthodes et des enjeux de la recherche.

Bio: Edmond Boyer est directeur de recherche à INRIA Grenoble Rhône-Alpes où il dirige une équipe de recherche dans le domaine de la vision par ordinateur. Il a obtenu une thèse de l'institut national polytechnique de Lorraine en 1996 et une habilitation à diriger des recherches de l'université Joseph Fourier de Grenoble en 2007. Ces thèmes de recherche couvrent la vision par ordinateur, le graphisme et les environnements immersifs et interactifs. Edmond Boyer a co-fondé, en 2007, la société 4D View Solutions qui commercialise des systèmes de capture 4D.

Vincent Danos et Jean Krivine

Le 7/9, 9h30-12h30

Stochastic graph transformations and applications in biology

We build probabilistic tools for manipulating stochastic complex systems based on a fairly generic class of syntaxes of graph transformations. In the second part, we zero down on a particular graph formalism for biological applications. We discuss knowledge representation in relation to this formalism and novel efforts for extracting automatically executable representations from the (large) biological literature.

Marc Tommasi

Le 8/9, 14h-17h

Apprentissage automatique dans les graphes

La conférence portera sur l'apprentissage automatique et plus particulièrement sur l'apprentissage automatique en présence de relations structurelles entre les données représentées sous forme de graphes.

L'accent sera mis sur la tâche fondamentale qui consiste à prédire une valeur associée à chaque donnée (ou ici à chaque nœud d'un graphe). L'exposé se terminera par une extension de ces algorithmes à des structures représentant des ensemble de relations entre groupes de données. Une application à la prédiction de matches entre équipes de joueurs, dans les jeux en ligne par exemple, sera présentée.

Eric Goubault

Le 9/9, 9h15-10h45

Que peut-on décider dans un monde imparfait? Calculs de processus et topologique algébrique

Le monde imparfait dont il s'agit est celui d'ordinateurs parallèles, ou de réseaux d'ordinateurs, dont certains processeurs peuvent tomber en panne sans prévenir, ou dans lesquels le système de messagerie peut échouer à délivrer des messages, ou être juste extrêmement lent. Encore pire, comme cela peut se passer dans des systèmes travaillant sous radiation (centrales nucléaires, mais aussi satellites), certains messages peuvent être modifiés de manière complètement non-déterministe. Comment faire alors pour que les différents processeurs collaborent? Un problème primordial est celui de l'élection d'un leader: comment faire pour coordonner différents processeurs, évoluant éventuellement de façon asynchrone, pour qu'ils décident qui est le «chef» ; on souhaite en général que le chef élu ne soit pas mort (ou en panne)... Ceci a des applications essentielles, par exemple, pour les systèmes embarqués, ou plusieurs ordinateurs de bord, dupliqués, contrôlant un processus critique (ex. calculateur de vol dans un avion) doivent décider en permanence qui est vivant et prend les commandes.

Ce qui peut être «calculé» dans un système distribué tolérant aux pannes est précisément l'ensemble de problèmes, comme l'élection d'un leader ou le consensus, qu'une architecture donnée (mémoire partagée, passage de message, synchrone, asynchrone etc.) sous des hypothèses de pannes possibles, peut décider, en temps fini. Les décisions que peuvent prendre les processeurs, locaux, dans un tel système distribué, dépendent essentiellement de ce qu'ils «savent» des autres, donc de la façon dont les primitives de synchronisation ou de communication utilisées permettent de construire une causalité et une information, globale.

Un résultat très important du domaine est relativement récent : il s'agit du résultat publié par Fisher, Lynch et Patterson en 1985, l'impossibilité de résoudre le consensus (similaire à l'election de leader), pour simplifier ici, dans un système à mémoire partagée, ou l'on a à disposition que l'écriture et lecture «atomiques» (non-interruptibles), en présence d'une ou plusieurs pannes. Ce résultat a démarré un domaine très riche, avec beaucoup de résultats assez étonnants (par exemple, pour le problème de «renommage»). Je présenterai deux approches permettant de caractériser au mieux ces problèmes de décision parallèle, toute s deux basées sur une idée géométrique, plus précisément, venant de la topologie algébrique.

La première est celle de Maurice Herlihy, Nir Shavit, Sergio Rajsbaum etc. qui est basée sur la géométrie des états atteignables par des programmes (ou «protocoles») sur ces architectures distribuées tolérantes aux pannes. La deuxième est celle de l'orateur, Martin Samuel Mimram, Christine Tasson etc. et est basée sur la géométrie du flot de contrôle que l'on peut observer sur ces architectures. Bien sûr, comme je le montrerai, ces deux approches sont liées et permettent de comprendre en détail le flot de l'information dans ces systèmes distribués. En passant, j'essaierai de montrer comme de belles mathématiques peuvent être développées sur ces problèmes, comme dans beaucoup d'autres en informatique. La première approche est basée sur de la topologie algébrique classique, la deuxième demande de développer une nouvelle théorie des espaces topologiques modulo déformations continues, mais qui respectent la «direction» du temps. On peut d'ailleurs revisiter à loisir, si le temps le permet, des problèmes géométriques classiques, à travers ces problèmes informatiques, comme des problèmes typiques de géométrie Riemanienne (géodésiques, courbure etc.), des problèmes combinatoires (intimement liés aux «discrétisations» des espaces topologiques) etc.

David Auber

Le 10/9, 9h30-12h30

Algorithmes de génération automatique de visualisations

(Le même résumé, avec des images.)

L'objectif de cette conférence est de présenter des algorithmes permettant d'imiter des visualisations qui ont été inventées par l'être humain bien avant l'apparition de l'informatique. Bien que ces visualisations semblent faciles à générer manuellement, elles soulèvent de nombreux problèmes algorithmiques difficiles. La conférence se concentrera sur les diagrammes d'Euler, l'agrégation d'arc, la cartographie de l'information et les nuages de points.

Le premier problème est la génération de diagrammes d'Euler (1761). Bien que la visualisation sous forme de patatoïde soit largement adoptée pour expliquer les notions ensemblistes, la génération de tels diagrammes requiert d'utiliser la théorie des graphes planaires mais aussi des méthodes de déformation de maillage. Après une présentation de la problématique nous expliquerons une méthode complètement automatique permettant de réaliser de telles représentations.

Le deuxième problème est la représentation de relations sous forme de faisceau. La représentation nœud-lien de graphe présente de nombreux avantages, cependant, lorsque la densité des connexions est trop importante il devient nécessaire de simplifier la visualisation en effectuant une agrégation des connexions. Cette méthode a été introduite par Minard (1862), nous montrerons comment, en utilisant des techniques de discrétisation du plan et aussi du routage dans les graphes, nous arrivons à reproduire ce genre de visualisation.

Le troisième problème sera la génération de cartographie de l'information ressemblant à des cartes géographiques. Comme l'avait proposé Murrell (1846) dans ses travaux précurseurs, la métaphore de la carte géographique permet d'utiliser des aptitudes que les utilisateurs développent depuis leur enfance. Ces représentations sont donc intuitives et assez facilement mémorisables. En utilisant des courbes fractales et la théorie des graphes planaires nous montrerons comme nous pouvons obtenir ce genre de carte automatiquement.

Dans le quatrième problème, nous nous intéresserons à une des techniques les plus anciennes pour la visualisation d'information. Nous montrerons comment permettre à la représentation de John Snow (1854) de passer à l'échelle des données du Big Data. Nous montrerons comment nous pouvons, en utilisant des techniques de clustering non supervisées et distribuées et du rendu au GPU, permettre l'analyse de nuages de points dépassant le milliard d'éléments sur des clients légers.

Contacter le Département Informatique
Dernières modifications : le 06/09/2015