Séance de cours

Profondeur-première recherche: Exploration et analyse

Dans cours

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, ma

Description

Cette séance de cours couvre l'algorithme DFS (Depth-First Search), qui explore systématiquement chaque bord d'un graphique, à partir de différents sommets. Il introduit le concept de découverte et de temps de finition pour chaque sommet, formant une forêt de profondeur. La séance de cours explique le pseudocode de DFS et analyse la classification des arêtes dans la forêt en profondeur, y compris les arêtes des arbres, des arrières, des avants et des traverses. Il traite également des théorèmes de Parenthèse et de Chemin blanc, fournissant des informations sur les relations entre les sommets lors de l'exploration DFS. Un exemple lié à s'habiller le matin est utilisé pour illustrer les concepts discutés.

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

Enseignants (3)

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.

Mikhail Kapralov

Source officielle

Proximité ontologique

Mathématiques

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

Séances de cours associées (26)

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.

Algorithmes graphiques : Modélisation et transversalité

Couvre les algorithmes graphiques, la modélisation des relations entre les objets et les techniques de traversée telles que BFS et DFS.

Algorithmes de graphes : notions de base

Introduit les bases des algorithmes de graphes, couvrant les structures de traversée, de représentation et de données pour BFS et DFS.

Graph Algorithms: Gestion de la mémoire et Traversal

Explore la gestion de la mémoire, la représentation graphique et les algorithmes de traversée en Python, en mettant l'accent sur BFS et DFS.

Graphiques: BFS

Introduit des algorithmes de graphes élémentaires, en se concentrant sur Breadth-First Search et Depth-First Search.

Afficher plus