Séance de cours

Problème de sous-réseau maximal

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 la méthode Master pour résoudre les récurrences, en introduisant le théorème Master pour analyser les algorithmes. Il se penche ensuite sur le problème du sous-réseau maximum, expliquant la structure de solution optimale et le concept de trouver le sous-réseau maximum qui traverse le point médian. La séance de cours explore les approches de la force brute, l'importance de considérer toutes les possibilités et la solution pour trouver le sous-réseau maximum. Il se termine par une explication détaillée de l'algorithme FIND-MAX-CROSSING-SUBARRAY. Les scénarios du monde réel, tels que la négociation dactions, sont utilisés pour illustrer les applications pratiques des concepts discutés.

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)

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.

Algorithme probabiliste

En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].

Stock trader

A stock trader or equity trader or share trader, also called a stock investor, is a person or company involved in trading equity securities and attempting to profit from the purchase and sale of those securities. Stock traders may be an investor, agent, hedger, arbitrageur, speculator, or stockbroker. Such equity trading in large publicly traded companies may be through a stock exchange. Stock shares in smaller public companies may be bought and sold in over-the-counter (OTC) markets or in some instances in equity crowdfunding platforms.

Bourse des valeurs

La bourse des valeurs est le lieu où s'échangent les valeurs mobilières, c'est-à-dire des titres financiers négociables, interchangeables et fongibles : actions, obligations, titres de créances négociables, parts d'OPCVM (sicav et FCP), bons de souscription, certificats d'investissement, warrants, options et stocks options. Les devises s'échangent sur le marché des changes et les matières premières dans les bourses de commerce. Ces dernières ont souvent été le premier lieu d'accueil de ces trois types de marché.

Algorithme de recherche

En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.

Afficher plus

Séances de cours associées (64)

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Programmation dynamique : prise de décision optimale

Explore la programmation dynamique pour optimiser les processus de prise de décision au fil du temps, en utilisant des exemples concrets tels que l'extraction de pétrole et la négociation d'actions.

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Multiplication matricielle et techniques de division et de conquête

Discute de la multiplication matricielle en utilisant des techniques de division et de conquête et introduit l'algorithme de Strassen pour une efficacité améliorée.

Algorithmes en informatique: techniques de recherche et de tri

Fournit un aperçu des algorithmes de recherche et de tri essentiels en informatique.

Afficher plus

Concepts associés (32)

Algorithme

Algorithme probabiliste

Stock trader

Bourse des valeurs

Algorithme de recherche

Afficher plus