Séance de cours

Maximisation sous-modulaire

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-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

Cette séance de cours couvre le sujet des fonctions sous-modulaires et de leur maximisation, en se concentrant sur l'algorithme gourmand et sa garantie d'approximation. L'instructeur explique le concept de monotonie et démontre l'algorithme gourmand étape par étape, en mettant l'accent sur son rapport d'approximation et l'importance des éléments spéciaux dans le processus.

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

Utility functions on indivisible goods

Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an item cannot be divided among two or more agents. It is usually assumed that every agent assigns subjective utility to every subset of the items. This can be represented in one of two ways: An ordinal utility preference relation, usually marked by .

Approximation diophantienne

vignette|Meilleurs approximations rationnelles pour les nombres irrationnels Π (vert), e (bleu), φ (rose), √3/2 (gris), 1/√2 (rouge) et 1/√3 (orange) tracées sous forme de pentes y/x avec des erreurs par rapport à leurs vraies valeurs (noirs) par CMG Lee. En théorie des nombres, l'approximation diophantienne, qui porte le nom de Diophante d'Alexandrie, traite de l'approximation des nombres réels par des nombres rationnels.

Algorithme de Kruskal

En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe.

Péché

vignette|redresse=1.2|La Chute de l'homme par Lucas Cranach. En religion, un péché est une offense faite à Dieu ou à un dieu, et une transgression délibérée ou non de la loi divine. Le mot « péché » vient du latin peccatum, « faute, erreur », lui-même dérivé du verbe peccare, qui signifie au sens premier « broncher, faire un faux pas ». Selon les linguistes Alfred Ernout et Antoine Meillet, . L'origine de peccare semble donc inconnue. L'adjectif correspondant est peccamineux et a aussi donné impeccable.

Péché mortel

Le péché mortel est une désobéissance à la loi de Dieu en matière grave, commise avec pleine advertance et consentement délibéré.[...] Le péché grave s’appelle mortel, parce qu’il prive l’âme de la grâce divine qui est sa vie, lui enlève les mérites et la capacité d’en acquérir de nouveaux, et la rend digne de la peine ou mort éternelle en enfer. Il s'enracine dans la Première épître de Jean où il est écrit (1 Jn 5,16) : .

Afficher plus

Séances de cours associées (41)

05.10.23 - Gauss and Green theorem in 2D

Introduction à la physique du plasma

Introduit les bases de la physique du plasma, couvrant le comportement collectif, la longueur de Debye, et les conditions plasmatiques.

Pendule simple et oscillateur harmonique

Explore la dynamique d'un pendule simple et d'un oscillateur harmonique, y compris la loi de Hooke et les équations du mouvement.

Algorithmes d'approximation

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

Effets dynamiques : Fringes d'épaisseur MOOC: Microscopie électronique à transmission pour les sciences des matériaux

Déplacez-vous dans l'effet de diffusion dynamique des franges d'épaisseur dans les images TEM, couvrant les équations, les diagrammes d'intensité et l'imagerie par faisceau faible.

Afficher plus

Concepts associés (31)

Utility functions on indivisible goods

Approximation diophantienne

Algorithme de Kruskal

Péché

Péché mortel

Afficher plus