This HTML5 document contains 44 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n7http://g.co/kg/g/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n2http://fr.dbpedia.org/resource/Théorème_optimisation/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n10http://fr.dbpedia.org/resource/Modèle:
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n9http://fr.wikipedia.org/wiki/Théorème_optimisation/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
n2:séparation
rdfs:label
Théorème optimisation/séparation
rdfs:comment
Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial.
owl:sameAs
n7:121xqlz0 wikidata:Q3527273
dbo:wikiPageID
2148236
dbo:wikiPageRevisionID
187314342
dbo:wikiPageWikiLink
dbpedia-fr:Polyèdre dbpedia-fr:Méthode_de_l'ellipsoïde dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) category-fr:Algorithmique_et_convexité dbpedia-fr:Théorème category-fr:Optimisation_combinatoire category-fr:Théorème_de_combinatoire dbpedia-fr:Approche_polyédrique dbpedia-fr:Séparation_des_convexes dbpedia-fr:Polytope dbpedia-fr:Optimisation_combinatoire dbpedia-fr:Martin_Grötschel dbpedia-fr:Informatique_théorique dbpedia-fr:László_Lovász dbpedia-fr:Mathématiques dbpedia-fr:Combinatorica dbpedia-fr:Inéquation_du_premier_degré dbpedia-fr:Algorithmique dbpedia-fr:Alexander_Schrijver
dbo:wikiPageLength
1956
dct:subject
category-fr:Optimisation_combinatoire category-fr:Algorithmique_et_convexité category-fr:Théorème_de_combinatoire
prop-fr:wikiPageUsesTemplate
n10:Palette n10:Article n10:Portail
prov:wasDerivedFrom
n9:séparation?oldid=187314342&ns=0
prop-fr:année
1981
prop-fr:auteur
dbpedia-fr:László_Lovász dbpedia-fr:Martin_Grötschel dbpedia-fr:Alexander_Schrijver
prop-fr:journal
dbpedia-fr:Combinatorica
prop-fr:lang
en
prop-fr:pages
169
prop-fr:titre
The ellipsoid method and its consequences in combinatorial optimization
prop-fr:volume
1
foaf:isPrimaryTopicOf
n9:séparation
dbo:abstract
Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. Un polyèdre convexe P de est constitué par l'ensemble des points satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme ). * Optimiser sur P consiste à déterminer pour toute fonction linéaire . * Séparer sur P consiste à déterminer, pour tout point , si appartient à P ou non, et sinon, à déterminer un hyperplan séparant de P (i.e. trouver une inégalité linéaire violée par mais satisfaite par tout point de P). On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial.