PROGRAMMADELCORSO < Algo_par

Tags: view all tags

---++ 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.