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

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.

Présentation de l’intervenant. Gilles Muller received the Ph.D. degree in 1988 from the University of Rennes I, and the Habilitation a Diriger des Recherches degree in 1997 from the University of Rennes I. After having been a researcher at INRIA and a Professor at the Ecole des Mines de Nantes, he is currently a senior research scientist at Inria Paris and the head of the Whisper group. His research interests include the development of methodologies based on domain-specific languages for the structuring of infrastructure softwares. He is one of the designers of the Coccinelle tool.

Gilles Muller has co-authored more than 100 international conferences and journal articles in venues such as TOCS, TOPLAS, ACM Computing Surveys, TCS, IEEE Software, IEEE Transactions on Reliability, OSDI, POPL, ASPLOS, EuroSys, RTSS, DSN, FTCS, OOPSLA, ECOOP and ICDCS. He has co-authored 4 patents in the domains of fault tolerant systems and Java embedded systems.

Gilles Muller was the PC Chair of DSN2018, EuroSys 2010 and PLOS 2010. He was involved in more than 80 program committees of international workshops and conferences such as SOSP, OSDI, Usenix ATC, EuroSys, ASPLOS, DSN, PLOS, VEE and the EuroSys prize for the best PhD thesis. Gilles Muller was a member of the Eurosys steering committee and was the vice chair of the ACM/SIGOPS from July 2003 to July 2007.

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.

12 novembre 2019. Melina Skouras (Inria, équipe Imagine).
Titre à préciser.
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.

Présentation de l’intervenante. Je suis directrice de recherche au CNRS à CRIStAL (Lille). Mes premiers contacts avec la recherche datent de mon DEA de Logique, réalisé à l’Université Paris 7 après une maîtrise de mathématiques fondamentales dans la même université. J’ai ensuite poursuivi mes études par une thèse en logique et informatique théorique au Loria, à Nancy. Le thème était la complexité des systèmes de réécriture, qui est un sous-domaine de la théorie de la démonstration. Ma thèse a été soutenue en 1997, et j’ai obtenu un poste de maître de conférences en informatique à Lille en 1998. Ce recrutement s’est accompagné d’une conversion thématique progressive vers l’algorithmique pour la bioinformatique. L’objectif est de concevoir des algorithmes et des modèles pour travailler sur des séquences biologiques, telles que l’ADN, l’ARN, les protéines. C’est un domaine qui se nourrit à la fois de techniques avancées issues de l’algorithmique discrète et de collaborations pluridisciplinaires en biologie et en santé. Aujourd’hui, après presque 20 ans d’activité en bioinformatique, je suis responsable d’une équipe de recherche au sein de CRIStAL (bonsai) et directrice du GDR Bioinformatique Moléculaire. Entre temps, j’ai quitté mon poste universitaire pour un poste de CR CNRS en 2005, promue DR CNRS en 2009.

10 décembre 2019 Mioara Joldes (CNRS, LAAS)
Titre à préciser.
17 décembre 2019 Rémi Gribonval (Inria, équipe Dante)
Titre à préciser.

Séminaires passés

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.