Algorithmique hétérogène
Cours de recherche (24h de cours, travail
sur des articles scientifiques)
Cours : Frederic Vivien (Frederic.Vivien)
Présentation
Ce cours présente
quelques techniques algorithmiques pour la résolution de problèmes
d'optimisation. Ces problèmes sont principalement issus de
l'ordonnancement et de la distribution de données sur plate-forme
de calcul hétérogène.
Positionnement
Ce cours s'insère dans la filière informatique distribuée. Mais le cours passe rapidement sur l'origine
des problèmes rencontrés (la motivation) pour se concentrer sur
leur résolution (les techniques algorithmiques). A ce titre, il
peut intéresser des filières plus théoriques.
Plan détaillé
Les problèmes d'optimisation abordés sont choisis parce qu'ils
sont simples à formuler et difficiles à résoudre. Voici trois
exemples de sujets (on en traitera vraisemblablement un ou deux
autres, encore à déterminer):
- Ordonnancement 1-port
- Présentation du modèle, résultats de
complexité, heuristiques, techniques d'obtention de garanties.
- Distribution de données
- Modélisation du problème, résultats
de complexité, heuristiques, techniques d'obtention de garanties.
- Paradigme maître-esclave
- Modélisation du problème,,
recherche du régime permanent, programmation linéaire, algorithmes
de flot, lien avec le job-shop scheduling.
Travail de recherche
Lecture d'articles de recherche récents et exposés oraux. Pour
chaque thème abordé, il y aura une introduction poussée, et une
synthèse après les exposés, mais le coeur du travail correspondra
aux exposés.
Bibliographie
- Algorithmique classique: livre de T.H. Cormen, C.E.
Leiserson, R.L. Rivest, C. Stein, Introduction to
Algorithms, MIT Press, 2001
- Algorithmes d'approximation: livres de D.S. Hochbaum,
Approximation Algorithms for NP-Hard Problems, PWS
Publishing Company, 1997 et de V.V. Vazirani, Approximation
Algorithms, Springer Verlag 2001
- Algorithmique parallèle: trois livres:
- V. Kumar, A. Grama, A. Gupta et G. Karypis, Introduction
to Parallel Computing, The Benjamin/Cummings Publishing
Company, 1994
- I. Foster and C. Kesselman, The Grid: Blueprint for a New
Computing Infrastructure,
Morgan-Kaufmann, 1999
- A. Legrand et Y. Robert, Algorithmique Parallèle: Cours et
Exercices Corrigés, Dunod, 2003