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
Coordination scientifique du séminaire : Guillaume Hanrot
Horaire et lieu
Les mardi à 13h30. Le séminaire se tiendra 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.

Séminaires à venir

25 février 2020. Francis Sourd (groupe Sun’R)

Des algorithmes d’optimisation aux applications industrielles

L’exposé commencera par la présentation des problèmes et algorithmes classiques de la Recherche Opérationnelle. Il se concentrera ensuite sur les difficultés théoriques et pratiques rencontrées lors de la résolution de problèmes
rencontrés dans l’industrie. Les principales manières de résoudre ces problèmes seront alors décrites (approximations, utilisation de librairies sur étagère et développement d’algorithmes dédiés). Elles seront illustrées par des applications réelles mises en œuvre dans différentes entreprises.

Séminaires passés

11 février 2020. Achour Mostefaoui (LS2N, Université de Nantes)
La calculabilité dans les systèmes répartis.

Résumé.
La calculabilité dans le calcul séquentiel est maintenant bien comprise. Il n’est est pas de même en ce qui concerne le calcul réparti (distribué). En effet, la question est plus complexe et surtout multidimensionnelle. Comme l’activité est multiple ; plusieurs parties de code peuvent s’exécuter simultanément (les processus), il se pose la question de la cohérence ce que devrait voir chaque processus et aussi sous quelle condition chaque process doit progresser. Une façon d’aborder ce problème passe la notion de construction universelle et d’objet universel.

Cet exposé va d’abord présenter et détailler le contexte avant de présenter les deux grands résultat d’impossibilité dans les systèmes répartis (FLP et CAP). On présentera quelques résultats et une construction universelle.

28 janvier 2020. Omar Fawzi (LIP, ENS de Lyon)
Prospects and challenges for quantum information.

Résumé.
In the first part of this talk, I will give a brief introduction to the mathematical formalism of quantum information. Then I will focus on one of the important scientific questions in the road towards a universal quantum computer : understanding quantum error-correcting codes. The second part of the talk will be given by Marc Kaplan, president of the startup VeriQloud, and he will present the prospects of applications of quantum technologies, in particular in the context of quantum networks.

17 décembre 2019 Rémi Gribonval (Inria, équipe Dante)

Parcimonie et problèmes inverses.

Résumé.
Supprimer le flou sur une image, restaurer un enregistrement sonore saturé, localiser l’épicentre d’un tremblement de terre à l’aide de sismomètres, reconstruire une image médicale 3D à partir de coupes 2D telles que des radiographies… Ces situations à première vue très différentes font en fait partie de la grande famille des problèmes inverses.

L’intuition nous suggère à juste titre que de tels problèmes sont difficiles, voir insolubles dès que le nombre de variables inconnues excède celui des variables observées. Et pourtant des progrès considérables et des solutions maîtrisées et efficaces ont été obtenus ces quinze dernières années en s’appuyant sur la notion de parcimonie. Objectif naturel pour la compression de données (MP3, JPEG), la parcimonie s’est ainsi révélée une propriété fructueuse là où on ne l’attendait sans doute pas.

L’exposé dressera un panorama des principes et multiples facettes des approches exploitant la notion de parcimonie. Si le temps le permet on en évoquera quelques-uns des avatars récents prometteurs, notamment en apprentissage statistique où sa combinaison avec la théorie des matrices aléatoires s’avère très fructueuse.

10 décembre 2019 Mioara Joldes (CNRS, LAAS)
A glimpse beyond Gravity: some symbolic-numeric algorithms.

Résumé.
Let us consider two examples related to the International Space Station (ISS). Firstly, when a spacecraft such as Soyuz or SpaceX moving on an initial orbit fly to and dock the ISS, that’s rendezvous in space. RDV-related problems have been studied since the ’60s. Today’s focus is in designing maneuver plans which minimize fuel consumption with increased autonomy (no human operator). Secondly, as active satellites and spaceships like the ISS orbit Earth, these are often hit by orbital debris – usually small fragments from satellites, rocket upper stages, lost equipment. Ever wondered how dangerous these can be, when the relative speed can be around 14km/s? What are today’s collision risk assessment and mitigation strategies? Inspired by these space mission design questions, the aim of this talk is to present both old and new algorithms tackling these problems where computer algebra, optimization and rigorous numerics come in handy. This is based on joint works with D. Arzelier, F. Bréhard, N. Brisebarre, J.-B. Lasserre, C. Louembet, A. Rondepierre, B. Salvy, R. Serra.

