Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes : examen final

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 une revue de l'examen final de 2016, en se concentrant sur les problèmes liés au hachage, aux relations de récurrence, à l'analyse de l'exécution de l'algorithme, aux arbres de recherche binaires, à la traversée des graphiques et à la conception de la structure des données. Les diapositives fournissent des explications détaillées et des solutions pour chaque problème, guidant les étudiants à travers le processus de compréhension et de résolution des défis 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)

Mikhail Kapralov

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

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

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.

Arbre binaire de recherche

En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

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.

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

Algorithmes graphiques II: Traversée et chemins

Explore les méthodes de traversée des graphes, les arbres couvrants et les chemins les plus courts en utilisant BFS et DFS.

Graphiques : Propriétés et représentations

Couvre les propriétés du graphique, les représentations et les algorithmes de traversée à l'aide de BFS et de DFS.

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.

Arbres d'éclaboussure minimum: Algorithme de Prim

Explore l'algorithme de Prim pour les arbres à portée minimale et introduit le problème Traveling Salesman.

Afficher plus

Concepts associés (32)

Algorithme

Arbre binaire de recherche

Self-balancing binary search tree

Arbre binaire

Algorithme de recherche

Afficher plus