corso

Algoritmi paralleli e distribuiti

Codice:	314AA	Crediti:	6	Semestre:	1	Sigla:	AlP

Settore disciplinare:		INF/01 - Informatica

Docente

Giuseppe Prencipe

Tel. 0502213148

Ultima versione disponibile: programma da confermare per l’a.a. 2014/2015

Prerequisiti

Nozioni base di algortimica.

Obiettivi di apprendimento

Progetto e analisi di algoritmi 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. 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

Models of computation
1. The PRAM model
2. Bounded degree networks. BSP.
3. The distributed model.
Design and analysis of parallel algorithms
1. Prefix sums, List Ranking, Euler tour.
2. Standard techniques and inner sequential problems.
Design and analysis of distributed algorithms
1. Communication complexity.
2. Control algorithms.
3. Fault tolerant algorithms.
4. Distributed data manipulation.
5. Classical examples: Broadcast e Spanning tree; Computationon trees: Saturation, functions evaluation; Election on Ring and othernetworks; Routing.
6. Distributed coordination and control of autonomous mobile robots.

Ore lezione:

Bibliografia

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

Introduction to Parallel Algorithms, Joseph JaJa, 1992.

Modalità di esame

L'esame consiste in una prova scritta che comprende sia il progetto di algoritmi che domande teoriche, e in un seminario su un argomento di ricerca scelto dallo studente.