Graphe [T6IS323M]

Graphe [T6IS323M]

En pratique

Nature
Elément constitutif
Volume horaire de TD
6
Volume horaire de CM
14
Volume horaire de travail personnel
14
Langue d'enseignement
Français

Description du contenu de l'enseignement

Ce module introduit la notion de graphe et présence les problèmes et propriétés théoriques associés ainsi que les algorithmes fondamentaux qui permettent de les résoudre.


This module introduces the notion of graph and presents the associated theoretical problems and properties as well as the fundamental algorithms used to solve them.

Organisation

Modalités d'organisation et de suivi

  1. Introduction, vocabulaire et définitions
  2. Type abstrait de données
  3. Opérations de base, opérations binaires et fermetures
  4. Connexité et composantes fortement connexes
  5. Graphes valués et recherche de chemins de valeur optimale
  6. Problèmes d'ordonnancement
  7. Réseaux de transport

  1. Introduction, vocabulary and definitions
  2. Abstract type of data
  3. Basic operations, binary operations and closures
  4. Connectivity and strongly connected components
  5. Valued graphs and search for optimal value paths
  6. Scheduling problems
  7. Transportation networks

Informations pédagogiques

Compétences à acquérir

  • Connaître et comparer les algorithmes de base des graphes
  • Identifier les conditions d'application des algorithmes de recherche de chemins
  • Modéliser un problème pratique à l'aide d'un graphe

  • Know and compare basic graph algorithms
  • Identify the conditions of application of path search algorithms
  • Model a practical problem using a graph

Pré-requis recommandés

  • T6IS313M Structures de données
  • TI3AOINR Algorithmique
  • TI3AORTR Algorithmique
  • TI3DOINR Développement objet
  • TI3DORTR Développement objet

  • T6IS313M Data Structures
  • TI3AOINR Algorithmics
  • TI3AORTR Algorithmics
  • TI3DOINR Object-oriented development
  • TI3DORTR Object-oriented development

 

Bibliographie, lectures recommandées

  • Introduction à l’algorithme, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Ed. Dunod
  • Conception d'algorithmes, P. Bosc, M. Guyomard, L. Miclet, Ed Eyrolles
Dernière modification : mer, 06/01/2021 - 17:34