Résumé : De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils s'exécutent en temps polynomial et fournissent des solutions dont la qualité est garantie. Nous introduirons la notion d'algorithme d'approximation et de schéma d'approximation en temps polynomial, et nous illustrerons ces notions sur de nombreux exemples. Nous montrerons également comment établir qu'un problème n'admet pas d'algorithme d'approximation (à moins que P=NP), ou comment établir une borne inférieure au facteur d'approximation de tout algorithme d'approximation (sauf si P=NP).
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 1 cnrs montpellier | |
| 20 Likes | 20 Dislikes |
| 1,924 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