.: Progetti realizzati in occasione di esami universitari :.

• Algoritmi euristici: Tabu search per il problema del commesso viaggiatore (TSP) e Simulated annealing per il problema del taglio di costo massimo (Max Cut)
• Geometria computazionele: Topsy-Turvy Fractal Growth Diffusion Limited Aggregation
• Sistemi di elaborazione dell'informazione: Browser offline in c#
• Tecnoligie Web: Una semplice agenda online in tecnologia JSP
• Laboratorio di reti: Simulazione di un server per analizzarne le prestazioni con un modello stocastico
• Complementi di Algoritmi: Simulazione biomolecolare di una molecola di urea in acqua
• Progettazione e analisi di algoritmi: Il problema della foresta ricoprente minima radicata
• Matematica del continuo: Lo spazio dei polinomi ortogonali
• Elettronica 1: Simulazione di un circuito CMOS nel dominio del tempo
• Elettronica 2: Analisi di un circuito di amplificazione nel dominio della frequenza
• Matematica del discreto: I triangoli nella geometria del Taxi
• Quantum Computing: I quantum Random Walks
• Sistemi Informativi: Data Mining: applicazioni

Progetto di Algoritmi euristici: Tabu search per il problema del commesso viaggiatore (TSP) e Simulated annealing per il problema del taglio di costo massimo (Max Cut)

Nella relazione sono stati presi in considerazione due problemi: TSP (Travelling Salesman Problem) e Max Cut, e sono state proposte delle tecniche euristiche, per trovare una soluzione. Nel caso del TSP è stata implementata un'euristica costruttiva basata sui Savings (Euristi Savings di Clarke & Wright) e un algoritmo di Tabu Search, in due versioni, come euristica di ricerca locale.
La prima versione è dotata di una lista tabu a lunghezza fissa, allo scopo bloccare i lati recentemente coinvolti in uno scambio. Nella seconda versione del Tabu Search è stata implementata una memoria a breve termine, in grado di regolare la lunghezza della lista tabu sulla base della qualià delle soluzioni trovate nel breve periodo.
Dopo una campagna di test sono stati tarati i parametri al problema e quindi si è proceduto alla simulazione con 7 istanze tratte da TSPLIB http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html. La prima versione trova risultati con gap compresi fra 2-5% dai valori ottimi. La versione con Short Time Memory migliora il risultato di 5 istanze pur mentenedo invariati i tempi di calcolo.

Il secondo problema combinatorio è stato affrontato implementando la meta-euristica Simulated Annealing, inizializzata con una soluzione costruita in modocasuale.i
Anche in questo caso, è stato necessario determinare il valore dei parametri che caratterizzano il comportamento dell'algoritmo. Le campagne di test sono sate condotte su un set di istanze tratte da, facendo variare singolarmente i parametri che caretterizzano l'algoritmo: la temperatura iniziale del sistema, il fattore che determina la diminuzione della temperatura e il numero di iterazioni a temperatura costante. I risultati evidenziano che diminuendo e aumentando la qualità delle soluzioni aumenta a discapito del tempo computazionale; mentre la temperatura iniziale non influenza i risultati ottenuti.

Nell'ultima parte è stato condotto un test di tipo time-to-target, su un'istanza (G1), con l'utilizzo di TTTPlots, per misurare l robustezza dell'algoritmo. Dai risultati del test sono stati costruiti due grafici nei quali si mostra la distribuzione empirica del tempo necessario all'algoritmo, per raggiungere una soluzione avente un certo valore.
Dalle osservazioni si conclude che il Simulated Annealing è robusto rispetto alla soluzione di partenza, costruita in modo casuale.

Di seguito i grafici time-totarger effettuati con TTTPlots:

Authors:

Yari Melzani

[ Relazione algoritmi euristici ]
[ Codice sorgente TSP ] [ Codice sorgente Max Cut ]

Progetto di Geometria Computazionale: Topsy-Turvy Fractal Growth Diffusion Limited Aggregation

Il frattale realizzato in questo progetto sfrutta una variante della tecnica Diffusione Limited Aggregation (DLA).
Il DLA è stato proposto per la prima volta da Tom Witten and Len Sander nel 1981.
Il meccanismo di costruzione è estremamente semplice: si parte con un punto di seed centrale, si lancia un walker in un punto casuale distante e lo si lascia diffondere liberamente (con moto casuale).
Quando il walker tocca un punto di seed si arresta e diventa esso stesso parte dell'aggregato. Viene quindi lanciato un nuovo walker. Proseguendo in questo modo si ottiene un aggregato cristallino sempre più grande.
Il risultato dell'implementazione è un'applet Java eseguibile in un qualunque browser con il plugin abilitato.

Authors:

Yari Melzani

Dott. Andrea Bettinelli

[ Applet Java ][ Relazione ]

Progetti di Sistemi di elaborazione dell'informazione

In occasione dell'esame di Sistemi di elaborazione dell'informazioneè stata realizzata un'applicazione in C# .NET allo scopo di permettere la navigazione offline di un sito. Il browser offline permette infatti di ricostruire in locale la struttura di un sito internet per permetterne in un secondo tempo l'esplorazione senza rete. Per eseguire l'applicazione è necessario il framework Microsoft .NET 1.0 o superiore.

Authors:

Yari Melzani

Beniamino Ferrari

[ Codice sorgente applicazione ][ Firma digitale Codice sorgente]

Progetto di Tecnoligie Web

L'applicazione web presentata vorrebbe essere un semplicissimo esempio di "Agenda online".
La funzionalità principale è quella di permettere la consultazione e l'inserimento di impegni attraverso l'interfaccia web.
Il progetto è stato sviluppato utilizzando le tecnologie XML, XSL, XSLT, JSP, JSTL su piattaforma Tomcat.

Authors:

Yari Melzani

Michele Vetturi

[ Relazione ][ Codice sorgente applicazione ][ Firma digitale Codice sorgente ]

Progetto di Laboratorio di reti

La simulazione si prefigge lo scopo di modellare, il più realisticamente possibile, il funzionamento di una macchina utilizzata come server per l'erogazione di servizi di rete. Le richieste che pervengono alla machina possono essere di 3 nature diverse:
APACHE: gestisce il traffico web, diviso in pagine di tipo statico e pagine di tipo dinamico;
SENDMAIL: è incaricato di spedire la posta elettronica relativa a 100 utenti.
OTHER: si tratta di traffico di disturbo rispetto alle richieste di interesse.
Il sistema simula l'arrivo di richieste destinate ai servizi, in esecuzione sulla macchina.
L'obiettivo della simulazione è ricavare il comportamento del sistema, sottoposto ad un carico medio stimato.
Nella seconda parte della simulazione cercheremo di stabilire, per quale dimensione del carico sul server APACHE (web), il sistema non deve ricorrere allo swap della memoria su disco.

