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 :

  1. Structure de Données efficaces, notion de complexité amortie (accès/construction)
    1. Récapitulation des structures de données (tas, B-arbre, arbres rouge-noir)
    2. Exemple des kd-trees pour accéder aux k+proches voisins
  2. Problèmes d’optimisation à algorithmes polynomiaux
    1. Programmation Linéaire (PL) en nombre réels (problèmes d'optimisation à solution continue) : étude de l'algorithme du Simplex
    2. Flots : problème de répartition optimale de la circulation d'une quantité dans un réseau.
  3. Méthodes de recherche locale sans garantie (incomplètes) : problèmes d'optimisation combinatoire à solution discrète
    1. voisinage (une affectation complète qu’on fait évoluer)
    2. algorithme génétique (plusieurs affectations complètes (population)) avec meta-heuristiques (pour éviter les optimum locaux)

TP + projets maison:

Objectifs

Attendus

Bibliographie

Introduction to Algorithms, third edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press.