Programma Del Corso di Algoritmi Paralleli e Distribuiti
Algoritmi su Grafi:
Accoppiamento massimo e massimale.
Algoritmo greedy per la ricerca di un accoppiamento massimale.
Cammini alternanti e cammini aumentanti.
Algoritmo per la ricerca di un accoppiamento massimo su grafi bipartiti.
Accoppiamento massimo e reti di flusso.
Algoritmo per la ricerca di un accoppiamento massimo su grafi qualunque.
Grafi planari: definizioni e proprietà fondamentali.
Formula di Eulero e sue applicazioni. Teorema di Kuratowski.. Teorema di Harary e Tutte.
Algoritmo per la st-numerazione di un grafo biconnesso.
Test di planarita’ per aggiunta successiva di nodi.
Disegno di grafi:
st-grafi; grafi st-duali.
Ordini parziali e totali di un st-grafo.
Rappresentazione di un st-grafo attraverso l’ordine totale.
Inserimento e cancellazione di archi o nodi su grafi st-planari.
Parametri per il disegno di grafi: convenzioni, criteri estetici, vincoli, efficienza.
Metodologie di disegno: l’aspetto topologico, l’approccio gerarchico, il criterio di visibilità, la tecnica divide et impera.
Criteri di scelta della metodologia da usare in base ai parametri da ottimizzare.
Esempi di diverse rappresentazione grafiche dei grafi st-planari.
Introduzione alla programmazione parallela:
Classificazione di Flynn delle macchine parallele.
Il modello P-RAM: lettura e scrittura esclusiva e/o concorrente.
Simulazione della lettura concorrente su una macchina a lettura esclusiva.
Simulazione della scrittura concorrente su una macchina a scrittura esclusiva.
Macchine SIMD a reti di interconnessione: vettore, matrice, albero, cubo.
Il problema del caricamento dei dati su macchine SIMD a reti di interconnessione.
Introduzione alla complessità parallela:
Tempo di esecuzione parallelo.
Misure di complessità nel parallelo: “speedup”, efficienza, costo.
Misure “concrete” di complessità parallela: area, lunghezza, periodo.
Circuiti combinatrici; fan in e fan out.
Il teorema di Brent.
Tecniche parallele di base:
La tecnica della prima parte: somma di n elementi; ricerca di un elemento in un vettore, ricerca del massimo e del minimo
La tecnica del salto del puntatore: rango di una lista, ricerca di radici in una foresta.
La tecnica del tour di Eulero: ordinamento dei vertici di un albero rispetto alla radice, calcolo dei livelli di un albero, calcolo del numero di nodi in un sottoalbero.
Numerazione in postordine, preordine e in modo simmetrico.
Algoritmi paralleli di base:
Soluzione di uno stesso problema su diversi modelli di macchine parallele: somma di n elementi; ricerca di un elemento in un vettore, ricerca del massimo e del minimo.
Operazioni parallele elementari su matrici: calcolo della trasposta di una matrice, prodotto di una matrice per un vettore, prodotto di due matrici.
Operatori left e right: loro applicazione al calcolo della numerazione in modo simmetrico.
Ricerca del minimo antecedente comune.
Esempi di algoritmi paralleli:
3-colorazione di un ciclo.
L'operazione di raccoglimento e di contrazione in un albero binario.
Valutazione di espressioni.
Calcolo del minimo, sia globale che parziale, associato ad un albero qualunque.
Ricerca componenti connesse: algoritmo per grafi densi, algoritmo per grafi sparsi.
Ricerca alberi ricoprenti..
Partizione degli spigoli di un grafo in cammini semplici.
Il problema dell’ordinamento nel parallelo:
Circuiti di confronto, il principio 0/1.
Circuito per l'ordinamento bitonico; circuiti di fusione e di ordinamento.
Algoritmo di ordinamento pari/dispari su macchine vettoriali.
Algoritmo di ordinamento in tempo parallelo costante su P-RAM CRCW.
Algoritmo di ordinamento su albero.
Ricerca di un elemento su un vettore ordinato
Rango di un vettore X in un vettore Y
Fusione di due liste ordinate.
Algoritmo parallelo di merge sort.
Cenni sull’algoritmo di Cole per l’ordinamento in tempo O(logn) su PRAM-CREW.
Riferimenti bibliografici:
Akl S.G., The design and analysis of parallel algorithms, Prentice Hall, 1989
Alsuwaiyel M.H., Algorithms: design Techniques and Analysis, World Scientific, 1999
Cormen T.H., Leiserson C.E. e Rivest R.L., Introduction to algorithms, The MIT Press, 1990.
Di Battista G., Eades P., Tamassia R. e Tollis I.G., Graph drawing: algorithms for the visualization of the graphs, Prentice Hall, 1999.
]aja J., An introduction to parallel algorithms, Addison-Wesley, 1992.
Nishizeki T. e Chiba N., Planar graphs: theory and algorithms, North-Holland, 1988.
Preparata F. e Tamassia R., Dynamic maintenance of planar digraphs , Algoritmica, 1990.