Informaticateorica:Glialbori

GiornatediInformaticaTeorica

dedicateallamemoriadiAldodeLuca

GiorgioAusielloRoma,10luglio2019

Duranteglianni60e70delloscorsosecoloabbiamoassistitoadunaevoluzionedelcampodell'informaticadatecnologialegataalcalcolatoreascienzadelcalcolo:-daunlatoabbiamovistounaevoluzioneinarrestabiledell'elettronicachehaportatoallosviluppodinuovegenerazionidimezzidicalcoloequindianuovearchitetture(daimainframealpersonalcomputereallereti),anuoviparadigmidicalcolo(calcoloparallelo,calcolodistribuito),anuovilinguaggidiprogrammazione;-allostessotemposonoiniziatiesisonosviluppatistuditeorici(definizionedimodelliformali,metodologiediprogetto,tecnichedianalisideiproblemi)conloscopodiprogettaresistemiedapplicazionicorrettiedefficienti.

Inunaprimafaseimodelliutilizzatiperformalizzareiconcettidell'informaticafuronoereditatidalleteoriematematichesviluppatenellaprimametàdelXXsecolo• calcolabilità• logica• algebra

efuronoestesieapplicatiallostudiodelleproprietàdeinuoviprodottidellatecnologiainformatica:calcolatori,programmieprocessidicalcolo.

1)ModellidicalcoloCalcolabilità-->Macchine,algoritmi(Turing,Church,Markov,...)Retineuronali-->Eventiregolari(McCulloch&Pitts,Kleene)1955-56MacchinediMealyeMoore1956"Automatastudies",ShannonandMcCarthyEds.,Princeton1959Autominondeterministici(Rabin&Scott)1963Randomaccessmachines(Shepherdson&Sturgis)1964-66"AutomataTheory",CaianielloEd.1966Linguaggifunzionali:ilCUCH(Böhm&Gross)1966Strutturedicontrollo:ilteoremadiBöhm&Jacopini1967"Computation.FiniteandInfiniteMachines",M.Minsky

2)ProprietàsintattichedeiprogrammiCalcolabilità,logica-->Sistemidiriscrittura(Post)Algebraastratta-->Teoriadeisemigruppi(Thue)1956-1959Grammaticheformali(Chomsky)1959Metalinguaggi:BackusNormalForm(Backus-NaurForm)1960Algol60Report1964"FormalLanguageDescriptionLanguagesforComputerProgramming",IFIP-TC21960-1965Classesoflanguagesandautomata(Oettinger,Schützenberger,Myhill,Kuroda,Greibach)1969"FormalLanguagesandTheirRelationtoAutomata",Hopcroft&Ullman

3)SemanticadeiprogrammiCalcolabilità-->λ-calcolo,logicacombinatoria

Logica-->Calcolodeipredicati,UniversodiHerbrandAlgebra-->Latticetheory1960Semanticaoperazionaledeilinguaggifunzionali(McCarthy)1964Attributegrammars(Knuth)1964Towardaformalsemantics(Strachey)1969Semanticaassiomatica(Floyd,Hoare)1970Semanticamatematica(denotazionale)(Scott)1972Fix-pointsemantics(Manna,Cadiou,Vuillemin)1972Semanticaalgebricaperschemidiprogrammi(Nivat)

4)ComplessitàcomputazionaleCalcolabilità-->MacchinediTuring,concettidiricorsività1960Proprietàdelle'stepcountingfunctions'(Rabin)1965ClassidicomplessitàbasatesumacchinediTuring(Hartmanis&Stearns)1965Facile=calcolabileintempopolinomiale(Edmonds)1966Complessitàassiomaticamachineindependent(Blum)1971Analisidialgoritmi(Knuth)1971-72RiduzionieNP-completezza(Cook,Karp)

“Therewasaveryspecialspiritintheair;weknewthatwewerewitnessingthebirthofanewscientificdisciplinecenteredonthecomputer”(RichardKarp)"Attributegrammarswerebornintheexhilaratingdaysofthemid-60swhenagreatmanyfundamentalprinciplesofcomputersciencewerebeginningtobeunderstood.Anenormousnumberofideaswerefloatingintheair,waitingtobecapturedinjusttherightcombinationsthatwouldprovetobepowerfulsourcesoffutureenergy"(DonaldKnuth)

Comesièsviluppatal'informaticateoricainItaliainqueiprimianni?Unapietramiliare:InternationalSchoolofPhysicson"AutomataTheory",Ravello,1964Temitrattati:Linguaggiformalieautomi(codici,automiprobabilistici,catenediMarkov,...)Calcolabilità(funzioniricorsive,macchinediTuring,algoritmidiMarkov,λ-calcolo,...)

Grafi(algoritmisugrafi,grafiecodici,...)Modellidelcervello(retineuronali,...)Participanti:M.Arbib,C.Berge,R.Büchi,M.Davies,M.Gross,M.P.Schützenberger,W.McCulloch,M.Nivat,L.Nolin,M.Rabin,L.Verbeek

