Séminaires du Département Informatique de l’ENS de Lyon (vf)

Public et Objectif
Ouvert à tous. Ce séminaire est obligatoire pour les L3, et recommandé pour les M1. Ce séminaire propose une introduction à un domaine de recherche actuel d’une manière accessible aux non spécialistes et aux étudiants. Même les chercheurs expérimentés peuvent être intéressés!
Contacts
Suivi administratif du séminaire par Nicolas Palmeri, coordination scientifique par Philippe Audebaud
Horaire et lieu
Les mardi à 13h30. Nous ferons le SIESTE en amphi B (campus Monod, 3ème étage du bâtiment principal). Des rafraichissements seront ensuite proposés en salle passerelle du quatrième étage. Le public pourra alors discuter avec l’orateur.

Contents

Actualités liées à nos orateurs

  1. Portrait d’Aline Parreau, ambassadrice de la culture mathématique.
  2. Patrick Flandrin élu vice-Président de l’académie des Sciences.

Séminaire à venir

09 avril 2019. Judicaël Courant | Vers des systèmes informatiques transparents par conception ?
(How I Learned to Stop Worrying and Love Parcoursup)

L’informatisation bouscule les enjeux démocratiques dans notre société : lorsqu’un ordinateur prend une décision, qui choisit vraiment ? Sur quels critères ? Qui contrôle ? Peut-on avoir confiance ?

Dans cet exposé, je m’intéresserai au cas particulier de l’affectation des bacheliers dans l’enseignement supérieur.

Sur l’exemple français d’Admission PostBac et de Parcoursup, je montrerai que le problème n’est pas tant dans les algorithmes utilisés, relativement bien compris depuis plus d’un demi-siècle, que dans leur mise en oeuvre dans laquelle il serait déraisonnable d’avoir confiance.

Je présenterai une mise en oeuvre alternative offrant de meilleures garanties de transparence.

Séminaires passés

26 mars 2019. Amaury Pouly | Continuous models of computation: computability, complexity, universality and biology
In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines.

A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno’s phenomenon, also known as space-time contraction.

In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

12 mars 2019. Laurent Lefevre | Faire plus avec moins: à la recherche de proportionnalité et d’efficacité énergétique en phase d’usage
Les grandes infrastructures numériques (Clouds, datacentres, réseaux, terminaux) engloutissent d’énormes quantités d’énergie et gaspillent de nombreuses ressources.

Après avoir dressé un panorama peu reluisant des multiples impacts environnementaux des technologies du numérique, je me focaliserai sur différentes innovations venant du domaine de la recherche pour améliorer la phase d’usage. Je présenterai différents modèles permettant de retrouver une proportionnalité énergétique dans le numérique.

Je décrirai et commenterai ensuite quelques approches abouties ou prometteuses permettant d’améliorer l’efficacité énergétique de ces grands systèmes.

26 février 2019. Sylvain Périfel | La catastrophe du premier bit
La robustesse du célèbre algorithme de compression de Lempel et Ziv n’est pas encore bien établie : en particulier, jusqu’à présent on ne savait pas si l’ajout d’un bit au début d’un mot compressible pouvait le rendre incompressible. C’est à cette question, popularisée par Jack Lutz sous le nom de « one-bit catastrophe » et dont on trouve trace dès 1998, que cet exposé va répondre. Nous montrerons qu’un mot « très compressible » reste compressible lorsqu’on ajoute un bit devant, mais que certains mots « peu compressibles » deviennent en effet incompressibles.

C’est un travail en commun avec Guillaume Lagarde.

12 février 2019. Assia Mahboubi | Mathématiques assistées par ordinateur
Les outils numériques ont transformé les mathématiques: typographie, moyens de communication, d’expérimentation, et même nature des démonstrations. Ces dernières peuvent par exemple reposer crucialement sur des calculs trop intensifs pour être effectués “à la main”. Ce recours à la puissance de calcul des ordinateurs traverse des champs variés de mathématiques: théorie des nombres, systèmes dynamiques, combinatoire, etc. Les problématiques de fiabilité du logiciel s’invitent dès lors dans la définition de la rigueur mathématique.Les assistants de preuve sont des logiciels qui permettent de faire des mathématiques avec l’aide d’un ordinateur. Plus spécifiquement, ils permettent de développer des bibliothèques numériques de théories mathématiques vérifiées, calculatoires ou pas. Dans cet exposé, nous discuterons au travers de quelques exemples récents la mise en oeuvre, les bénéfices et les perspectives de la vérification formelle de théorèmes mathématiques.
29 janvier 2019. Jean-Marc Vincent | Comment trouver une aiguille dans une botte de foin ?
L’exposé, en français, s’appuiera sur un travail commun avec Robin Lamarche-Perrin , Lucas Mello Schnorr, Damien Dosimont, Guillaume Huard, et Yves Demazeau, dont voici le résumé en anglais :

How to find a Needle in a Haystack ? On the Detection of Anomalies in Large Traces.

Large-scale high-performance applications are involving an ever-increasing number of threads to explore the extreme concurrency of today’s systems. The performance analysis through visualization techniques usually suffers severe semantic limitations due, from one side, to the size of parallel applications and, from another side, to the challenges regarding the visualization of large-scale traces. Most of performance visualization tools rely therefore on data aggregation to work at scale. Even if this abstraction technique is frequently used, to the best of our knowledge, there has not been any attempt to evaluate the quality of aggregated data for performance visualization.

This presentation presents an approach which fills the gap. We propose to build optimized macroscopic visualizations using measures inherited from information theory, and in particular the Kullback-Leibler divergence. These measures are exploited to estimate the complexity reduction and the information loss during the aggregation.

