Journée JCJC (jeudi 19)

Dans cet exposé, nous ferons un tour d'horizon sur différents problèmes se posant dans un graphe lorsqu'une partie de l'information sur ce graphe ne nous est pas accessible. Ce manque d'information peut avoir des causes variées :

• en premier lieu, nous nous placerons dans une situation de calcul distribué : chaque noeud connaît uniquement les informations sur son voisinage immédiat, et doit prendre une décision sans connaître le reste du graphe. Nous l'illustrerons sur le problème de la certification locale de classes géométriques.
• dans un second temps, nous nous intéresserons à un problème algorithmique online, c'est-à-dire lorsqu'une partie de l'entrée ne nous sera révélée qu'au fur et à mesure de nos choix. Nous étudierons pour cela comment choisir un itinéraire d'un point à un autre lorsque certaines rues sont susceptibles d'être bloquées par la neige : c'est le Problème du Voyageur Canadien.
• enfin, il se peut que l'ensemble des solutions à explorer soit tout simplement exponentiel en la taille de notre entrée : c'est le cas des colorations d'arêtes sur un graphe donné en entrée. Comment pouvons-nous alors naviguer dans cet espace trop grand des solutions ? Est-il connexe ? Pouvons-nous tirer une coloration au hasard ?

Cet exposé sera l'occasion de mettre en valeur des problèmétiques étudiées au sein du GT-Graphes, à l'interface avec d'autres GT du GDR-IFM (GT CoA, GT Calculabilité, GT Alea...).

A context-free grammar is unambiguous if every word in its language is derived in a unique way.
Unlike finite automata, there exist context-free languages that are not recognized by any unambiguous grammar. Such languages are called inherently ambiguous.
Showing that a context-free language is inherently ambiguous is a difficult problem, since one must prove that every context-free grammar recognizing it is necessarily ambiguous. In this talk, I will present some nice (and surprisingly simple) techniques based on generating functions to address this problem.

De nombreux problèmes géométriques issus de domaines variés tels que la robotique, la vérification de programmes et l'optimisation peuvent être formulés sous forme de questions impliquant des ensembles définis par des équations et des inégalités polynomiales. La géométrie algébrique réelle fournit un cadre unificateur pour l'étude de ces objets, ainsi qu'une boîte à outils algorithmique permettant de répondre à des questions fondamentales telles que l'existence de solutions ou celle d'un chemin entre deux solutions.

Dans cet exposé, je montrerai comment des questions géométriques émergent et guident la conception d'algorithmes exacts en calcul formel, à partir de problèmes issus de différents domaines. J'expliquerai également comment les progrès en matière de complexité et d'implémentation ont permis de transformer ces approches en méthodes efficaces. En particulier, nous verrons le rôle essentiel joué par des briques algorithmiques du calcul formel, telles que les bases de Gröbner.

Several geometric problems arising from various fields such as robotics, program verification and optimisation can be formulated as questions involving sets defined by polynomial equations and inequalities. Real algebraic geometry provides a unifying framework for studying these objects, as well as an algorithmic toolbox for answering fundamental questions such as whether solutions exist or whether two solutions are connected by a path.

In this talk, I will show how geometric questions emerge and guide the design of exact algorithms in computer algebra, based on problems from different fields. I will also explain how advances in complexity and implementation have transformed these approaches into effective methods. In particular, we will see the essential role played by algorithmic building blocks of computer algebra, such as Gröbner bases.

Distributed systems are systems in which distinct processes interact and change states. These systems exhibit complex behaviours, and verifying their correctness is a challenging task. Model-checking is a verification method which checks whether a formal model satisfies a formal property. An example of a property is mutual exclusion : given N processes executing the same piece of code to access a shared resource, we want to verify that no two processes can access the shared resource simultaneously. In general, we expect such properties to hold independently of the number N of participating processes. This leads to the study of parameterized properties, where N is treated as a parameter that may be unbounded. In this talk, I will survey important concepts and results of parameterized verification.

Dans un monde où l'intelligence artificielle (IA) suscite autant de peurs que d'espoirs, cette intervention dresse un état des lieux des transformations réelles du travail et de son automatisation. En m'appuyant sur les sciences sociales et des enquêtes en cours, j'interroge trois mythes récurrents : la fin du travail est-elle réellement à l'horizon ? L'IA nous rend-elle effectivement plus productifs ? Et nous simplifie-t-elle vraiment la vie ? Cette intervention replace l'IA dans l'histoire longue des techniques, marquée par la promesse sans cesse renouvelée du « cette fois-ci, c'est différent ! ».

