| | | corso | | | | |
Algoritmi paralleli e distribuiti
Codice: | 314AA | Crediti: | 6 | Semestre: | 1 | Sigla: | AlP | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Giuseppe Prencipe
Tel. 0502213148Prerequisiti
Nozioni base di algortimica.
Obiettivi di apprendimento
Progetto e analisi di algortimi paralleli e distribuiti
Descrizione
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.
English Description
The goal of the course is to introduce the main algorithmic techniques in the framework of parallel and distributed models of computing,
and 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.
Programma
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
Bibliografia
Nicola Santoro: "Design and Analysis of Distributed Algorithms", Whiley- Interscience, 2007.
Modalità di esame
Esame scritto, e presentazione orale di un articolo scientifico su un argomento concordato con il docente.