Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/wikka.php on line 315
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/libs/Wakka.class.php on line 176
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/libs/Wakka.class.php on line 463
Deprecated: Function set_magic_quotes_runtime() is deprecated in /home/demetres/public_html/didattica/ae2008/wikka.php on line 120
Most recent edit on 2008-03-11 22:40:13 by CamilDemetrescu
Additions:
~& Può essere utile la classe FIleParser.java∞ per caricare in memoria grafi da file in formato DIMACS realizzata da Valerio Bellizia.
Deletions:
~& Può essere utile la classe FIleParser.java∞ per caricare in memoria grafi da file in formato DIMACS realizzata da Valerio Bellizia.
Edited on 2008-03-11 22:16:03 by CamilDemetrescu
Additions:
~& Può essere utile la classe FIleParser.java∞ per caricare in memoria grafi da file in formato DIMACS realizzata da Valerio Bellizia.
Deletions:
~& Può essere utile la classe http://www.dis.uniroma1.it/~demetres/didattica/sr2008/upload/FIleParser.java∞ per caricare in memoria grafi in formato DIMACS realizzata da Valerio Bellizia.
Edited on 2008-03-11 22:14:43 by CamilDemetrescu
Additions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe GrafoLA∞ nel caso in cui le operazioni siano generate dalla visita in ampiezza∞ di un grafo a partire dal suo nodo di indice zero. Utilizzare come dati di test i grafi stradali del 9th DIMACS Implementation Challenge∞.
Deletions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe GrafoLA∞ nel caso in cui le operazioni siano generate dalla visita in ampiezza∞ di un grafo a partire dal suo nodo di indice zero. Utilizzare come dati di test i grafi stradali del 9th DIMACS Implementation Challenge∞.
Edited on 2008-03-10 17:34:35 by CamilDemetrescu
Deletions:
Maggiori dettagli nei prossimi giorni.
Edited on 2008-03-10 17:33:57 by CamilDemetrescu
Additions:
Scrivere una classe Java che realizza gli heap binomiali rilassati come estensione degli heap binomiali∞ della libreria asdlab∞ e una classe che realizza gli heap di Fibonacci come estensione degli heap binomiali rilassati. Confrontare poi sperimentalmente l'efficienza dell'algoritmo di Dijkstra∞ utilizzando come code con priorità i d-Heap∞, gli heap binomiali∞, gli heap binomiali rilassati, e gli heap di Fibonacci. Utilizzare i grafi dell'homework 6 come dati di test.
Deletions:
Scrivere una classe Java che realizza gli heap binomiali rilassati come estensione degli heap binomiali∞ della libreria asdlab∞ e una classe che realizza gli heap di Fibonacci come estensione degli heap binomiali rilassati. Confrontare poi sperimentalmente l'efficienza dell'algoritmo di Dijkstra utilizzando come code con priorità i d-Heap∞, gli heap binomiali∞, gli heap binomiali rilassati, e gli heap di Fibonacci. Utilizzare i grafi dell'homework 6 come dati di test.
Edited on 2008-03-10 17:28:57 by CamilDemetrescu
Additions:
HW9
Scrivere una classe Java che realizza gli heap binomiali rilassati come estensione degli heap binomiali∞ della libreria asdlab∞ e una classe che realizza gli heap di Fibonacci come estensione degli heap binomiali rilassati. Confrontare poi sperimentalmente l'efficienza dell'algoritmo di Dijkstra utilizzando come code con priorità i d-Heap∞, gli heap binomiali∞, gli heap binomiali rilassati, e gli heap di Fibonacci. Utilizzare i grafi dell'homework 6 come dati di test.
Edited on 2008-02-25 15:18:39 by CamilDemetrescu
Additions:
Scrivere due programmi A e B in un linguaggio a scelta: A apre un file e lo legge 4 byte alla volta sequenzialmente. B apre lo stesso file e lo legge 4 byte alla volta saltando in posizioni casuali nel file. Questa seconda modalità di lettura potrebbe richiedere anche settimane se il file è molto grande: si consiglia pertanto di non leggere tutto il file, ma effettuare solo qualche decina di migliaia di letture e calcolare il tempo medio per ogni lettura. Graficare il rapporto di prestazioni di B rispetto ad A (tempo medio per leggere 4 byte).
Deletions:
Scrivere due programmi A e B in un linguaggio a scelta: A apre un file e lo legge 4 byte alla volta sequenzialmente. B apre lo stesso file e lo legge 4 byte alla volta saltando in posizioni casuali nel file. Graficare il rapporto di prestazioni di B rispetto ad A per varie dimensioni di file da qualche centinaio di mega a qualche giga.
Edited on 2008-02-16 08:42:30 by CamilDemetrescu
Additions:
Realizzare l'operazione di cancellazione di un item da un B-Tree completando il codice C disponibile qui∞.
Graficare poi il tempo totale richiesto per effettuare una sequenza di N inserimenti di chiavi seguita da una sequenza alternata di N inserimenti ed N cancellazioni di chiavi in funzione di N. Scegliere ad esempio le chiavi casualmente e assumere che il dizionario possa contenere duplicati. Provare con N che varia da qualche milione a qualche miliardo con chiavi a 32 bit fissando la block size a 8KB. Fare un ulteriore esperimento in cui si fissa N e si varia B ad esempio da 64 byte a 256 KB graficando il tempo totale in funzione di B.
Deletions:
Realizzare l'operazione di cancellazione di un item da un B-Tree completando il codice C disponibile qui.
Graficare poi il tempo totale richiesto per effettuare una sequenza di N inserimenti di chiavi seguita da una sequenza alternata di N inserimenti ed N cancellazioni di chiavi in funzione di N. Prendere ad esempio le chiavi casualmente dall'intervallo [0,9999] e assumere che il dizionario possa contenere duplicati. Provare con N che varia da qualche milione a qualche miliardo con chiavi a 32 bit fissando la block size a 8KB. Fare un ulteriore esperimento in cui si fissa N e si varia B ad esempio da 64 byte a 256 KB graficando il tempo totale in funzione di B.
Edited on 2008-02-15 16:18:27 by CamilDemetrescu
Additions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe GrafoLA∞ nel caso in cui le operazioni siano generate dalla visita in ampiezza∞ di un grafo a partire dal suo nodo di indice zero. Utilizzare come dati di test i grafi stradali del 9th DIMACS Implementation Challenge∞.
Realizzare l'operazione di cancellazione di un item da un B-Tree completando il codice C disponibile qui.
Graficare poi il tempo totale richiesto per effettuare una sequenza di N inserimenti di chiavi seguita da una sequenza alternata di N inserimenti ed N cancellazioni di chiavi in funzione di N. Prendere ad esempio le chiavi casualmente dall'intervallo [0,9999] e assumere che il dizionario possa contenere duplicati. Provare con N che varia da qualche milione a qualche miliardo con chiavi a 32 bit fissando la block size a 8KB. Fare un ulteriore esperimento in cui si fissa N e si varia B ad esempio da 64 byte a 256 KB graficando il tempo totale in funzione di B.
Deletions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe GrafoLA∞ nel caso in cui le operazioni siano generate dalla visita di un grafo. Utilizzare come dati di test i grafi stradali del 9th DIMACS Implementation Challenge∞.
Edited on 2008-02-15 15:57:01 by CamilDemetrescu
Additions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe GrafoLA∞ nel caso in cui le operazioni siano generate dalla visita di un grafo. Utilizzare come dati di test i grafi stradali del 9th DIMACS Implementation Challenge∞.
Deletions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto di prestazioni della visita di un grafo rappresentato mediante classe realizzata rispetto al caso in cui il grafo è rappresentato mediante la classe GrafoLA∞.
Edited on 2008-02-15 15:53:13 by CamilDemetrescu
Additions:
Realizzare una classe grafo in Java come implementazione dell'interfaccia Grafo∞ della libreria asdlab [Software] e graficare il rapporto di prestazioni della visita di un grafo rappresentato mediante classe realizzata rispetto al caso in cui il grafo è rappresentato mediante la classe GrafoLA∞.
Maggiori dettagli nei prossimi giorni.
Deletions:
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/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/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 471
Realizzazione di una classe grafo in Java come implementazione dell'interfaccia Grafo della libreria asdlab [Software] e analisi sperimentale delle prestazioni. Maggiori dettagli nei prossimi giorni.
Edited on 2008-02-15 15:49:21 by CamilDemetrescu
Additions:
HW6
Realizzazione di una classe grafo in Java come implementazione dell'interfaccia Grafo della libreria asdlab [Software] e analisi sperimentale delle prestazioni. Maggiori dettagli nei prossimi giorni.
HW7
Scrivere due programmi A e B in un linguaggio a scelta: A apre un file e lo legge 4 byte alla volta sequenzialmente. B apre lo stesso file e lo legge 4 byte alla volta saltando in posizioni casuali nel file. Graficare il rapporto di prestazioni di B rispetto ad A per varie dimensioni di file da qualche centinaio di mega a qualche giga.
HW8
Edited on 2008-02-04 22:32:07 by CamilDemetrescu
Additions:
HW5
Implementare un allocatore di memoria in C (malloc, free, realloc) e studiarne le prestazioni su vari tipi di sequenze di operazioni reali e sintetiche. La descrizione completa dell'homework è disponibile qui.
Edited on 2008-02-04 14:23:55 by CamilDemetrescu
Deletions:
HW5
Scrivere un allocatore di memoria in C. Per informazioni preliminari sull'homework si veda [Malloc Lab: Writing a Dynamic Storage Allocator∞]. Maggiori dettagli su questa pagina a breve.
Edited on 2008-02-04 14:23:36 by CamilDemetrescu
Additions:
Scrivere un allocatore di memoria in C. Per informazioni preliminari sull'homework si veda [Malloc Lab: Writing a Dynamic Storage Allocator∞]. Maggiori dettagli su questa pagina a breve.
Deletions:
Scrivere un allocatore di memoria in C. Si veda [Malloc Lab: Writing a Dynamic Storage Allocator∞].
Edited on 2008-02-04 14:22:22 by CamilDemetrescu
Additions:
HW5
Scrivere un allocatore di memoria in C. Si veda [Malloc Lab: Writing a Dynamic Storage Allocator∞].
Edited on 2008-01-28 22:01:43 by CamilDemetrescu
Additions:
Scrivere una classe Java DynamicArray che implementa l'interfaccia List∞ ed estende la classe AbstractList∞ basata sulla tecnica del raddoppiamento/dimezzamento. Supportare almeno le seguenti operazioni:
Scrivere una classe Java DynamicArrayWC che implementa l'interfaccia List∞ ed estende la classe AbstractList∞ basata sulla struttura dati dell'homework 2. Supportare almeno le stesse operazioni previste dall'homework 3 per la classe DynamicArray. Estendere inoltre la sperimentazione dell'homework 3 includendo anche la classe DynamicArrayWC nei grafici.
Deletions:
Scrivere una classe Java DynamicArray che implementa l'interfaccia List∞ basata sulla tecnica del raddoppiamento/dimezzamento. Supportare almeno le seguenti operazioni:
Scrivere una classe Java DynamicArrayWC che implementa l'interfaccia List∞ basata sulla struttura dati dell'homework 2. Supportare almeno le stesse operazioni previste dall'homework 3 per la classe DynamicArray. Estendere inoltre la sperimentazione dell'homework 3 includendo anche la classe DynamicArrayWC nei grafici.
Edited on 2008-01-28 21:53:46 by CamilDemetrescu
Additions:
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) in funzione di n per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata. Per questo esperimento utilizzare una sequenza di sole add.
Deletions:
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) in funzione di n per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata.
Edited on 2008-01-28 09:27:18 by CamilDemetrescu
Additions:
Misurare il tempo complessivo richiesto dai metodi di ciascuna classe su sequenze con n che varia ad esempio da 50000 a 100000 con passo 5000. Graficare poi il tempo di esecuzione medio per operazione (ottenuto dividendo il tempo totale per 3n) in funzione di n.
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) in funzione di n per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata.
Deletions:
Misurare il tempo complessivo richiesto dai metodi di ciascuna classe su sequenze con n che varia ad esempio da 50000 a 100000 con passo 5000. Graficare poi il tempo di esecuzione medio per operazione (ottenuto dividendo il tempo totale per 3n).
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata.
Oldest known version of this page was edited on 2008-01-27 19:20:52 by CamilDemetrescu []
Page view:
Homework
Questa pagina raccoglie gli homework che vengono assegnati come esercitazione durante il corso. La soluzione di tutti gli homework o di un loro sottoinsieme può confluire nella tesina software prevista per il superamento dell'esame.
HW0
Confrontare sperimentalmente il tempo di esecuzione di un programma che scandisce una matrice n x n per righe e il tempo di esecuzione di un programma che la scandisce per colonne. Ci aspettiamo che i tempi di esecuzione siano uguali o diversi? Produrre un grafico che mostra il rapporto tra il tempo di scansione per colonne diviso il tempo di scansione per righe in funzione del lato n della matrice. Considerare n che varia da qualche centinaio a qualche migliaio.
HW1
Implementare il seguente algoritmo per la verifica di duplicati in una lista:
algoritmo verificaDupHashList(sequenza L) -> boolean
sia H una tabella hash inizialmente vuota
per ogni elemento x di L
se x appartiene ad H allora restituisci true
altrimenti aggiungi x ad H
restituisce false
realizzando un metodo Java con il seguente prototipo:
public static boolean verificaDupHashList
(List L
)
Estendere inoltre l'analisi sperimentale del capitolo 1 di [
T1] in modo da confrontare le prestazioni dell'algoritmo scritto con quelle dell'algoritmo
verificaDupOrdList basato su ordinamento. Scrivere una breve relazione sui risultati sperimentali ottenuti, includendo grafici prestazionali. In particolare, graficare il rapporto di prestazioni di
verificaDupHashList e
verificaDupOrdList rispetto a quello di
verificaDupArray (si veda [
T1, capitolo 1]).
Come dati di test si suggerisce di utilizzare:
- sequenze di valori casuali (ad esempio, interi)
- sequenze di valori derivati da testi reali (ad esempio, sequenze di stringhe ottenute da romanzi classici come quelli citati alla pagina materiale didattico).
Per effettuare gli esperimenti utilizzare la metodologia illustrata in [
A1].
HW2
Progettare una struttura dati di dimensione O(n) che realizza il tipo di dato
ArrayDinamico in modo che ciascuna operazione set/get/expand/shrink abbia costo costante nel caso peggiore (e non soltanto ammortizzato come visto a lezione).
HW3
Scrivere una classe Java DynamicArray che implementa l'interfaccia
List∞ basata sulla tecnica del raddoppiamento/dimezzamento. Supportare almeno le seguenti operazioni:
- boolean add∞(E e)
- E get∞(int index)
- E set∞(int index, E element)
- int size∞()
Effettuare poi un confronto sperimentale delle prestazioni delle classi DynamicArray,
ArrayList∞ e
LinkedList∞ su una sequenza di 3n operazioni della forma <add, set, get, add, set, get, ...> dove ciascuna add aggiunge alla collezione un intero a caso, ciascuna get preleva una cella a caso tra 0 e size()-1, e ciascuna set modifica il contenuto di una cella a caso tra 0 e size()-1 con un intero casuale.
Scrivere un programma java per ciascuna classe in modo da poter effettuare test separati per ognuna di esse.
Misurare il tempo complessivo richiesto dai metodi di ciascuna classe su sequenze con n che varia ad esempio da 50000 a 100000 con passo 5000. Graficare poi il tempo di esecuzione medio per operazione (ottenuto dividendo il tempo totale per 3n).
HW4
Scrivere una classe Java DynamicArrayWC che implementa l'interfaccia
List∞ basata sulla struttura dati dell'homework 2. Supportare almeno le stesse operazioni previste dall'homework 3 per la classe DynamicArray. Estendere inoltre la sperimentazione dell'homework 3 includendo anche la classe DynamicArrayWC nei grafici.
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata.