Colloquium d’Informatique de Sorbonne Université – Session d’octobre 2024

Le 10 octobre à 18h se tiendra la prochaine session du Colloquium d’Informatique de Sorbonne Université sur le thème des algorithmes paramétrés et des classes de complexité. De nombreuses tâches informatiques sont complexes et chronophages pour les ordinateurs et autres appareils qui doivent les réaliser. Une question centrale est : comment créer des méthodes – des algorithmes – qui résolvent ces tâches de manière efficace ? Une partie de la réponse tient au fait que certains problèmes complexes peuvent être simplifiés en réduisant la taille de l’entrée ou de la réponse demandée. Dans le domaine des algorithmes paramétrés, la complexité des problèmes informatiques est étudiée sous l'angle où un paramètre de l'entrée est considéré comme significativement plus petit que l'entrée elle-même.

Professeur à l’université d’Utrecht (Pays-Bas), spécialiste en complexité paramétrée et deux fois lauréat du prix EATCS-IPEC Nerode en algorithmique multivariée, Pr. Hans Bodlaender abordera certains des principaux concepts du domaine (FPT algorithms, W-hierarchy, slicewise polynomial time (XP), kernelization, and polynomial kernels), ainsi que ses évolutions récentes. Son exposé en amphi 25 sera précédé par un cocktail sur le patio attenant, à partir de 17h15.