Procedure di Programmazione Dinamica per Determinare le K Migliori Soluzioni del Knapsack Problem 0-1 e dello Shortest Path Problem

In questa tesi viene trattata la problematica di determinare le migliori K soluzioni per due problemi di ottimizzazione, il Knapsack Problem 0-1 e lo Shortest Path Problem. Tali soluzioni possono essere impiegate all'interno di metodi di column generation per la risoluzione di problemi reali, ad esempio Bin Packing Problems e problemi di scheduling di veicoli ed equipaggi. Sono stati implementati, per verificarne sperimentalmente le prestazioni, nuovi algoritmi di programmazione dinamica, sviluppati nell’ambito di un programma di ricerca. Inizialmente, per entrambi i problemi, è stato descritto un algoritmo che determinasse le migliori K soluzioni per ogni possibile sottoproblema; partendo da uno zaino con capacità nulla, nel caso del Knapsack Problem 0-1, e dalla determinazione di un cammino dal vertice sorgente in se stesso per lo Shortest Path Problem, l’algoritmo determina le migliori soluzioni di sottoproblemi via via sempre più grandi, utilizzando le soluzioni costruite per gli stati precedenti, fino a ottenere le migliori soluzioni del problema globale. Successivamente, è stato definito un algoritmo basato su un approccio di ricorsione backward; in questo caso si utilizza una funzione ricorsiva che, chiamata a partire dallo stato corrispondente al problema globale, viene richiamata solo sugli stati intermedi strettamente necessari, e per ognuno di essi non vengono determinate soluzioni superflue.

Crittografia e reticoli geometrici

Introduzione alla crittografia e presentazione delle primitive matematiche attualmente utilizzate. Presentazione dei reticoli geometrici, riduzione reticolare e algoritmo LLL. Descrizione dei critto-sistemi Ajtai-Dwork e NTRU. In appendice introduzione a complessità computazionale, problemi P e NP.

Sperimentazione di protocolli di routing ip su piattaforme raspberry pi.

Tesi mirata allo studio dei protocolli di routing IP utilizzati per l'inoltro dei pacchetti in una topologia non banale. Sono state utilizzate macchine Linux Raspberry Pi per il loro costo e ingombro per costruire la rete. In particolare, è stata implementata una rete caratterizzata da sette router divisi in tre aree distinte, ai quali sono state connesse sette LAN. Si è installato e utilizzato il software quagga per attivare il protocollo OSPF (Open Shortest Path First). Per limitare i dispositivi fisici si è utilizzato il software Mininet per virtualizzare switch e LAN. Infine, sono stati trattati elementi teorici del routing su Internet, applicati alla rete creata per verificarne il funzionamento.

Simulation of URLLC slicing with resource reconfiguration in 5G networks

This thesis seeks to analyse the performance of dynamic slice provisioning in a 5G metro network with the low latency and reliability guaranties. This elaborate highlight the comparison in terms of performance of two versions of a simulator developed in Python based on different models: the Exhaustive research model and Shortest Path First Fit (SPFF) model. It further presents the differences between the dedicated path protection and the shared path protection. This analysis is made through several simulations at different network conditions by varying networks resources and observing the network performances while comparing the 2 models mentioned above. A reconfiguration procedure was implemented on backup resources in the shortest path first fit in order to improve its performance with respect to the exhaustive research which is more optimised. Subsequently, several triggering events was implemented, for the reconfiguration. And a comparison is made between these different triggering events in terms blocking probability, bandwidth at link, capacity at each node, primary and backup bandwidth per slice and backup capacity per slice.

Studio e implementazione di algoritmi per il tracciamento ottimo di satellite LEO da stazioni di terra di tipo radioamatoriale

Questo elaborato di tesi ha l’obbiettivo di studiare le limitazioni delle stazioni di terra nel tracciamento di satelliti in orbita LEO, investigare possibili soluzioni ed implementare queste soluzioni all’interno della Ground Station AMGS di Forlì per verificarne l’efficacia. A questo scopo, dopo un’attenta revisione della letteratura sono stati identificati due promettenti algoritmi descritti nei paper: “Trajectory optimisation to minimise antenna pointing error” di P. S. Crawford , R. J. H. Brush e “An optimal antenna motion generation using shortest path planning” di Moon-Jin Jeon , Dong-Soo Kwon. Questi algoritmi sono stati implementi in Python 3, al fine di inglobarli all’interno del software di tracking al momento in uso nella GS di Forlì, ovvero AMGS Orbit Predictor. All’interno di questo elaborato sono anche riportati i risultati dei test conseguiti e una valutazione dettagliata di questi ultimi.