Graphes

Graphes

  • 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.
Lire moins

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.
Lire moins

Heures d'enseignement

  • Graphes - CMCours Magistral19,5h
  • Graphes - TPTravaux Pratique19,5h

Pré-requis obligatoires

UE structures de données et type abstrait - Informatique Fondamentale.

Lire moins

Contrôle des connaissances

100% Contrôle Continu

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.

Lire moins

Informations complémentaires

Poursuites possibles : UE Recherche Opérationnelle en S6 .

Lire moins

Compétences acquises

Compétences

Niveau d'acquisition

Analyse d'un questionnement en mobilisant des concepts disciplinairesAnalyser 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 disciplinaireAnalyser 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 boucle1 - 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èmes3 - Maitrise
Identification d'un questionnement au sein d'un champ disciplinaireChoisir, sur des critères objectifs, les structures de données et construire les algorithmes les mieux adaptés à un problème donné.3 - Maitrise