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
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/safehtml.php on line 308
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 159
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 161
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 162
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 163
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 165
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 166
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 167
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 243
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 250
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 259
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 266
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 273
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 280
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 467
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 469
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 471
Informazioni generali (A.A. 2009-2010)
Un progettista capisce di aver raggiunto la perfezione non quando
non c'è più niente da aggiungere, ma quando non c'è più niente da togliere.
—Antoine de Saint-Exupéry, "Terres des hommes"
Le lezioni vengono tenute nel periodo compreso tra il 28 settembre e il 18 dicembre 2009 nella sede di Via Eudossiana 18.
Orario: giovedi 8:30-10:55 in aula 24 e venerdi 8:30-10:55 in aula 33
Docente:
Camil Demetrescu∞
Ricevimento studenti: martedi 14:00-15:30 durante il corso, poi su appuntamento
(si prega di prenotarsi 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. Alcune tipiche domande che affronteremo nel corso:
- 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 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?
- Perché scorrendo una matrice per righe o per colonne si possono ottenere in pratica tempi di esecuzione estremamente diversi? Il tempo predetto dall'analisi teorica è pur sempre quadratico. E' ragionevole assumere che i tempi di accesso a memoria siano costanti?
- Consideriamo una sequenza di operazioni su una collezione di dati (ad esempio, interrogazioni a un motore di ricerca): alcune operazioni potrebbero essere molto lente, mentre altre molto veloci. Misurare il tempo di picco nel caso peggiore (come avviene nell'analisi tradizionale) potrebbe essere pessimistico e lontano dalla realtà. Non avrebbe più senso misurare il tempo medio per operazione sull'intera sequenza?
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.
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à.