ALGORITMI AVANZATI (AA.2010-2011)

Prof.ssa Rossella Petreschi

Avviso:
Per permettere a tutti i fuori sede di andare a votare, il Rettore ha sospeso la didattica nei giorni 16 e 30 maggio.
La lezioni di Algoritmi Avanzati del 16 e 30 maggio saranno pertanto recuperate nei giorni 18 maggio e 1 giugno dalle 14 alle 15.30 in aula beta.

Appelli di esame:
Giugno: Martedì 21 ore 9 -
Luglio: Martedì 12 ore 9 -
Settembre: Martedì 27 ore 9 -

Orario di ricevimento:
Quando: Durante il periodo delle lezioni: Lunedì e Mercoledì ore 12 - 13.30. Terminate le lezioni: su appuntamento.
Dove: D.to Informatica - Via Salaria,113, stanza n°341a.

PROGRAMMA DEL CORSO (AA.2010-2011) (Scarica il pdf).

Finalità del corso: Il corso è incentrato sul progetto di algoritmi che operano su architetture concorrenti e si propone di spiegare come l'approccio a tale progettazione dipenda strettamente dal tipo di architettura utilizzata e sia completamente diverso da quello usato per gli algoritmi sequenziali.

Prerequisiti: Si assume che gli studenti conoscano gli argomenti trattati negli insegnamenti di algoritmi e probabilità del corso di laurea in Informatica e nell'insegnamento di Algoritmi e Strutture Dati del corso di laurea magistrale in Informatica.

I lucidi relativi alle lezioni possono essere scaricati dalla tabella a fondo pagina.

Il seguente elenco contiene riferimenti bibliografici relativi alle singole lezioni.

• Lezioni del 14,16,21/03/2011: [A]Cap.1, §2.5, [CLR] §30.3, [GGKK] Cap.1, §2.1, [J] Cap.1, [V] Cap.1,2, [Z] Cap.1.
• Lezioni del 23,28,30/03/2011: [CLR] Cap.28,§30.1, 30.2, [J] §12.2, 12.3,[JS] §12.1,12.2, [V] Cap.3,§5.1,9.1,9.2.
• Lezioni del 4,6/04/2011: [AW] cap.1,§2.1,2.2, [JS] §12.5, [Z] §5.1,5.2.
• Lezione del 14/04/2011: [J] §5.2,[V] Cap.11.
• Lezione del 18/04/2011: [GHS], [Z] §5.3.3.2.
• Lezione del 20/04/2011: [J] §3.3,[V] Cap.10.
• Lezione del 4/05/2011: [SHM] §1-10,[V].
• Lezione del 9/05/2011: [J] §5.4,[R] §7.1,7.2.
• Lezione del 10/05/2011: [J] §4.2,[R] §10.1,10.2,10.3.
• Lezione del 11/05/2011: [J] §4.3,[R] §10.4.
• Lezione del 23/05/2011: [AW] cap.7,cap.8.
• Lezione del 25/05/201(mattina): [AW] cap.3.
• Lezione del 25/05/2011(pomeriggio): [AW] cap.6.
• Lezione del 1/06/2011: [R] cap.18.
• Lezione del 6/05/2011: [AW] cap.14.

Riferimenti bibliografici

[A] Akl S.G. Progettazione ed analisi degli algoritmi paralleli, Gruppo Editoriale Jackson.

[AW] Attiya H., Welch J. Distributed Computing, McGraw-Hill.

[CLR] Cormen T.H., Leiserson C.E., Rivest R.L. Introduzione agli algoritmi, Jackson Libri.

[GHS] Gallager R.G., Humblet P.A., and Spira P.M., A Distributed Algorithm for Minimum-Weight Spanning Trees. ACM Transactions on Programming Languages and Systems, 1(5), 1983, pages 66-77. p66-gallager.pdf

[GGKK] Grama A., Gupta A., Karypis G., Kumar V. Introduction to parallel Computing, Pearson-Addison-Wesley.

[J] Jaja J. An introduction to parallel algorithms, Addison-Wesley.

[JS] Johnsonbaugh R., Schaefer M. Algorithms, Pearson-Addison-Wesley.

[R] Reif J.H. Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers.

[SHM] Skillicorn D.B., Hill J.M.D., McColl W.F. Question and answers about BSP, ftp://ftp.comlab.ox.ac.uk/pub/Packages/BSP/papers/SkillHillMcColl_QA.ps.gz.

[Va] Valiant L. G. A bridging model for parallel computation, Communication of the ACM, 33 (8): 101 – 111, August 1990

[V] Vishkin U. Thinking in parallel: some basic data-parallel algorithms and tecniques, http://www.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf

[Z] Zomaya A.Y.H. Parallel and distributed computing handbook, McGraw-Hill.