Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Bounds inférieurs pour les PST analytiques

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 (17)

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.

Poussière

La poussière est constituée de matériaux divers assez légers pour être mis en suspension dans l'air, ou plus généralement, de matériaux particulaires d'un diamètre inférieur à (micromètres). Les poussières peuvent poser des problèmes graves pour la santé des humains, des animaux et des plantes, mais aussi pour le fonctionnement des machines. Les poussières sont éliminées de l'air intérieur par des aspirateurs , divers systèmes de filtres ou le procédé du cyclone.

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.

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.

Sans titre

Afficher plus

Concepts associés (17)

Inégalité de Chernoff

Majorant ou minorant

Inégalité de concentration

Borne supérieure et borne inférieure

Poussière

Afficher plus