Algoritmi e ricorsività: macchine di Turing e algoritmi di Markov

In questa questa tesi vengono presentate alcune delle più importanti definizioni di funzione computabile mediante un algoritmo: una prima descrizione è quella data tramite le funzioni ricorsive, un secondo approccio è dato in termini di macchine di Turing, infine, vengono considerati gli algoritmi di Markov. Si dimostra che tutte queste definizioni sono equivalenti. Completa la tesi un breve cenno al lambda-K-calcolo.

Il gruppo delle trecce ed il teorema di Markov

Il lavoro concerne il gruppo delle trecce, il suo legame con i link e si concentra sui teoremi di Markov e Alexander.

Ottimizzazione del progetto della macchina di sollevamento cris light

Macchina di sollevamento per autoveicoli.

Catene di Markov nascoste e giochi stocastici.

In questa trattazione si introduce il concetto di catena di Markov nascosta: una coppia di processi stocastici (X,O), dove X è una catena di Markov non osservabile direttamente e O è il processo stocastico delle osservazioni, dipendente istante per istante solo dallo stato corrente della catena X. In prima istanza si illustrano i metodi per la soluzione di tre problemi classici, dato un modello di Markov nascosto e una sequenza di segnali osservati: valutare la probabilità della osservazione nel modello, trovare la sequenza nascosta di stati più probabile e aggiornare il modello per rendere più probabile l'osservazione. In secondo luogo si applica il modello ai giochi stocastici, nel caso in cui solo uno dei giocatori non è a conoscenza del gioco in ogni turno, ma può cercare di ottenere informazioni utili osservando le mosse dell'avversario informato. In particolare si cercano strategie basate sul concetto di catena di Markov nascoste e si analizzano i risultati ottenuti per valutare l'efficienza dell'approccio.

Catene di Markov reversibili e applicazioni al metodo Montecarlo basato sulle catene di Markov

Gli argomenti trattati in questa tesi sono le catene di Markov reversibili e alcune applicazioni al metodo Montecarlo basato sulle catene di Markov. Inizialmente vengono descritte alcune delle proprietà fondamentali delle catene di Markov e in particolare delle catene di Markov reversibili. In seguito viene descritto il metodo Montecarlo basato sulle catene di Markov, il quale attraverso la simulazione di catene di Markov cerca di stimare la distribuzione di una variabile casuale o di un vettore di variabili casuali con una certa distribuzione di probabilità. La parte finale è dedicata ad un esempio in cui utilizzando Matlab sono evidenziati alcuni aspetti studiati nel corso della tesi.

Caratterizzazione di sequenze di DNA mediante catene di Markov

Questa tesi si inserisce nell’ambito di studio dei modelli stocastici applicati alle sequenze di DNA. I random walk e le catene di Markov sono tra i processi aleatori che hanno trovato maggiore diffusione in ambito applicativo grazie alla loro capacità di cogliere le caratteristiche salienti di molti sistemi complessi, pur mantenendo semplice la descrizione di questi. Nello specifico, la trattazione si concentra sull’applicazione di questi nel contesto dell’analisi statistica delle sequenze genomiche. Il DNA può essere rappresentato in prima approssimazione da una sequenza di nucleotidi che risulta ben riprodotta dal modello a catena di Markov; ciò rappresenta il punto di partenza per andare a studiare le proprietà statistiche delle catene di DNA. Si approfondisce questo discorso andando ad analizzare uno studio che si ripropone di caratterizzare le sequenze di DNA tramite le distribuzioni delle distanze inter-dinucleotidiche. Se ne commentano i risultati, al fine di mostrare le potenzialità di questi modelli nel fare emergere caratteristiche rilevanti in altri ambiti, in questo caso quello biologico.

Algoritmi quantistici e classi di complessità

Solitamente il concetto di difficoltà è piuttosto soggettivo, ma per un matematico questa parola ha un significato diverso: anche con l’aiuto dei più potenti computer può essere impossibile trovare la soluzione di un sudoku, risolvere l’enigma del commesso viaggiatore o scomporre un numero nei suoi fattori primi; in questo senso le classi di complessità computazionale quantificano il concetto di difficoltà secondo le leggi dell’informatica classica. Una macchina quantistica, però, non segue le leggi classiche e costituisce un nuovo punto di vista in una frontiera della ricerca legata alla risoluzione dei celebri problemi del millennio: gli algoritmi quantistici implementano le proprietà straordinarie e misteriose della teoria dei quanti che, quando applicate lucidamente, danno luogo a risultati sorprendenti.

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.

Programmazione funzionale in spazio logaritmico: una libreria di funzione aritmetiche

