Il problema della primalità in complessità computazionale

Questa tesi vuole fornire un'introduzione alla complessità computazionale e allo studio dei numeri primi riferito a questa materia. Si tratterà della Macchina di Turing e della sua importanza per calcolabilità e complessità, introducendo le classi P ed NP. Queste saranno approfondite studiando prima la classe di problemi NP-completi e successivamente fornendo alcuni esempi importanti. Nella parte finale ci si occuperà esplicitamente del problema dei numeri primi e si guarderà da vicino l'algoritmo AKS, dimostrandone la correttezza.

Isomorfismo tra alberi: algoritmi e complessità computazionale

La trattazione è volta all'esposizione dell'algoritmo di Lindell per determinare in logspazio se due alberi sono isomorfi. Un'ampia parte introduttiva richiama i prerequisiti teorici necessari alla comprensione della parte di esposizione dell'algoritmo.

Macchine di Schönhage e Complessità Computazionale implicita

Partendo dallo studio del modello computazionale introdotto da Schönhage, la presente tesi si propone di fornire una simulazione delle Evolving Graph Structures di Leivant e Marion che ne conservi le proprietà in termini di complessità computazionale.

Il test di primalità aks

La tesi presenta l'algoritmo AKS, deterministico e polinomiale, scoperto dai matematici Agrawal, Kayal e Saxena nel 2002. Esso si basa su una generalizzazione del Piccolo Teorema di Fermat all'anello dei polinomi a coefficienti in Zp.

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.

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.

Geophotohunt: Studio di algoritmi di confronto di immagini per realizzare una caccia al tesoro fotografica

Questo studio si propone di realizzare un’applicazione per dispositivi Android che permetta, per mezzo di un gioco di ruolo strutturato come caccia al tesoro, di visitare in prima persona città d’arte e luoghi turistici. Gli utenti finali, grazie alle funzionalità dell’app stessa, potranno giocare, creare e condividere cacce al tesoro basate sulla ricerca di edifici, monumenti, luoghi di rilevanza artistico-storica o turistica; in particolare al fine di completare ciascuna tappa di una caccia al tesoro il giocatore dovrà scattare una fotografia al monumento o edificio descritto nell’obiettivo della caccia stessa. Il software grazie ai dati rilevati tramite GPS e giroscopio (qualora il dispositivo ne sia dotato) e per mezzo di un algoritmo di instance recognition sarà in grado di affermare se la foto scattata rappresenta la risposta corretta al quesito della tappa. L’applicazione GeoPhotoHunt rappresenta non solo uno strumento ludico per la visita di città turistiche o più in generale luoghi di interesse, lo studio propone, infatti come suo contributo originale, l’implementazione su piattaforma mobile di un Content Based Image Retrieval System (CBIR) del tutto indipendente da un supporto server. Nello specifico il server dell’applicazione non sarà altro che uno strumento di appoggio con il quale i membri della “community” di GeoPhotoHunt potranno pubblicare le cacce al tesoro da loro create e condividere i punteggi che hanno totalizzato partecipando a una caccia al tesoro. In questo modo quando un utente ha scaricato sul proprio smartphone i dati di una caccia al tesoro potrà iniziare l’avventura anche in assenza di una connessione internet. L’intero studio è stato suddiviso in più fasi, ognuna di queste corrisponde ad una specifica sezione dell’elaborato che segue. In primo luogo si sono effettuate delle ricerche, soprattutto nel web, con lo scopo di individuare altre applicazioni che implementano l’idea della caccia al tesoro su piattaforma mobile o applicazioni che implementassero algoritmi di instance recognition direttamente su smartphone. In secondo luogo si è ricercato in letteratura quali fossero gli algoritmi di riconoscimento di immagini più largamente diffusi e studiati in modo da avere una panoramica dei metodi da testare per poi fare la scelta dell’algoritmo più adatto al caso di studio. Quindi si è proceduto con lo sviluppo dell’applicazione GeoPhotoHunt stessa, sia per quanto riguarda l’app front-end per dispositivi Android sia la parte back-end server. Infine si è passati ad una fase di test di algoritmi di riconoscimento di immagini in modo di avere una sufficiente quantità di dati sperimentali da permettere di effettuare una scelta dell’algoritmo più adatto al caso di studio. Al termine della fase di testing si è deciso di implementare su Android un algoritmo basato sulla distanza tra istogrammi di colore costruiti sulla scala cromatica HSV, questo metodo pur non essendo robusto in presenza di variazioni di luminosità e contrasto, rappresenta un buon compromesso tra prestazioni, complessità computazionale in modo da rendere la user experience quanto più coinvolgente.

