Intitulé de la matière :       Algorithmes Avancées

Intitulé de l’UE :      UEF2

Crédits : 4

Coefficients : 2

Objectifs de l’enseignement

L’implémentation de systèmes capables d’opérer des tâches intelligentes requiert des langages puissants pour représenter des problèmes complexes et des méthodes avancées pour explorer des espaces de solutions dont la taille croît exponentiellement. Le but c’est maîtriser ces deux aspects.

Connaissances préalables recommandées: Notions en algorithmique.

Contenu de la matière

1.      Algorithmes d'approximation pour les problèmes d'ordonnancement, de sac à dos multidimensionnel (bin packing), de multi-coupes, de connectivité, de classification, couverture d'ensembles, localisation d'entrepôts, SAT.

2.      Algorithmes d'approximation pour les problèmes géométriques (voyageur de commerce, arbre de Steiner, triangulation de poids minimum, p-centres).

3.      Notions variées d'approximation.

4.      Algorithmes randomisés à performance garantie.

5.      Algorithmes en ligne: la pagination et les k-serveurs.



Mode d’évaluation : (Continu :40%, EMD :  60%).

Références

  • V. Vazirani. Algorithmes d'approximation. Springer Editions (mars 2006).
  • J. Carlier, P. Chrétienne. Problèmes d'ordonnancement.
  • J.C. Billaut, A. Moukrim, E. Sanlaville. Flexibilité et robustesse en ordonnancement Hermès Science 2005.

Algorithmes Avancés (Cours)


Le cours d'algorithme avancé ou algorithme à performance garantie est destiné aux étudiants inscrits en master informatique, ayants des prérequis en algorithmique (algorithme1, Algorithme2 et Algorithme3) et en théorie des graphes et programmation linéaire. L'objectif de ce cours est d'initier les étudiants aux différents classes des problèmes et de donner les méthodes de résolutions appropriées pour les problèmes de classes NP-difficile.