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
Diario delle lezioni 2008-2009
Settimana 1
Mercoledi 24 Settembre
Inquadramento del corso. Il linguaggio C. Fasi della compilazione di un programma C: preprocessore, compilatore, linker. Librerie e
direttiva #include∞. Spazio logico degli indirizzi e layout di memoria di un programma C: segmento codice, dati, stack e heap. Byte come unità fondamentale di memoria indirizzabile. Nozione di
oggetto C∞ come regione di memoria il cui contenuto può rappresentare valori. Tipi come interpretazione del contenuto di oggetti. Tipi primitivi: void, char, short, int, long, long long, float, double, long double. Tipi interi con e senza segno. Richiamo su rappresentazioni little endian e big endian. Operatore sizeof per determinare la dimensione in byte di oggetti di un certo tipo. Tipi derivati: funzioni, struct, union, puntatori, array (panoramica introduttiva) [
T1].
Introduzione alle funzioni di output:
fprintf∞ e
printf∞. Stringhe di formato e specificatori %d, %u, %f, %s. Specificatori di dimensione campo, allineamento e precisione. Esempio di interpretazione di un oggetto di tipo int da parte della funzione printf come intero con segno (%d) o senza segno (%u). Introduzione alle
macro C∞: sostituzione dei parametri e tranelli nella definizione e uso di macro [
T1].
Giovedi 25 Settembre
Nozione di valore come interpretazione del contenuto di un oggetto. Espressioni in C: espressioni
LValue∞ per denotare oggetti ed espressioni
RValue∞ per denotare valori.
Conversione di LValue a RValue∞. Assegnazioni di oggetti mediante l'operatore =. Puntatori come tipi derivati. Generazione di valori di tipo puntatore mediante cast di valori interi e modifica di un oggetto ad un indirizzo arbitrario in memoria. Rischi dell'accesso diretto alla memoria. Operatori
* ("all'indirizzo")∞ e
& ("indirizzo di")∞. Funzioni con parametri formali di tipo puntatore: esempio di funzione che raddoppia il contenuto di un oggetto [
T1].
Settimana 2
Mercoledi 1 Ottobre
Allocazione e dellocazione dinamica di blocchi: funzioni di libreria
malloc∞ e
free∞. Partizionamento dello spazio heap e frammentazione esterna.
Aritmetica dei puntatori∞: operazione somma. Uso di v[i] come espressione equivalente a *(v+i). Esempio: verifica dei duplicati in un array in Java e in C. Puntatori generici void* e
conversioni fra puntatori∞. Creazione e distruzione di matrici allocate dinamicamente. Stringhe C e
letterali stringa∞ [
T1].
Giovedi 2 Ottobre
Aritmetica dei puntatori: differenza tra puntatori.
Array allocati staticamente in C∞. Allocazione nel segmento dati come variabile globale e allocazione in stack come variabile locale. Rischi di stack overflow usando variabili locali di tipo array in contesti ricorsivi. Nome di variabile array come LValue non modificabile (eccezione alla regola per cui i nomi di variabili sono LValue modificabili). Conversione automatica di una variabile array a un RValue di tipo puntatore. Equivalenza dei parametri formali di tipo array a parametri formati di tipo puntatore. Matrici allocate staticamente e differenza di rappresentazione rispetto alle matrici allocate dinamicamente.
Settimana 3
Mercoledi 8 Ottobre
Tipi base e tipi derivati. Tipi funzione. Espressioni che denotano tipi in C: regole sintattiche e restrizioni semantiche [
P2∞]. Puntatori a funzione ed esempi di uso. Polimorfismo sulle operazioni in C mediante puntatori a funzione e analogie con il polimorfismo in Java. Parola chiave typedef e alias di tipi. Esempi al calcolatore: ispezionare gli indirizzi dei record attivazione di funzioni ricorsive (esempio funzione che calcola il fattoriale di un numero); pericoli nell'usare puntatori direttamente a record di attivazione.
Giovedi 9 Ottobre
Lezione annullata.
Settimana 4
Mercoledi 15 Ottobre
Strutture in C∞: dichiarazione e accesso agli attributi mediante l'operatore punto. Tag delle strutture come spazio di nomi separato dallo spazio dei nomi di variabili, tipi e funzioni. Uso di typedef per creare alias di tipi struct. Copia byte a byte nelle assegnazioni di struct. Array come attributi di struct e loro passaggio come parametri a funzioni. Allocazione dinamica di oggetti struct e operatore -> per accedere ai loro attributi. Rappresentazione di tipi di dato complessi in C mediante struct: costruttore, distruttore, operazioni sugli oggetti. Memory leak dovuti a mancata deallocazione di oggetti. Esempio del tipo di dato
Persona in Java e in C. Allineamento e padding nelle struct: layout di memoria e aspetti architetturali. Programmi C suddivisi su più file e uso di header file. Inclusioni di header di sistema con #include <...> e inclusioni di header utente con #include "...". Compilazione separata di moduli C e linking: errori di simboli non definiti ed errori di simboli duplicati. Problema dell'inclusione multipla di header e soluzione basata su direttive di preprocessore #ifndef ... #define ... #endif.
Giovedi 16 Ottobre
Aspetti di ingegnerizzazione nella rappresentazione di strutture dati elementari. Limiti dei modelli di costo teorici. Influenza delle cache nelle prestazioni dei programmi e importanza della località nel pattern di accesso alla memoria. Esempio della scansione per righe e per colonne di una matrice. Esempio della ricerca di un elemento in una collezione:
confronto prestazionale scansione lineare array e struttura collegata.
Settimana 5
Mercoledi 22 Ottobre
Richiami sui tipi di dato astratti e sulle strutture dati come loro realizzazione. Vantaggi e svantaggi nell'uso di array e strutture collegate per implementare strutture dati. Tipo di dato astratto array dinamico: dominio, costruttore, operazioni set, get, expand e shrink. Realizzazione del tipo di dato array dinamico mediante array in C. Operazioni expand e shrink mediante la tecnica del raddoppiamento/dimezzamento e analisi sperimentale delle prestazioni di una sequenza di expand (tempo medio per operazione). Limiti del modello di costo asintotico tradizionale per stimare il costo di una sequenza di operazioni e modello di costo ammortizzato. Metodo dei crediti. Esempio di analisi ammortizzata dell'operazione expand dell'array dinamico [
T2].
Giovedi 23 Ottobre
Analisi sperimentale delle prestazioni di una sequenza di expand in funzione del tasso di crescita dell'array e misura del tempo di esecuzione per operazione nel caso peggiore [
D3∞]. Array dinamico per applicazioni real-time con tutte le operazioni O(1) nel caso peggiore [Appunti].
Settimana 6
Mercoledi 29 Ottobre
Risoluzione esercizio: analisi ammortizzata del costo di incremento di un contatore binario. Il tipo di dato Dizionario: operazioni insert, delete e search [
T2]. Realizzazione in C con chiavi ed elementi generici mediante array non ordinato e mediante array ordinato. Uso della funzione standard C di ricerca binaria
bsearch. Uso di puntatori a funzione per definire comparatori. Costi asintotici per operazione [Appunti].
Giovedi 30 Ottobre
Aspetti di ingegnerizzazione nella realizzazione di strutture dati. Riferimenti diretti agli elementi interni di una struttura dati per l'aggiornamento e la cancellazione di elementi. Esempio del dizionario realizzato mediante array. Aspetti di robustezza: verifica che un riferimento interno non sia usato su una struttura dati diversa da quella per cui è stato creato [Appunti].
Settimana 7
Mercoledi 5 Novembre
Tabelle ad accesso diretto e tabelle hash: richiami su funzioni hash perfette e proprietà di uniformità. Paradosso del compleanno: calcolo della probabilità di conflitto in una tabella hash utilizzando funzioni hash uniformi [
T2]. Esempi.
Giovedi 6 Novembre
Realizzazione in C di un dizionario basato su liste di collisione con chiavi ed elementi generici: costruttore, operazioni
insert e
search. Esempio di funzione hash generica e definizione di una funzione hash per chiavi di tipo double. File C: header
Hash.h, modulo
Hash.c, programma di prova
main.c.
Settimana 8
Mercoledi 12 Novembre
Tipo di dato coda con priorità: operazioni
insert,
remove,
findMin,
removeMin,
decreaseKey,
increaseKey,
merge. Struttura dati d-Heap e sue proprietà (ordinamento a heap, altezza, minimo nella radice). Realizzazione di una coda con priorità mediante d-Heap. Alberi binomiali: definizione e proprietà (altezza, numero nodi, grado della radice). Heap binomiali e loro proprietà (collezione di alberi binomiali, unicità, ordinamento a heap). Realizzazione di una coda con priorità mediate struttura dati heap binomiale: operazioni
decreaseKey,
increaseKey,
insert. Operazione
ristruttura per ristabilire il vincolo di unicità [
T2].
Giovedi 13 Novembre
Operazione
removeMin. Realizzazione in C di una coda con priorità basata su heap binomiale: rappresentazione struttura dati e implementazione operazioni
insert e
findMin. File C: header
HeapB.h, modulo
HeapB.c, programma di prova
main.c.
Settimana 9
Mercoledi 19 Novembre
Liste XOR [
P5∞]. Liste unrolled [
P6∞] e analisi dello spazio richiesto: operazioni di fusione e divisione di nodi. Heap binomiali rilassati e analisi ammortizzata del costo delle operazioni. Heap di Fibonacci: operazione
decreaseKey e operazione
staccaInCascata [
T2]. Esempio di applicazione degli heap di Fibonacci nell'algoritmo di Dijkstra per il calcolo dei cammini minimi.
Giovedi 20 Novembre
Analisi ammortizzata dell'operazione
decreaseKey degli heap di Fibonacci. Esponenzialità del numero di nodi degli alberi di un heap di Fibonacci rispetto al loro grado: formula chiusa per i numeri di Fibonacci, sezione aurea come base di una funzione esponenziale che descrive il minimo numero di nodi di un albero di un heap di Fibonacci [
T2].
Settimana 10
Mercoledi 26 Novembre
Modello di macchina con sistema di memoria gerarchica a due livelli (RAM e disco) [
T2]. Costo di un programma come numero di trasferimenti di blocchi effettuati fra i due livelli (I/O). Primitive di scansione lineare (SCAN) e ordinamento (SORT). Analisi del numero di I/O dell'algoritmo MergeSort classico e algoritmo MergeSort a k vie (k-way MergeSort) [
D4]. Lower bound sul numero di I/O per il problema dell'ordinamento (prima parte) [
D4,
D5].
Giovedi 27 Novembre
Lower bound sul numero di I/O per il problema dell'ordinamento (passaggi finali della dimostrazione). Versione iterativa del k-way MergeSort [
D4]. Aspetti implementativi nella realizzazione dell'operazione di fusione a più vie di sottosequenze ordinate in memoria esterna. Valutazione sperimentale dei tempi di accesso sequenziale [
D6] e casuale a file di grandi dimensioni [
D7].
Settimana 11
Mercoledi 3 Dicembre
Implementazione in C della versione iterativa del k-way MergeSort [
D4]: strutture dati e funzioni [
LFileSort.h,
LFileSort.c,
main.c].
Giovedi 4 Dicembre
Profiling di programmi in ambiente Linux/UNIX: uso del tool
gprof [
P7]. Esempio: profiling dell'implementazione
LFileSort.h/
LFileSort.c/
main.c del k-way MergeSort. Code con priorità in memoria esterna: Sequence Heaps: operazioni
insert e
deleteMin [
A1]. Analisi ammortizzata del numero di I/O in caso di sole
insert, cammino canonico [Appunti].
Settimana 12
Mercoledi 10 Dicembre
Sequence Heaps: analisi ammortizzata del numero di I/O in caso di operazioni miste
insert/
deleteMin, analisi impatto retrocessione elementi durante le
insert [Appunti]. Allocatori come strutture dati per la gestione dinamica della memoria. Operazioni
malloc e
free. Heap e suo partizionamento in blocchi liberi, blocchi in uso e informazioni di controllo. Primitive
brk() e
sbrk() per il ridimensionamento dell'heap. Design goal, strategie, politiche, meccanismi. Meccanismi di basso livello: header e boundary tag [
A2].
Giovedi 11 Dicembre
Meccanismi di basso livello: link integrati nei blocchi. Panoramica sui meccanismi di allocazione: sequential fits (best fit, first fit, next fit, worst fit) e segregated free lists (simple segregated storage e segregated fits) [
A2].
Settimana 13
Mercoledi 17 Dicembre
Buddy system binari [
T4, Volume 1, Paragrafo 2.5]. Cenni a buddy system di Fibonacci, pesati, e doppi. Cenni a indexed fits e bitmapped fits [
A2]. Introduzione al package
malloclab.
Giovedi 18 Dicembre
Riepilogo degli argomenti del corso e collegamenti tra i diversi argomenti trattati. Modalità di esame. Strutturazione delle relazioni di documentazione delle tesine.