Séance de cours

Arrondissement de la détente : Diversification Max Sum

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.

Dans cours

MATH-513: Metric embeddings

The course aims to introduce the basic concepts and results on metric embeddings, or more precisely on approximate embeddings. This area has been under rapid development since the 90's and it has strong impact on algorithms for discrete optimization proble ...

Description

Cette séance de cours couvre le concept d'arrondi de la relaxation et de la diversification Max Sum, en mettant l'accent sur les hypothèses, les objectifs et les idées qui sous-tendent le processus. Il explique les effets de l'arrondi, des solutions intégrales et des composants fractionnels. L'instructeur discute des étapes de l'algorithme, des limites de perte et de la sélection des solutions optimales. Différents lemmas et preuves sont présentés pour illustrer les fondements théoriques du processus d'arrondi.

Source officielle

Concepts associés (30)

Équation intégrale

Une équation intégrale est une équation où la fonction inconnue est à l'intérieur d'une intégrale. Elles sont importantes dans plusieurs domaines physiques. Les équations de Maxwell sont probablement leurs plus célèbres représentantes. Elles apparaissent dans des problèmes des transferts d'énergie radiative et des problèmes d'oscillations d'une corde, d'une membrane ou d'un axe. Les problèmes d'oscillation peuvent aussi être résolus à l'aide d'équations différentielles.

Relaxation continue

En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode.

Fondements des mathématiques

Les fondements des mathématiques sont les principes de la philosophie des mathématiques sur lesquels est établie cette science. Le logicisme a été prôné notamment par Gottlob Frege et Bertrand Russell. La mathématique pure présente deux caractéristiques : la généralité de son discours et la déductibilité du discours mathématique . En ce que le discours mathématique ne prétend qu’à une vérité formelle, il est possible de réduire les mathématiques à la logique, les lois logiques étant les lois du « vrai ».

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Intégration (mathématiques)

En mathématiques, l'intégration ou calcul intégral est l'une des deux branches du calcul infinitésimal, l'autre étant le calcul différentiel. Les intégrales sont utilisées dans de multiples disciplines scientifiques notamment en physique pour des opérations de mesure de grandeurs (longueur d'une courbe, aire, volume, flux) ou en probabilités. Ses utilités pluridisciplinaires en font un outil scientifique fondamental. C'est la raison pour laquelle l'intégration est souvent abordée dès l'enseignement secondaire.

Afficher plus

Séances de cours associées (64)

Preuves : Logique, Mathématiques et Algorithmes

Explore les concepts, les techniques et les applications de la preuve dans la logique, les mathématiques et les algorithmes.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Calcul d'angle sur des surfaces régulières

Couvre le calcul des angles entre les courbes sur les surfaces régulières et le concept d'abscisse curviligne.

Formes harmoniques : théorème principal

Explore les formes harmoniques sur les surfaces de Riemann et l'unicité des solutions aux équations harmoniques.

Caratheodory Bounds : programmation intégrale

Couvre les limites de Caratheodory pour la programmation d'entiers, en se concentrant sur la programmation linéaire et l'existence de solutions optimales.

Afficher plus

Concepts associés (30)

Équation intégrale

Relaxation continue

Fondements des mathématiques

Algorithme

Intégration (mathématiques)

Afficher plus