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

Optimisation discrète : la malédiction de la dimensionnalité

Description

Cette séance de cours explore les défis de l'optimisation discrète, en se concentrant sur la malédiction de la dimensionnalité. L'instructeur explique comment le temps de calcul augmente exponentiellement avec la taille du problème, ce qui rend l'énumération complète infaisable. Même avec les progrès de la puissance de calcul, la malédiction de la dimensionnalité reste un obstacle important, nécessitant le développement d’algorithmes plus efficaces.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Source officielle

Concepts associés (18)

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.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

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.

Afficher plus

Séances de cours associées (49)

Algorithme de Simplex : Tableau MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Couvre l'idée principale derrière l'algorithme Simplex et explique la méthode Tableau pour résoudre les problèmes de programmation linéaire.

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.

Classes de complexité: P et NP

Explore les classes de complexité P et NP, en mettant en évidence les problèmes solvables et vérifiables, y compris les défis complets du NP.

Algorithmes d'approximation

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

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

Optimisation linéaire en nombres entiers

Computational complexity

Théorie de la complexité (informatique théorique)

Classe de complexité

Optimisation combinatoire

Afficher plus