Mercoledì 14 aprile 2021 - ore 17.30
Incontro con il prof. Eugenio Omodeo
A cura del prof. Andrea Sgarro
Uno dei sette problemi per il millennio proposti dal Clay Mathematics Institute nell'anno 2000 è noto con la sigla “P vs NP". Esso presenta una contiguità concettuale con il decimo dei 23 problemi che Hilbert proponeva, nell'anno 1900, come sfide per la matematica del XX secolo.
Per poter dare risposta al 10° problema di Hilbert occorreva esplicitare la nozione di algoritmo e dunque sviluppare una teoria della computabilità; da questa, con l'evolversi della tecnologia, si è diramato lo studio della complessità computazionale, che si domanda: “quanto tempo di calcolo e quanta memoria richiede la risoluzione di ciascun'istanza di un certo problema?"
Non di rado un algoritmo è atto alla risoluzione di un problema ma solo in linea di principio, in quanto esso richiede in qualche caso tempi di calcolo proibitivi; da ciò scaturisce la questione: “quali, fra i problemi algoritmicamente risolubili, sono davvero trattabili?"
C'è una pervasiva famiglia di problemi, detti NP-completi, dei quali ancor oggi non siamo in grado di dire se siano risolubili tramite algoritmi di complessità polinomiale. Sappiamo nondimeno che se uno di essi si rivelasse - in questa ben poco esigente accezione del termine - trattabile, tali allora risulterebbero anche tutti gli altri.
Questa comunicazione delineerà le nozioni centrali all'ambito della complessità computazionale, per poi approfondire il significato dell'NP-completezza. Esporrà alcuni problemi emblematici della famiglia NP, spiegherà in che senso ciascuno sia riconducibile agli altri. Esaminando uno dei più rappresentativi problemi di questa famiglia, quello di stabilire se un enunciato proposizionale sia soddisfacibile o meno, chiarirà infine perchè la sua risoluzione sembri esigere - allo stato odierno delle nostre conoscenze - un sia pur occasionale ricorso alla forza bruta.
Prof. Eugenio G. Omodeo – Nasce a Pisa e ha come campi di interesse: Automazione del ragionamento; Logica computazionale; Verifica automatica di dimostrazioni; Teoria computabile degli insiemi; Specifica di algoritmi e rapida prototipazione; Programmazione dichiarativa; Ambienti per la programmazione logica; Logica algebrica.
Dopo la laurea in Matematica conferitagli dall’Università di Padova (1975), Eugenio Omodeo conseguì i titoli di Master of Science (1979) e di Ph.D. (1984) in Computer Science presso la New York University, GSAS, sotto la supervisione di Martin Davis. Finché era all’NYU,
fruì di varie borse di studio del Consiglio Nazionale delle Ricerche italiano,di una research assistantship nel Dept. of Economics (1978/79, per conto di Andrew Schotter), e di una nel Computer Science Dept. (1979/80, per Jacob T. Schwartz).
Dal 1981 al 1989, Eugenio Omodeo fu dipendente di aziende—Tema ed Enidata—appartenenti all’ENI, il Gruppo nazionale idrocarburi dell’Italia. Prese parte (1981-1984) all’implementazione di un grande sistema computerizzato per la simulazione di reti di gasdotti e in seguito (1984- 1989) coordinò le attività R&D dell’Enidata nell’area di Advanced Information Processing. Il suo gruppo di lavoro, costituito da oltre 15 persone a Bologna,
prese parte in numerosi progetti finanziati dall’European Commission (CEC): Alpes (Esprit, P363 and P973), Epsilon (Esprit P530), SED (Esprit P1227); e in altre attività di ricerca sponsorizzate dall’ENI, fra le quali un progetto sulla programmazione dichiarativa con insiemi. Il fuoco di tutte queste attività era sulla programmazione dichiarativa e sue applicazioni in Intelligenza Artificiale; inoltre, esse riguardavano la rapida prototipazione.
In varie occasioni, Eugenio Omodeo è stato valutatore di progetti per conto della EU. Dal 2001 al 2004, è stato rappresentante dell’Italia per l’azione europea COST 274 (TARSKI).
Eugenio Omodeo divenne professore associato nel 1989 e intraprese la sua nuova attività presso l’Università di Udine; nel 1990 si trasferì all’Università “La Sapienza” di Roma.
Divenne professore (stra)ordinario nel 1994. Dopo un anno all’Università di Salerno, prestò servizio all’Università di L’Aquila dal 1995 al 2004, contribuendo alla creazione e all’avvio di un Dipartimento di Informatica presso quella sede.
Dall’1 Nov. 2004 sino al 31 Ott. 2020, è stato alle dipendenze dell’Università degli Studi di Trieste. È in pensione dall’1 Nov. 2020.
I suoi insegnamenti in corsi di laurea triennale per l’anno accademico 2019/2020 sono stati: un modulo sulla programmazione Java per studenti d’Ingegneria, un corso sulla Logica matematica per studenti iscritti a Matematica, due corsi introduttivi sull’Informatica per studenti di Geologia e di Tecnica della Riabilitazione Psichiatrica. I suoi insegnamenti in corsi di laurea triennale per il corrente a.a. 2020/2021 includono: lezioni su aspetti di base dell’Informatica rivolte a studenti in Tecnica della Riabilitazione Psichiatrica; un modulo di un corso intitolato “Planet Earth modeling in Matlab”, a Geologia.
È stato coordinatore del Collegio di Dottorato in Informatica ed Applicazioni all’Università di L’Aquila dal 2001 al 2004. È stato delegato del Rettore per i servizi IT all’Università di Trieste dal 2007 al 2009. Recentemente ha coordinato i lavori di una commissione per l’acquisizione di infrastrutture HW/SW funzionali al progetto ‘Dipartimento di eccellenza’ del DMG (“Dipartimento di Matematica e Geoscienze”), sua affiliazione presso l’Università di Trieste.
Videoregistrazione: https://www.facebook.com/502593113124623/videos/130326215679260
