ECTS
4 crédits
Composante
Collège Sciences et Technologies pour l’Energie et l’Environnement (STEE)
Volume horaire
39h
Description
L’objectif est de donner aux étudiants les prérequis nécessaires pour modéliser un problèmes réel à l’aide d’un graphe et le formuler, ensuite, en terme d’un problème classique des graphes, problème dont la résolution se ramène à un choix critique (calculabilité, complexité) d’un algorithme sur les graphes.
Les thématiques abordées sont :
- Notions de base sur les graphes,
- Connexité dans les graphes,
- Recouvrement minimum,
- Coloration de graphes,
- Recherche de chemin optimal.
Objectifs
À la fin de cette UE, vous serez capable de :
- Analyser un problème réel et le modéliser à l’aide d’un graphe,
- Formuler le problème en terme d’un problème de graphe,
- Proposer un algorithme de graphe pour le résoudre,
- Interpréter le résultat en terme du problème réel.
Heures d'enseignement
- Graphes - CMCours Magistral19,5h
- Graphes - TPTravaux Pratique19,5h
Pré-requis obligatoires
UE structures de données et type abstrait - Informatique Fondamentale.
Contrôle des connaissances
1ère session : 100% Contrôle Continu écrit
Le contrôle continu se base sur deux contrôles écrits de 1.5 h maximum chacun et d’un projet quasi-réel réalisé partiellement en séance.
2ème session : 100% examen terminal écrit.
Informations complémentaires
Poursuites possibles : UE Recherche Opérationnelle en S6 .
Compétences acquises
Compétences | Niveau d'acquisition | |
|---|---|---|
| Analyse d'un questionnement en mobilisant des concepts disciplinaires | Analyser et synthétiser des données complexes en vue de leur exploitation informatique. | 2 - Application |
| Mise en œuvre de méthodes et d'outils du champ disciplinaire | Analyser et interpréter les résultats produits par l'exécution d'un programme: terminaison, test , complexité | 1 - Notion |
| Expliquer et documenter la mise en œuvre d'une solution Informatique. | 1 - Notion | |
| Caractériser le rôle des tests et des preuves de correction dans le développement des logiciels et mettre en œuvre des tests élémentaires et des invariants de boucle | 1 - Notion | |
| Mettre en œuvre des méthodes d'analyse pour concevoir des modèles de données et des algorithmes à partir d'un cahier des charges partiellement défini. | 3 - Maitrise | |
| Appliquer des approches raisonnées de résolution de problèmes complexes: modèle formel d'un problème, réduction et complétude de problèmes | 3 - Maitrise | |
| Identification d'un questionnement au sein d'un champ disciplinaire | Choisir, sur des critères objectifs, les structures de données et construire les algorithmes les mieux adaptés à un problème donné. | 3 - Maitrise |
