Also appears in collection : Exposés de recherche
Dans la deuxième partie de ce cours nous considérerons un problème lié, celui des algorithmes compétitifs. Dans le cadre de l'algorithmique « en-ligne », les caractéristiques d'une instance d'un problème ne sont découvertes qu'au fur et à mesure du traitement de l'instance (comme on ne découvre l'histoire d'un livre qu'au fur et à mesure où on en lit des pages). Ne pas connaître à l'avance toutes les caractéristiques d'une instance interdit souvent - mais pas toujours - de construire un algorithme optimal. Nous montrerons, entre autres, comment utiliser la technique de l'adversaire pour établir une borne inférieure au facteur de compétitivité de tout algorithme en-ligne (cette fois-ci en dehors de toute notion de complexité).
By Dominique Barbolosi
By Dominique Barbolosi
By Luc Bougé
By Gilles Dowek
By François Boisson
By Gérard Berry
By Simon Lacoste-Julien
By Olivier Bournez
By Judicaël Courant
By Frédéric Vivien
By Frédéric Vivien
By Sylvie Boldo
By Gilles Dowek
By Pierre Deligne
By Fyodor Petrov
