Linguaggi, modelli, complessità

I temi trattati in questo testo costituiscono una parte essenziale della preparazione di uno specialista informatico. La loro trattazione si può svolgere in un unico corso, o anche in più corsi universitari di informatica, ingegneria informatica o matematica, nell'ambito sia della laurea triennale che della laurea specialistica. L'organizzazione del volume consente vari percorsi di lettura. I capitoli 1-5 possono essere di riferimento per un modulo dedicato allo studio delle proprietà sintattiche dei linguaggi di programmazione; i capitoli 5, 6, 7 sono la base di un corso di teoria della calcolabilità, che può essere svolto in un primo modulo sui fondamenti teorici dell'informatica. Infine, i capitoli 5, 8, 9 possono costituire un percorso dedicato allo studio della complessità nell'ambito di un modulo avanzato di algoritmica o di un secondo modulo sui fondamenti teorici dell'informatica. Oltre che per gli specialisti di informatica o di ingegneria informatica, la conoscenza dei principi teorici dell'informatica assume anche un ruolo importante nella preparazione culturale degli insegnanti di discipline informatiche nell'ambito della scuola media superiore. In ogni caso, la conoscenza delle proprietà di grammatiche ed automi, dei limiti del calcolo automatico, della complessità computazionale e del problema "da un milione di dollari" P = NP? ha assunto un ruolo importante anche nella cultura scientifica contemporanea, e può risultare interessante per chi voglia approfondire alcuni dei temi che hanno caratterizzato la logica e la matematica degli ultimi cinquanta anni. Il volume contiene anche esercizi e note storiche e bibliografiche che consentono di comprendere meglio i concetti introdotti e rinviano ad altre letture di approfondimento. Giorgio Ausiello è professore ordinario di Informatica teorica presso l'Università "La Sapienza" di Roma. La sua area di ricerca riguarda prevalentemente la teoria degli algoritmi e la complessità computazionale. Fabrizio d'Amore è professore associato di Algoritmi e Strutture dati presso l'Università "La Sapienza" di Roma. Svolge ricerche nel campo delle strutture di dati e delle loro applicazioni nella geometria computazionale e nei sistemi informativi geografici. Giorgio Gambosi è professore ordinario di Sistemi di elaborazione dell'informazione presso l'Università "Tor Vergata" di Roma. Si interessa di algoritmi a strutture dati, con particolare riferimento alle loro applicazioni alle reti ed ai sistemi distribuiti.