AccueilLicence généraleInformatiqueEnseignementsAlgorithmique avancée et théorie des graphes

Licence InformatiqueUE Algorithmique avancée et théorie des graphes

Contenu

L'objectif de cette unité d'enseignement est d'étudier les graphes tant du point de vue de leurs possibilités de modélisation de problèmes réels, en tant que structure de données avec les algorithmes associés et aussi pour leurs caractéristiques mathématiques propres.

  • Algorithmes de plus court chemins (algorithmes de Dijkstra et Floyd-Warshall)
  • Parcours de graphes : propriétés et applications (tri topologique, composantes fortement connexes)
  • Flots dans un graphe, coupe minimum
  • Énumération et algorithmes par rebroussement
  • Programmation récursive
  • Algorithmes d'approximation
  • Algorithmes randomisés
  • Géométrie algorithmique
  • Circuits Hamiltoniens, cycle Eulérien, graphes bipartis
  • Couplages
  • Coloration de graphes

Compétences visées

  • Évaluer la complexité et la correction d’une solution algorithmique
  • Mettre en œuvre des algorithmes et des structures de données
  • Choisir, sur des critères objectifs, les structures de données et construire ou sélectionner les algorithmes les mieux adaptés à un problème donné
  • Concevoir un algorithme en utilisant des stratégies algorithmiques adaptées aux problèmes
  • Modéliser un problème concret sous la forme d'un problème algorithmique connu
  • Faire preuve d'esprit critique vis-à-vis d'une solution technique pour en vérifier son efficacité, sa fiabilité et sa robustesse dans son contexte d'utilisation

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

  • Algorithmique (3ème édition). Thomas H. Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, 2010.

Pré-requis recommandés

  • Algorithmique et structures discrètes

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 18 heures
  • Travaux pratiques : 24 heures

Les formations qui utilisent cet enseignement