Tags:
create new tag
view all tags
---++!! <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. -->
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r52
<
r51
<
r50
<
r49
<
r48
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r52 - 2013-09-16
-
IreneFinocchi
Log In
or
Register
Ing_algo Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Prenotazioni esami
Laurea Triennale ...
Laurea Triennale
Algebra
Algoritmi
Introduzione agli algoritmi
Algoritmi 1
Algoritmi 2
Algoritmi per la
visualizzazione
Architetture
Prog. sist. digitali
Architetture 2
Basi di Dati
Basi di Dati 1 Inf.
Basi di Dati 1 T.I.
Basi di Dati (I modulo, A-L)
Basi di Dati (I modulo, M-Z)
Basi di Dati 2
Calcolo
Calcolo differenziale
Calcolo integrale
Calcolo delle Probabilitą
Metodi mat. per l'inf. (ex. Logica)
canale AD
canale PZ
Programmazione
Fond. di Programmazione
Metodologie di Programmazione
Prog. di sistemi multicore
Programmazione 2
AD
EO
PZ
Esercitazioni Prog. 2
Lab. Prog. AD
Lab. Prog. EO
Lab. Prog. 2
Prog. a Oggetti
Reti
Arch. di internet
Lab. di prog. di rete
Programmazione Web
Reti di elaboratori
Sistemi operativi
Sistemi Operativi (12 CFU)
Anni precedenti
Sistemi operativi 1
Sistemi operativi 2
Lab. SO 1
Lab. SO 2
Altri corsi
Automi, Calcolabilitą
e Complessitą
Apprendimento Automatico
Economia Aziendale
Elaborazione Immagini
Fisica 2
Grafica 3D
Informatica Giuridica
Laboratorio di Sistemi Interattivi
Linguaggi di Programmazione 3° anno Matematica
Linguaggi e Compilatori
Sistemi Informativi
Tecniche di Sicurezza dei Sistemi
ACSAI ...
ACSAI
Computer Architectures 1
Programming
Laurea Magistrale ...
Laurea Magistrale
Percorsi di studio
Corsi
Algoritmi Avanzati
Algoritmica
Algoritmi e Strutture Dati
Algoritmi per le reti
Architetture degli elaboratori 3
Architetture avanzate e parallele
Autonomous Networking
Big Data Computing
Business Intelligence
Calcolo Intensivo
Complessitą
Computer Systems and Programming
Concurrent Systems
Crittografia
Elaborazione del Linguaggio Naturale
Estrazione inf. dal web
Fisica 3
Gamification Lab
Information Systems
Ingegneria degli Algoritmi
Interazione Multi Modale
Metodi Formali per il Software
Methods in Computer Science Education: Analysis
Methods in Computer Science Education: Design
Prestazioni dei Sistemi di Rete
Prog. avanzata
Internet of Things
Sistemi Centrali
Reti Wireless
Sistemi Biometrici
Sistemi Distribuiti
Sistemi Informativi Geografici
Sistemi operativi 3
Tecniche di Sicurezza basate sui Linguaggi
Teoria della
Dimostrazione
Verifica del software
Visione artificiale
Attivitą complementari
Biologia Computazionale
Design and development of embedded systems for the Internet of Things
Lego Lab
Logic Programming
Pietre miliari della scienza
Prog. di processori multicore
Sistemi per l'interazione locale e remota
Laboratorio di Cyber-Security
Verifica e Validazione di Software Embedded
Altri Webs ...
Altri Webs
Dottorandi
Commissioni
Comm. Didattica
Comm. Didattica_r
Comm. Dottorato
Comm. Erasmus
Comm. Finanziamenti
Comm. Scientifica
Comm Scientifica_r
Corsi esterni
Sistemi Operativi (Matematica)
Perl e Bioperl
ECDL
Fondamenti 1
(NETTUNO)
Tecniche della Programmazione 1° modulo
(NETTUNO)
Seminars in Artificial Intelligence and Robotics: Natural Language Processing
Informatica generale
Primo canale
Secondo canale
II canale A.A. 10-11
Informatica
Informatica per Statistica
Laboratorio di Strumentazione Elettronica e Informatica
Progetti
Nemo
Quis
Remus
TWiki ...
TWiki
Tutto su TWiki
Users
Main
Sandbox
Home
Site map
AA web
AAP web
ACSAI web
AA2021 web
Programming web
AA2021 web
AN web
ASD web
Algebra web
AL web
AA1112 web
AA1213 web
AA1920 web
AA2021 web
MZ web
AA1112 web
AA1213 web
AA1112 web
AA1314 web
AA1415 web
AA1516 web
AA1617 web
AA1819 web
Old web
Algo_par_dis web
Algoreti web
More...
Ing_algo Web
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
View
Raw View
Print version
Find backlinks
History
More topic actions
Edit
Raw edit
Attach file or image
Edit topic preference settings
Set new parent
More topic actions
Account
Log In
Register User
Questo sito usa cookies, usandolo ne accettate la presenza. (
CookiePolicy
)
Torna al
Dipartimento di Informatica
E
dit
A
ttach
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