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
Soluzioni compito sessione B - appello del 9 febbraio 2010
Domanda 1
Si consideri il seguente programma C:
#include <stdio.h>
#include <string.h>
typedef struct {
char name
[128];
char* gender;
} Person;
void setData
(Person p,
char* name,
char* gender
) {
strcpy
(p.
name, name
);
strcpy
(p.
gender, gender
);
}
int main
(){
char gender
[5] =
"male";
Person p =
{ "Vincent Vega", gender
};
setData
(p,
"Mia Wallace",
"female");
printf("%s %s\n", p.
name, p.
gender);
return 0;
}
(a)
Cosa stampa?
(b)
Al di là di eventuali errori logici, il programma usa la memoria in modo corretto?
Soluzione:
All'inizio dell'esecuzione del programma vengono allocati due oggetti nel record di attivazione del
main:
- un array gender di 5 char;
- un oggetto p di tipo Person.
L'oggetto
p contiene un campo
name di 128 caratteri seguito da un campo
gender di tipo puntatore (4 o 8 byte). Esso viene inizializzato con
{ "Vincent Vega", gender } in modo che i primi 13 byte dell'array
name contengono la stringa
"Vincent Vega" e il terminatore
'\0' e il campo
gender contiene l'indirizzo del primo byte dell'array
gender allocato nel record di attivazione del
main.
La funzione
setData riceve come primo parametro una copia byte a byte della struttura
p allocata nel record di attivazione del
main: essa viene memorizzata al momento del passaggio dei parametri nel parametro formale
p allocato nel record di attivazione di
setData. La prima
strcpy modifica pertanto la copia locale
p dell'oggetto
Person memorizzata nel record di attivazione di
setData, scrivendo
"Mia Wallace" nel campo
name. La seconda
strcpy modifica invece il buffer
gender di 5 byte localizzato nel record di attivazione del
main, copiandovi i 7 byte della stringa
"female". Il programma usa quindi in modo scorretto la memoria poiché si ha un
buffer overflow. L'overflow tuttavia tipicamente non compromette il funzionamento del programma poiché l'oggetto
p che segue il buffer
gender deve essere allineato a 32 o 64 bit, e quindi ci sono almento 3 byte inutilizzati di padding tra
gender e
p, quanto basta per contenere i due byte aggiuntivi
"le" di
"female" che provocano l'overflow. All'uscita da
setData il parametro formale
p viene deallocato e quindi il valore
"Mia Wallace" scritto si perde, dando luogo a un errore logico. Rimane invece il side-effect sul buffer
gender dichiarato nel
main. Pertanto, la
printf stampa
"Vincent Vega" e
"female".
Domanda 2
In un heap di Fibonacci, qual è il minimo numero di nodi di un sottoalbero in funzione del grado della sua radice? Fornire una dimostrazione dettagliata.
Soluzione:
Si vedano gli appunti del corso o il testo [
T2] (C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill), Capitolo 8, Teorema 8.4.
Domanda 3
Si descrivano le caratteristiche principali degli allocatori di memoria di tipo "segregated free lists".
Soluzione:
Si vedano gli appunti del corso o l'articolo [
A2] (Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles: Dynamic Storage Allocation: A Survey and Critical Review. In Proceedings of the 2nd International Workshop on Memory Management, 1995), Paragrafo 3.6.
Domanda 4
Si supponga di avere un calcolatore con memoria interna in grado di contenere M item di dati (es. interi a 32 bit) e x file ordinati su disco, ciascuno contenente N item, con N>>M. Descrivere un algoritmo per fondere gli item degli x file di input in un unico file ordinato di output. L'algoritmo deve effettuare il minor numero possibile di accessi a disco. Fornire sia i dettagli dell'algoritmo che l'analisi del suo numero di I/O in funzione dei parametri del problema, assumendo che ogni accesso a disco trasferisca B item tra memoria centrale e disco. Che influenza ha il valore di x sul numero di I/O?
Soluzione:
- Caso 1. x<= M/B -1. Basta usare un merger a x vie che fonde gli x file ordinati in un unico file di uscita ordinato effettuando un numero di I/O pari a O(xN/B).
- Caso 2. x > M/B - 1. Non vi è sufficiente memoria interna per usare un merger a x vie. Si possono pertanto fondere gli x file a k a k applicando per ceil(x/k) volte un merger a k=M/B - 1 vie producendo ceil(x/k) file ordinati di al più kN item ciascuno, dove ceil denota la parte intera superiore. Il numero x di file da fondere si riduce di un fattore k e gli I/O richiesti sono ceil(x/k)*O(kN/B)=O(xN/B). Iterando il procedimento per logkx volte si arriva pertanto ad avere un solo file ordinato. Il numero totale di I/O richiesto per tutte le iterazioni è pertanto O((xN/B)*logM/Bx).