Séance de cours

La sous-séquence la plus longue et la BST optimale

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 formulation récursive du problème de la sous-séquence commune la plus longue (LCS), en discutant de la mise en œuvre naïve et de l'approche ascendante pour trouver LCS. Il se penche également sur l'enregistrement des solutions optimales, la présentation du pseudocode et l'analyse pour LCS, et l'impression de la solution. En outre, il introduit le concept d'arbres de recherche binaires optimaux (BST), expliquant comment construire une BST avec un coût de recherche minimal en utilisant des probabilités. Des exemples sont fournis pour illustrer les concepts, soulignant que la BST optimale peut ne pas avoir la plus petite hauteur ou la clé de probabilité la plus élevée à la racine. La séance de cours se termine par des discussions sur le coût de recherche des clés dans une BST optimale et la sous-structure optimale pour construire un arbre de recherche binaire.

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

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Bayesian probability

Bayesian probability (ˈbeɪziən or ˈbeɪʒən ) is an interpretation of the concept of probability, in which, instead of frequency or propensity of some phenomenon, probability is interpreted as reasonable expectation representing a state of knowledge or as quantification of a personal belief. The Bayesian interpretation of probability can be seen as an extension of propositional logic that enables reasoning with hypotheses; that is, with propositions whose truth or falsity is unknown.

Probabilité conditionnelle

vignette|Illustration des probabilités conditionnelles avec un diagramme d'Euler. On a la probabilité a priori et les probabilités conditionnelles , et .|320x320px En théorie des probabilités, une probabilité conditionnelle est la probabilité d'un événement sachant qu'un autre événement a eu lieu. Par exemple, si une carte d'un jeu est tirée au hasard, on estime qu'il y a une chance sur quatre d'obtenir un cœur ; mais si on aperçoit un reflet rouge sur la table, il y a maintenant une chance sur deux d'obtenir un cœur.

Théorie des probabilités

La théorie des probabilités en mathématiques est l'étude des phénomènes caractérisés par le hasard et l'incertitude. Elle forme avec la statistique les deux sciences du hasard qui sont partie intégrante des mathématiques. Les débuts de l'étude des probabilités correspondent aux premières observations du hasard dans les jeux ou dans les phénomènes climatiques par exemple. Bien que le calcul de probabilités sur des questions liées au hasard existe depuis longtemps, la formalisation mathématique n'est que récente.

Afficher plus

Séances de cours associées (64)

Probabilités et statistiques: bases et applications

Couvre les concepts fondamentaux de probabilité et de statistiques, en se concentrant sur l'analyse des données, la représentation graphique et les applications pratiques.

Arbre de recherche binaire optimal

Explore les arbres de recherche binaires optimaux pour minimiser efficacement les coûts de recherche attendus.

Loi des grands nombres : Convergence forte

Explore la forte convergence des variables aléatoires et l'approximation de la distribution normale dans les probabilités et les statistiques.

Variables aléatoires continues

Explore les variables aléatoires continues, les fonctions de densité, les variables articulaires, l'indépendance et les densités conditionnelles.

Probabilité et statistiques

Introduit des concepts clés en probabilité et en statistiques, tels que les événements, les diagrammes de Venn et la probabilité conditionnelle.

Afficher plus

Concepts associés (31)

Self-balancing binary search tree

Arbre binaire

Bayesian probability

Probabilité conditionnelle

Théorie des probabilités

Afficher plus