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.
This topic: Algo_par_dis
> WebHome > PROGRAMMADELCORSO
Topic revision: r1 - 2005-05-25 - RossellaPetreschi