In questa Tesi forniamo una libreria di funzioni aritmetiche che operano in spazio logaritmico rispetto all'input. Partiamo con un'analisi dei campi in cui è necessario o conveniente porre dei limiti, in termini di spazio utilizzato, alla computazione di un determinato software. Vista la larga diffusione del Web, si ha a che fare con collezioni di dati enormi e che magari risiedono su server remoti: c'è quindi la necessità di scrivere programmi che operino su questi dati, pur non potendo questi dati entrare tutti insieme nella memoria di lavoro del programma stesso. In seguito studiamo le nozioni teoriche di Complessità, in particolare quelle legate allo spazio di calcolo, utilizzando un modello alternativo di Macchina di Turing: la Offline Turing Machine. Presentiamo quindi un nuovo “modello” di programmazione: la computazione bidirezionale, che riteniamo essere un buon modo di strutturare la computazione limitata in spazio. Forniamo poi una “guida al programmatore” per un linguaggio di recente introduzione, IntML, che permettere la realizzazione di programmi logspace mantenendo però il tradizionale stile di programmazione funzionale. Infine, per mostrare come IntML permetta concretamente di scrivere programmi limitati in spazio, realizziamo una libreria di funzioni aritmetiche che operano in spazio logaritmico. In particolare, mostriamo funzioni per calcolare divisione intera e resto sui naturali, e funzioni per confrontare, sommare e moltiplicare numeri espressi come parole binarie.

Studio, verifica ed ottimizzazione di una macchina automatica opercolatrice

“Perdita di fase tra il gruppo riempimento polvere/cronoidi con LVDT ed il gruppo piattello durante la fase di arresto a causa della mancanza imprevista di corrente elettrica”. La perdita della fase tra differenti gruppi può avvenire per due ragioni: 1) a causa della cedevolezza di alcuni elementi della catena cinematica 2) per problemi relativi al software che comanda gli assi elettronici e che è responsabile del movimento coordinato dei vari gruppi. La prima ipotesi è molto improbabile in macchine come l’ADAPTA, dove non sono presenti elementi cinematici con elevata cedevolezza (come ad esempio delle cinghie) essendo i movimenti guidati da camme scanalate (che, contrariamente, sono molto rigide) e/o da camme elettriche (motori Brushless). Il secondo caso invece avviene ogni volta che viene a mancare la corrente elettrica in maniera accidentale (ad esempio a causa di un black-out). La mancanza di energia elettrica impedisce al computer a bordo macchina di continuare a monitorare e controllare il funzionamento dei vari assi elettronici della macchina, che sono comandati da motori brushless, che quindi continuano per inerzia il loro moto fino a fermarsi. Siccome ogni gruppo ha un’inerzia e una velocità/accelerazione istantanea diversa e variabile in funzione della posizione assunta all’interno del proprio ciclo nel momento della mancanza di corrente elettrica, i tempi di arresto risultano differenti, e questo causa la perdita di fase. I gruppi riempimento polvere/cronoidi e spingitori fondelli presentano interferenza meccanica col gruppo piattello per una certa durata del suo ciclo; in questa fase gli elementi entrano nelle boccole porta fondelli delle slitte mobili del piattello. È l’unico caso in tutta la macchina in cui parti meccaniche di gruppi diversi, vanno a “intersecare” i propri spostamenti. La progettazione di macchine che presentano interferenze di questo genere è generalmente sconsigliabile poiché si potrebbe presentare il rischio di uno scontro nel caso avvenga una perdita di fase tra i gruppi. Si sono cercate diverse soluzioni mirate a evitare un urto, derivato dall’interferenza meccanica, in caso di black-out oppure di ridurre il più possibile i danni che questa casualità può portare alla macchina. Il gruppo piattello è definito master rispetto a tutti gli altri gruppi; ha un’inerzia molto piccola e questo fa si che, in caso di black-out, il suo arresto avvenga praticamente istantaneamente, al contrario di ciò che avviene per tutti gli altri gruppi slave dotati di inerzia maggiore. Siccome l’arresto del piattello è istantaneo, il pericolo per tastatori e punzoni sollevatori di urto può avvenire solamente per compenetrazione: se gli elementi sono già all’interno della boccola, e restando fermo il piattello, l’inerzia del gruppo che fa proseguire il moto per alcuni istanti non farebbe altro che portarli fuori dalla boccola, non provocando alcun danno. Non vi è perciò il pericolo di “taglio” di questi elementi da parte del piattello. Perciò l’unica possibilità è che il black-out avvenga in un istante del ciclo dove gli elementi si stanno muovendo per entrare nelle boccole mentre anche il piattello è in rotazione.

Valutazione di un'attrezzatura per eseguire prove di torsione e/o flessione su una macchina assiale

Analisi di apparecchiature esistenti su macchina di prova assiale per l'esecuzione di prove differenti e sviluppo di una nuova attrezzatura per l'esecuzione di prove di torsione pura su macchina assiale.

Analisi e ottimizzazione delle prestazioni e dell'affidabilità di una macchina per il packaging di prodotti igienico-sanitari

