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

Physarum peut calculer les chemins les plus courts

Dans cours

COM-502: Dynamical system theory for engineers

Linear and nonlinear dynamical systems are found in all fields of science and engineering. After a short review of linear system theory, the class will explain and develop the main tools for the qualitative analysis of nonlinear systems, both in discrete-t ...

Description

Cette séance de cours explore comment Physarum Polycephalum, un moule mince, peut calculer les chemins les plus courts dans un modèle graphique dirigé. Il se déplace dans le routage du flux d'unité dans le graphique, les points d'équilibre, et les fonctions de Lyapunov.

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

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

Source officielle

Concepts associés (32)

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Problème de plus court chemin

vignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.

Graphe (type abstrait)

thumb|upright=1.3|Un graphe orienté, dont les arcs et certains sommets sont « valués » par des couleurs. En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est la spécification formelle des données qui définissent l'objet mathématique graphe et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.

Base de données orientée graphe

Une base de données orientée graphe est une base de données orientée objet utilisant la théorie des graphes, donc avec des nœuds et des arcs, permettant de représenter et stocker les données. Par définition, une base de données orientée graphe correspond à un système de stockage capable de fournir une adjacence entre éléments voisins : chaque voisin d'une entité est accessible grâce à un pointeur physique. C'est une base de données orientée objet adaptée à l'exploitation des structures de données de type graphe ou dérivée, comme des arbres.

Afficher plus

Séances de cours associées (35)

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.

Points fixes dans la théorie des graphiques

Se concentre sur les points fixes dans la théorie des graphiques et leurs implications dans les algorithmes et l'analyse.

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.

Connectivité dans la théorie des graphiques

Couvre les fondamentaux de la connectivité dans la théorie des graphiques, y compris les chemins, les cycles et les arbres qui s'étendent.

Voies les plus courtes: Poids négatifs et applications

Couvre Minimum Spanning Trees, Kruskal's Algorithm, et Shortest Paths dans les graphiques dirigés.

Afficher plus

Concepts associés (32)

Graphe orienté acyclique

Théorie des graphes

Problème de plus court chemin

Graphe (type abstrait)

Base de données orientée graphe

Afficher plus