FormationsMasterInformatiqueEnseignementsAlgorithme à performance garantie

Master InformatiqueUE Algorithme à performance garantie

Informations

Contenu

  • Algorithmes d'approximation de nature combinatoire pour les problèmes

NP-complets suivants : Voyageur de Commerce, arbre de Steiner, ordonnancement de taches, clustering, p-centres, sac à dos, bin packing, couverture d'ensemble, la plus courte sur-séquence commune ;

  • FPTAS et PTAS (ordonnancement de taches et sac à dos) ;
  • Algorithmes d'approximation par programmation linéaire : l'arrondi et la méthode primale-duale (MAXSAT, couverture d'ensemble, multicoupes et multiflots dans les arbres) ;
  • Algorithmes en ligne et compétitivité : la pagination et les k-serveurs.

Langue utilisée

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

Volume des enseignements

  • Cours magistraux : 10 heures
  • Travaux dirigés : 10 heures
  • Travaux pratiques : 10 heures

LES FORMATIONS QUI UTILISENT CET ENSEIGNEMENT