La simulazione è stata scritta in C per poter avere una granularità più fine e un maggiore controllo sul sistema da modellare (oltre che per riuscire a commettere un po' più di errori durante la stesura del codice).

Authors:

Yari Melzani

Andrea Bettinelli

[ Relazione ][ Codice sorgente ][ Firma digitale codice sorgente ]

Progetto di Complementi di Algoritmi

Analisi e costruzione di un cluster di molecole di acqua in soluzione con una molecola di urea.
Il presente progetto è stato realizzato per risolvere un problema al professore di fisica nell'ambito di una simulazione biomolecolare.

Codice disponibile in versione C standard versione '99 (Standard 2)

Authors:

Yari Melzani

Dott. Andrea Bettinelli

[ Codice sorgente prima parte ][ Firma digitale Codice prima parte ]
[ Codice sorgente seconda parte ][ Firma digitale Codice seconda parte ]

Progettazione e analisi di algoritmi

Il problema della foresta ricoprente minima radicata

Authors:

Yari Melzani

Dott. Andrea Bettinelli

[ Relazione ]

Relazione Matematica del continuo

Come relazione per l'esame di Matematica del continuo è stato scelto "Lo spazio dei polinomi ortogonali". Questa famiglia di polinomi sono molto utili, sia nel campo della matematica applicata, che della fisica. La principale funzione di questi polinomi, consiste nell'approssimare funzioni continue in un determinato intervallo. Nella relazione vengono trattate due famiglie particolari di polinomi ortogonali: i polinomi trigonometrici e i polinomi di Legendre. Inizialmente vengono presentati alcuni richiami di algebra vettoriale per poi illustrare nel dettaglio la costruzione di insiemi ortogonali, mediante il procedimento di Gram-Schmidt. La trattazione prosegue con il teorema di approssimazione per poi passare alla trattazione dei polinomi trigonometrici e di Legendre. Di quest'ultima famiglia ne viene mostrata la costruzione nel dettaglio. Per concludere, si mostra un esempio di approssimazione di una semplice funzione continua sull'intervallo [-1,1]; si è scelto in particolare di approssimare la funzione mediante un polinomio di terzo grado.

La relazione è disponibile in formato pdf

Authors:

Yari Melzani

Daniele Bonomi

[ Relazione Spazio dei polinomi ortogonali ]

Relazione di Elettronica 1

Le relazioni si riferiscono ad una simulazione di un circuito CMOS nel dominio del tempo. Il primo è un inverter CMOS e il secondo implementa una porta logica OR.

La relazione è disponibile in formato pdf

Authors:

Yari Melzani

[ Relazione Inverter CMOS ] [ Relazione Porta logica OR CMOS ]

Relazione di Elettronica 2

La presente relazione, svolta in occasione dell'esame di elettronica 2 rappresenta la simulazione di un semplice circuito elettronico.
In particolare si tratta di un amplificatore realizzato mediante un transistore a giunzione bipolare (BJT).
Nella relazione in formato pdf si presentano: lo schema circuitale, il modello per piccoli segnali, il calcolo della funzione di trasferimento nel dominio della frequenza e il diagramma di Bode della funzione di trasferimento.
Oltre ad una trattazione del modello ideale, si considerano gli elementi fisici che causano problemi nell'amplificazio, fornendo una spiegazione semplice ma chiara.
Nel secondo file compresso .rar ci sono i files del modello circuitale fatti con il simulatore P-Spice.

La relazione è disponibile in formato pdf, mentre la simulazione circuitale è in formato compresso .rar

Authors:

Yari Melzani

[ Relazione Elettronica 2 ][ Simulazione circuitale con PSpice ]

Progetto di Matematica del discreto

Ecco un bellissimo progetto fatto con il Dott. Brusati per l'esame di Matematica del discreto. Il problema che abbiamo risolto consiste in una costruzione geometrica nella geometria dei taxi. Se siete curiosi sulle leggi che governano questo tipo di geometria, avete a disposizione la relazione del progetto stesso, in formato pdf.
Il progetto considera la costruzione di triangoli equilateri appunto nella geometria del taxi. Nel dettaglio, vengono forniti due vertici del triangolo da costruire su di una griglia e il programma costruisce tutti i possibili triangoli equilateri, eliminando parte dei triangoli simmetrici.
Un punto fondamentale sul quale si è soffermata la nostra analisi è l'area massima e minima possibile, di un triangolo equilatero che ha i vertici disposti sul reticolo, in un determinato modo. Sono certo che anche voi sarete sorpresi nel vedere quanto possa essere complesso predire queste due grandezze. Per poter costruire tutti i possibili triangoli equlateri, dati due vertici iniziali, è stato progettato un algoritmo per induzione matematica avente complessità esponenziale nella lunghezza del perimentro del triangolo.
Se vediamo il problema di costruire un lato del triangolo come quello di un taxi che deve giungere da un punto della griglia ad un altro seguendo la trada più breve possibile attraverso le strade, il problema si riduce a considerare tutte le possibili strade di minima lunghezza che uniscono due punti sul reticolo. La costruzione dei lati successivi al primo considerano come partenza, tutte le possibili strade di arrivo alla tappa precedente.
Questo approccio suggerisce immediatamente l'esplosione del numero di strade che permetteranno di chiudere il percorso formato dai 3 vertici del triangolo.

Nella relazione, è spiegato come il problema delle strade comporti la costruzione di un albero binario. L'applicazione è stata implementata in Java: il mio compito, da bravo algoritmista è stato quello di realizzare il motore dell'applicazione, mentre, il compito del Dott. Brusati si è concretizzato nell'implementazione della parte grafica.
Il risultato lo potete giudicare voi stessi, scaricando il filegeota.jar e testandolo sul vostro calcolatore; si riciede ovviamente la presenza di una Java Virtual Machine (JVM) per far partire il programma.
Se utilizzate Microsoft Windows è sufficiente eseguire il file, oppure, in una console scrivere il comendo java -jar geota.jar.
E' disponibile, inoltre, un archivio compresso contenente l'albero completo dei sorgenti del programma. Per semplicità abbiamo utilizzato come IDE di programmazione il software liberoEclipse. Se volete modificare il nostro programma o semplicemente giocarci basterà semplicemente importarlo.

Il .jar è visto da Microsoft come eseguibile, la relazione è in formato pdf, mentre l'archivio con i sorgenti è in formato compresso tar.bz2

Authors:

Yari Melzani

Enrico Brusati

[ geota.jar ][ Relazione GeoTa ][ Archivio codice sorgente GeoTa ]

Progetto di Quantum Computing: Quantum Random Walks

Fra i corsi più spinti seguiti, Quantum Computing occupa sicuramente una delle prime posizioni. La fisica quantistica è estremamente affascinante ma nello stesso tempo misteriosa e proibitiva per i non addetti ai lavori. Il progetto che qui di seguito propongo ha visto la luce anche grazie al pesante impegno di Andrea Bettinelli. La parte progettuale dell'esame rappresenta l'analisi di un problema nell'ambito della fisica quantistica e la sua simulazione medianteMatlab. Mi è difficile spiegare con semplici parole cosa siano i Quantum Random Walks senza ricorrere all'aiuto del matematichese.
Possiamo considerare i Quantum Random Walks come delle particelle il cui movimento è governato da ampiezze di probabilità. Il loro movimento avviene su una retta numerata; le posizione che un Quantum Random Walk può assumere sono rappresentate da numeri interi. La simulazione che abbiamo condotto può essere sintetizzata in questi termini. Non enuncerò i postulati della meccanica quantistica ma cercherò di dare un'idea approssimativa di quello che accade alle particelle.
Supponiamo di avere una particella detta Walker in posizione 0 della retta; a questo punto mediante un opportuno operatore di shift, facciamo muovere il walker di una posizione. Dopo questo primo movimento, se vado a vedere dove è finita la particella, troverò che con una certa probabilità è finita a destra e con un'altra probabilità è finita a sinistra del punto di partenza.

Il sistema quantistico vuole che fino a che non osservo quale sia la nuova posizione assunta, è come se la particella fosse contemporaneamente in entrambe le posizioni (destra e sinistra della posizione 0). Si dice in generale che la probabilità di trovare il walker nella posizione x dopo t movimenti è data dal modulo quadro di una certo numero complesso, detto ampiezza di probabilità. Se non misuro la posizione della particella di volta in volta e faccio evolvere la posizione della particella lungo le "tacche" della retta ottengo una serie di fenomeni di interferenza che si possono osservare nella figura presentata e più in particolare nella relazione. In quest'ultima è spiegato nel dettaglio quali sono le regole che governano il sistema e vengono mostrati numerevoli grafici che mostrano come i fenomeni di interferenza, condizionino la possibilità di trovare la particella in una certa posizione della retta dopo un certo numero di passi. La simulazione, come detto in precedenza è stata realizzata in matlab per poter sfruttare le comodissime librerie di calcolo vettoriale e tensoriale.

La relazione è disponibile in formato pdf

Authors:

Yari Melzani

Andrea Bettinelli

[ Relazione Quantum Computing: Quantum random walks ]

Sistemi Informativi

Il data mining: applicazioni

Authors:

Yari Melzani

[ Presentazione ][ Codice sorgente Presentazione in Beamer (Latex)