Parallelizzazione e rinormalizzazione numerica

I processori multi core stanno cambiando lo sviluppo dei software in tutti i settori dell'informatica poiché offrono prestazioni più elevate con un consumo energetico più basso. Abbiamo quindi la possibilità di una computazione realmente parallela, distribuita tra i diversi core del processore. Uno standard per la programmazione multithreading è sicuramente OpenMP, il quale si propone di fornire direttive semplici e chiare per lo sviluppo di programmi su sistemi a memoria condivisa, fornendo un controllo completo sulla parallelizzazione. Nella fisica moderna spesso vengono utilizzate simulazioni al computer di sistemi con alti livelli di complessità computazionale. Si ottimizzerà un software che utilizza l'algoritmo DMRG (Density Matrix Renormalization Group), un algoritmo che consente di studiare reticoli lineari di sistemi a molti corpi, al fine di renderlo più veloce nei calcoli cercando di sfruttare al meglio i core del processore. Per fare ciò verrà utilizzata l'API OpenMP, che ci permetterà in modo poco invasivo di parallelizzare l'algoritmo rendendo così più veloce l'esecuzione su architetture multi core.

Tecniche automatiche di mapping e localizzazione in ambienti indoor

Il mapping di grandezze fisiche risulta estremamente importante, essendo in grado di fornire un adeguato supporto per la localizzazione e il monitoraggio di parametri ambientali sensibili. Nel caso indoor, in assenza di un sistema di localizzazione di riferimento analogo al GPS per il caso outdoor, sfruttando appieno le potenzialità della sensoristica a bordo degli smartphone, si è fatto progressivamente strada il mapping di grandezze fisiche quali, ad esempio, il segnale Wi-Fi e il campo magnetico terrestre. In questo caso il mapping, senza richiedere alcuna infrastruttura e coadiuvato dall'utilizzo di dispositivi portatili largamente diffusi ad uso quotidiano, rappresenta una soluzione relativamente recente ridefinibile come Mobile Crowd Sensing. Il MCS rappresenta un nuovo paradigma di servizio, volto a sfruttare l'interconnettività tra dispositivi portatili per effettuare misurazioni di caratteristiche ambientali in maniera automatizzata, aggregandole in un sistema cloud usufruibile ad una vasta comunità. Tuttavia , il considerevole flusso di dati generato, la variabilità temporale delle grandezze di interesse e il rumore insito nelle misurazioni costituiscono problematiche fondamentali per l'utilizzo e la gestione delle misurazioni effettuate. Per tali motivi l'attività di tesi ha previsto i seguenti obiettivi: (i) fornire una panoramica delle principali tecniche e tecnologie di localizzazione volta a motivare l'importanza del mapping di grandezze fisiche ambientali; (ii) individuazione di grandezze fisiche appetibili per la creazione di mappe affidabili e realizzabili nei contesti applicativi più disparati, sfruttando risorse già presenti nell'ambiente; (iii) sviluppo di un algoritmo statistico in grado di fornire una stima accurata dell'andamento spaziale della grandezza di interesse attraverso un numero limitato di misurazioni, mantenendo la compatibilità con processi MCS e una bassa complessità computazionale. L’algoritmo sviluppato è stato validato attraverso simulazioni e misurazioni svolte in ambienti reali. In particolare, prove sperimentali sono state effettuate nell’arena Vicon nei laboratori DEI dell’Università di Bologna, sede Cesena, concepita dal gruppo di ricerca Casy.

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.

Sistemi di sicurezza urbana