L’oggetto di studio di questo lavoro, svolto presso l’azienda Vire Automation del gruppo Bucci Industries di Faenza, è una macchina per il packaging di prodotti igienico-sanitari, più precisamente pannolini baby. Dopo una prima indagine di mercato svolta con l’aiuto dei commerciali dell’azienda, si sono ipotizzate una serie di soluzioni tecniche per migliorare il funzionamento e le prestazioni della macchina. Tramite uno strumento detto Casa della qualità si sono evidenziate le soluzioni tecniche che risultano più apprezzate dal mercato e per questo posseggono una maggior priorità di realizzazione. Si è intervenuti su di un gruppo funzionale per lo spostamento orizzontale del prodotto che agisce superiormente rispetto al pianale di processo e sul trasporto pioli che invece agisce per ostacolo tra cilindri di acciaio ed i prodotti. In particolare per il primo si è realizzato un apposito studio delle grandezze cinematiche in gioco e, dopo una progettazione 3D, si sono stimate le coppie motrici richieste dal nuovo asse che è risultato vantaggioso rispetto al precedente. Per il secondo invece, vista l’esigenza di ottenere un gruppo rifasatore che permettesse alla macchina di funzionare correttamente nonostante i ritardi di arrivo dei prodotti dalla linea di produzione, si è realizzata una nuova gestione logica del gruppo per sopperire alla peggior condizione di funzionamento verificabile e si è riprogettato il gruppo per dotarlo delle nuove necessarie caratteristiche.

Effetti di intaglio in accoppiamenti albero-mozzo per interferenza

L’obiettivo dello studio è quello di determinare le cause della rottura a fatica in un accoppiamento albero–mozzo. Nella prima parte si cerca di costruire un modello FEM (attraverso Ansys Workbench 12.0) che simuli il comportamento del provino albero-mozzo sottoposto a una flessione alterna, come nella macchina di Moore. Con esso si cercherà di individuare le variabili del problema e quali potranno influenzare la σy_max e il Kt. Nella seconda parte si cercherà di stabilire se il fretting sia funzione dalle stesse variabili del Kt, se esiste una transizione tra i due fenomeni e la quantità di usura prodotta dal fretting. Infine si realizzeranno delle prove sperimentali per verificare le ipotesi dedotte dall'analisi FEM.

Analisi e confronto di sequenze di DNA mediante modelli Markoviani

Lo scopo di questa tesi è quello di evidenziare, attraverso varie analisi statistiche ed applicazione di modelli stocastici, il comportamento strutturale e funzionale dei dinucleotidi che compongono le sequenze di DNA di diversi organismi. Gli organismi che abbiamo scelto di prendere in considerazione sono l'uomo, il topo e l'Escherichia coli. Questa scelta non è stata casuale, ma oculata, al fine di mettere in risalto alcune differenze tra organismi eucarioti, quali l'uomo e il topo, ed organismi procarioti come il batterio E.coli. Nella prima parte del nostro studio, abbiamo computato le distanze che intercorrono tra occorrenze successive dello stesso dinucleotide lungo la sequenza, usando un metodo di non sovrapposizione, ed abbiamo iterato il calcolo per tutti i 16 dinucleotidi. Dopodiché ci siamo preoccupati di graficare le distribuzioni di distanza dei 16 dinucleotidi per l'E.Coli, il topo e l'uomo; gli istogrammi evidenziano un comportamento anomalo della distribuzione di CG che accomuna gli organismi eucarioti e di cui, invece, è esente l'organismo procariote esaminato. Questo dato statistico trova una spiegazione nei processi biologici di metilazione che possono innescarsi sul dinucleotide CG nelle sequenze eucariotiche. In seguito, per determinare quanto ciascuna delle 16 distribuzioni si discosti dalle altre abbiamo usato la divergenza di Jensen-Shannon. Per quantificare le differenze sostanziali tra le distribuzioni di CG dei 3 organismi considerati abbiamo deciso di verificare quale fosse il miglior fit per tali curve tra un esponenziale ed una power-law. L'esponenziale rappresenta un buon fit per le code delle distribuzioni di CG del topo e dell'uomo; ciò rivela la presenza di una lunghezza caratteristica per entrambi gli organismi. Nella seconda parte dello studio, i risultati vengono confrontati con modelli markoviani: sequenze random generate con catene di Markov di ordine zero (basate sulle frequenze relative dei nucleotidi) e uno (basate sulle probabilità di transizione tra diversi nucleotidi). Quest'ultima riproduce abbastanza fedelmente la sequenza biologica di partenza, per cui abbiamo scelto di utilizzare la catena Markov del 1° ordine per altre analisi statistiche riguardanti le distribuzioni dei nucleotidi, dinucleotidi, ed anche dei trinucleotidi con particolare interesse per quelli in cui è contenuto CG, in modo da verificare se l'anomalia si ripercuote anche in essi. Riteniamo pertanto che metodi basati su questo approccio potrebbero essere sfruttati per confermare le peculiarità biologiche e per migliorare l'individuazione delle aree di interesse, come le isole CpG, ed eventualmente promotori e Lamina Associated Domains (LAD), nel genoma di diversi organismi.