Idées d’apprentissage actif
Les graphes représentent l'outil de modélisation le plus polyvalent du programme de NSI. Ils permettent de formaliser des relations complexes entre des objets, qu'il s'agisse de réseaux sociaux, de cartes routières ou de liaisons internet. Les élèves découvrent les notions de sommets, d'arcs (ou arêtes), de pondération et d'orientation, tout en apprenant à traduire ces schémas en structures de données informatiques comme les matrices d'adjacence ou les listes de listes.
Activité 01
Plusieurs situations sont affichées (réseau de bus, amitiés Facebook, dépendances logicielles). Les élèves circulent et doivent dessiner le graphe correspondant en précisant s'il est orienté ou pondéré.
Comment représenter un graphe en mémoire ?
Activité 02
Les groupes reçoivent un graphe dense et un graphe creux. Ils doivent essayer de les représenter avec une matrice d'adjacence et une liste de successeurs, puis débattre de la méthode la plus efficace en mémoire.
Quelle est la différence entre un graphe orienté et non orienté ?
Activité 03
Sur un grand graphe au sol, les élèves doivent trouver le chemin le plus court entre deux points. Ils découvrent par l'expérience la difficulté de l'optimisation dans les graphes complexes.
Qu'est-ce qu'un chemin dans un graphe ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Penser qu'un graphe est forcément planaire (sans croisement d'arêtes).
Un graphe est une structure abstraite ; la position des sommets n'importe pas, seules les connexions comptent. Faire redessiner le même graphe de plusieurs façons différentes aide à briser cette illusion visuelle.
Confondre successeurs et prédécesseurs dans un graphe orienté.
Dans un graphe orienté, le sens de la flèche est crucial. Utiliser des exemples de relations asymétriques (A suit B sur Twitter) permet de clarifier cette notion par la discussion.
Méthodes utilisées dans ce dossier
Structures de données linéaires
Étude des listes, piles et files, ainsi que de leurs implémentations. Compréhension des interfaces et de la séparation entre spécification et implémentation.
8 methodologies
Arbres
Découverte des arbres hiérarchiques, des arbres binaires et des arbres binaires de recherche. Calcul de la taille et de la hauteur d'un arbre.
8 methodologies