Calcul sous incertitude : algorithmique en ligne, jeux de recherche et systèmes interruptibles
Ce mémoire d'Habilitation explore les aspects de la computation dans un statut d'incertitude. En premier lieu nous étudions les problèmes en ligne, dans lesquels les données (input) ne sont pas connues à l'avance et où l'algorithme doit prendre des décisions pour chaque donnée en l'absence de connaissance des données apportées par la suite. En deuxième lieu nous considérons les jeux de recherche, dans lesquels un acteur en démarche de recherche doit localiser un acteur caché immobile qui se trouve à un point inconnu du domaine de recherche. En dernier lieu, nous examinons la conception et l'analyse de systèmes interruptibles, dans lesquels le système doit être en capacité de produire un résultat de manière raisonnablement efficace même s'il est interrompu à un instant arbitraire.
Un fil rouge dans l'étude des sujets succinctement présentés ci-dessus est l'examen de la puissance et des limites de mesures de performance dans le cas le plus défavorable, tels le rapport de compétitivité et le rapport d'accélération. Nous avançons que dans certains cas, des mesures de performance plus nuancées s'imposent, et à cet effet nous introduisons de nouveaux modèles et techniques d'analyse. Nous démontrons et exploitons aussi des relations entre ces mesures et ces approches, même si elles s'appliquent en apparence à des domaines distincts.
Soutenance : 14/12/2020
Membres du jury :
Nikhil Bansal, TU Eindhoven [rapporteur]Pierre Fraigniaud, CNRS et Université de Paris [rapporteur]
Lisa Hellerstein, New York University [rapporteur]
Steve Alpern, Warwick Business School
Christoph Dürr, CNRS et Sorbonne Université
Patrick Jaillet, MIT
Claire Mathieu, CNRS et Université de Paris
Date de départ : 14/12/2020