Prochaines séances
Date : Vendredi 11 avril 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Jill-Jênn Vie, INRIA Saclay, et Michael Anoprenko, IP Paris
Titre : Knowledge tracing assistant for learning competitive programming
The International Collegiate Programming Contest (ICPC) has been around since 1977 and welcomes 70,000 students from all around the world every year. The first chapter is SWERC on November 21-23 2025, where people compete as teams of 3 students. The curriculum covers a wide range of topics, including using VSCode efficiently, dynamic programming, segment trees, matching and flows, etc. We are focusing on C++ but it is okay to code in Python even though you may be frustrated at times that your solution is too slow.
In this talk we will first present how AI can be used to learn programming in a personalized way (pdf). Then we will give some examples of problems and answer your questions! To learn more, check org/icpc/polytechnique/
Date : Vendredi 16 mai 2025 de 16h30 à 18h00 en salle 1Z61
Intervenantes : Cécile Pierrot, INRIA / LORIA, et Camille Désenclos, Université de Picardie, UFR d'Histoire et de Géographie
Titre : Percer le secret des lettres chiffrées de Charles Quint: un travail interdisciplinaire entre cryptographes et historiens.
Hiver 2020. Une dépêche presque intégralement chiffrée est redécouverte dans les 16 kilomètres de rayonnages de la bibliothèque du patrimoine de Nancy. Elle semble datée de 1546 et signée de la main de l'empereur Charles Quint. Mais comment percer le mystère d'une lettre chiffrée multiséculaire ? Venez suivre l'histoire de ce décryptage qui ouvre la voie d'une recherche à la frontière entre cryptographie, histoire, linguistique et intelligence artificielle. Aucune prérequis n'est indispensable dans ces disciplines pour suivre l'exposé.
Séances passées
Date : Vendredi 28 mars 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Aliaume Lopez, Université de Varsovie
Titre : Largeur de clique et beaux préordres
Un beau préordre est un espace X muni d’un préordre, tel qu’il n’existe pas de séquences infinies strictement décroissantes dans X ni de sous-ensembles infinis d’éléments incomparables deux à deux. Ces deux propriétés de finitude font des beaux préordres des outils mathématiques pertinents pour comprendre la terminaison de certains algorithmes, par exemple de vérification. L’ensemble des graphes munis du préordre “sous-graphe induit” n’est pas un beau préordre. L’objectif de cet exposé est de discuter de plusieurs conjectures sur le sujet et de montrer comment la théorie des automates (via la notion de largeur de clique) peut fournir des pistes de solution. Il sera aussi l’occasion de discuter de ce que l’on devient 10 ans après être entré à l’ENS.
Date : Vendredi 21 mars 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Sylvain Périfel, LIPN, Sorbonne Paris Nord
Titre : Deux facettes de l'aléatoire en complexité algorithmique
Qu'est-ce qu'un mot aléatoire ? L'utilisation de bits aléatoires dans les algorithmes peut-elle accélérer les calculs ? Par le biais de deux problèmes ouverts, nous aborderons ces questionnements sur la définition et l'utilisation de l'aléatoire en informatique.
Date : Vendredi 14 mars 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Sam van Gool, IRIF, Université Paris Cité
Titre : De Bruijn graphs, unifiability, and Stone duality
In this talk, I will discuss the sequence of De Bruijn automata, where the De Bruijn automaton of dimension n is defined as the minimal automaton that "remembers the last n letters of a finite input word". More specifically, I will be interested in the following decision problem:
Given a non-deterministic finite automaton, when does it admit a homomorphism from one of the de Bruijn graphs?
I will show how this problem is a reformulation of an apparently very different decision problem of "unifiability" in a propositional logic with next-time operator. The equivalence between the two decision problems is mediated by a general technique called Stone duality, which I will explain in the finite case. I will then show how this technique helped us to solve both problems at once, how this relates to an old open problem in logic, and what all this has to do with a hamburger and fries.
Date : Vendredi 7 mars 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Gaëtan Douéneau, Ministère des armées
Titre : ENS & doctorat : une formation par la recherche, pour le secteur public
Ancien élève du département informatique (2015-2019), j’ai réalisé une thèse en théorie des automates et reçu le prix de thèse Ackermann 2024. A la sortie de l’ENS, j'ai également rejoint un grand corps technique de l'Etat pour réaliser une carrière dans l’administration publique. Je travaille actuellement au Ministère des Armées sur les projets de surveillance et d’action dans l’espace.
Je parlerai d’abord de mes travaux de recherche. Ceux-ci concernent les transducteurs, qui sont des «automates avec des sorties», autrement dit des machines à états finis qui calculent des fonctions des mots vers les mots. Ils peuvent être vus comme des programmes à mémoire bornée qui manipulent des chaînes de caractères. Dans ma thèse, j’ai développé plusieurs techniques visant à «optimiser» ce type de programmes : étant donné un transducteur «complexe», on cherche à construire automatiquement un transducteur «plus simple» (souvent à comprendre comme «plus rapide à l’exécution») qui calcule la même fonction.
Sur la base de mon parcours, j'essayerai ensuite de répondre aux questions suivantes : est-ce que le service de l’Etat se limite à la recherche et à l’enseignement ? Pourquoi l’administration publique est-elle un débouché naturel pour un normalien-docteur dans un domaine scientifique ? A quoi sert de faire une thèse pour faire autre chose que de la recherche ? Certaines analyses seront basées sur un rapport présenté au cabinet de la ministre de la fonction publique en 2021, et disponible ici.
Date : Vendredi 14 février 2025 de 16h30 à 17h30 en salle 1Z61
Intervenante : Hang Zhou, LIX, École Polytechnique
Titre : Traveling Salesman Problem and Capacitated Vehicle Routing
In the traveling salesman problem (TSP), we look for a minimum length tour visiting a given set of n vertices. As a natural generalization of TSP, we consider the capacitated vehicle routing problem (CVRP). In CVRP, we are given a tour capacity k and a vertex called depot, and we look for a minimum length collection of tours starting and ending at the depot, such that those tours together visit a given set of n vertices and each tour visits at most k vertices. In this talk, I am going to talk about recent progress on both TSP and CVRP.
Date : Vendredi 7 février 2025 de 16h30 à 17h30 en salle 1Z61
Intervenant : Étienne André, LIPN, Université Sorbonne Paris-Nord
Titre : Perdez votre temps et votre argent (et celui des autres) : égarez les données de vos expériences
De nombreuses expériences scientifiques ne sont pas reproductibles. Si cela peut s'expliquer, au moins en partie, dans certaines disciplines, c'est nettement moins compréhensible en informatique où, dans de nombreuses situations, il devrait être aisé voire trivial de reproduire les expériences décrites dans nos articles scientifiques, dont beaucoup se résument à exécuter du code. Pourtant, c'est loin d'être le cas : en cause, la perte des données nécessaires à reproduire les expériences. Nous allons dresser un bref panorama : pourquoi, comment, et où conserver les données des expériences scientifiques en informatique.
Date : Vendredi 13 décembre 2024 de 16h15 à 17h15 en salle 1Z61
Intervenants : Vincent Lafeychine, M2 MPRI, et Baptiste Lemoine, membre du CA d'OpenStreetMap France. OpenStreetMap en anglais et OpenStreetMap en français
Titre : OpenStreetMap au service des acteurs publics
La cartographie en ligne s'est imposée comme un outil incontournable pour se déplacer ou accéder à des informations sur un lieu.
Depuis 20 ans, OpenStreetMap (OSM) propose une alternative libre et collaborative, comparable à Wikipédia pour les encyclopédies. OSM permet à chacun de contribuer en enrichissant le contenu de la carte ainsi que son ontologie.
OSM se distingue aujourd'hui d'autres acteurs par la richesse, l'homogénéité et la précision de ses données. Des acteurs publics (comme l'IGN, le SDIS, Île-de-France mobilités ou la SNCF) ou privées (comme la majorité des GAFAM) utilisent des données issues d'OSM.
Après avoir exploré l'ensemble des possibilités offertes par OpenStreetMap, nous analyserons comment son écosystème évolue grâce à l'intéraction entre acteurs publics, privées et bénévoles, perpétuant ainsi le cercle vertueux de la contribution libre.
Date : Vendredi 6 décembre 2024 de 16h15 à 17h15 en salle 1Z61
Intervenant : Frédéric Magniez, IRIF, CNRS
Titre : L'ordinateur quantique : principes et potentiels usages
Les ordinateurs actuels, basés sur les machines de Turing, restent contraints par la physique classique, malgré des progrès en semi-conducteurs et lasers utilisant déjà certaines propriétés quantiques de la matière et de la lumière. Dans les années 80, une autre approche a émergé : le calcul quantique, exploitant les phénomènes de superposition et d'intrication pour garantir la sécurité des transmissions par les lois de la physique quantique, ou encore pour changer la difficulté de certains calculs jugés irréalisables en temps polynomial. Aujourd'hui, des technologies prometteuses pourraient rendre ce paradigme une réalité, ce qui marquerait une "deuxième révolution quantique" capable de transformer des domaines comme l'algorithmique et la cryptographie. Cet exposé présentera les bases de cette discipline et les défis à relever.
Date : Vendredi 29 novembre 2024 de 16h15 à 17h15 en salle 1Z61
Intervenant : Pierre Depaz, NYU Berlin, Sciences Po
Titre : Esthétiques et éthiques des codes sources
La mise en forme du code source—comment on l’écrit, et comment on le lit—implique toujours des jugements de valeur(s). Traditionnellement considérée comme orthogonale à la rigueur de l’ingénierie, l’esthétique n’en est pas moins présente, principalement dans son rapport à la fonctionnalité de ce qui est fabriqué. S’intéresser à l’esthétique du code source, c’est donc aussi mettre à jour les dimensions implicites et irrationnelles des pratiques de programmation. En examinant ces esthétiques à travers le prisme des jugements de valeur(s), en établissant une connexion entre le beau et le bien, le laid et le mauvais, il est donc possible de détailler comment ces valeurs ont elles-mêmes des implications éthiques. Plus spécifiquement, il s’agit de montrer comment elles sous-tendent une certaine manière de fabriquer des logiciels, de collaborer avec autrui, et de traduire le monde, mais aussi comment d’autres valeurs esthétiques et éthiques peuvent suggérer d’autres manières de faire, à travers des approches artistiques du code source et des langages de programmation.