Il problema della sicurezza/insicurezza delle città, dalle grandi metropoli sino ai più piccoli centri urbani, ha sollecitato negli ultimi anni un’attenzione crescente da parte degli studiosi, degli analisti, degli organi di informazione, delle singole comunità. La delinquenza metropolitana viene oggi diffusamente considerata «un aspetto usuale della società moderna»: «un fatto – o meglio un insieme di fatti – che non richiede nessuna speciale motivazione o predisposizione, nessuna patologia o anormalità, e che è iscritto nella routine della vita economica e sociale». Svincolata dagli schemi positivistici, la dottrina criminologica ha maturato una nuova «cultura del controllo sociale» che ha messo in risalto, rispetto ad ogni visione enfatizzante del reo, l’esigenza di pianificare adeguate politiche e pratiche di prevenzione della devianza urbana attraverso «tutto l’insieme di istituzioni sociali, di strategie e di sanzioni, che mirano a ottenere la conformità di comportamento nella sfera normativa penalmente tutelata». Tale obiettivo viene generalmente perseguito dagli organismi istituzionali, locali e centrali, con diverse modalità annoverabili nel quadro degli interventi di: prevenzione sociale in cui si includono iniziative volte ad arginare la valenza dei fattori criminogeni, incidendo sulle circostanze sociali ed economiche che determinano l’insorgenza e la proliferazione delle condotte delittuose negli ambienti urbani; prevenzione giovanile con cui si tende a migliorare le capacità cognitive e relazionali del minore, in maniera tale da controllare un suo eventuale comportamento aggressivo, e ad insegnare a genitori e docenti come gestire, senza traumi ed ulteriori motivi di tensione, eventuali situazioni di crisi e di conflittualità interpersonale ed interfamiliare che coinvolgano adolescenti; prevenzione situazionale con cui si mira a disincentivare la propensione al delitto, aumentando le difficoltà pratiche ed il rischio di essere scoperti e sanzionati che – ovviamente – viene ponderato dal reo. Nella loro quotidianità, le “politiche di controllo sociale” si sono tuttavia espresse in diversi contesti – ed anche nel nostro Paese - in maniera a tratti assai discutibile e, comunque, con risultati non sempre apprezzabili quando non - addirittura – controproducenti. La violenta repressione dei soggetti ritenuti “devianti” (zero tolerance policy), l’ulteriore ghettizzazione di individui di per sé già emarginati dal contesto sociale, l’edificazione di interi quartieri fortificati, chiusi anche simbolicamente dal resto della comunità urbana, si sono rivelate, più che misure efficaci nel contrasto alla criminalità, come dei «cortocircuiti semplificatori in rapporto alla complessità dell’insieme dei problemi posti dall’insicurezza». L’apologia della paura è venuta così a riflettersi, anche fisicamente, nelle forme architettoniche delle nuove città fortificate ed ipersorvegliate; in quelle gated-communities in cui l’individuo non esita a sacrificare una componente essenziale della propria libertà, della propria privacy, delle proprie possibilità di contatto diretto con l’altro da sé, sull’altare di un sistema di controllo che malcela, a sua volta, implacabili contraddizioni. Nei pressanti interrogativi circa la percezione, la diffusione e la padronanza del rischio nella società contemporanea - glocale, postmoderna, tardomoderna, surmoderna o della “seconda modernità”, a seconda del punto di vista al quale si aderisce – va colto l’eco delle diverse concezioni della sicurezza urbana, intesa sia in senso oggettivo, quale «situazione che, in modo obiettivo e verificabile, non comporta l’esposizione a fattori di rischio», che in senso soggettivo, quale «risultante psicologica di un complesso insieme di fattori, tra cui anche indicatori oggettivi di sicurezza ma soprattutto modelli culturali, stili di vita, caratteristiche di personalità, pregiudizi, e così via». Le amministrazioni locali sono direttamente chiamate a garantire questo bisogno primario di sicurezza che promana dagli individui, assumendo un ruolo di primo piano nell’adozione di innovative politiche per la sicurezza urbana che siano fra loro complementari, funzionalmente differenziate, integrali (in quanto parte della politica di protezione integrale di tutti i diritti), integrate (perché rivolte a soggetti e responsabilità diverse), sussidiarie (perché non valgono a sostituire i meccanismi spontanei di prevenzione e controllo della devianza che si sviluppano nella società), partecipative e multidimensionali (perché attuate con il concorso di organismi comunali, regionali, provinciali, nazionali e sovranazionali). Questa nuova assunzione di responsabilità da parte delle Amministrazioni di prossimità contribuisce a sancire il passaggio epocale «da una tradizionale attività di governo a una di governance» che deriva «da un’azione integrata di una molteplicità di soggetti e si esercita tanto secondo procedure precostituite, quanto per una libera scelta di dar vita a una coalizione che vada a vantaggio di ciascuno degli attori e della società urbana nel suo complesso». All’analisi dei diversi sistemi di governance della sicurezza urbana che hanno trovato applicazione e sperimentazione in Italia, negli ultimi anni, e in particolare negli ambienti territoriali e comunitari di Roma e del Lazio che appaiono, per molti versi, esemplificativi della complessa realtà metropolitana del nostro tempo, è dedicata questa ricerca. Risulterà immediatamente chiaro come il paradigma teorico entro il quale si dipana il percorso di questo studio sia riconducibile agli orientamenti della psicologia topologica di Kurt Lewin, introdotti nella letteratura sociocriminologica dall’opera di Augusto Balloni. Il provvidenziale crollo di antichi steccati di divisione, l’avvento di internet e, quindi, la deflagrante estensione delle frontiere degli «ambienti psicologici» in cui è destinata a svilupparsi, nel bene ma anche nel male, la personalità umana non hanno scalfito, a nostro sommesso avviso, l’attualità e la validità della «teoria del campo» lewiniana per cui il comportamento degli individui (C) appare anche a noi, oggi, condizionato dalla stretta interrelazione che sussiste fra le proprie connotazioni soggettive (P) e il proprio ambiente di riferimento (A), all’interno di un particolare «spazio di vita». Su queste basi, il nostro itinerario concettuale prende avvio dall’analisi dell’ambiente urbano, quale componente essenziale del più ampio «ambiente psicologico» e quale cornice straordinariamente ricca di elementi di “con-formazione” dei comportamenti sociali, per poi soffermarsi sulla disamina delle pulsioni e dei sentimenti soggettivi che agitano le persone nei controversi spazi di vita del nostro tempo. Particolare attenzione viene inoltre riservata all’approfondimento, a tratti anche critico, della normativa vigente in materia di «sicurezza urbana», nella ferma convinzione che proprio nel diritto – ed in special modo nell’ordinamento penale – vada colto il riflesso e la misura del grado di civiltà ma anche delle tensioni e delle contraddizioni sociali che tormentano la nostra epoca. Notevoli spunti ed un contributo essenziale per l’elaborazione della parte di ricerca empirica sono derivati dall’intensa attività di analisi sociale espletata (in collaborazione con l’ANCI) nell’ambito dell’Osservatorio Tecnico Scientifico per la Sicurezza e la Legalità della Regione Lazio, un organismo di supporto della Presidenza della Giunta Regionale del Lazio al quale compete, ai sensi dell’art. 8 della legge regionale n. 15 del 2001, la funzione specifica di provvedere al monitoraggio costante dei fenomeni criminali nel Lazio.

