Séance de cours

Arbres de recherche binaires optimaux

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 le concept d'arbres de recherche binaires optimaux, expliquant l'approche ascendante pour calculer le coût de recherche attendu. L'instructeur démontre l'algorithme de programmation dynamique, en discutant du pseudocode et de l'analyse de l'exécution. La séance de cours comprend également une section sur la résolution d'un examen à mi-parcours de 2016, en se concentrant sur les stratégies de résolution de problèmes algorithmiques.

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)

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.

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

Source officielle

Concepts associés (32)

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.

Arbre splay

Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.

Algorithme de Rémy

L'algorithme de Rémy est un générateur d'arbres binaires, dont la principale application est un algorithme efficace de génération aléatoire d'arbres binaires. L'algorithme doit son nom à son inventeur Jean-Luc Rémy. L'algorithme de Rémy est dû à Jean-Luc Rémy, chercheur au Centre de recherche en informatique de Nancy. Il a été créé en 1978 sans être publié immédiatement et a fait partie du folklore de l'algorithmique et de la combinatoire énumérative jusqu'à sa parution dans une revue francophone en 1985.

Recherche dichotomique

La recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

Afficher plus

Séances de cours associées (64)

Programmation dynamique : sous-séquences palindromiques

Explore la programmation dynamique des sous-séquences palindromiques, fusionnant les arbres de recherche binaires et trouvant la médiane de deux tableaux triés.

Algorithmes Préparation à l'examen

Offre un récapitulatif avant l'examen Algorithmes, couvrant les stratégies de résolution de problèmes et la mise en œuvre de l'algorithme avec des problèmes d'échantillon.

Structures de données : piles, files d'attente, listes liées

Couvre les piles, les files d'attente, les listes liées et les arbres de recherche binaires dans les structures de données.

Arbre de recherche binaire optimal

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

Recherche Binaire: Bases et Exécution MOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Explore les fondamentaux de la recherche binaire, l'efficacité et la complexité temporelle dans la recherche algorithmique.

Afficher plus

Concepts associés (32)

Self-balancing binary search tree

Arbre binaire

Arbre splay

Algorithme de Rémy

Recherche dichotomique

Afficher plus