CURRICULUM VITAE

Nato a Barlassina nel 1946, Alberto Bertoni si è laureato cum laude in Fisica nel 1970. Dal 1981 è professore ordinario, prima presso l’Università della Calabria poi presso l’Università degli Studi di Milano.

Attività didattica

Ha insegnato i corsi universitari di Teoria e Applicazioni delle Macchine Calcolatrici, Algoritmi e Strutture Dati, Teoria dei Linguaggi, Elaborazione Numerica dei Segnali, Metodi per il trattamento dell’Informazione, Informatica Teorica, Algebra, Istituzioni di Matematiche presso i corsi di laurea in Scienze dell’Informazione, Informatica o Matematica. Ha tenuto corsi di Teoria della Complessità, Algoritmi e Combinatoria, Elaborazione dei Segnali, Ottimizzazione Combinatoria, Teoria dei Giochi per il Dottorato di Informatica, anche in Scuole Nazionali

E’ stato relatore di più di 200 tesi in Informatica, Matematica e Fisica, ed ha seguito più di 20 tesi di Dottorato in Informatica, Matematica e Ingegneria.

Attività organizzativa e promozionale

E’ uno dei fondatori del Capitolo Italiano dell'Associazione Europea di Informatica Teorica (EATCS), di cui è stato presidente per 6 anni. E’ stato rappresentante italiano presso il Consiglio EATCS. E' uno dei promotori della Società Italiana Reti Neuroniche (SIREN); attualmente è membro del Consiglio Scientifico di SIREN.

E' stato membro del Senato Accademico dell’Università di Milano, per la revisione dello statuto. E’ stato membro del Consiglio Scientifico dello IAMI (CNR). E’ attualmente membro di TC1 presso IFIP.

E’ stato Direttore della scuola di Dottorato in Informatica, Milano –Torino, per 4 anni. E’ stato presidente del Corso di Laurea in Informatica per 6 anni. E’ stato Direttore del Dipartimento di Scienze dell’Informazione, presso l’Università di Milano.

E’ stato membro del Comitato di Programma di numerose Conferenze internazionali (CAAP, STACS, AdPeNets, DLT, MFCS, SOFSEM, ….). Recentemente: 15th International Conference on Developments in Language Theory, Milan, 2011; International Computer Science Symposium, Nizhny Novgorod, 2012.

E’ membro dell’Editorial Board di Theoretical Informatics and Applications.

Attività di ricerca

L’attività di ricerca si svolge nell'ambito dell'Informatica Teorica, in particolare in complessità computazionale, linguaggi formali, macchine probabilistiche e quantistiche, apprendimento computazionale, aspetti teorici delle reti di neuroni e di modelli evolutivi. L’attività è documentata da più di 140 pubblicazioni in sede internazionale.

In particolare, in complessità ha risolto problemi aperti nell’area degli automi probabilistici (per esempio in [BeMaTo77a]), ha affrontato problematiche di simulazione tra modelli di calcolo (per esempio ha provato che la classe dei problemi risolubili su RAM aritmetiche con un numero polinomiale di operazioni è PSPACE [BeMaSa81]) e ha studiato la classificazione di problemi di conteggio e di “rango” (per esempio in [BeGo93]). Nell’area della concorrenza, ha proposto di studiare le problematiche sui linguaggi traccia di Mazurkiewicz nel contesto di linguaggi formali, utilizzando la teoria dei monoidi liberi parzialmente commutatici [BeBrMaSa81, BeMaSa89] . La problematica di “gap” richiede di stimare la minima quantità di risorse necessaria a riconoscere linguaggi non regolari: in [BeMePi94] vengono presi in considerazione modelli di Macchina di Turing aventi risorse come spazio, inversioni di testina e grado di non determinismo.

Alberto Bertoni ha offerto contributi anche nell’area dell’analisi sperimentale degli algoritmi [BeCaGr02], del calcolo evolutivo [BeDo93], delle reti neurali e apprendimento computazionale [BeCaPaMo92], della specifica dei dati astratti [BeMaMi83].

Alcuni risultati recenti sono discussi più in dettaglio.

Teoria e applicazioni della complessità computazionale e descrizionale

Nell’area dei linguaggi bidimensionali, è stata caratterizzata la classe dei linguaggi unari regolari in termini di linguaggi accettati da Macchine di Turing con limiti di spazio e di inversioni di testina [BeGoLo09]. Nell’area della compressione grammaticale, in [BeChRa08], sono esibite alcune trasformazioni tra parole che preservano la compressione ed altre che non preservano.

Nell’area degli algoritmi per il conteggio e la generazione casuale di parole, in [BeMaRa03] viene presentato un algoritmo lineare per la generazione casuale di parole, con un fissato numero di occorrenze di simboli, in linguaggi regolari. In [BeChGoLo06] viene analizzata la stima asintotica del numero di parole in linguaggi regolari con un fissato numero di occorrenze di simboli e ne sono mostrate applicazioni alle statistiche di pattern.

Progetto, analisi e applicazioni (es. in bioinformatica) di algoritmi evolutivi e calcolo quantistico.