A proposito di Crittografia a chiave asimmetrica e numeri primi: tecniche note e proposta di un nuovo test di primalità euristico e deterministico

Con questa tesi verrà spiegata l'intrinseca connessione tra la matematica della teoria dei numeri e l'affidabilità e sicurezza dei crittosistemi asimmetrici moderni. I principali argomenti trattati saranno la crittografia a chiave pubblica ed il problema della verifica della primalità. Nei primi capitoli si capirà cosa vuol dire crittografia e qual è la differenza tra asimmetria e simmetria delle chiavi. Successivamente verrà fatta maggiore luce sugli utilizzi della crittografia asimmetrica, mostrando tecniche per: comunicare in modo confidenziale, scambiare in modo sicuro chiavi private su un canale insicuro, firmare messaggi, certificare identità e chiavi pubbliche. La tesi proseguirà con la spiegazione di quale sia la natura dei problemi alla base della sicurezza dei crittosistemi asimmetrici oggigiorno più diffusi, illustrando brevemente le novità introdotte dall'avvento dei calcolatori quantistici e dimostrando l'importanza che riveste in questo contesto il problema della verifica della primalità. Per concludere verrà fatta una panoramica di quali sono i test di primalità più efficienti ed efficaci allo stato dell'arte, presentando una nuova tecnica per migliorare l'affidabilità del test di Fermat mediante un nuovo algoritmo deterministico per fattorizzare gli pseudoprimi di Carmichael, euristicamente in tempo O~( log^3{n}), poi modificato sfruttando alcune proprietà del test di Miller per ottenere un nuovo test di primalità deterministico ed euristico con complessità O~( log^2{n} ) e la cui probabilità di errore tende a 0 con n che tende ad infinito.

