UE Graphes, optimisation discrète et continue

Au préalable, les outils nécessaires au développement, à la compréhension et à la description des méthodes seront
présentés :
- éléments de calcul différentiel
- théorie des graphes

Programme résumé :
Préambule :
Tous les algorithmes étudiés dans le cours sont présentés ainsi :
- principe de l'algorithme,
- l'algorithme
- étude d'un exemple
- justification de l'algorithme et analyse de sa complexité et/ou de sa convergence

Partie Graphes et applications:
- Généralités : définitions, terminologies
- Parcours de graphes (orientés, non orientés) :
    . parcours en profondeur (version récursive, itérative, forêt couvrante associée)
    . parcours en largeur
- Connexité et forte connexité : définitions, recherche de composantes connexes, fortement connexes
- Plus courts chemins :
      . définitions, conditions d'existence
      . les algorithmes : Dijsktra, Bellman, Floyd
- Arbres de recouvrement minimum :
      . définitions, conditions d'existence, d'unicité
      . les algorithmes : Kruskal, Prim
-  Etudes de problèmes :  problèmes de coloration, tri topologique, ...

Voir la page complète

Au préalable, les outils nécessaires au développement, à la compréhension et à la description des méthodes seront
présentés :
- éléments de calcul différentiel
- théorie des graphes

Programme résumé :
Préambule :
Tous les algorithmes étudiés dans le cours sont présentés ainsi :
- principe de l'algorithme,
- l'algorithme
- étude d'un exemple
- justification de l'algorithme et analyse de sa complexité et/ou de sa convergence

Partie Optimisation:
- Exemples et modèlisation conduisant à des problèmes d'optimisation
- Calcul différentiel
- Algorithmes d'optimisation en dimension finie :
    . résolution d'équation : méthode de Newton ;
    . recherche du minimum :  gradient, gradient conjugué.
- Exemples de problèmes avec contraintes :
    . programmation linéaire ;
    . optimisation de flot dans les graphes ;
    . méthode de Lagrange.

Voir la page complète