ENGLISH
COMPLEXITY AND APPROXIMATION
This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensible source of reference for professionals. The smooth integration of numerous
illustrations, examples, and exercises make this monograph an ideal textbook.
INTRODUCTION TO THE THEORY OF COMPLEXITY
From the beginning of 2006 the authors have decided to get back the rights of the book and to make it freely available on the web. The electronic version is identical to the original printed version (apart, of course, from the cover pages), but it also includes the errata corrige collected since the first printing of the book.
ITALIAN
INFORMATICA TEORICA
Scopo del libro è fornire gli elementi di base delle teorie che sono di fondamento all’informatica, ovvero la teoria della calcolabilità, quella dei linguaggi formali e quella della complessità. In particolare, gli argomenti trattati includono le macchine di Turing, la macchina di Turing universale, i limiti delle macchine di Turing, la tesi di Church-Turing, la gerarchia di Chomsky, i linguaggi regolari, i linguaggi liberi da contestom le classi di complessità, le classi P, NP, PSPACE e EXP e gli algoritmi di approssimazione.
STRUTTURE DI DATI E ALGORITMI
Semplicità e chiarezza nella presentazione e nell’approfondimento si uniscono, in questo libro, al rigore scientifico degli argomenti. La trattazione copre i contenuti classici dei corsi introduttivi di algoritmi e strutture di dati offerti nei corsi di laurea triennali e, per motivarne lo studio in stretta connessione con la programmazione nella pratica, l’approccio scelto è applicativo, rivolto alla soluzione di problemi concreti, ispirati agli “argomenti caldi” della tecnologia dell’informazione: computer graphic, data mining, information retrieval, instradamento Internet, kernel di Linux, P2P, Web searching, XML, e molto altro ancora. Il libro descrive gli algoritmi utilizzando uno pseudocodice molto vicino al codice reale, ed è integrato con il sistema di visualizzazione denominato ALVIE (Algorithm Visualization Environment) che consente di esplorare il comportamento delle strutture di dati e degli algoritmi attraverso esempi personalizzabili.
GOCCE DI JAVA
Quando si sceglie il primo linguaggio di programmazione da insegnare ad uno studente, si devono valutare diversi aspetti pedagogici come la
semplicità del linguaggio, il supporto fornito a specifici paradigmi di programmazione (quali quello procedurale oppure quello orientato agli oggetti) ed il valore pratico del linguaggio nel mondo reale. Gocce di Java si propone di tenere in considerazione tutti questi aspetti ed introduce il lettore al linguaggio di programmazione Java seguendo un approccio programmazione procedurale prima di programmazione orientata agli oggetti. Il processo di apprendimento di Java è organizzato in due fasi ben distinte: la prima fase consente allo studente di sviluppare abilità relative al comune meccanismo procedurale di basso livello, mentre nella seconda fase lo studente affronta l’implementazione e la verifica di classi ed oggetti. Per poter realizzare questa filosofia facendo riferimento al linguaggio Java, il volume utilizza un’applicazione (chiamata Java--) che consente agli studenti di familiarizzare con la sintassi Java senza necessariamente avere nozioni di programmazione orientata agli oggetti. Il volume è rivolto a chiunque intenda avvicinare la programmazione in Java e non abbia alcuna conoscenza preliminare, se non quelle fornite dalla scuola superiore. L’obiettivo non è quello di trattare Java in modo esaustivo, ma di familiarizzare con quelle nozioni di base necessarie per scrivere programmi non troppo complessi oppure per affrontare, successivamente, lo studio del linguaggio ad un livello più alto con l’eventuale ausilio di altri manuali.
TEORIA DELLA COMPLESSITA’ COMPUTAZIONALE
La teoria della complessità computazionale è una disciplina relativamente recente che ha come obiettivo principale quello di formalizzare il concetto di complessità di un problema. Questo volume ha un carattere introduttivo e si propone di presentare al lettore un quadro sistematico dei risultati più significativi ottenuti finora nel campo di questa nuova teoria. L’approccio seguito consiste nel definire nei capitoli iniziali gli strumenti con i quali affrontare lo studio per poi passare ad esaminare in dettaglio le caratteristiche delle classi di complessità più importanti. Gli ultimi capitoli sono dedicati allo studio di classi di complessità probabilistiche ed a quello della complessità del calcolo parallelo. Usato in ambito universitario, il testo permette di coprire le esigenze di più moduli didattici sia in corsi di informatica che nell’ambito di corsi interessati a vari aspetti della matematica che nell’ambito di corsi interessati a vari aspetti della matematica computazionale. Un secondo tipo di lettori è costituito da quanti hanno già una buona preparazione informatica e desiderano approfondire gli sviluppi metodologici più significativi della teoria della complessità, sia per iniziare un’attività di ricerca in tale campo che per impadronirsi rapidamente di alcuni concetti o tecniche di dimostrazione per poi trasferirli in altri campi dell’informatica teorica. Ogni capitolo è corredato di numerosi esempi e problemi che aiutano il lettore ad assimilare i nuovi concetti introdotti.