Lapartecipazioneitaliana:E.Caianiello,IstitutodiFisicaTeorica,NapoliC.Böhm&W.Gross,INAC-CNR,RomaA.CaracciolodiForino,CSCE-CNR,PisaV.Amar&G.Putzolu,L.R.E.Olivetti,PregnanaMilaneseM.Borillo&P.Camion,EURATOM,Ispra+C.Berge,InternationalComputationCentre,RomaM.P.Schützenberger,adhonorem,perilsuorapportoconNapoli

IlruolodelCNRneglianni'60:capacedicoglierenuovedirezionidiricercacheilmondouniversitariopiùingessato(eaqueltempofortementecentralizzato)noneraancoracapacedicogliereIlLaboratoriodiCibernetica(ArcoFelice):comedalfallimentodiunprogettopossononascereeccellentigruppidiricerca:“Essentiallytheprogramofcybernetics,althoughextremelyinteresting,wastooambitiousandtheresultsthatwereachievedwereindeeddisappointinglymodestwithrespecttotheexpectedgoal.Theprogramoriginallywastodescribeneuralnets,todesignmathematicalmodelsofthenervoussystemandfromthistoderiveanexplanationofhighlevelmentalfunctionssuchaslearning,intelligenceandevenconsciousnessbutthestudyandunderstandingofthecentralnervoussystemdidnotdevelopasexpected...Eventuallyfromcyberneticsaseriesofspecificdisciplinesdeveloped,eachonewithitsownlanguageanditsowngoals”(AldodeLuca)

L'IstitutoperleApplicazionidelCalcolo(Roma):afiancoalleeccellentiapplicazionidelcalcolonumericosisviluppanoglistudisuλ-calcolo,logicacombinatoria,CUCH,LISPdiBöhm,GrosseJacopini

“InthatperiodIwasinterestedtofindthe‘best’computationmodelamongTuringmachines,Postproductionsystems,Markovalgorithms,Curry’scombinatorylogic(CL)andChurch’slambda-calculus(LC).Thefundamentalideawastotransformthe‘winning’modelintoapowerfulandsyntheticprogramminglanguage.ThepaperthatisatthebaseofstructuredprogrammingwasbornfromtheexaminationofthestructuresofsomeUniversalTuringMachines,togetherwithJacopini’sintuitionthatthenecessaryrestrictionsmighthavebeenrepresentedintermsofflowdiagrams.AtthesametimeIwasconvincedthatindeedwithCUCH,afusionofCLandLC,Ihadfoundthebestabstractmachine”(CorradoBöhm)