La cosiddetta Quantum Computing esplora il vantaggio di usare modelli di calcolo quantistici rispetto a quelli classici o probabilistici. Questi modelli esibiscono profonde differenze: per esempio, risolvendo un problema aperto da Rabin in [BeTo74] si prova che nel caso di automi probabilistici è in indecidibile se un dato valore di taglio è isolato, mentre lo stesso problema è stato provato essere decidibile nel caso di automi quantistici. In [BeCa01a] vengono evidenziata analogie e differenze tra automi quantistici e probabilistici, mentre in [BeCa01b, BeMePa03c, BeMePa09] sono introdotti e discussi nuovi modelli di automi quantistici.

In [BeFoVa06, BeVa06, BeVa07] vengono proposti algoritmi di apprendimento computazionale supervisionato e non supervisionato basati su proiezioni randomizzate, con applicazioni alla bioinformatica. In [BeFrVa11] è presentato un algoritmo neurale per applicazioni bioinformatiche.

Bibliografia

[BeMaTo77a] A. Bertoni, G. Mauri, M. Torelli, Some Recursive Unsolvable Problems Relating to Isolated Cutpoints in Probabilistic Automata. ICALP 1977: 87-94

[BeMaSa81] A.Bertoni, G.Mauri, N.Sabadini, A characterization of the class of functions computable in polynamial time on Random Access Machines, 13th ACM Symp. On Theoy of Computation, pp.168-178, 1981.

[BeMaMi83]A.Bertoni, G.Mauri, P.A.Miglioli, On the power of model theory in specifying abstract data types and in capturing their recursiveness, Fundamenta Informaticae, Vol.2, pp.129-170, 1983.

[BeGo93] A.Bertoni, M.Goldwurm, On ranking 1-way finitely ambiguous NL languages and #P1-complete census functions, RAIRO Theo.Info. and Applications,Vol.27, n.2, pp.135-148, 1993.

[BeBrMaSa81] A.Bertoni, M.Brambilla, G.Mauri, N.Sabadini, An application of the theory of free partially commutative monoids: asymptotic density of trace languages, 10th MFCS, LNCS 118, pp.205-215, 1981.

[BeMaSa89] A.Bertoni, G:Mauri, N.Sabadini, Membership problems for regular and context-free languages, Information and Computation, 82, n.2, pp.135-150, 1989

[BeMePi94] A. Bertoni, C. Mereghetti, G. Pighizzini, An optimal lower bound for nonregular languages, Info.Pro.Lett., 50, pp.289-292, 1994

[BeCaPaMo92] A.Bertoni, P.Campadelli, A.Morpurgo, S.Panizza, Polynomial uniform convergence and polynomial sample learnability, 5th ACM COLT, pp.265-271, 1992.

[BeDo93] A.Bertoni, M.Dorigo, Implicit parallelism in genetic algorithms, Artificial Intelligence: an int. Jour., Vol.61, 2, pp.307-313, 1993.

[BeCaGr02] A. Bertoni, P. Campadelli, G. Grossi, A Neural Algorithm for the Maximum Clique Problem: Analysis, Experiments and Circuit Implementation, Algoritmica 33 (1), pp.71-88, 2002.

[BeGoLo09] A. Bertoni,, M. Goldwurm, and V. Lonati. The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases. Fundamenta Informaticae, Vol. 91(2), 2009.

[BeChRa11] Alberto Bertoni, Christian Choffrut, Roberto Radicioni: The Inclusion Problem of Context-Free Languages: Some Tractable Cases. Int. J. Found. Comput. Sci. 22(2): 289-299 (2011)

[BeChGoLo06] A. Bertoni, C.Choffrut, M.Goldwurm, V.Lonati Local limit properties for pattern statistics and rational models. THEORY OF COMPUTING SYSTEMS. vol. 39, pp. 209-235 ISSN: 1432-4350, 2006.

[BeCa01a] A. Bertoni and M. Carpentieri, Analogies and Differences between Quantum and Stochastic Automata, Theoretical Computer Science, vol. 262, pp. 69-81, 2001

[BeCa01b] A. Bertoni and M. Carpentieri, Regular Languages Accepted by Quantum Automata, Information and Computation. vol. 165, pp. 174-182, 2001

[BeMePa09] Alberto Bertoni, Carlo Mereghetti, Beatrice Palano: Trace monoids with idempotent generators and measure-only quantum automata. Natural Computing 9(2): 383-395 (2010)

[BeMePa03c] A. Bertoni, C. Mereghetti e B. Palano. Quantum Computing: 1-way quantum automata. In Developments in Language Theory, 7th International Conference, LNCS 2710, pp. 1--20, Springer, 2003.

[BeVa07] A.Bertoni, G.Valentini, Model order selection for biomolecular data clustering,

BMC Bioinformatics, vol.8, Suppl.3, 2007.

[BeVa06] A.Bertoni, G.Valentini, Randomized maps for assessing the reliability of patients clusters in DNA microarray data analyses, Artificial Intelligence in Medicine. vol. 37:2, pp. 85-109 ISSN: 0933-3657, 2006.

