Séance de cours

Optimisation intégrale: Théorie et applications

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-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

Cette séance de cours couvre les fondamentaux de l'optimisation d'entier, y compris la programmation d'entier, la programmation dynamique, les algorithmes d'approximation et les problèmes de couverture. L'instructeur discute de la complexité de la programmation entière, de la relaxation de programmation linéaire, de la branche & liée, et du problème knapsack. La séance de cours explore également des sujets tels que Steinitz Lemma, GCD, Euclidean Algorithm, treillis, Théorème de Minkowski, et les limites de transfert. En outre, la séance de cours se penche sur l'application de la programmation entière dans les dimensions fixes et les algorithmes pour le plus court problème vectoriel (SVP).

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie de la complexité (informatique théorique)

Concepts associés (32)

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.

Algorithme d'Euclide

En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres. vignette|Peinture censée représenter le mathématicien Euclide d'Alexandrie, par Justus of Ghent. Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes.

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

Afficher plus

Séances de cours associées (64)

Algorithmes d'approximation

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

Problème de Knapsack: Optimisation et Voyageur Salesman

Explore le problème knapsack et le problème de vendeur itinérant avec un accent sur les algorithmes d'optimisation.

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Définir la couverture : Integrality Gap

Explore le concept d'écart d'intégralité dans les algorithmes de couverture et de pondérations multiplicatives.

Systèmes complexes : phénomènes critiques

Explore les phénomènes critiques dans les systèmes complexes, y compris les objets stochastiques, la percolation et l'optimisation combinatoire.

Afficher plus

Concepts associés (32)

Optimisation linéaire en nombres entiers

Optimisation linéaire

Algorithme d'Euclide

Optimisation combinatoire

Algorithme d'approximation

Afficher plus