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 A.A. 2009-2010
Lezione 1 - Giovedi 1 ottobre
Panoramica su motivazioni e obiettivi del corso. Il linguaggio C. Fasi della compilazione di un programma C: preprocessore, compilatore, linker. Librerie e
direttiva #include∞. Introduzione alle
macro C∞: sostituzione dei parametri e tranelli nella definizione e uso di macro [
T1]. 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. 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. Compilazione condizionale: direttive di preprocessore
#if,
#elif,
#else,
#endif.
[
Esercizi del giorno]
Lezione 2 - Venerdi 2 ottobre
Nozione di
oggetto C∞ come regione di memoria contenente un valore. 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: funzione
printf∞. Stringhe di formato e specificatori %d, %f, %s. 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. Operatori
* ("all'indirizzo")∞ e
& ("indirizzo di")∞.
[
Esercizi del giorno]
Lezione 3 - Giovedi 8 ottobre
Realizzazione del passaggio dei parametri per riferimento in C mediante uso di puntatori. Conversione da intero a puntatore e viceversa: accesso diretto a un indirizzo arbitrario nello spazio logico del processo. Il riferimento
NULL. Allocazione e dellocazione dinamica di blocchi: funzioni di libreria
malloc∞ e
free∞.
Aritmetica dei puntatori∞: operazione somma. Uso di v[i] come espressione equivalente a *(v+i). Puntatori generici void* e
conversioni fra puntatori∞. Stringhe C e
letterali stringa∞ [
T1]. Esempi: funzione
int strlen(char* s) per calcolare la lunghezza di una stringa, funzione
void concat(char* s1, char* s2, char** p) per concatenare due stringhe in un nuovo blocco restituito per parametro.
[
Esercizi del giorno]
Lezione 4 - Venerdi 9 ottobre
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 dinamicamente. Incompatibilità delle due rappresentazioni. Esercizio svolto: soluzione
esercizi 4 e 5 dell'8/10/2009.
[
Esercizi del giorno]
Lezione 5 - Giovedi 15 ottobre
Tipi base e tipi derivati. Parola chiave
typedef e alias di tipi. 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. Esercizi svolti: funzione che calcola il massimo di un array di elementi di tipo generico, definizione di funzioni comparatore, soluzione
esercizio 3 dell'8/10/2009, funzione che rovescia l'ordine degli elementi di un array di oggetti di tipo generico. Uso della funzione
memcpy.
[
Esercizi del giorno]
Lezione 6 - Venerdi 16 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 di tipo di dato
Punto in C. Allineamento e padding nelle struct: layout di memoria e aspetti architetturali.
[
Esercizi del giorno]
Lezione 7 - Giovedi 22 ottobre
Compilazione incrementale: programma
make e scrittura di
makefile [
P10∞] [
P11∞]. Regole, commenti, macro nei
makefile. Dinamica dell'esecuzione dei
makefile. Dummy target. Complementi di C:
unioni∞ (
union) ed
enumerazioni∞ (
enum). Differenze tra
union e
struct. Variabili dichiarate globalmente e localmente.
Storage class delle variabili∞: specificatori
extern,
static,
auto,
register. Differenza tra
external linkage e static (o internal) linkage per le variabili globali∞. Variabili globali con campo di visibilità locale alle funzioni: esempio di funzione
char* aggiungiestensione(char* nome, char* ext) che concatena nome ed estensione di un file restituendo il risultato in un buffer statico dichiarato localmente alla funzione e differenza con la corrispondente realizzazione che alloca memoria in heap.
[
Esercizi del giorno]
Lezione 8 - Venerdi 23 ottobre
Soluzione esercizi:
2 e 5 del 22/10/2009 e
1, 2 e 4 del 15/10/2009.
[
Esercizi del giorno]
Lezione 9 - Giovedi 29 ottobre
Vantaggi e svantaggi nell'uso di array e strutture collegate per implementare strutture dati [
T2, §3.1]. Strutture collegate in C. Esempio del tipo di dato
Set con operazioni
insert,
delete e
find implementata mediante lista semplice. Strutture collegate con elementi di tipo generico con size nota solo a tempo di esecuzione: tecnica del fat node. Variante del tipo di dato
Set con elementi generici: costruttore,
insert e
find. Liste doppiamente collegate, liste unrolled [
P6∞], liste XOR [
P5∞]. Calcolo dello spazio richiesto per mantenere
n elementi di dimensione
k usando una lista semplice, una lista unrolled e un array. 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 tipo
Set realizzato mediante lista doppiamente collegata. Alberi n-ari con strutture collegate non lineari mediante rappresentazione padre/primo-figlio/fratello-successivo.
[
Esercizi del giorno]
Lezione 10 - Venerdi 30 ottobre
Richiami sul modello di costo asintotico di caso peggiore e suoi limiti per analizzare sequenze di operazioni. Esempio dell'incremento di un contatore binario. Calcolo sperimentale del tempo per effettuare una sequenza di k=2
n incrementi su un array di
n bit per diversi valori di
n: tempo medio e massimo per incremento. Nozione di costo totale effettivo di una sequenza di operazioni. Analisi ammortizzata come tecnica di analisi che consente di stimare in modo più accurato il tempo totale effettivo. Analisi ammortizzata basata sul metodo dei crediti: definizione di costo ammortizzato di un'operazione. Dimostrazione che il metodo dei crediti fornisce un upper bound al tempo totale effettivo e relativi corollari. Esempio del contatore binario: costo ammortizzato dell'operazione incrementa [
D8∞]. Discussione dei tempi sperimentali per la scansione sequenziale di un array e di una struttura collegata con vari pattern di layout dei nodi in memoria. Tipo di dato astratto array dinamico: operazioni
set,
get,
expand,
shrink. Implementazione del tipo di dato array dinamico mediante tecnica del raddoppiamento/dimezzamento. Analisi del caso peggiore per operazione.
[
Esercizi del giorno]
Lezione 11 - Giovedi 5 novembre
Analisi ammortizzata delle operazioni del tipo di dato array dinamico realizzate mediante la tecnica del raddoppiamento/dimezzamento. Analisi ammortizzata di una variante che ridimesiona l'array di 1 ad ogni expand. Realizzazione del tipo di dato array dinamico con tutte le operazioni O(1) nel caso peggiore. Implementazione in C.
[
Esercizi del giorno]
Lezione 12 - Venerdi 6 novembre
Caso di studio di analisi ammortizzata: cammini minimi in grafi dinamici [
D8∞]. Definizione del problema rispetto a una sorgente prefissata. Soluzione inefficiente con ricalcolo da zero delle distanze dopo ogni aggiornamento del grafo e soluzione efficiente nel caso di sequenze di sole cancellazioni e query di distanza. Analisi ammortizzata (da completare nella prossima lezione).
Lezione 13 - Giovedi 12 novembre
Analisi ammortizzata delle operazioni di cancellazione e query di distanza in grafi dinamici con pesi unitari sugli archi (fine della dimostrazione) [
D8∞]. Tipo di dato astratto grafo dinamico. Trade-off spazio/tempo nella realizzazione di strutture dati. Possibile realizzazione mediante strutture collegate con tempo ammortizzato O(1) per operazione e spazio usato pari a 32+x byte per nodo e 40+x byte per arco, dove x è il numero di byte della header di blocco dell'allocatore, assumendo puntatori a 8 byte e grafi con meno di 2
32 nodi. Tecnica della
lazy deletion come alternativa alle liste doppiamente collegate e sua analisi ammortizzata. Tecnica del
bit stealing per mantenere un flag binario usando lo spazio di un puntatore.
[
Esercizi del giorno]
Lezione 14 - Venerdi 13 novembre
Implementazione in C della tecnica della
lazy deletion e del bit stealing: esempio di applicazione delle due tecniche al tipo di dato
LongList (variante dell'
esercizio 1 del 12/11/2009). Calcolo dello spazio utilizzato dall'implementazione. Strategie per il garbage collection dei nodi marcati come cancellati. Valutazione sperimentale delle differenze prestazionali degli accessi a memoria allineati e non allineati.
Lezione 15 - Giovedi 19 novembre
Analisi del fattore di carico dell'implementazioni della
LongList mediante nodi allocati con
malloc/
free e lazy deletion con bit stealing. Discussione dell'accuratezza dell'analisi e degli effetti dovuti alla frammentazione dell'heap. Fattore di carico di picco. Analisi del fattore di carico di picco della
LongList: alpha <= 1/6. Realizzazione del tipo di dato
LongList senza usare
malloc/
free per ogni nodo, ma usando un allocatore proprio che opera su un array di nodi: descrizione della struttura dati, macro e realizzazione dell'operazione
Add (realizzazione in C:
LongList_Array). Analisi del fattore di carico di picco della nuova realizzazione: alpha = 1/2.
Lezione 16 - Giovedi 26 novembre
Tipo di dato astratto coda con priorità: operazioni
insert,
remove removeMin,
findMin,
decreaseKey,
increaseKey,
merge. Esempio di applicazione del tipo di dato coda con priorità per velocizzare l'algoritmo di Dijkstra per il calcolo dei cammini minimi: prospettiva storica e progressi fondamentali nella teoria delle code con priorità. Realizzazione mediante struttura dati d-heap. Proprietà di un d-heap: struttura, ordinamento padre-figli, altezza di un d-heap con n nodi. Calcolo del d ottimale per migliorare il tempo dell'algoritmo di Dijkstra rispetto all'uso di heap binari. Alberi binomiali: altezza, grado, numero di nodi. Heap binomiali e loro proprietà: struttura, ordinamento padre-figli, unicità degli alberi nella foresta. Numero di alberi in un heap binomiale con n nodi. Realizzazione delle operazioni di una coda con priorità basata su heap binomiali.
Lezione 17 - Venerdi 27 dicembre
Heap binomiali rilassati e analisi ammortizzata del costo delle operazioni mediante il metodo dei crediti. Heap di Fibonacci: costo ammortizzato dell'operazione
decreaseKey con il metodo dei crediti. Dimostrazione dell'esponenzialità del numero di nodi di ogni albero della foresta nel grado della propria radice. Esponenzialità della successione dei numeri di FIbonacci e sezione aurea.
Lezione 18 - Giovedi 3 dicembre
Realizzazione in C di un heap binomiale: struttura dati per rappresentare la foresta di alberi e realizzazione dell'operazione
ristruttura. Modello di costo per programmi che usano memoria esterna e motivazioni architetturali. Modello di macchina con due livelli di memoria (interna ed esterna). Parametri
N (numero item in memoria esterna da elaborare),
M (numero item memorizzabili in memoria interna) e
B (numero item trasferiti ad ogni accesso a disco, in scrittura o in lettura). Valutazione dell'efficienza mediante stima del numero di accessi a disco (operazioni di I/O effettuate) e differenze rispetto al modello tradizionale di costo che stima il numero di istruzioni mandate in esecuzione. Primitive di scansione lineare (SCAN) e di ordinamento (SORT). Versione dell'algoritmo di ordinamento per fusione a 2 vie (mergesort classico) che accede a disco a blocchi e analisi del numero di I/O effettuati per ordinare N item usando memoria interna di dimensione M e blocchi di B item. Algoritmo di ordinamento per fusione a k vie (k-way mergesort): descrizione della versione ricorsiva dell'algoritmo e analisi del numero di I/O effettuati per ordinare N item usando memoria interna di dimensione M e blocchi di B item.
Lezione 19 - Venerdi 4 dicembre
Lower bound sul numero di I/O necessari nel caso peggiore per qualsiasi algoritmo di ordinamento in funzione del numero N di item da ordinare, la dimensione M della memoria centrale, e il numero B di item per blocco. Analisi sperimentale dei tempi necessari per l'accesso a disco in modo
sequenziale e
casuale.
Lezione 20 - Giovedi 10 dicembre
Versione iterativa dell'algoritmo k-way mergesort e sua implementazione in C (
LFileSort.h,
LFileSort.c,
main.c). Allocatori di memoria: definizione del problema e obiettivi. Aspetti generali: splitting e coalescing, pattern di riuso di memoria, splitting threshold e problematiche di fit ([A2], paragrafi 1.2 e 3.1)
Lezione 21 - Venerdi 11 dicembre
Dimostrazione pratica del funzionamento dell'algoritmo iterativo k-way mergesort e tuning dei parametri. Uso di tool di profiling per identificare le funzioni in cui si concentra la maggior parte del tempo di esecuzione:
gprof. Meccanismi di basso livello per allocatori di memoria: header di blocco, boundary tags, strutture collegate per mantenere blocchi liberi con puntatori nei blocchi stessi, lookup tables, trattamento diverso di blocchi piccoli e blocchi grandi ([A2], paragrafo 3.2).
Lezione 22 - Giovedi 17 dicembre
Classificazione allocatori: sequential fits, segregated free lists (simple segregated storage e segregated fits), buddy systems (binary, FIbonacci, weighted, double), indexed fits, bitmapped fits ([A2], paragrafi 3.3, 3.4, 3.6, 3.7, 3.8, 3.9). Caso di studio: descrizione generale dell'allocatore
dlmalloc∞ [C4] (libc in sistemi Linux/UNIX). Esempio di semplice
allocatore reale in C per sistemi Linux/UNIX∞ [C3] basato su system call
sbrk (
codice C∞).
[
Diario delle lezioni 2008-2009 ]