Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-1-9 [2011/07/12 14:29] (current)
baptiste created
Line 1: Line 1:
 +<html>
 +<h2>Algorithmique parallèle et distribuée</h2>
  
 +<p>Resp.: C. Delporte-Gallet, H. Fauconnier</p>
 +
 +<h3>Objectifs</h3>
 +
 +<p>Comprendre les possibilités et les limites du calcul parallèle et distribué.
 +Être capable de concevoir de tels algorithmes.</p>
 +
 +<h3>Plan du cours</h3>
 +
 +<ul>
 +<li> Introduction </li>
 +<li> Éléments d'algorithmique parallèle
 +<ul>
 +<li> Architectures parallèles
 + (Processeurs, communication entre processeur (mémoire partagée,
 + transmission de messages), contrôle (SISD, SIMD, MISD, MIMD)).</li>
 +<li> Modèle de calcul (les différents modèles de PRAM, complexité)</li>
 +<li> Algorithmes:
 + algorithmes élémentaires (opération associative, préfixe, pointer
 + jumping, rang), multiplication de matrice, 
 + algorithme de tri (tri pair/impair).</li>
 +</ul>
 +</li>
 +<li> Algorithmique distribuée sans pannes 
 +<ul>
 +<li> Mémoire partagée et communication par messages</li> 
 +<li> Algorithmes de vagues et applications (causalité et ordre de Lamport, 
 + algorithmes de vagues et de traversées, élections, routage minimal). </li> 
 +<li> Détermination d'un état global (prédicats stables, 
 + algorithmes de snapshot, terminaison distribuée). </li> 
 +<li> Algorithmes de diffusion ( diffusion FIFO, vecteur d'horloge et diffusion
 + causale multicast et diffusion ordonnée).</li>
 +</ul>
 +</li>
 +<li> Algorithmique distribuée en présence de pannes 
 +<ul>
 +<li> Problèmes d'accord en synchrone </li>
 +<li> Problèmes d'accord en asynchrone </li>
 +<li> Résultat d'impossibilité et complexité </li>
 +<li> Redondance active (diffusion atomique) </li>
 +<li> Introduction à l'auto-stabilisation </li>
 +</ul>
 +</li>
 +</ul>
 +
 +<h3>Pré-requis</h3>
 +
 +<p>Algorithmique séquentielle.</p>
 +
 +<h3>Bibliographie</h3>
 +
 +<ul>
 +<li> Hesham El-Rewini and Ted G. Lewis. 
 + **Distributed and parallel computing. **
 + Manning, 1997. </li>
 +<li> Nancy A. Lynch. 
 + **Distributed Algorithms. **
 + Morgan Kaufmann, 1996. </li>
 +<li> Gerard Tel. 
 + **Introduction to Distributed Algorithms.** 
 + Cambridge University Press, 2000.</li>
 +</ul>
 +
 +<h3>Équipe pédagogique</h3>
 +<table border''"2">
 +<tr><td>C. Delporte-Gallet</td>
 +<td>MC</td>
 +<td>Univ. Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>H. Fauconnier</td>
 +<td>MC</td>
 +<td>Univ. Paris 7</td>
 +<td>LIAFA</td>
 +</tr></table>
 +</html>
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA