Il teorema di Cook-Levin e i SAT-solver

In questa tesi è trattato il tema della soddisfacibilità booleana o proposizionale, detta anche SAT, ovvero il problema di determinare se una formula booleana è soddisfacibile o meno. Soddisfacibile significa che è possibile assegnare le variabili in modo che la formula assuma il valore di verità vero; viceversa si dice insoddisfacibile se tale assegnamento non esiste e se quindi la formula esprime una funzione identicamente falsa. A tal fine si introducono degli strumenti preliminari che permetteranno di affrontare più approfonditamente la questione, partendo dalla definizione basilare di macchina di Turing, affrontando poi le classi di complessità e la riduzione, la nozione di NP-completezza e si dimostra poi che SAT è un problema NP-completo. Infine è fornita una definizione generale di SAT-solver e si discutono due dei principali algoritmi utilizzati a tale scopo.

Crittoanalisi Logica di DES

La crittografia ha sempre rivestito un ruolo primario nella storia del genere umano, dagli albori ai giorni nostri, e il periodo in cui viviamo non fa certo eccezione. Al giorno d'oggi, molti dei gesti che vengono compiuti anche solo come abitudine (operazioni bancarie, apertura automatica dell'auto, accedere a Facebook, ecc.), celano al loro interno la costante presenza di sofisticati sistemi crittografici. Proprio a causa di questo fatto, è importante che gli algoritmi utilizzati siano in qualche modo certificati come ragionevolmente sicuri e che la ricerca in questo campo proceda costantemente, sia dal punto di vista dei possibili nuovi exploit per forzare gli algoritmi usati, sia introducendo nuovi e sempre più complessi sistemi di sicurezza. In questa tesi viene proposto una possibile implementazione di un particolare tipo di attacco crittoanalitico, introdotto nel 2000 da due ricercatori dell'Università "La Sapienza" di Roma, e conosciuto come "Crittoanalisi Logica". L'algoritmo su cui è incentrato il lavoro è il Data Encryption Standard (DES), ostico standard crittografico caduto in disuso nel 1999 a causa delle dimensioni ridotte della chiave, seppur tuttora sia algebricamente inviolato. Il testo è strutturato nel seguente modo: il primo capitolo è dedicato ad una breve descrizione di DES e della sua storia, introducendo i concetti fondamentali con cui si avrà a che fare per l'intera dissertazione Nel secondo capitolo viene introdotta la Crittoanalisi Logica e viene fornita una definizione della stessa, accennando ai concetti matematici necessari alla comprensione dei capitoli seguenti. Nel capitolo 3 viene presentato il primo dei due software sviluppati per rendere possibile l'attuazione di questo attacco crittoanalitico, una libreria per la rappresentazione e la manipolazione di formule logiche scritta in Java. Il quarto ed ultimo capitolo descrive il programma che, utilizzando la libreria descritta nel capitolo 3, elabora in maniera automatica un insieme di proposizioni logiche semanticamente equivalenti a DES, la cui verifica di soddisfacibilità, effettuata tramite appositi tools (SAT solvers) equivale ad effettuare un attacco di tipo known-plaintext su tale algoritmo.

Progettazione e realizzazione di una macchina automatica per l'applicazione del sigillo anti-effrazione in campo farmaceutico

Con il seguente elaborato si vuole evidenziare il percorso seguito per progettare e realizzare una macchina automatica adibita all’applicazione del sigillo di anti effrazione sulle diverse confezioni di farmaci presenti nel mercato farmaceutico. Obiettivo dunque del lavoro che viene presentato è quello di esplicitare e motivare le diverse scelte fatte in campo progettuale, grazie alle quali si è giunti alla realizzazione vera e propria della macchina in tutte le sue componenti e alla vendita di quest’ultima ad una casa farmaceutica del torinese. L’elaborato è così suddiviso: nella prima parte verrà descritta l’azienda demandante del progetto, la sua attività ed il suo campo di ricerca. Seguirà poi la descrizione dell’operazione per cui la macchina è stata concepita, i requisiti minimi di produttività che quest’ultima deve avere, e il campo di utilizzo. Nella seconda parte verranno presentati i vari gruppi che compongono la macchina, esplicitando la loro funzione, gli studi e le scelte fatte per la loro realizzazione, portando foto e disegni CAD dei componenti. Verranno poi descritti gli accorgimenti per la corretta installazione della macchina ed in fine verranno descritte le operazioni di collaudo effettuate sulla macchina, quali SAT (Site Acceptance Tests - Collaudo del sistema presso l’Utilizzatore) e FAT (Factory Acceptance Tests - Collaudo del sistema presso il costruttore)

Impianti di ripartizione di farmaci in asepsi e atmosfera controllata

Tesi in azienda che verte sugli impianti di ripartizione di farmaci in asepsi e atmosfera controllata. Sono stati analizzati: norme riguardanti progettazione e installazione di impianti farmaceutici; tecnologie di ripartizione (isolatori e RABS) con riferimento all'isolatore in azienda e all'impianto HVAC asservito; la linea di ripartizione in generale (washing machine - tunnel di depirogenazione - isolatore - coding station); test SAT di convalida per l'installazione di isolatore e impianto HVAC; sviluppo e convalida del ciclo di decontaminazione con VHP; conti di ottimizzazione dell'inertizzazione della camera di riempimento.

Analisi e studio computazionale di solver per problemi di routing di interesse industriale

Il Routing rappresenta uno dei problemi più studiati nell’ambito della Ricerca Operativa in quanto offre molteplici possibilità di ottimizzazione da cui possono derivare altrettanti vantaggi per le aziende che decidono di gestirlo in maniera strutturata. Uno dei principali ambiti di applicazione del routing è la pianificazione operativa del trasporto merci a clienti sparsi in un determinato territorio. Ci sono aziende che devono organizzare la loro Logistica distributiva ogni giorno. Ormai è diventato evidente che la realizzazione di questo processo mediante modalità “standard”, senza l’utilizzo di appositi strumenti di ottimizzazione, non solo porta alla perdita di occasioni importanti in termini di vantaggi raggiungibili, ma è anche molto più dispendiosa a livello di tempo richiesto. Molte aziende si stanno quindi affidando a soluzioni SW che si vadano ad integrare con i loro processi decisionali. Questi sistemi hanno alla base delle componenti algoritmiche in grado di trovare la migliore soluzione possibile per la tipologia specifica di Routing da affrontare. Per questi motivi, lo sviluppo di algoritmi in grado di risolvere questo problema rappresenta una parte consistente della letteratura scientifica in ambito di ottimizzazione. In questo elaborato si andranno a definire le principali caratteristiche di un problema di Routing in forma base e nelle sue varianti principali. Si descriveranno le caratteristiche dei problemi di Routing incontrati da Optit S.r.l, un’azienda che opera nel settore dello sviluppo di soluzioni SW di ottimizzazione. Nel fare ciò, si cercherà di trovare sovrapposizione con quanto descritto in letteratura. Infine, si descriveranno alcuni solver Open-Source per risolvere problemi di Routing e si mostreranno i risultati da essi ottenuti su alcuni casi di interesse industriale.