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

Ford-Fulkerson : un exemple travaillé

Dans cours

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

Cette séance de cours fournit un exemple détaillé de l'algorithme de Ford-Fulkerson utilisant un graphique résiduel pour trouver le débit maximal d'une source à un puits dans un graphique donné. L'instructeur explique le processus étape par étape, en commençant par un flux initial de zéro et en trouvant de manière itérative des voies d'augmentation pour augmenter le flux. La séance de cours montre comment mettre à jour le graphique résiduel après chaque itération, pousser le flux à travers les chemins d'augmentation et déterminer quand l'algorithme atteint le flux maximum. L'instructeur met l'accent sur l'importance de choisir des chemins d'augmentation stratégiquement pour optimiser les performances et l'efficacité de l'algorithme.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e·s (2)

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Rom Pinchasi

Source officielle

Concepts associés (13)

Réseau de flot

En théorie des graphes, un réseau de flot (aussi appelé réseau de transport) est un graphe orienté où chaque arête possède une capacité et peut recevoir un flot (ou flux). Le cumul des flots sur une arête ne peut pas excéder sa capacité. Un graphe orienté est souvent appelé réseau en recherche opérationnelle. Les sommets sont alors appelés des nœuds et les arêtes des arcs. Pour qu'un flot soit valide, il faut que la somme des flots atteignant un nœud soit égale à la somme des flots quittant ce nœud, sauf s'il s'agit d'une source (qui n'a pas de flot entrant), ou d'un puits (qui n'a pas de flot sortant).

Théorème flot-max/coupe-min

Le théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits. Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

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

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.

Afficher plus

Séances de cours associées (36)

Optimisation des suspensions : analyse et optimisation des performances

Explore la conception et l'optimisation des suspensions de voiture pour améliorer les performances.

PCA : Dérivation et optimisation

Couvre la dérivation de la projection PCA, la minimisation des erreurs et l'optimisation du vecteur propre.

Rendu de pièce de monnaie: Partie 1 MOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Couvre le rendu des pièces et les limites de l'algorithme gourmand dans la recherche de solutions optimales.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Construction d'Ensembles Robust via Margin Boosting

Déplacez-vous dans la construction d'ensembles robustes grâce à l'augmentation de la marge pour améliorer la défense contradictoire dans les modèles d'apprentissage automatique.

Afficher plus

Concepts associés (13)

Réseau de flot

Théorème flot-max/coupe-min

Optimisation (mathématiques)

Optimisation combinatoire

Algorithme

Afficher plus