Ricerca ovunque con Google ...

Ingegneria degli Algoritmi / Algorithm Engineering

Corso di Laurea Magistrale in Informatica A.A. 2011-2012, secondo semestre Docente: Irene Finocchi Ricevimento: per appuntamento

Avvisi Orari Descrizione del corso Diario delle lezioni Obiettivi formativi Libri e materiale didattico Modalità d'esame

Avvisi

• Primo homework: scadenza 8 giugno.

Orari

giorno	ora	luogo
mercoledì	12.00-13.30	aula Alfa
venerdì	10.15-11.45	aula Alfa

Descrizione del corso

The course will cover fundamental techniques for bridging algorithmic theory and programming practice: it will offer a general introduction to the area of Algorithm Engineering and to the major techniques and research topics in this area.

The aim of algorithm engineering is to conjugate the design and theoretical analysis of efficient algorithms and data structures with their actual implementation and experimental analysis on modern computer platforms. The lectures will follow an experimental and problem-driven approach. The goal for the class is to be broad rather than deep: our plan is to touch upon a variety of areas and techniques. This is a tentative list of questions that are likely be covered in the class:

• The running times obtained in practice by scanning a moderately large matrix by row or by column may be very different: what is the reason? Is the assumption that memory access times are constant realistic?

• How would you sort 1TB of data? How would you measure the performances of algorithms in applications that need to process massive data sets stored in secondary memories?

• Do memory allocation and free operations really require constant time? How do real memory allocators work?

• How can we maintain statistics related to the traffic routed by a backbone server? The observed data are a continuous and possibly infinite stream that cannot be stored explicitly. What can be computed without even storing the input?

• For several decades, most classes of applications have enjoyed free and regular performance gains thanks to faster clock speeds. In multicore platforms, the free lunch is over. How can algorithms take advantage of multiple cores? Which are the main algorithmic and programming challenges in the multicore era?

In the course we will introduce computational models that, differently from the standard RAM model considered in undergraduate courses, take into account architectural aspects of modern computer platforms such as the presence of memory hierarchies and multiple cores. We will show how to design efficient algorithms and data structures in such models and how to analyze them both by theoretical and by experimental means. Along the way, we will introduce advanced tools for engineering and tuning the performance of algorithmic code.

Diario delle lezioni

Trovate a questo link il diario delle lezioni dettagliato, oltre a dispense, slides, articoli e riferimenti bibliografici.

Diario delle lezioni A.A. 2010-2011

Obiettivi formativi

• Familiarity with problems and techniques in algorithm engineering
• Knowledge of advanced computational models, such as external memory, data streaming, cache-oblivious, multi-core.
• Ability to design algorithms and data structures and to write efficient code taking into account architectural features of modern computer platforms.
• Performance analysis skills using both mathematical and experimental tools.
• Ability to study advanced research topics in algorithmics

Libri e materiale didattico

• J. Bentley. Programming pearls, 2/ed, Addison-Wesley, 2000. Book web site.
• R. Bryant, D. O'Hallaron: Computer Systems: A Programmer's Perspective, Prentice Hall, 2003.
• C. Demetrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati, 2/ed, McGraw-Hill, 2008.
• K. Mehlhorn, P. Sanders. Algorithms and data structures: The basic toolbox, Springer, 2009. Book web site.
• M. Herlihy, N. Shavit. The Art of Multiprocessor Programming, Morgan Kaufmann, 2008.
• C. Demetrescu, I. Finocchi. Algorithms for data streams. In Handbook of Applied Algorithms, John Wiley and Sons, 2008
• Research papers that will be posted on-line during the course

Modalità d'esame

L'esame consiste di due prove:

• un "orale-scritto", ovvero uno scritto con domande aperte tipiche da esame orale, tese a verificare la conoscenza e la comprensione di base della materia (e.g., descrizione ed analisi di algoritmi e strutture dati presentati durante il corso);
• lo svolgimento di homework assegnati durante il corso. Gli homework possono essere svolti a coppie e dovranno essere consegnati entro una data comunicata di volta in volta dal docente.

Chi non riesca a svolgere con successo almeno il 70% degli homework assegnati, potrà svolgere una tesina o un progetto da concordare con il docente al termine del corso. La frequenza del corso e la consegna degli homework sono fortemente consigliate.

Nella settimana di interruzione della didattica è prevista una prova intermedia sugli argomenti affrontati nella prima parte del corso.