Tags:
create new tag
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.
Topic revision: r1 - 2005-05-25 - RossellaPetreschi





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback