Ricerca

Elaborazione di immagini digitali

Le immagini digitali sono uno strumento di analisi in molti settori scientifici, quali robotica, medicina, astronomia, studio di documenti, etc... In molti casi, a causa di degradazioni quali l'invecchiamento dei documenti o la sfocatura dei mezzi di acquisizione, non è possibile condurre un'adeguata analisi di tali immagini. Sono così necessarie tecniche di restauro per il miglioramento della qualità dell'immagine e l'eliminazione delle degradazioni.

I problemi inversi visivi risultano avere una natura mal posta, ovvero non sono garantite l'esistenza, l'unicità e la stabilità della soluzione. Per questo dobbiamo ricorrere a tecniche di regolarizzazione per imporre dei vincoli relativi alle conoscenze a priori che si hanno sulla soluzione.

Algebra Numerica Lineare

I problemi del calcolo in algebra lineare numerica riguardano la soluzione di sistemi lineari, il calcolo degli autovalori, la decomposizione ai valori singolari, il problema lineare dei minimi quadrati. Per ciascuno di questi problemi esistono algoritmi efficienti, tuttavia gli algoritmi classici danno risultati scadenti quando le dimensioni dei problemi diventano grandi ed occorre sviluppare nuovi algoritmi o varianti degli algoritmi classici che sfruttino la struttura, come per esempio i metodi basati su spazi di Krylov.

La ricerca contemporanea si occupa anche di problemi più specifici come: la soluzione di equazioni matriciali, il calcolo di funzioni di matrici, la soluzione di problemi non lineari agli autovalori.

Algoritmi genetici ed evolutivi

In natura esistono molto sistemi di ottimizzazione. L'evoluzione, ad esempio, è un sistema che garantisce la sopravvivenza degli individui che meglio si adattano all'ambiente in cui vivono. Altri sistemi complessi, come le colonie di formiche, sono un esempio di aggregazione di centinaia di migliaia di individui, il cui comportamento globale (ricerca del cibo, difesa...) è determinato da attività dei singoli individui che apparentemente non hanno nulla a che fare con il risultato globale.

La matematica computazionale crea modelli che simulano il comportamento di questi sistemi complessi per risolvere problemi computazionali. Questi modelli sono generalmente applicati alla ricerca di cammini minimi su grafi, ma anche al miglioramento di immagini digitali.

Complessità Computazionale

La matematica computazionale si occupa dell'analisi dei problemi computazionali. Un problema computazionale è costituito da un insieme di istanze alle quali occorre dare una risposta. Ad esempio il problema della colorazione di un grafo consiste nel determinare il numero minimo di colori affinché ogni vertice possa essere colorato con un colore differente. L'insieme delle istanze del problema è costituito da tutti i possibili grafi, ad ogni grafo la risposta associata è rappresentata dal minimo numero di colori.

Per classificare i vari problemi computazionali in base alle loro difficoltà occorre innanzi tutto fissare un modello di calcolo (ad esempio la macchina di Turing), attraverso il quale si definisce un algoritmo per la risoluzione del problema. Il costo di un algoritmo dipende dalle risorse necessarie per la sua computazione, quali ad esempio il tempo di computazione e lo spazio di memoria utilizzato.

Una volta stabilita la misura del costo computazionale, la complessità di un problema si definisce come il costo computazionale del migliore algoritmo che lo risolve. Dare una classificazione precisa ad ogni problema computazionale non è spesso possibile, pertanto ci si limita a dare dei limiti inferiori di complessità, cioè le risorse minime di computazione per la risoluzione del problema, o dei limiti superiori di complessità, spesso rappresentati dal costo del migliore algoritmo conosciuto per risolvere il problema. Questo ci permette di suddividere i problemi computazionali in classi.

Uno dei maggiori problemi aperti della matematica è la determinazione di una corretta gerarchia di tali classi, quale ad esempio il problema di P=NP.