- Unité d'enseignement : Graphes et applications
Nombre de crédits de l'UE : 2
Code APOGEE : PL6021IF
Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
Durée de projet en autonomie (PRJ)
3 h
Activité tuteurée personnelle (étudiant)
15 h
Activité tuteurée encadrée (enseignant)
3 h
Heures de Tutorat étudiant
0 h
* Ces horaires sont donnés à titre indicatif.
Pré-requis :
Elève Ingénieur de Polytech Lyon, Spécialité Informatique, Année 3
Compétences attestées (transversales, spécifiques) :
A l’issue de ce cours, les étudiants :
-
maîtriserons les algorithmes fondamentaux de la théorie des graphes, leur complexité ainsi que leur implémentation
-
serons capable de modéliser un problème sous forme d’un graphe, puis d’utiliser, d’adapter ou de créer un algorithme pour résoudre ce problème sur ce graphe
Programme de l'UE / Thématiques abordées :
L’objectif est de vous présenter les concepts et les algorithmes fondamentaux de théorie des graphes, ainsi que les problématiques qui y sont associées.
Le plan du cours ets le suivant :
- Introduction
- Généralités sur les graphes
- Représentation d’un graphe en machine
- Parcours dans les graphes
- Arbre recouvrant
- Plus court chemin dans un graphe
- Coloration d’un graphe
- Graphes planaires
- Flots et réseaux de ransports
- Analyse des réseaux d’interactions
Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 13/02/2024
SELECT MEN_ID, `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`, `PAR_ID` FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='18674' ORDER BY `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`
