Parcours de Graphes
(PDG)
- Coefficient : 1
- Volume Horaire: 19.25h estimées de travail (dont 13.75h EdT)
- Labo : 10h encadrées (et 3.75h 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
Évaluations en contrôle continu grâce à l'environnement de travail ENIBEXAM utilisé en labo.
Mots clés
Graphes, parcours de graphes.
Pré-requis
Algorithmique et langage de type python.