ALGORITMI AVANZATI (AA.2010-2011)
Prof.ssa Rossella Petreschi
Le prenotazioni per gli appelli di Giugno e Luglio si possono effettuare su Infostud dal 26/05/2011 al 20/06/2011
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.