26 novembre 2019. Hélène Touzet (CNRS, CRIStAL)
Décrypter les génomes.

Résumé.
Le séquençage des génomes permet aujourd’hui de produire des données de séquences d’ADN à faible coût et en grandes quantités, avec de nombreuses applications en santé, en écologie, en agro-alimentaire. Le traitement de toutes ces données pose toutefois des questions difficiles en algorithmique, et notamment en algorithmique du texte. Comment reconstruire les séquences, les comparer, localiser des régions d’intérêt ? Lors de la présentation, nous présenterons en détails le problème de la recherche de motifs avec erreurs dans une séquence d’ADN, qui fait intervenir de la théorie des automates et de la théorie de l’information. Nous illustrerons le propos avec l’exemple du séquenceur nomade ultraportable, le Minion.

12 novembre 2019. Melina Skouras (Inria, équipe Imagine).
Physics-aware design tools for digital fabrication.

Résumé.
Recent technological advances in digital manufacturing enable experts and casual users alike to design and fabricate complex structures with fine control over their external geometry and internal material distribution. However, designing an object that is truly functional by manually specifying its material composition and its external shape is extremely challenging. Indeed, the functionality of real objects is not determined by macro-scale shape alone. Stability, robustness, compliance, and other properties also depend directly on the material distribution of the object and largely affect its behavior in the physical world. Therefore, the designer needs to estimate and invert the effects of the physics on the object to obtain a structure that behaves as desired. In this talk, I will show how we can use physics-based simulation and inverse modeling to alleviate these difficulties and to allow the designer to easily create custom deformable objects. I will demonstrate these capabilities in the context of the design of objects as diverse as inflatable membranes, actuated characters and high-resolution functional objects. While some of the systems that I propose are fully automatic, others put the user in the loop and allow them to interactively explore alternative design solutions.

15 octobre 2019. Philippe Blache (CNRS, LPL)
Communiquer avec un agent artificiel en réalité virtuelle

Résumé.
L’interaction humain-machine est un enjeu scientifique, économique et sociétal majeur. Mais comment communiquer avec une machine aussi naturellement que possible ? Pour répondre à cette question, il faut tout d’abord observer comment les humains interagissent, par exemple pendant une conversation. Il faut ensuite modéliser ces informations, à partir de données naturelles. Il faut enfin développer des systèmes capables de reproduire de telles interactions naturelles en intégrant ces modèles. Une des façons les plus avancées de faire cela consiste à développer des agents virtuels capables de comprendre les multiples informations produites par le sujet humain (à la fois dans ce qu’il dit, mais également dans ses comportements), puis de synthétiser des réponses et des attitudes adaptées à ces informations.

Je présenterai pendant ce séminaire les résultats d’un projet de recherche ayant permis de développer un agent conversationnel animé en réalité virtuelle doté de ces capacités d’interaction naturelle. Cet agent est utilisé pour former les médecins à l’annonce de mauvaises nouvelles, en jouant le rôle du patient à qui l’annonce est faite. L’agent est ainsi capable de comprendre ce que dit le médecin, et de produire un comportement adapté, y compris du point de vue émotionnel. Je présenterai également les premiers résultats utilisant de tels agents pour étudier l’activité cérébrale pendant une interaction, et les spécificités qui peuvent être observées au niveau du cerveau pendant une interaction humain-machine, en comparaison avec une interaction entre humains.

1er octobre 2019. Gilles Muller (INRIA, équipe Whisper)
Research problems in thread scheduling for multicore general purpose operating systems

Résumé (l’exposé sera donné en français)
An OS thread scheduler decides which thread runs at a given moment on a given core. A thread scheduler is a key OS service since any bad decision that it makes may lead to cores wasting cycles and may increase application response times. A thread scheduler must operate under stringent performance constraints, support concurrency, adapt to complex hardware specificities, such as NUMA, and address not only scheduling of the threads within cores but also balancing the load across cores. As a result, while schedulers were services of a few hundred lines of code twenty years ago when machines were single core, they have grown into highly complex pieces of software in the era of multicore NUMA machines. As an example, CFS contains more than 35,000 lines of code in Linux 4.19, released in October 2018.

In this talk, we show that CFS suffers from performance bugs such as lack of work conservation (no core remains idle when work is ready to be scheduled) and badly manages modern multicore architectures with frequency scaling. We will present on-going research in the Inria Whisper team that aim at solving these problems.

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.

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.