Séance de cours

Flow Networks : la méthode Ford-Fulkerson

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

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

Description

Cette séance de cours couvre les réseaux de flux, y compris la définition d'un flux, la valeur d'un flux et la méthode Ford-Fulkerson. Il explique comment trouver des voies croissantes et augmenter le flux dans un réseau, en mettant l'accent sur la conservation des flux et les contraintes de capacité.

Enseignant·e·s (3)

Mikhail Kapralov

Enseignement et PhD Doctorant·es actuel·les Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth A dirigé les thèses EPFL de Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail A co-dirigé les thèses EPFL de Paritosh Garg Cours Algorithms II CS-450 Un premier cours de 2eme cycle sur les algorithmes, ce cours a peu de prerequis, mais va vite. Il couvre les techniques principales d'analyse et de

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Source officielle

Concepts associés (12)

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.

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.

Loi de conservation

vignette|redresse|Emmy Noether est une mathématicienne allemande dont le théorème explique le lien fondamental entre la symétrie et les lois de conservation. En physique, une loi de conservation exprime qu'une propriété mesurable particulière d'un système physique reste constante au cours de l'évolution de ce système.

Conservation de la masse

La conservation de la masse (ou de Lavoisier) est une loi fondamentale de la chimie et de la physique. Elle indique non seulement qu'au cours de toute expérience, y compris si elle implique une transformation chimique, la masse se conserve, mais aussi que le nombre d'éléments de chaque espèce chimique se conserve (cette loi ne s'applique pas à l'échelle nucléaire : voir défaut de masse). Comme toute loi de conservation elle s'exprime par une équation de conservation.

Fluide incompressible

Un fluide incompressible est un fluide dont le volume est considéré comme constant quelle que soit la pression qu'il subit, tout fluide étant en réalité sensible à la pression. Par nature, tous les fluides sont compressibles, certains plus que d'autres, et en phase gazeuse considérablement plus qu'en phase liquide. La compressibilité d'un fluide mesure la variation de volume d'une certaine quantité de ce fluide lorsqu'il est soumis à une pression extérieure.

Afficher plus

Séances de cours associées (22)

Flux de réseau et formulations LP

Explique les flux réseau, les formulations LP, la méthode simplex, la dualité et les applications pratiques.

Le problème du transbordement, Le problème de l'affectation MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore le problème de la cession et sa transformation en un problème de transbordement, en montrant un exemple avec la vente de chefs-d'œuvre aux enfants.

Simplex Algorithme: Bases

Introduit l'algorithme Simplex pour résoudre les problèmes de flux et gérer les cycles de coûts négatifs.

Algorithmes graphiques : Ford-Fulkerson et composants fortement connectés

Discute de la méthode Ford-Fulkerson et des composants fortement connectés dans les algorithmes graphiques.

Pitot Tube et Venturi Principe

Explique le tube de Pitot, le principe de Venturi, la conservation de l'écoulement, et l'équation de Bernoulli pour la dynamique des fluides.

Afficher plus

Concepts associés (12)

Optimisation combinatoire

Optimisation (mathématiques)

Loi de conservation

Conservation de la masse

Fluide incompressible

Afficher plus