m

F Nous contacter

0

Documents  68W25 | enregistrements trouvés : 11

O
     

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science

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

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xi; 556 p.
ISBN 978-2-85629-371-3

Astérisque , 0352

Localisation : Périodique 1er étage

Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces homogènes # espaces métriques # espaces normés # espaces perfectoïdes # existence globale # fibré de Higgs # fibré holomorphe plat # forme quartique binaire # formule de KPZ # gravité quantique # groupe de Galois motivique # groupe de Selmer # groupes de Lie # groupes quasi-fuchsiens # hamiltonien # marches aléatoires # mélange exponentiel du fibré des repères # mesures de Liouville # mesures stationnaires # métrique harmonique # modération topologique # monodromie-poids # motifs de Tate mixtes # multizêtas # nonlinéaire # norme d'uniformité # orbites coadjointes # plongement métrique # principe de transfert # programmation semi-définie # Programme de Ribe # progression arithmétique # pureté # rang # réarrangement # Relativité générale # représentations des groupes algébriques réductifs # représentations des groupes de Lie compacts # résonances en espace temps # rigidité # singularités irrégulières # stabilité orbitale # surfaces enfermées # système stellaire auto-gravitant # théorème de Lefschetz difficile # théorie de Hodge # théorie géométrique des invariants # topologie étale # trous noirs # types stablement dominés # variétés de drapeaux # variétés hyperboliques de dimension 3 # Vlasov-Poisson Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces ...

14L24 ; 14M15 ; 20G05 ; 22E46 ; 35-XX ; 35Qxx ; 37-XX ; 37NXX ; 37N20 ; 82-XX ; 82Cxx ; 85-XX ; 85AXX ; 05C12 ; 05C85 ; 46N10 ; 68Q17 ; 68R10 ; 68W25 ; 90C22 ; 91B14 ; 11G99 ; 11G05 ; 11E76 ; 14J60 ; 32C38 ; 53C07 ; 83C57 ; 83C75 ; 83C05 ; 35L67 ; 60C05 ; 60F17 ; 60-02 ; 05C10 ; 05C80 ; 82B20 ; 82B05 ; 82B27 ; 35B34 ; 35E20 ; 35B60 ; 35Q60 ; 35Q35 ; 11N13 ; 11B25 ; 30F99 ; 03C64 ; 03C65 ; 03C99 ; 14G22 ; 11G25 ; 14F20 ; 14G20 ; 22E40 ; 37D40 ; 60B99

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- ix; 382 p.
ISBN 978-0-8218-8737-0

Contemporary mathematics , 0586

Localisation : Collection 1er étage

analyse numérique # mathématiques appliquées # homogénisation # diffraction

65N55 ; 76M50 ; 78A45 ; 81V55 ; 49N45 ; 68W25 ; 78M40 ; 92C15 ; 65-06 ; 65Z05 ; 00A69 ; 00A79 ; 00B25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks

Analysis of algorithms in noisy high-dimensional probabilistic problems poses many current challenges. In a subclass of these problems the corresponding challenges can be overcome with the help of a method coming from statistical mechanics. I will review some of the related recent work together with progress on rigorous justification of the corresponding results.

68T05 ; 62P35 ; 68W25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science

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

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science

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

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xi; 251 p.
ISBN 978-3-642-22014-2

Localisation : Ouvrage RdC (GART)

algorithme # programmation # programmation semi-définie # programmation mathématique # méthode numérique

68W25 ; 90C22 ; 90-01 ; 65K05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xi; 440p.
ISBN 978-1-4614-1700-2

Springer optimization and its applications , 0062

Localisation : Ouvrage RdC (DU)

informatique # algorithme d'approximation # analyse d'algorithme # stratégie gloutonne # restriction # partition # arbre de Steiner # relaxation # programmation linéaire # dualité # programmation semi-definie # inaproximabilité

68W25 ; 68W40 ; 90C90 ; 68-02

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xii; 362 p.
ISBN 978-0-8218-4911-8

Mathematical surveys and monographs , 0173

Localisation : Collection 1er étage

algorithme d'approximation # géométrie algorithmique # géométrie discrète # programmation linéaire # informatique

68U05 ; 68W25 ; 68P05 ; 52Cxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xii; 343 p.
ISBN 978-3-540-33258-9

Mathematics and visualization

Localisation : Ouvrage RdC (EFFE)

graphisme # informatique # géométrie calculatoire non-linéaire # structure de données # algorithme # courbe # surface # topologie calculatoire

68U05 ; 65D18 ; 14Q05 ; 14Q10 ; 14Q20 ; 68N19 ; 68N30 ; 65D17 ; 57Q15 ; 57R05 ; 57Q55 ; 65D05 ; 57N05 ; 57N65 ; 58A05 ; 68W05 ; 68W20 ; 68W25 ; 68W40 ; 68W30 ; 33F05 ; 57N25 ; 58A10 ; 58A20 ; 58A25 ; 65-06 ; 00B15

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xxiv; 322 p.
ISBN 978-0-8176-4682-0

Applied and numerical harmonic analysis

Localisation : Ouvrage RdC (REPR)

analyse de Fourier # ondelettes

22D10 ; 22E45 ; 28A80 ; 32A70 ; 34A45 ; 35M99 ; 37B05 ; 41A58 ; 42B35 ; 42C10 ; 42C40 ; 42C99 ; 45L05 ; 44A05 ; 43A65 ; 54H10 ; 46E22 ; 46C07 ; 46A20 ; 46A35 ; 46L60 ; 46E35 ; 47L10 ; 47L40 ; 47A25 ; 47A20 ; 58D25 ; 60B15 ; 60G35 ; 65T50 ; 65T60 ; 68U10 ; 68W25 ; 81Q10 ; 92C55 ; 93A13 ; 94A08 ; 94A12 ; 94A24 ; 42-06 ; 00B30

... Lire [+]

Z