- Complessità computazionale
- Teoria del Caos
-Automi Cellulari
- Bioinformatica
-
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).
