Algoritmi paralleli e distribuiti

 
Nozioni base di algortimica.

Progetto e analisi di algortimi paralleli e distribuiti

Il corso introduce le principali tecniche algoritmiche nell’ambito dei modelli di calcolo paralleli e distribuiti. 
Definisce i parametri di complessità significativi per questi modelli, i limiti computazionali e gli strumenti necessari 
per affrontare il progetto e l’analisi di algoritmi paralleli e distribuiti.

The goal of the course is to introduce the main algorithmic techniques in the framework of parallel and distributed models of computing; to define the most significant complexity parameters and the computational limits of parallelism and concurrency. Finally computational tools to design and analyze parallel and distributed algorithms are given.

1)	Modelli di calcolo: 
    	Il modello PRAM; Altri modelli di computazione parallela. Il modello distribuito
2)	Tecniche di progetto  e analisi di algoritmi paralleli:
	Somme prefisse, List ranking,  Euler tour. Altre tecniche e problemi difficilmente parallelizzabili
3)	Tecniche di progetto  e analisi di algoritmi distribuiti:
        La complessità della comunicazione. Algoritmi di controllo. Algoritmi fault tolerant. Manipolazioni di dati distribuiti.
4)	Esempi classici:
        Coordinazione e controllo. Broadcast e Spanning Tree. Calcolo su alberi: Saturazione e valutazione di funzioni.
        L’elezione su anello e altre reti. Routing

Nicola Santoro: "Design and Analysis of Distributed Algorithms", Whiley- Interscience, 2007.