Connectez-vous à Affiligue
Lumni propose un catalogue de contenus éducatifs à destination des éducateurs et médiateurs, salariés ou bénévoles des structures du réseau de la Ligue de l'Enseignement.
Logo Lumni

Oups, veuillez renseigner une adresse email valide

France Télévisions et l’INA traitent votre adresse e-mail afin de vous adresser respectivement les newsletters Lumni et Lumni Médiateurs FTV, la newsletter Lumni Enseignants INA. Pour exercer vos droits sur vos données personnelles, cliquez sur le lien de désabonnement intégré dans les newsletters ou contactez FTV ou l’INA. Pour en savoir plus, voir les politiques de confidentialité de FTV et de l’INA.

Culture algorithmique

L’informatique et ses fondements

Publié le 25/06/19Modifié le 06/11/19
Connectez-vous à Affiligue
Lumni propose un catalogue de contenus éducatifs à destination des éducateurs et médiateurs, salariés ou bénévoles des structures du réseau de la Ligue de l'Enseignement.

Comment structurer les données avec un graphe ?

Il existe beaucoup de structures de données complexes en informatique : la liste, les listes doublement chaînées, les piles et files qui servent notamment à stocker des tâches à effectuer, les tables de hachage pour représenter des ensembles, des arbres et des tas qui sont des structures plus compliquées, avec beaucoup de structures sous-jacentes, les graphes et les bases de données

Qu'est-ce qu'un graphe ? 

Un graphe est constitué de nœuds et d'arêtes (des flèches qui vont d'un nœud vers un autre nœud). Un graphe peut représenter beaucoup de choses : des réseaux (internet, électrique, d'eau...), des dépendances (pour faire C, on a besoin de faire B), des relations (A et B se connaissent)... Il y a différents types de graphes. Il peut y avoir des graphes sans flèches, ce sont des graphes non orientés. Pour les représenter par des structures de données, il y a plusieurs possibilités :

  • le graphe d'adjacence, qui consiste à utiliser un booléen pour indiquer si deux nœuds sont en relation.
  • la liste de voisins. Par exemple, le graphe A a deux voisins qui sont B et C. Le graphe C n'a pas de voisin.

On peut utiliser un graphe de dépendances pour représenter ce MOOC : cela permet d'identifier les séquences nécessaires pour suivre une séquence donnée. Pour ce faire, on peut utiliser un algorithme

Nom de l'auteur : Liliane Kahmsay / Florent Masseglia

Producteur : Inria

Année de diffusion : 2016

Voir plus