Séance de cours

Bounds inférieurs pour les PST analytiques

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre deux limites inférieures pour l'analyse Traveling Salesman Problem (TSP), se concentrant sur les fonctions H(K) et H'(r), le théorème Bishop-Jones et la compacité des ensembles KSC. L'instructeur discute la relation entre H(K) et H'(r), les propriétés des courbes universelles, et l'application de ces limites dans l'analyse TSP.

Source officielle

Concepts associés (24)

Inégalité de Chernoff

En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée. On parle également de borne de Chernoff. Elle est nommée ainsi en l'honneur du mathématicien Herman Chernoff. Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle. Il existe de nombreux énoncés, et de nombreux cas particuliers.

Majorant ou minorant

En mathématiques, soient (E , ≤) un ensemble ordonné et F une partie de E ; un élément x de E est : un majorant de F s'il est supérieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F : ; un minorant de F s'il est inférieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F :. Si F possède un majorant x alors on dit que F est une partie majorée. Si F possède un minorant x alors on dit que F est une partie minorée.

Inégalité de concentration

Dans la théorie des probabilités, les inégalités de concentration fournissent des bornes sur la probabilité qu'une variable aléatoire dévie d'une certaine valeur (généralement l'espérance de cette variable aléatoire). Par exemple, la loi des grands nombres établit qu'une moyenne de variables aléatoires i.i.d. est, sous réserve de vérifier certaines conditions, proche de leur espérance commune. Certains résultats récents vont plus loin, en montrant que ce comportement est également vérifié par d'autres fonctions de variables aléatoires indépendantes.

Borne supérieure et borne inférieure

En mathématiques, les notions de borne supérieure et borne inférieure d'un ensemble de nombres réels interviennent en analyse, comme cas particulier de la définition générale suivante : la borne supérieure (ou le supremum) d'une partie d'un ensemble (partiellement) ordonné est le plus petit de ses majorants. Une telle borne n'existe pas toujours, mais si elle existe alors elle est unique. Elle n'appartient pas nécessairement à la partie considérée. Dualement, la borne inférieure (ou l'infimum) d'une partie est le plus grand de ses minorants.

Problème du voyageur de commerce

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.

Afficher plus

Séances de cours associées (6)

Relations, séquences et sommations

Couvre des sujets sur les relations, les séquences et les sommations, y compris les réseaux, les relations de récurrence et la notation sigma.

Les nombres réels : définitions et limites

Explique les définitions et les propriétés de maximum, minimum, supremum et infimum en nombres réels.

Estimation de la distribution

Explore les méthodes d'estimation de la distribution, les fonctions de remise en forme et l'importance de choisir le bon estimateur pour obtenir des résultats précis.

Méthodes exactes pour l'optimisation d'entier MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Couvre les méthodes exactes pour l'optimisation des entiers, en mettant l'accent sur les techniques Branch et Bound.

Marcelo Campos (University of Cambridge)

Afficher plus

Concepts associés (24)

Inégalité de Chernoff

Majorant ou minorant

Inégalité de concentration

Borne supérieure et borne inférieure

Problème du voyageur de commerce

Afficher plus