Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/wikka.php on line 315
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/libs/Wakka.class.php on line 176
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/libs/Wakka.class.php on line 463
Deprecated: Function set_magic_quotes_runtime() is deprecated in /home/demetres/public_html/didattica/ae/wikka.php on line 120
Informazioni generali
People who analyze algorithms have double happiness. First of all they experience
the sheer beauty of elegant mathematical patterns that surround elegant computational
procedures. Then they receive a practical payoff when their theories make it possible to
get other jobs done more quickly and more economically.
—Donald Knuth
Le lezioni vengono tenute nel periodo compreso tra il 6 marzo e il 31 maggio 2012 nella sede di Via Eudossiana 18.
Orario: martedi 15:45-17:15 in aula 8 e giovedi 10:15-13:30 in aula 29 della sede di Via Eudossiana, 18
Docente:
Camil Demetrescu∞
Ricevimento studenti: giovedi 14:00-15:30 durante il corso, poi su appuntamento
(si prega di prenotarsi in ogni caso scrivendo una email al docente)
Contesto e obiettivi
Il modello di costo teorico tradizionale per valutare le prestazioni di programmi si basa sulla stima asintotica del numero di istruzioni eseguite nel caso peggiore, assumendo ad esempio che operazioni aritmetico-logiche, accessi a memoria, allocazione e deallocazione di oggetti, richiedano tempo costante. Sebbene questo modello sia generalmente molto efficace, vi sono tuttavia diversi contesti in cui le assunzioni semplificative su cui si basa possono essere piuttosto irrealistiche.
L'obiettivo del corso è di approfondire aspetti prestazionali legati allo sviluppo del software, coniugando il progetto e l'analisi teorica di algoritmi e strutture dati efficienti con la loro effettiva codifica in un linguaggio di programmazione reale e la loro validazione sperimentale. Il corso affronterà sia aspetti teorici che implementativi e si baserà prevalentemente sul linguaggio C, affiancandosi in modo complementare alla trattazione svolta nel corso di Sistemi Operativi. Alcune tipiche domande che affronteremo nel corso:
- Quali ottimizzazioni del codice vengono effettuate automaticamente dai compilatori e quali invece devono essere effettuate manualmente dai programmatori per ottenere le massime prestazioni per un problema di calcolo?
- Le operazioni di allocazione e deallocazione di memoria (malloc/free) hanno veramente costo costante? Come funziona un allocatore di memoria reale?
- Molte applicazioni su larga scala, come ad esempio l'Earth Observing System della NASA o motori di ricerca come Google, richiedono di processare enormi quantità di dati mantenuti in memorie secondarie. I tempi di accesso a disco sono almeno tre ordini di grandezza maggiori dei tempi di accesso a memoria centrale: come progettare e misurare realisticamente le prestazioni di algoritmi in scenari di questo tipo?
Alla fine del corso lo studente sarà in grado di definire e manipolare strutture dati in C per risolvere problemi algoritmici fondamentali che sono alla base dei moderni sistemi software. Acquisirà inoltre la capacità di analizzare le prestazioni di un programma utilizzando da una parte modelli di costo teorici in grado di catturare aspetti architetturali come la presenza di memorie gerarchiche, e dall'altra metodologie sperimentali su piattaforme di calcolo reali.
Prerequisiti
Conoscenza di almeno un linguaggio di programmazione procedurale/orientato agli oggetti. Tecniche di programmazione. Architetture dei calcolatori elettronici. Algoritmi e strutture dati. Analisi matematica. Calcolo delle probabilità.
[
A.A. 2009-2010 |
A.A. 2010-2011 |
A.A. 2011-2012 |
A.A. 2012-2013 ]