Foto del docente

Ugo Dal Lago

Professore ordinario

Dipartimento di Informatica - Scienza e Ingegneria

Settore scientifico disciplinare: INF/01 INFORMATICA

Temi di ricerca

Parole chiave: Semantica Differenziale dei Programmi Computazione Quantistica Crittografia Analisi Statica dei Programmi

I principali interessi di ricerca di Ugo Dal Lago riguardano l'informatica teorica e, in particolare, le possibili relazioni tra la teoria della complessità computazionale, la teoria della probabilità, la teoria dei linguaggi di programmazione e la logica matematica.

COMPUTAZIONE PROBABILISTICA ALL'ORDINE SUPERIORE

Nonostante l'algoritmo sia tradizionalmente considerato un processo deterministico, l'accesso ad una sorgente di casualità è stata presa in considerazione fin dagli albori dell'informatica teorica. Permettere agli algoritmi di evolvere in modo casuale risulta indispensabile in crittografia, mentre i modelli probabilistici sono alla base del machine learning. Tutta una serie di questioni rimangono tutt'ora aperte, nonostante la letteratura sull'argomento sia sconfinata. In particolare, l'impatto dell'adozione di un modello di calcolo probabilistico sulla teoria dei linguaggi di programmazione risulta largamente inesplorata, soprattutto in presenza di programmi all'ordine superiore.

SEMANTICA DIFFERENZIALE DEI LINGUAGGI DI PROGRAMMAZONE

La semantica dei linguaggi di programmazione è storicamente studiata tramite equivalenze e preordini su programmi, i quali non danno nessuna informazione di tipo quantitativo riguardo coppie di programmi tra loro non confrontabili attraverso tali relazioni. L'uso di metriche e pseudometriche, purché promettente, non permette di dare conto di differenze tra programmi che dipendano in modo determinante dal contesto. Si sta quindi cercando, attraverso nozioni di distanza tra programmi che non siano meramente numeriche, di riuscire a giustificare certe trasformazioni tra programmi.

COMPLESSITA' COMPUTAZIONALE IMPLICITA

La complessità computazionale implicita mira a dare caratterizzazioni di classi di complessità basate sulla logica matematica. A partire dalla logica lineare (introdotta da Girard quasi vent'anni fa) si possono definire sistemi deduttivi cui corrispondono classi di complessità, non appena l'eliminazione del taglio è interpretata come meccanismo di computazione. In particolare, caratterizzazioni del tempo polinomiale (deterministico o nondeterministico) e del tempo elementare sono state introdotte da Girard, Lafont e altri ricercatori. Tali proposte risultano interessanti sia dal punto di vista della complessità computazionale, sia nel senso dei linguaggi di programmazione, visto che i sistemi proposti corrispondono (nel senso della corrispondenza di Curry-Howard) a linguaggi paradigmatici di programmazione.

 

Ultimi avvisi

Al momento non sono presenti avvisi.