Le 2/9, 14h-17h
La Programmation Diffuse du Web
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.
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.
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.
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.
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.
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 InformatiqueDernières modifications : le 06/09/2015