Professore Ordinario di Informatica.
Short Bio.
Luciano Margara is Professor of Computer Science at the University of Bologna, Italy. He received the Laurea degree in Scienze dell'Informazione (1991) and the Dottorato di Ricerca in Informatica (Ph.D. in Computer Science, 1995) from the University of Pisa. He Joined the University of Bologna in 1995 (Research Associate from 1995 to 2000 and Associate Professor from 2000 to 2005). He has been a visiting scientist at the International Computer Science Institute (Berkeley) and a visiting Professor at the Cornell University (Department of Computer Science). His research interests are in Discrete Time Dynamical Systems, Optical Networks, Computational Complexity, and recently in Bioinformatics. His Erdös number is 3.
Research Interests
Soluzioni approssimate per problemi NP-Hard.
L'attività di ricerca in questo settore ha avuto un duplice obiettivo: da un lato si è cercato di studiare proprietà generali delle soluzioni di minimo locale per alcuni problemi NP-Hard con opportune nozioni di intorno, dall'altro sono state ideate e sperimentate nuove tecniche euristiche per la determinazione di soluzioni approssimate per tali problemi.
Sistemi dinamici discreti e caos.
Partendo dalla teoria dei sistemi dinamici caotici sviluppata negli ultimi decenni in matematica ed in fisica sono state affrontate le seguenti tematiche. Definizione della nozione di caos per una classe particolare di sistemi dinamici: gli automi cellulari. Applicazione della teoria del caos sviluppata per sistemi continui al caso discreto e classificazione degli automi secondo le definizioni presenti in letteratura. Analisi di diverse proprietà topologiche e metriche. Relazioni tra caos e complessità computazionale.
Complessità di algoritmi sequenziali e paralleli.
L'attività di ricerca nell'ambito della complessità computazionale e della sintesi di algoritmi può riassumersi nei seguenti aspetti. Analisi delle prestazioni dell'algoritmo del minimo residuo per la risoluzione di sistemi lineari. Studio quantitativo del gap esistente tra rango della matrice associata ad un problema e la sua communication complexity. Studio della complessità in parallelo delle fattorizzazioni di matrici LU e QR.
Sintesi di algoritmi di Routing su reti ottiche.
L'attività di ricerca in quest'ambito può riassumersi nei seguenti aspetti. Studio del rapporto tra congestione (load) e numero minimo di "wavelength'' necessarie per instradare un dato insieme di messaggi su reti ottiche con topologia ad albero. Sintesi di algoritmi di instradamento per reti ottiche con più fibre ottiche per collegamento (link). Analisi della complessità computazionale dell'instradamento su reti ottiche di insiemi di messaggi fortemente strutturati (permutation routing)
Bioinformatica
Recentemente, Luciano Margara ha avviato una attività di ricerca in ambito bioinformatico. L'attività di ricerca in questione può riassumersi nei seguenti aspetti. Sintesi di algoritmi ed euristiche per la ricostruzione di strutture proteiche tridimensionali a partire dalla sequenza di aminoacidi che le compongono. Sintesi di algoritmi ed euristiche per il cosiddetto problema del Decoy Selection (selezione e riconoscimento di strutture proteiche native). Analisi della complessità computazionale di alcuni problemi fondamentali in bioinformatica. Attività svolta in collaborazione con: R. Casadio e P. Fariselli (BES - Dipartimento di Biologia Evoluzionistica Sperimentale, Università di Bologna).