ECUE XSE912 - Graphes et applications

UE Informatique industrielle S9 - 1 ECTS



 Structure & Enseignants
Type
Heures
Enseignants Associés
CM 12 (x1)
 Bruno Rouzeyre 12h


 Description
Enseignant Responsable Bruno Rouzeyre
THE 12
Description ECUE

Applications de la théorie des graphes dans le métier d'ingénieur.

Mots clés Graphes
Algorithmes et méthodes
Optimisation

Modalités de contrôle
  • 1 examen final
Contexte

De nombreux problèmes rencontrés dans la pratique du métier d'ingénieur (planification, optimisation, etc...) relèvent de la théorie des graphes. La finalité de cet enseignement est de donner aux étudiants les outils et méthodes permettant de résoudre de façon efficace ce type de problème.

Contenu
  • Notions de complexité algorithmique
  • Graphes, définitions et représentations
  • Méthodes de parcours
  • Recherche et existence de chemins
  • Détection de circuits
  • Enumération des chemins
  • Définition, représentation, recherche d'un chemin extremum
  • Algorithmes de FORD, de Moore, de FLOYD
  • Problèmes d'ordonnancement
  • Arbres et arborescences
  • Arbres de recouvrements minimums : méthodes de Prim, de Kruskal
  • Applications
  • Flot sur un graphe, définition
  • Recherche du flot maximum, algorithme de FORD-FULKERSON
  • Couplages
  • Chemins hamiltoniens et eulériens
  • Problèmes ouverts
Ressources
  • Polycopié : www.lirmm.fr/~rouzeyre
  • Livres de référence :
    • ”Graphes et Algorithmes” M. Gondran et M. Minoux. Coll. de la direction des études et recherche d’électricité de France. Editions Eyrolles.
    • ”Graph theory with applications to engineering and computer science” N. Deo. Series in Automatic Computation. Editions Prentice Hall.
Prérequis
+ -
+ -
+ -
+ -


 Connaissances
#
Libellé
N
A
M
E
0
Graphe x
0
Optimisation de chemin x
0
Recouvrement d'un graphe x
0
Couplage x


 Compétences
#
Libellé
N
A
M
E
0
Identifier un problème relevant de la théorie des graphes x
0
Choisir la méthode de résolution du problème x
0
Développer des variantes de l'algorithme du problème standard pour des cas particuliers x


 Capacités
#
Libellé
Non
Oui
1
Rédiger x
2
Communiquer x
3
Travailler en équipe x
4
Animer et piloter un groupe, un projet x
5
Rigueur et organisation x
6
Sens pratique x
7
Sens critique x
8
Ouverture d'esprit x
9
Capacité d'analyse et de synthèse x
10
Capacité d'abstraction, logique x
11
Capacité d'initiative x
12
Créativité x


 Compétences RNCP
Type
#
Libellé
0
1
2
CTI
1
Aptitude à mobiliser les ressources d'un large champ de sciences fondamentales. x
CTI
2
Connaissance et compréhension d'un champ scientifique et technique de spécialité. x
CTI
3
Maîtrise des méthodes et des outils de l'ingénieur : identification et résolution de problèmes, même non familiers et non complètement définis, collecte et interprétation de données, utilisation des outils informatiques, analyse et conception de systèmes complexes, expérimentation. x
CTI
4
Capacité à s'intégrer dans une organisation, à l'animer et à la faire évoluer : engagement et leadership, management de projets, maîtrise d'ouvrage, communication avec des spécialistes comme avec des non-spécialistes. x
CTI
5
Prise en compte des enjeux industriels, économiques et professionnels : compétitivité et productivité, innovation, propriété intellectuelle et industrielle, respect des procédures qualité, sécurité. x
CTI
6
Aptitude à travailler en contexte international : maîtrise d'une ou plusieurs langues étrangères, sûreté, intelligence économique, ouverture culturelle, expérience internationale. x
CTI
7
Respect des valeurs sociétales : connaissance des relations sociales, environnement et développement durable, éthique. x
POL
1
Aptitude à participer aux actions de recherche et développement des entreprises, éventuellement en lien avec les acteurs de la recherche publique, et à apporter l’esprit d’innovation favorisant l’évolution technologique. x
MEA-SE
1
Spécifier et modéliser dans leur environnement des systèmes embarqués, sous contrainte de cahier des charges, en intégrant les évolutions de l'état de l'art. x
MEA-SE
2
Concevoir, simuler, prototyper et programmer des systèmes embarqués. x
MEA-SE
3
Réaliser, industrialiser, tester et maintenir des systèmes embarqués. x
MEA
4
Spécifier et concevoir des circuits et systèmes intégrés en vue de leur production industrielle. x
MEA
5
Modéliser un système physique, puis concevoir et mettre en œuvre une architecture de contrôle/commande adaptée. x