Relatore: dott. Marco Carpentieri

giovedì 3 luglio 2008, ore 16:00, aula 39 del Dipartimento di Matematica

Sommario: I modelli tradizionali dell'Informatica Teorica risultano essere troppo generali se si intende rappresentare in modo "ragionevole" un processo di calcolo. Infatti, i vincoli imposti dalla disponibilità limitata di risorse di spazio e tempo impongono la necessità di definizione di un modello rigoroso, formale di rappresentazione (possibilmente) semplice da analizzare e da realizzare nelle applicazioni.
Tra le proposte recenti più interessanti vi sono gli approcci della Teoria del Calcolo Reversibile che consente di caratterizzare il calcolo sul gruppo simmetrico in termini di permutazioni di configurazioni e l'approccio dei Linguaggi Formali basato su grammatiche di modelli di categorie.
Gli Algoritmi Evoluzionistici propongono di rappresentare i processi di calcolo ispirandosi ad alcuni aspetti (qualitativi) dei sistemi biologici naturali.
Tale approccio consente di riproporre tematiche ben note dell'Informatica Teorica in un "framework" multidisciplinare con il pregio di evidenziare analogie e differenze tra modelli sempre meno semplificati di (approssimazioni di) sistemi complessi basati su popolazioni di individui ed i modelli tradizionali di calcolo.
Di recente, l'approccio evoluzionistico ha anche mostrato di poter contribuire a migliorare il disegno di tecniche di ottimizzazione combinatoria tradizionali per problemi difficili.
In questa presentazione, si introdurrà il problema di rappresentazione seguendo le linee guida della Teoria del Calcolo Reversibile e verranno descritti i principali risultati della Teoria degli Algoritmi Evoluzionistici a partire dal primo semplice modello di John Holland fino ad arrivare ad il più moderno approccio degli Algoritmi di Stima di Distribuzioni.