Séance de cours

Définir la couverture : Integrality Gap

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 concept de l'écart d'intégralité dans le contexte des algorithmes de couverture fixe et de pondérations multiplicatives. L'instructeur explique pourquoi le concept est utile et démontre son application à travers des exemples et des preuves.

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

Edge cover

In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time. Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C.

Proof by contradiction

In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved.

Ensemble flou

La théorie des sous-ensembles flous est une théorie mathématique du domaine de l’algèbre abstraite. Elle a été développée par Lotfi Zadeh en 1965 afin de représenter mathématiquement l'imprécision relative à certaines classes d'objets et sert de fondement à la logique floue. Les sous-ensembles flous (ou parties floues) ont été introduits afin de modéliser la représentation humaine des connaissances, et ainsi améliorer les performances des systèmes de décision qui utilisent cette modélisation.

Théorie des ensembles approximatifs

Théorie des ensembles approximatifs – est un formalisme mathématique proposé en 1982 par le professeur Zdzisław Pawlak. Elle généralise la théorie des ensembles classique. Un ensemble approximatif (anglais : rough set) est un objet mathématique basé sur la logique 3 états. Dans sa première définition, un ensemble approximatif est une paire de deux ensembles : une approximation inférieure et une approximation supérieure. Il existe également un type d'ensembles approximatifs défini par une paire d'ensembles flous (anglais : fuzzy set).

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.

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.

Sémantique à grande échelle : définition d'expressions et de commandes arithmétiques

Couvre la définition d'un langage de programmation simple et sa sémantique à grande échelle, y compris les expressions arithmétiques et les commandes impératives.

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Ensembles et fonctions

Introduit des ensembles et des fonctions, couvrant les analogies d'union, d'intersection, de complément, de terminologie de fonctions et d'opérations d'ensemble.

Optimisation quasi-newton

Couvre les méthodes de recherche de ligne de gradient et les techniques d'optimisation en mettant l'accent sur les conditions Wolfe et la définition positive.

Afficher plus

Concepts associés (32)

Edge cover

Proof by contradiction

Ensemble flou

Théorie des ensembles approximatifs

Optimisation (mathématiques)

Afficher plus