Algorithmique Avancée
Recherches complètes et incomplètes de solutions optimales
5 ECTS - 60% CDT - 40% TPs - Tronc
commun
Prérequis :
Graphes + Structures de données
Responsable :
Florence Bannay
Programme :
- Structure de Données efficaces, notion de complexité amortie
(accès/construction)
- Récapitulation des structures de données (tas, B-arbre, arbres
rouge-noir)
- Exemple des kd-trees pour accéder aux k+proches voisins
- Problèmes d’optimisation à algorithmes polynomiaux
- Programmation Linéaire (PL) en nombre réels (problèmes
d'optimisation à solution continue) : étude de l'algorithme du
Simplex
- Flots : problème de répartition optimale de la circulation
d'une quantité dans un réseau.
- Méthodes de recherche locale sans garantie (incomplètes) :
problèmes d'optimisation combinatoire à solution discrète
- voisinage (une affectation complète qu’on fait évoluer)
- algorithme génétique (plusieurs affectations complètes (population))
avec meta-heuristiques (pour éviter les optimum locaux)
TP + projets maison:
- codage d’un kd-tree
- codage de l’alogrithme de Ford-Fulkerson et utilisation des outils PL
- modélisation de petits problèmes en Flots et PL
- codage d'un algorithme de recherche locale
Objectifs
- acquérir les bases de différents formalismes permettant de modéliser
un problème de recherche de solution optimale
- maîtriser des classes d’algorithmes adaptées à chaque formalisme et
différencier les recherches dans les cas discrets ou continus, et les
recherches complètes ou incomplètes
Attendus
- Connaître les structures de données efficaces (Notions)
- Savoir évaluer la complexité amortie de l’accès/construction des
données (Usage)
- Savoir implémenter des kd-trees (Usage)
- Identifier les caractéristiques d’un problème d’optimisation (Notions)
- Formaliser un problème spécifié en langage naturel en termes de
contraintes linéaires ou en termes de Flots
- Savoir implémenter et utiliser un algorithme de résolution de PL ou de
Flots (Usage)
- Choisir et implémenter un algorithme approprié de recherche locale
(Usage)
Bibliographie
Introduction to Algorithms, third edition. By Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press.