IlCentrodiStudisulleCalcolatriciElettroniche(dal1970:IstitutodiElaborazionedell'Informazione,Pisa):avalledelprogettodicostruzionedellaCEPsisviluppanovarifilonidiricercateorica:algoritmidiMarkov,patternrecognition,algoritmiestrutturedati,teoriadellaprogrammazione,ecc.Nel1970l'istituzionedeiprimicorsidilaureainScienzadel'Informazionedeterminaladiffusionedigruppidiricercadiinformaticateoricainambitouniversitario.

1971:Nasceiltermineinformaticateoricaesicreanolebasiperlacomunitàscientificacheoperainquestocampo.1971,giugno:MauriceNivat,insiemeaNolineSchützenberger,proponeunacooperazioneinteruniversitariaalivelloeuropeosuitemidell'informaticateoricaconlafinalitàdifavorirel'armonizzazionedeiprogrammidiinsegnamento,lacircolazionedeglistudentielacollaborazionescientifica.NivateCaracciolodiForinoorganizzanounariunioneaBruxellessuquestitemi

1971,luglio:"Rapportpréliminairesurl'informatiquethéorique"Primotentativodidefinireilcampodell'informaticateorica:undocumentodi12paginepreparatoaParigiVIIdaNivat,NolineSchützenberger(cosaèecosanonèinformaticateorica)

MauriceNivat(asinistra)conilsuomaestroMarcel-PaulSchützenbergernel1972

1967 avec Schutzenberger

1967 avec Paule

1967 avec Samuel Eilenberg

Treprincipalicampi:• Algoritmi:modellidicalcoloparallelo,memorieamoltilivelli,tecnichediprogetto(divide-et-impera),analisidialgoritminelcasopeggioreenelcasomedio,complessitàdicalcolo

• Automielinguaggiformali:proprietàdeilinguaggiregolariedeilinguaggicontext-free,autominon-deterministici,treelanguagesetreeautomata

• Semanticaformaledeilinguaggidiprogrammazione:verificadicorrettezza(Floyd,pre-epost-condizioni),trasformazionidiprogrammi(ricorsivovsiterativo),schemidiprogrammi,approccibasatisuλ-calcolo(Scott)esulogicacombinatoria(Nolin)

1971,ottobre:primariunioneaFirenzeper-preparazioneallariunioneprevistainsedeeuropea(Caracciolo)-creazionedelGruppoRicercatoridiInformaticaTeorica(GRIT-poi,neglianni1986-87risortocomeCapitoloItalianodell'EATCSancheperiniziativadiAldodeLucaeBrunoApolloni).ComitatopromotoredelGRITTorino:BöhmMilano:DegliAntoni,SomalvicoFirenze:PinzaniPisa:Luccio,MontanariRoma:Ausiello,VenturiniNapoli:deLuca,Lauria

1971,dicembre:CensimentodellericerchesvolteinItalianell'ambitodell'informaticateorica.Scienzadell'Informazione,Torino(Böhm,Dezani,RonchidellaRocca,Simone,...):λ-calcolo,struttureinformative,linguaggidiprogrammazioneElettronicaeCibernetica,Milano(DegliAntoni,Bertoni,DeMichelis,Maiocchi,...):automielinguaggiformali,correttezzadeiprogrammiPolitecnicodiMilano(CrespiReghizzi,DellaVigna,Ghezzi,Sami,...):basididatirelazionali,linguaggicontext-free,traduzionedirettadallasintassi,retidiPetriIstitutoMatematico,Firenze(Aguzzi,Cesarini,Pinzani,Soda,...):teoriadellaprogrammazione

IstitutodiElaborazionedell'Informazione-CNR+IstitutodiScienzadell'Informazione,Pisa(Aiello,Albano,Caracciolo,Carlucci,Grasselli,Levi,Luccio,Martelli,Montanari,Sirovich,Sprugnoli,...):algoritmidiMarkov,elaborazonedell'informazionesemantica(QAsystems,problemsolving,semanticadeiprogrammi),teoriadell'elaborazionediimmagini,struttureinformative(hashing),euristicheperproblemidiottimizzazioneIstitutoperleApplicazionidelCalcolo-CNR,Roma(Ausiello,Jacopini,Longo,Miola,Venturini,...):abstractcomputationalcomplexity,linguaggifunzionali,sistemidicalcolosimbolico,deduzioneautomaticaLaboratorodiCibernetica-CNR,ArcoFelice(deLuca,Germano,MaggioloSchettini,Termini,...):fuzzyset,algoritmidiMarkovGruppodiCiberneticapressoIstitutodiFisicaTeorica,Napoli(Aloisio,Lauria,Trautteur,...):modellineuronali,automi,ricorsività,complessità

Nel1971AldodeLucaprendelaliberadocenzainCiberneticaeteoriadell'informazione.Primicontributi:A.deLuca,S.Termini,Algebraicpropertiesoffuzzysets,JournalMathematicalAnalysisandApplicationsA.deLuca,S.Termini,Algorithmicaspectsincomplexsystemsanalysis,Scientia

1972:'Annusmirabilis'dell'informaticateoricaAlcunipilastridell'informaticateorica.-Programmazione:"StructuredProgramming"(Dahl,Dijkstra,Hoare)-Algoritmiestrutturedati:invenzionedeiB-tree(Bayer&McCreight),algoritmilinearisugrafibasatisuDFS(Tarjan)-Basididati:pubblicazionedeiproceedingsdelCourantSymposiumsu"DataBaseSystems"(modellorelazionalediCodd)-Semantica:CourantSymposiumsu"FormalSemantics"(Scott)-Verificadicorrettezzadiprogrammi:"ACMConferenceonProvingAssertionsaboutPrograms"(MilnerpresentaLCF-LogicforComputableFunctions)-Programmazionelogica:nascePROLOG(Colmerauer)-Complessitàdicalcolo:SimposioIBMsu"ComplexityofComputerComputations"(problemiNP-completi,Karp)

NascitadellaAssociazioneEuropeadiInformaticaTeorica1972,gennaio:RiunioneaBruxellesfinalizzataallacreazionedellacollaborazioneinteruniversitariaininformaticateoricaecheportaallanascitadellaAssociationEuropéenned'InformatiqueThéorique(AEIT-EATCS).LariunioneècoordinatadaAlfonsoCaracciolodiForinoedaMauriceNivat.Seipaesirappresentati:Belgio,Francia,Germania,GranBretagna,Italia,PaesiBassi.L'istituzionedell'EATCSvieneufficialmenteapprovatadalRedelBelgionelsettembre1972.

Nascitadelledueprincipaliconferenzeeuropeediinformaticateorica,1972,luglio: PrimoICALP,chairM.-P.Schützenberger Parigi,INRIA Tematiche:comeneldocumentodiNivat Lingueufficiali:inglese,francese,tedesco1972,agosto:PrimoMFCS,chairH.Rasiowa Jablonna(Varsavia) Tematiche:Semanticadilinguaggidiprogrammazione, fondamentiteoricideisistemidicalcolo Lingueufficiali:ingleseerusso

...e...primoimportantelavorodiAldodeLucasurivistainternazionaleA.deLuca,S.Termini,Adefinitionofanon-probabilisticentropyinthesettingoffuzzysetstheory,InformationandControl20(4)(2240citazioni)

Perquantohaidatoallascienza,

perlatuaamicizia

GRAZIEALDO!