Imparare il pensiero computazionale, imparare a programmare

Nell'ultimo decennio il trend topic nell'ambito dell'insegnamento dell'informatica è il pensiero computazionale. Concetto già presente, è stato risaltato nel 2006 da Jeannette Wing, che ha mostrato come l'informatica abbia portato alla scienza non solo strumenti (computer e linguaggi di programmazione) ma anche innovazioni nel modo di pensare (es. algoritmo shotgun per sequenziamento del DNA umano). Il pensiero computazionale è il processo mentale coinvolto nel formulare problemi e loro soluzioni, rappresentate in una forma che sia effettivamente eseguibile da un agente che processa informazioni. Si tratta di “pensare come un informatico” quando si affronta un problema. Dopo aver passato in rassegna la letteratura sul pensiero computazionale, viene proposta una definizione del concetto. Si prende atto che la ricerca in questi anni sia rimasta molto legata ai linguaggi di programmazione, concetto centrale dell’Informatica. Vengono allora proposte due strade. La prima strada consiste nella riesumazione di tutta una serie di studi di Psicologia della Programmazione, in particolare: studi sulle misconcezioni, che si occupano di individuare i concetti che sono compresi male dai programmatori novizi, e studi sul commonsense computing, che cercano di capire come persone che non hanno mai ricevuto nozioni di programmazione - o più in generale di informatica – esprimano (in linguaggio naturale) concetti e processi computazionali. A partire da queste scoperte, si forniscono una serie di consigli per insegnare al meglio la programmazione (con i linguaggi attuali, con nuovi linguaggi appositamente progettati, con l'aiuto di strumenti ed ambienti ad-hoc) al più ampio pubblico possibile. La seconda strada invece porta più lontano: riconoscere il pensiero computazionale come quarta abilità di base oltre a leggere, scrivere e calcolare, dandogli dunque grande importanza nell’istruzione. Si vuole renderlo “autonomo” rispetto alla programmazione, fornendo consigli su come insegnarlo senza - ma anche con - l'ausilio di un formalismo.

Implementazione e benchmarking dell'algoritmo QDANet PRO per l'analisi di big data genomici

Dato il recente avvento delle tecnologie NGS, in grado di sequenziare interi genomi umani in tempi e costi ridotti, la capacità di estrarre informazioni dai dati ha un ruolo fondamentale per lo sviluppo della ricerca. Attualmente i problemi computazionali connessi a tali analisi rientrano nel topic dei Big Data, con databases contenenti svariati tipi di dati sperimentali di dimensione sempre più ampia. Questo lavoro di tesi si occupa dell'implementazione e del benchmarking dell'algoritmo QDANet PRO, sviluppato dal gruppo di Biofisica dell'Università di Bologna: il metodo consente l'elaborazione di dati ad alta dimensionalità per l'estrazione di una Signature a bassa dimensionalità di features con un'elevata performance di classificazione, mediante una pipeline d'analisi che comprende algoritmi di dimensionality reduction. Il metodo è generalizzabile anche all'analisi di dati non biologici, ma caratterizzati comunque da un elevato volume e complessità, fattori tipici dei Big Data. L'algoritmo QDANet PRO, valutando la performance di tutte le possibili coppie di features, ne stima il potere discriminante utilizzando un Naive Bayes Quadratic Classifier per poi determinarne il ranking. Una volta selezionata una soglia di performance, viene costruito un network delle features, da cui vengono determinate le componenti connesse. Ogni sottografo viene analizzato separatamente e ridotto mediante metodi basati sulla teoria dei networks fino all'estrapolazione della Signature finale. Il metodo, già precedentemente testato su alcuni datasets disponibili al gruppo di ricerca con riscontri positivi, è stato messo a confronto con i risultati ottenuti su databases omici disponibili in letteratura, i quali costituiscono un riferimento nel settore, e con algoritmi già esistenti che svolgono simili compiti. Per la riduzione dei tempi computazionali l'algoritmo è stato implementato in linguaggio C++ su HPC, con la parallelizzazione mediante librerie OpenMP delle parti più critiche.