| | | corso | | | |
Algoritmi e Strutture Dati: Algoritmi Paralleli e Distribuiti
(Corso di Laurea in Informatica (quinquennale))
Codice: | 4I026 | Crediti: | 6 | Semestre: | 2 | Sigla: | ASP | |
Docente
Linda Pagli
Tel. 0502212735Prerequisiti
Algoritmi e Strutture Dati, Architettura
Obiettivi di apprendimento
Si introducono i modelli di computazione parallela (PRAM) e distribuita per
apprendere la progettazione e la valutazione di algoritmi in tali modelli.
Il confronto di questi modelli tra loro e con altri possibili dovrebbe
fornire allo studente la capacità di selezionare il modello
opportuno nell=
o
sviluppo di applicazioni che impiegano contemporaneamente più
processori.
Descrizione
Introduzione all'analisi e alla complessit=E0 degli algoritmi paralleli e
distribuiti. Definizione e confronto tra i pi=F9 diffusi modelli di calcolo
con particolare riferimento al modello PRAM e
distribuito. Tecniche algoritmiche principali e studio di problemi
importanti. Limiti inferiori e problemi difficilmente parallelizzabili.
English Description
Introduction to analysis and design of parallel and distributed algorithms.
Definition and comparison among the most important models of parallel
computation as PRAM model and distributed model. Basic algorithmic
techniques and important problems. Lower bounds and P-complete problems.
Programma
1. Algoritmi Paralleli (25 ore)
Il modello PRAM e le sue varianti
Tecniche di base per la costruzione di algoritmi PRAM efficienti: Prefix
Sum, List Ranking,Tree Contraction, Symmetry Breaking, Pipelining.
Sorting, Merging e Selection.
Tecniche per la dimostrazione di limiti inferiori: Il problema dell'OR.
Algortimi NC e problemi P-completi.
Cenni al modello BSP.
2. Algoritmi Distribuiti (15 ore)
Il modello distribuito punto-punto.
Misure di complessità: tempo e comunicazione.
Definizione di algoritmo distribuito.
Algoritmi base per reti con diverse topologie come anelli, alberi e grafi.
Spanning tree e Elezione del leader.
Ore lezione: | 25 | Ore esercitazione: | 15 | | | |
Bibliografia
Joseph Jajà: "An Introduction to Parallel algorithms" Addison Wesley
publishing Company 1992.
Attiya H., Welch J.: "Distributed computing : foundamentals, simulations and
advanced topics" 1998.
Modalità di esame
Ulteriore pagina web del corso: