Linguaggi, modelli, complessità

Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Luigi Laura

Linguaggi, modelli, complessità

Questa nuova edizione del volume presenta temi che 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 magistrale.

Printed Edition

42.00

Pages: 454

ISBN: 9788891705532

Edition: 1a ristampa 2023, 2a edizione, nuova edizione 2014

Publisher code: 1385.11

Availability: Discreta

I temi presentati 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 sia di quella magistrale.
Oltre che per gli specialisti, la conoscenza dei principi teorici dell'informatica assume un ruolo importante anche 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 dell'ultimo secolo.
Il volume contiene anche esercizi, note storiche e bibliografiche che consentono di comprendere meglio i concetti introdotti e rinviano ad altre letture di approfondimento.
Questa nuova edizione, ampliata, riveduta e corretta, presenta un capitolo aggiuntivo dedicato agli algoritmi di risoluzione approssimata di problemi di ottimizzazione; inoltre, sono state aggiunte delle sezioni dedicate alle applicazioni pratiche degli argomenti trattati.
Nel sito www.informaticateorica.it è possibile trovare materiale di supporto a quanto trattato nel volume.

Giorgio Ausiello è professore emerito 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 in ruolo presso l'Università "La Sapienza" di Roma dove insegna Fondamenti di Informatica II e dirige il Master di 2° livello in Sicurezza delle Informazioni e Informazione Strategica. Svolge ricerche nel campo degli algoritmi e della sicurezza informatica.
Giorgio Gambosi è professore ordinario di Fondamenti di Informatica presso l'Università "Tor Vergata" di Roma. Si interessa, tra l'altro, di algoritmi e strutture di dati, con particolare riferimento alle loro applicazioni alle reti ed ai sistemi distribuiti.
Luigi Laura, abilitato professore associato, è docente di Progetto di Sistemi Web-based presso l'Università "Tor Vergata" di Roma. È il responsabile scientifico delle Olimpiadi Italiane di Informatica, ed allena la squadra italiana per le olimpiadi internazionali. La sua area di ricerca riguarda principalmente gli algoritmi per grafi.

Introduzione
Concetti matematici di base
(Calcolo proposizionale; Insiemi, relazioni e funzioni; Cardinalità di insiemi infiniti e numerabilità; Strutture algebriche elementari; Caratteristiche elementari dei linguaggi; Notazione asintotica; Note storiche e bibliografiche)
Linguaggi formali
(Grammatiche di Chomsky; Grammatiche con e-produzioni; Linguaggi lineari; Forma Normale di Backus e diagrammi sintattici; Accettazione e riconoscimento di linguaggi; Note storiche e bibliografiche)
Linguaggi regolari
(Automi a stati finiti; Automi a stati finiti non deterministici; Relazioni tra automi a stati finiti deterministici, non deterministici e grammatiche di tipo 3; Il "pumping lemma" per i linguaggi regolari; Proprietà di chiusura dei linguaggi regolari; Espressioni regolari e grammatiche regolari; Predicati decidibili sui linguaggi regolari; Il teorema di Myhill-Nerode; Espressioni regolari nella pratica; Note storiche e bibliografiche)
Linguaggi non contestuali
(Alberi sintattici; Forme ridotte e forme normali; Il "pumping lemma" per i linguaggi non contestuali; Proprietà di chiusura dei linguaggi non contestuali; Predicati decidibili sui linguaggi non contestuali; Automi a pila e linguaggi non contestuali; Automi a pila deterministici; Analisi sintattica e linguaggi non contestuali deterministici; Grammatiche e linguaggi ambigui; Algoritmi di riconoscimento di linguaggi non contestuali; Linguaggi non contestuali nella pratica: XML e DTD; Note storiche e bibliografiche)
Macchine di Turing e T-calcolabilità
(Macchine di Turing a nastro singolo; Calcolo di funzioni e macchine di Turing deterministiche; Calcolabilità secondo Turing; Macchine di Turing multinastro; Macchine di Turing non deterministiche; Riduzione delle macchine di Turing; Descrizione linearizzata delle macchine di Turing; La macchina di Turing universale; Il problema della terminazione; Linguaggi di tipo 0 e macchine di Turing; Linguaggi di tipo 1 e automi lineari; Note storiche e bibliografiche)
Modelli di calcolo imperativi e funzionali
(Macchine a registri; Macchine a registri e macchine di Turing; Macchine a registri e linguaggi imperativi; Funzioni ricorsive; Funzioni ricorsive e linguaggi imperativi; Funzioni ricorsive e linguaggi funzionali; Note storiche e bibliografiche)
Teoria generale della calcolabilità
(Enumerazione di funzioni ricorsive; Proprietà di enumerazioni di funzioni ricorsive; Funzioni non calcolabili; Indecidibilità del problema delle corrispondenze di Post; Indecidibilità in matematica ed informatica; Teoremi di Kleene e di Rice; Insiemi decidibili e semidecidibili; Note storiche e bibliografiche)
Teoria della complessità
(Valutazioni di complessità; Tipi di problemi; Complessità temporale e spaziale; Teoremi di compressione ed accelerazione; Classi di complessità; Teoremi di gerarchia; Relazioni tra misure di complessità; Riducibilità tra problemi; Note storiche e bibliografiche)
Trattabilità ed intrattabilità dei problemi
(La classe P; Problemi P-completi; La classe NP; Problemi NP-completi; Ancora sulla classe NP; La gerarchia polinomiale; La classe PSPACE; Note storiche e bibliografiche)
Complessità dei problemi di ottimizzazione
(Soluzioni ad approssimazione garantita; Schemi di approssimazione polinomiali; Schemi di approssimazione pienamente polinomiali; Note storiche e bibliografiche)
Bibliografia
Indice analitico.



Serie: Scienze e tecnologie informatiche

Subjects: Software Programming and Development

Level: Textbooks

You could also be interested in