---++!! <big>Ingegneria degli Algoritmi / Algorithm Engineering</big> <table width="100%" border=0 cellpadding=0> <tr> <td width="75%" valign="top"> <font color=#AF0F0F size="+1"><b>Corso di Laurea Magistrale in Informatica</b></font> <font color=#AF0F0F size="+1"><b>A.A. 2012-2013, secondo semestre</b></font> <font color=#AF0F0F size="+1"><b>Docente: [[http://www.dsi.uniroma1.it/~finocchi][Irene Finocchi]]</b></font> *Ricevimento*: per appuntamento </td> <td width="25%" valign="top" style="border-left: 1px solid #999999; "> %TOC% </td> </tr> </table> ---++Avvisi * L'esame di mercoledì *18 settembre* è posticipato a *giovedì 19 settembre, ore 9:30*, presso il mio studio. * Date esami: martedì *11 giugno*, mercoledì *10 luglio*, mercoledì *18 settembre*. Tutti gli appelli si svolgono alle ore 9:00 in Aula Seminari. * Articoli per tesine: * [[%ATTACHURL%/triangles.pdf][Triangle counting 1]]: Reductions in streaming algorithms with an application to counting triangles in graphs, Bar-Yossef, Kumar & Sivakumar, ACM-SIAM Symposium on Discrete Algorithms, 2002 (Cammarano & Mile) * [[%ATTACHURL%/p677-kutzkov.pdf][Triangle counting 2]]: On the streaming complexity of computing local clustering coefficients, Kutzkov & Pagh, ACM Conference on Web Search and Data Mining, 2013 (Mauro) * [[%ATTACHURL%/p1095-metwally.pdf][Frequent items 1]]: An integrated efficient solution for computing frequent and top-k elements in data streams, Metwally, Agrawal & El Abbadi, ACM Transactions on Database Systems, 2006 (Carnevale & Papandrea) * [[%ATTACHURL%/CALDERSIWKDDS06.pdf][Frequent items 2]]: Mining frequent items in a stream using flexible windows, Calders, Dexters & Goethals, ACM Conference on Knowledge Discovery and Data Mining, 2010 (Iovino) * [[%ATTACHURL%/p14_Cormode_JAl_05.pdf][Count-min sketch]]: An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, 2005 (Ciciarelli) * [[%ATTACHURL%/FindRepeatedElements.pdf][Repeated elements]]: Finding repeated elements, Misra & Gries, Science of Computer Programming, 1982 (Colazzo & Rauso) * [[%ATTACHURL%/80munro-median.pdf][Sorting & selection]]: Selection and sorting with limited storage, Theoretical Computer Science, 1980 (Bronzini) <!-- * [[%ATTACHURL%/hw2-aa2011-2012.pdf][Mini-homework su data streams]] * [[%ATTACHURLPATH%/hw1-aa2011-2012.pdf][Primo homework]]: scadenza 8 giugno. * Prova intermedia: *martedì 24 aprile, ore 9:30, aula Beta*. Trovate il [[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/WebHome][foglio di prenotazioni]] su twiki. * [[%ATTACHURLPATH%/hw2-aa2010-2011.pdf][Secondo homework]]: nuova scadenza per la consegna *1 luglio*. Ricevuti gli homework, avrò bisogno di qualche giorno per esaminarli. Chi parteciperà all'appello di giugno potrà concordare con me via e-mail una data per la verbalizzazione. Nota sull'homework: nell'esercizio 2 potete assumere che n e m siano noti all'algoritmo. --> ---++Orari <!--<font color=#AF0F0F size="+0"><b>Lectures schedule</b></font>--> | *giorno* | *ora* | *luogo* | | lunedì | 12.00-13.30 | aula Alfa | | mercoledì | 10.15-11.45 | aula Alfa | ---++ Descrizione del corso <img src="%ATTACHURLPATH%/english_flag.jpg" alt="english flag" /> 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: <!--Among the typical questions that might be addressed:--> * 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, [[http://www.gotw.ca/publications/concurrency-ddj.htm][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 [[Ing_algo/DiarioLezioni][questo link]] il diario delle lezioni dettagliato, oltre a dispense, slides, articoli e riferimenti bibliografici. [[Ing_algo/DiarioLezioni1112][Diario delle lezioni A.A. 2011-2012]] <!-- [[Ing_algo/DiarioLezioni1011][Diario delle lezioni A.A. 2010-2011]] --> ---++ Obiettivi formativi <img src="%ATTACHURLPATH%/english_flag.jpg" alt="english flag" /> <!-- Learning outcomes --> * 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 <!--Molti dei temi trattati nel corso sono argomenti di ricerca e non sono ancora descritti in modo sistematico in un unico libro di testo. Materiale di specifiche lezioni sarà tratto da:--> * J. Bentley. _Programming pearls_, 2/ed, Addison-Wesley, 2000. [[http://netlib.bell-labs.com/cm/cs/pearls/][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. [[http://www.mpi-inf.mpg.de/~mehlhorn/Toolbox.html][Book web site]]. * M. Herlihy, N. Shavit. _The Art of Multiprocessor Programming_, Morgan Kaufmann, 2008. * C. Demetrescu, I. Finocchi. [[%ATTACHURL%/DFchapter08.pdf][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 <!--Per molti altri argomenti ci baseremo su articoli scientifici.--> ---++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); * la presentazione di una tesina concordata con il docente durante il corso. Le tesine possono essere svolte a coppie e verranno presentate dagli studenti in aula durante le ultime due settimane di 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 (nell'A.A. 2012-2013: algoritmi per data stream). <!-- Nel corso discuteremo problemi e tecniche fondamentali per coniugare teoria e pratica degli algoritmi, tenendo conto degli aspetti architetturali delle piattaforme di calcolo moderne (gerarchie di memoria, pipelining, parallelismo) e dei vincoli presenti in molte applicazioni reali (con particolare enfasi sulla gestione di insiemi di dati di grandi dimensioni). Affronteremo una varietà di tematiche motivandole con esperimenti ed esempi concreti, calcolatore alla mano. Alcune domande cui cercheremo di rispondere: * Perché scorrendo una matrice (di opportune dimensioni) per righe o per colonne si possono ottenere in pratica tempi di esecuzione estremamente diversi? L'analisi asintotica standard predice prestazioni identiche. E' ragionevole assumere che i tempi di accesso a memoria siano costanti? * Come ordinereste 1TB di dati? Come misurereste realisticamente le prestazioni di algoritmi in applicazioni che richiedono di processare enormi quantità di dati mantenuti in memorie secondarie? * Come manterreste statistiche sul traffico instradato in Internet da un backbone server? I dati osservati sono uno stream continuo e possibilmente infinito. Come è possibile progettare algoritmi in situazioni in cui è addirittura impossibile memorizzare l'input? * Per vari decenni, ai miglioramenti nella velocità di clock sono corrisposti miglioramenti nelle prestazioni del software. Con l'avvento del multi-core, [[http://www.gotw.ca/publications/concurrency-ddj.htm][the free lunch is over]]. Come trarre vantaggio dalla presenza di core multipli? Quali sono le principali sfide algoritmiche e di programmazione nell'era del multi-core? * Le operazioni di allocazione e deallocazione di memoria richiedono veramente tempo costante? Come funziona un allocatore di memoria reale? Nel corso introdurremo modelli computazionali più realistici del classico modello RAM usato nei corsi algoritmici di base, catturando aspetti architetturali come la presenza di memorie gerarchiche e di più core, e mostreremo come progettare algoritmi e strutture dati efficienti in tali modelli. Discuteremo le soluzioni proposte a livello teorico e sperimentale, introducendo strumenti avanzati per l'ingegnerizzazione ed il tuning delle prestazioni di codice algoritmico. -->
This topic: Ing_algo
>
WebHome
Topic revision: r52 - 2013-09-16 - IreneFinocchi
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback