Résumé : 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é).
Enregistré pendant le session thématique « Algorithme et programmation » le 3 mai 2016 au Centre International de Rencontres Mathématiques (Marseille, France)
Réalisation: Guillaume Hennenfent
Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities:
- Chapter markers and keywords to watch the parts of your choice in the video
- Videos enriched with abstracts, bibliographies, Mathematics Subject Classification
- Multi-criteria search by author, title, tags, mathematical area
Frédéric Vivien : Algorithmes d’approximation - Partie 2 cnrs montpellier | |
| 6 Likes | 6 Dislikes |
| 401 views views | 10K followers |
| Science & Technology | Upload TimePublished on 25 May 2016 |
Không có nhận xét nào:
Đăng nhận xét