Algorithmique et optimisation discrète - 4MMAOD6

Objectif(s)

Titre complet: Algorithmique de l’optimisation discrète. Introduction à l'analyse de dépendances: parallélisme et localité mémoire

Objectifs:

• analyser la performance d'un programme en terme de nombre d'opérations et de localité (nombre de défauts de localité)
• concevoir un algorithme en prenant en compte les problématiques de hiérarchie mémoire (internet, disque dur, RAM, cache)
• maîtriser les schémas de programmation itératifs et récursifs, et leur combinaison en cascade
• concevoir et programmer des méthodes d’optimisation discrète: programmation dynamique et branch&Bound; exemples d’applications
• pratiquer : TP
• apprendre à modéliser par l'abstraction: temps et nombre d'opérations; cache et modèle de cache CO; optimisation et modélisation récursive

Contenu(s)

Descriptif des 5 séances de cours et 6 de TDs:

• Chap 1. Analyse de la performance mémoire. Modèle CO. Technique par bloc cache-aware. Applications à des algorithmes sur des tableaux (tris et produits matrice-vecteur(s) [TP 0: produit matrice-matrice)
  TD1: produit matrice vecteur; tri fusion.
  => TP0 Produit de matrice.

• Chap 2. De cache aware à cache oblivious. Applications à la transposition et au produit matrice-vecteur.
  TP: patch optimal
  TD2 : transposition et produit de matrices; tri par insertion

• Chap 3. Programmation des formules récursives: élimination de la redondance par tabulation (mémoisation); programmation itérative; programmation récursive cache oblivious.
  TD 3: Formules récursive et cache : exemple des coefficients binomiaux

• Chap 4. Application à la programmation d'un algorithme de programmation dynamique: distance de Fréchet
  TD4: Cageots de fraises.

• Chap 5. Gestion des contraintes mémoire dans une exploration récursive: application au Branch&Bound.
  TD5: Compromis mémoire file et pile

• Exemple de révision (dernière séance)

En terme de modules : Algorithmique et structures de données 1 et 2.
En terme de compétences : programmation impérative (itération, récursion, programmation procédurale, généricité ; mise en pratique). Structures de données