Parcours de Graphes (05_XBPDG)
- Coefficient : 1
- Volume Horaire: 16.0h estimées de travail (dont 10.5h EdT)
- Labo : 9h encadrées (et 1.5h de séances d'études dirigées)
- Travail personnel hors EdT : 5.5h
Liste des AATs
Description
- Graphes orientés et non orientés :
- Eléments de théorie : définitions, représentations, matrice d’adjacence ;
- Propriétés : chemins, connexité, forte connexité, fermeture transitive ;
- Parcours :
- Parcours en largeur, profondeur ;
- Plus court chemin dans un graphe valué ou non : algorithmes de Ford et Dijkstra ;
- Algorithme A*.
Acquis d'Apprentissage visés (AAv)
- AAv1 [heures: 16, B2,B3] : À l'issue de l'enseignement, chaque élève est capable de mettre en œuvre correctement les outils mathématiques pertinents pour résoudre des problèmes de calculs de chemins optimaux (profondeur, largeur, plus court via Ford ou Dijkstra) dans des graphes orientés ou non, valués ou non. Concrètement, ceci signifie ici :
- L'élève est capable d'implémenter des algorithmes de parcours de graphe simples.
- L'élève peut reconnaître, éventuellement corriger, choisir et utiliser des algorithmes déjà fournis, pour résoudre un problème spécifique.
Modalités d'évaluation
Évaluation en contrôle continu grâce à l'environnement de travail ENIBEXAM utilisé en labo, et une évaluation en fin d'enseignement.
Mots clés
Graphes, parcours de graphes.
Pré-requis
Algorithmique et langage de type python.