We first illustrate the applicability of our approach in the domain of parallel/distributed systems by exploiting these two measures for the analysis of work stealing traces using squarified treemaps. We then report the effective scalability of our approach by visualizing known anomalies in a synthetic trace file recording the behavior of one million processes. Then we analyse the behavior of embedded systems on very long periods (scaling problem) and finally we show how this approach could be applied for Web Data and the analysis of RSS flows.

08 janvier 2019. Gabriel Kerneis | Atteindre un haut niveau de fiabilité pour un grand nombre d’utilisateurs.
Étude des difficultés qui surgissent dès lors que l’on essaye d’atteindre un haut niveau de fiabilité pour un grand nombre d’utilisateurs, et introduction à certaines des techniques utilisés par les Site Reliability Engineers (SRE) pour résoudre ces problèmes à Google.
18 décembre 2018. Jean-Michel Muller | Histoire et nouveaux problèmes de l’arithmétique virgule flottante.
L’arithmétique virgule flottante est de loin le moyen le plus utilisé pour représenter des nombres réels sur ordinateur. L’histoire de l’arithmétique virgule flottante est une longue histoire, qui nous mène des babyloniens aux derniers processeurs, en passant pas Archimède, Descartes, Leonardo Torres, Konrad Zuse, William Kahan et quelques autres, en alternant brillantes trouvailles et énormes bêtises.

J’essaierai de donner un coup de projecteur sur certaines étapes importantes, sans prétendre ni à l’exhaustivité ni à l’objectivité. Je terminerai en montrant certains problèmes actuels, qui illustrent que cette arithmétique permet d’obtenir des informations beaucoup plus précises qu’on ne le croit, que l’on peut en particulier prouver des propriétés intéressantes d’algorithmes numériques.

04 décembre 2018. Patrick Flandrin | Voir et dessiner les sons.
Le problème d’extraire ou manipuler l’information contenue dans un son (l’identifier, le débruiter, le transcrire, le modifier, etc.) s’est posé dès que la possibilité d’un enregistrement est apparue dans la deuxième moitié du XIXème siècle. Ceci a donné lieu, et jusqu’à aujourd’hui, à de nombreuses recherches visant à fournir des représentations graphiques pouvant s’apparenter à celle de la musique sur une portée. On évoquera les approches actuelles d’usage le plus courant (Fourier, ondelettes et variations) et on les illustrera sur quelques exemples typiques, dont celui des cris d’écholocation des chauves-souris.
20 novembre 2018. Ralf Everaers | Computational Statistical Physics
Since the time of Newton and Gallilei, physicists have made great progress in discovering fundamental laws and elementary particles. Unfortunately, the resulting equations can be solved analytically only in rare limiting cases, posing a severe challenge for the scientific problem of modeling the complex world surrounding us on this basis.

With the rapid development of computers, numerical techniques play an increasingly important role. I will illustrate the numerical approach for the example of the Ising model of interacting spins in Statistical Physics, which is one of the simplest models exhibiting a transition between a disordered (paramagnetic) and a ordered (ferromagnetic) phase.

In particular, I will try compare the importance of algorithmic developments and of the increase in the shear computing power over the last 75 years.

L’exposé aura lieu en français.

06 novembre 2018. Aline Parreau | Identification dans les structures discrètes, ou comment les chercheurs jouent à “Qui est-ce ?”.
Dans le jeu “Qui est-ce”, on cherche à identifier efficacement un individu parmi d’autres en questionnant sur son aspect physique. Si toutes les questions sont posées en même temps, cela revient au problème d’identification dans une structure appelée hypergraphe : les individus sont représentés par des points, appelés sommets, et chaque caractéristique physique est représenté par un sous-ensemble de sommets, appelés hyper-arête, qui contient tous les individus partageant cette caractéristique. La question principale est de trouver le plus petit ensemble d’hyper-arêtes qui permet de distinguer tous les individus. Cette question est difficile dans le cas général mais peut s’avérer plus facile s’il y a des contraintes sur les hyper-arêtes. Nous nous intéresserons au cas particulier où les points sont situés dans le plan et les hyper-arêtes correspondent aux ensembles de points pouvant être dans un même disque. Nous montrerons dans ce cas des résultats à la fois combinatoire (de bonnes bornes sur le nombre de caractéristiques nécessaires) et algorithmiques.
16 octobre 2018 Alain Passelègue | De la complexité à la sécurité informatique : une introduction à la recherche en cryptographie.
Nous utilisons tous la cryptographie des dizaines de fois par jour, souvent sans même en avoir conscience. Les problèmes de sécurité informatique font de plus en plus régulièrement la une de l’actualité et plus que jamais, avec l’avènement du Big Data, d’importants problèmes de confidentialité des données sont à résoudre. La cryptographie s’attelle à résoudre ses problèmes afin de proposer des solutions pour construire des systèmes sécurisés.
Dans cet exposé, j’expliquerai 3 grands axes de recherche en cryptographie, de la théorie à la pratique. J’illustrerai ma présentation avec un problème élémentaire mais central : comment produire de l’alea de qualité sur une machine.
02 octobre 2018. Jean-Christophe Filliâtre | Vérification déductive de programmes avec l’outil Why3
Ce séminaire a pour objectif de présenter la vérification déductive. Dans cette approche, la correction d’un programme est réduite à un ensemble d’énoncés mathématiques, dont la validité est ensuite établie à l’aide d’outils de démonstration automatique ou interactive. Les principales idées et techniques derrière cette approche seront illustrées à l’aide de l’outil Why3 développé dans l’équipe VALS du LRI.

Archives (et maquette du futur site)

En suivant ce lien, vous trouverez l’ensemble des archives, qu’il est possible d’explorer par saison, par orateur ou par séminaires.