[ BeFoVa06] Bertoni A., R. Folgieri, G. Valentini, Bio-molecular cancer prediction with random subspace ensembles of Support Vector Machines, Neurocomputing 63C, 535-539, 2006

[BeFrVa11] Alberto Bertoni, Marco Frasca, Giorgio Valentini: COSNet: A Cost Sensitive Neural Network for Semi-supervised Learning in Graphs. ECML/PKDD (1) 2011: 219-234

Developments in Language Theory, Milan, 2011; International Computer Science Symposium, Nizhny Novgorod, 2012.

CURRICULUM VITAE

Alberto Bertoni was born in Barlassina, Italy, the 17:7:1946. He took the degree in Physics, cum laude, at the University of Milano, July 22, 1970. He was Assistant professor in Computer Science at the Department of Physics, University of Milan, from 1976 to 1980. Full professor since 1981, he though at the University of Cosenza and, since 1982, he has been at the Department of Computer Science , University of Milan.

Teaching activity

He tought the courses of Theory end Application of Computers, Algorithms and Data Structures, Formal Languages and Compilers, Algebra, Signal Processing, Neural Networks, Theoretical Computer Science, Digital Signal Processor, Theory of Languages to the graduate students in Computer Science and Mathematics, and courses of Theory of Complexity, Algorithms and Combinatorics, Signal Processing, Combinatorial Optimization, Game Theory to the PhD students in Computer Science.

He was advisor of more than 200 thesis of degree in Computer Science, Mathematics, Physics and more than 20 PhD thesis in Computer Science, Mathematics and Engineering.

Promotional and organizing activity

He was co-promoter of Italian Association of Theoretical Computer Science (ICh-EATCS) and first President of this association for 6 years. He was for 6 years the Italian member in the Council of the European Association of Theoretical Computer Science.

He contributed to the birth of the Italian Society for Neural Networks (SIREN); he is member of the Scientific Council of SIREN.

He was member of the Academic Senate for the revision of the Statute of the University of Milano. He was member of Scientific Committee of Institute IAMI (CNR). He is member of TC1 in IFIP.

He was the Director of the PhD school in Computer Science, Milano-Torino, for 4 years. He was President of the Faculty of Computer Science, University of Milano, for 6 years.

He was the Director of the Department of Information Sciences, University of Milano, for 6 years (2003-09).

He was member of the PC of several International Conferences (CAAP, STACS, AdPeNets, DLT, MFCS, SOFSEM, ….). Recently: 15th International Conference on Developments in Language Theory, Milan, 2011; International Computer Science Symposium, Nizhny Novgorod, 2012.

He is member of the Editorial Board of Theoretical Informatics and Applications.

Research Activity

The research activity is in the area of Theoretical Computer Science, mainly in computability and complexity, probabilistic and quantum machines, formal languages, computational learning, theoretical aspects in neural networks and genetic models. The research is documented by more than 120 international papers.

In particular, in complexity theory he solved open problems on probabilistic automata (see for instance [BeMaTo77a]), he studied problems of simulations among computational models (for instance he proved that the class of problems solvable by arithmetic RAM with a polynomial number of operations is PSPACE [BeMaSa81]) and the classification of counting and ranking problems (see for instance [BeGo93]). In the concurrency he proposed of studying the trace theory, in the context of formal languages, by means of the theory of free partially commutative monoids [BeBrMaSa81, BeMaSa89]. Problems on “gap” require to evaluate the minimum quantity of resources to recognize non regular languages: in [BeMePi94] some models of Turing Machines are considered and resources such as space, head inversion and non determinism degree are studied.

Alberto Bertoni contributed also in the area of experimental algorithms [BeCaGr02], evolutionary computation [BeDo93], neural networks and computational learning [BeCaPaMo92], abstract data specification [BeMaMi83].

Recent activity is described in more details.

Theory and Application of Computational and Descriptional Complexity

In the area of picture languages, the class of unary tiling recognizable picture languages is characterized by languages accepted by Turing machines with bound on space and head inversions [BeGoLo09]. Algorithmic applications of methods of grammatical compression are presented in[BeChRa11].

In the area of random generation and counting algorithms, in [BeMaRa03] is designed a linear algorithm for random generation of words in regular languages with fixed number of occurrences of the symbols. Asymptotic estimation of the number of words in regular languages with fixed number of occurrences of the symbols are given in [BeChGoLo06], with applications to pattern statistics.

Design, analysis and applications (i.e. bioinformatics) of algorithms in the area of neural networks, genetic model and quantum computing

Quantum computing explores the advantages of using quantum devices in the computation with respect to, for instance, the probabilistic models. In [BeCa01a,BeCa01b,BeMePa03c,BeMePa09] new models of quantum automata are introduced, discussed and compared with the probabilistic counterpart.

In [BeFoVa05, BeVa06,BeVa07] supervised and not supervised learning algorithms based on random projections with application to clustering stability are proposed. A neural algorithm is designed in [BeFrVa11], with applications in Bioinformatics.

References