Horaires : Cours : 24h. Travaux dirigés : 12h. Travaux pratiques : 9h.
Responsable : René NATOWICZ
Objectifs : La programmation dynamique est une méthode
d'optimisation opérant par phases (ou séquences) dont l'efficacité
repose sur le principe d'optimalité de Bellman : " Toute politique
optimale est composée de sous-politiques optimales ".
Cette unité met l'accent sur la diversité des domaines
et des problèmes d'apparence très éloignés
qui, lorsqu'ils sont correctement modélisés, relèvent
de la même technique. Elle permet de mettre en pratique, sur des
problèmes de traitement du signal, de contrôle et d'informatique,
les concepts abordés dans les cours d'informatique logicielle et
matérielle des deux premières années du tronc commun.
Résoudre un problème d'optimalité par la programmation
dynamique est, dans ce contexte précis, une mise en oeuvre significative
de la diversité des compétences attendues d'un ingénieur
: modélisation du problème, proposition d'une équation
de récurrence, proposition d'un algorithme efficace de résolution
du problème (modélisation informatique des données,
évaluation de la complexité); étude des différentes
optimisations possibles de l'algorithme; programmation effective; possibilité
d'implantation sur architectures spécifiques déduites de
l'algorithme et des contraintes de programmation.
|
|
|||
|
|
|
|
|
|
|
|
|
|
| Le principe de la programmation dynamique : Complexité de problèmes; méthodes de réduction de complexité; diverses formes de récurrence; programmation tabulaire; reconstruction des solutions; réduction de complexité des algorithmes; programmation dynamique en horizon illimité. |
|
|
|
| Application à la commande optimale : Forme discrète du problème variationnel; relation de récurrence et calculs associés |
|
|
|
| Applications au traitement du signal : Ajustement temporel des signaux; mise en correspondance de signaux; approximation linéaire de courbes |
|
|
|
| Applications au traitement de séquences : Formatage de données textuelles; recherche d'une plus longue sous-séquence commune; appariements; application à l'analyse du génome. |
|
|
|
| Architectures associées : Architecture pipeline, parallèles, systoliques; application au calcul des distances entre chaînes |
|
|
|
Evaluation :
|
|
|
|
| Examen final (f) |
|
|
| Rapports de TP |
|
Moyens pédagogiques particuliers : Station de travail
UNIX