In a world where artificial intelligence (AI) inspires both fear and hope, this talk takes stock of the concrete transformations of work and its automation. Drawing on social science research and ongoing fieldwork, I examine three recurring myths: Is the end of work really on the horizon? Does AI actually make us more productive? And does it truly make our lives easier? The talk situates AI within the long history of technologies, shaped by the endlessly renewed promise that "this time, it's−really−different."

Cet atelier propose un cadre pour examiner collectivement la place que prennent aujourd’hui les outils d’IA générative dans le travail académique ordinaire. Le protocole vise à rendre visibles des usages souvent dispersés, implicites ou difficiles à discuter, et à produire des repères partagés pour évaluer leur utilité, leurs limites et leurs conséquences concrètes sur le travail académique.

L’atelier propose une forme collective, qualitative et réflexive de benchmarking. À partir de situations concrètes apportées par les participant·es, il s’agit de sélectionner quelques tâches ordinaires mais représentatives, de faire produire des réponses par différents LLM, puis de les évaluer en aveugle. Le cœur de l’exercice n’est pas le classement en soi, mais la conversation qu’il suscite : ce qui fait une « bonne » réponse, la part tacite dans l’évaluation, ainsi que les tensions entre l’attention portée au résultat final et celle accordée au processus de production. Cette mise à l’épreuve permet de déplacer la question de l’IA, de « ce que la machine sait faire » vers « ce que nous jugeons pertinent, acceptable ou utile dans nos pratiques académiques ».

Aucune compétence technique spécifique n’est requise. Toute posture vis-à-vis de l’IA est la bienvenue, dès lors que les participant·es acceptent de tester ces outils et de s’engager dans le cadre proposé.

Les participant·es peuvent attendre plusieurs bénéfices de cet atelier. Sans être une formation technique, le dispositif offre un espace structuré d’expérimentation et permet de se constituer une expérience située de ces outils. Il favorise une prise de recul à partir de sa propre pratique et de son expertise professionnelle, loin des discours généraux. Il crée enfin un espace collectif rare pour partager des expériences individuelles, discuter de situations concrètes et aborder les enjeux réels liés aux usages de l’IA dans la vie académique.

This workshop offers a framework for collectively examining the place that Generative AI tools now occupy in everyday academic work. The protocol aims to make visible uses that are often scattered, implicit, or difficult to discuss, and to produce shared reference points for assessing their usefulness, limits, and concrete consequences for academic work.

The workshop proposes a collective, qualitative, and reflexive form of benchmarking. Starting from concrete situations brought by participants, the group selects a small number of ordinary but representative tasks, has different LLMs produce responses, and then evaluates these outputs blind. The core of the exercise is not the ranking itself, but the conversation it generates: what counts as a “good” answer, the tacit dimensions of evaluation, and the tensions between attention to the final result and to the process of production. This trial shifts the question of AI away from “what the machine can do” toward “what we consider relevant, acceptable, or useful in our academic practices.”

No specific technical skills are required. All positions toward AI are welcome, provided that participants are willing to test these tools and engage with the proposed framework.

Participants can expect several benefits from the workshop. Without being a technical training, the format provides a structured space for experimentation and for building a situated experience of these tools. It encourages reflexive distance grounded in one’s own practice and professional expertise, rather than in general discourse. Finally, it creates a rare collective space to share individual experiences, discuss concrete situations, and address the real stakes of AI use in academic life.

Les bouleversements écologiques et sociaux en cours rendent la question plus pressante que jamais : Quel rôle notre activité de recherche scientifique joue-t-elle dans ces bouleversements ? Comment s’intègre-t-elle dans les sociétés actuelles et dans la part destructrice de leur fonctionnement, et comment l’intégrer dans des scénarios prospectifs souhaitables à moyen et long terme ?

Ces questions en ouvrent une plus large, plus ancienne, mais dont les scientifiques s’emparent rarement : est-ce que les résultats de nos recherches participent à la construction d’un monde qui correspond à nos valeurs ?

Pour aborder cette question, il faut apprendre à expliciter les valeurs avec lesquelles nous travaillons, et comprendre les tenants et aboutissants de nos recherches, démarche qui relève de l’histoire, de la philosophie, de la sociologie, de la politique, de l’économie, du droit, et de l’éthique de nos disciplines, auxquels nous ne sommes, en majorité, pas formé.es.

Cet atelier a été conçu dans le but de fournir un espace et un cadre de discussion collective sur les conséquences de nos recherches, les valeurs qu’elles véhiculent et le rôle de la recherche scientifique dans l’Anthropocène, ainsi que pour sensibiliser aux sciences humaines et sociales, et en particulier à la philosophie, l’histoire, et la sociologie des sciences. Il ne cherche pas à mettre tout le monde d’accord, mais plutôt à offrir des moyens de se positionner sur les enjeux environnementaux et sociaux de la recherche, au-delà des calculs d’empreinte environnementale.