F Nous contacter


0

Documents  68W25 | enregistrements trouvés : 3

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

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). 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 ...

68W25 ; 68Q25 ; 68T20

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é). 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 ...

68W25 ; 68Q25 ; 68T20

Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - property testing
Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - ...

68Q15 ; 68Q17 ; 68Q19 ; 68W20 ; 68W25

Nuage de mots clefs ici

Z