Algorithmique et Optimisation Discrète - 4MMAOD

Objectif(s)

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

Objectifs:
- conception et programmation de méthodes d’optimisation discrete: programmation dynamique (et branch&Bound); exemples d’applications
- analyser un algorithme (graphe de dépendances ou de flots de données): programmation itérative et récursive, de l’un à l’autre
- analyse de la localité mémoire et du parallélisme; performance des schémas itératifs et récursifs
- initiation au parallélisme multicoeur (boucles OpenMP simples)
- pratiquer : TP

Contenu(s)

Descriptif des 11 séances:

• Chap 1 Programmation des formules récursives : élimination de la redondance par tabulation
• Chap 2. Programmation dynamique (2 séances)
  => Démarrage TP : tex-display: justification optimale d’un texte (par paragraphe mais avec plusieurs paragraphes)
• Chap. 3 Analyse de dépendances (2 séances): de récursif à itératif et d'itératif à récursif.
• Chap 4. Exemple de synthèse: Processus de décision (MDP): algorithme EM (expectation–maximization)
• Chap 5. Analyse des défauts de localité des accès mémoire: algorithmes cache-aware et cache-oblivious (2 séances)
• Chap 6. Branch&Bound (2 séances)
• 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