Daniel P. Bovet, Pierluigi Crescenzi
Teoria della complessità computazionale
Pagine: 328
ISBN: 9788820465551
Edizione: 1a ristampa 2005, 1a edizione 1991
Codice editore: 1385.7
Disponibilità: Esaurito
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.
• Notazioni matematiche e richiami
* Insiemi, relazioni e funzioni
* Cardinalità di insiemi
* Grafi - Alfabeti, parole e linguaggi
* Classe di funzioni O
* Problemi
• Richiami di teoria della calcolabilità
* Modelli di calcolo, algoritmi e computazioni
* Grammatiche e linguaggi
* Macchine e linguaggi
* Riducibilità tra linguaggi
• Problemi, codifiche e linguaggi
* Problemi decisionali
* Codifica dei problemi decisionali
* Problemi complementari
* Altri tipi di problemi
• Misure di complessità
* Misure statiche e dinamiche
* Definizione assiomatica
* TEMPO e SPAZIO deterministico e non deterministico
* Altre misure di complessità
• Classi di complessità temporale
* Classi di linguaggi
* Confronto tra classi
* Classi di complessità
• La classe P
* La classe FP
* Esempi di problemi in P
* Alcune proprietà della classe P
* Diagonalizzazione uniforme
* Polinomialità non costruttiva
• La classe NP
* Linguaggi NP-completi
* Il teorema di Cook
* Dimostrazioni di NP-completezza
* Linguaggi p-isomorfi
* Linguaggi NP-intermedi
* Linguaggi radi ed unari
* Calcolo e verifica di una funzione
• Complessità dei problemi di ottimizzazione
* Problemi di ottimizzazione
* La classe NPO - PO
* Linguaggi soggiacenti
* Misura e soluzione ottima
* Approssimabilità: la classe APX - PAS - FPAS
• Oltre NP
* La classe coNP
* La gerarchia Booleana
* La gerarchia polinomiale
* Complessità esponenziale
• Classi di complessità spaziale
* Relazioni tra tempo e spazio
* La classe LOGSPAZIO
* La classe PSPAZIO
* Chiusura rispetto al complemento
* Inclusioni tra classi di complessità
• Relativizzazione
* Le classi P ed NP relativizzate
* Separazione forte
* Relativizzazione positiva
• Algoritmi probabilistici
* Un algoritmo probabilistico
* Monte Carlo o Las Vegas?
* Altri esempi
• Classi di complessità probabilistiche
* Macchine di Turing probabilistiche
* Classi probabilistiche
• Algoritmi probabilistici e PSPAZIO
* Dimostrazioni interattive e PSPAZIO
* IP = PSPAZIO
• Modelli di calcolo parallelo
* Modelli PRAM
* Il modello SIMDAG
* Inclusione stretta tra modelli SIMDAG
* Complessità circuitale di funzioni booleane
* Famiglie di circuiti
* Famiglie di circuiti uniformi
* Conglomerati
* Confronto tra modelli
• Calcolo parallelo
* Problemi parallelizzabili in modo efficace
* Esempi di problemi in NC
* La tesi del calcolo parallelo
* Problemi non parallelizzabili
* Insiemi, relazioni e funzioni
* Cardinalità di insiemi
* Grafi - Alfabeti, parole e linguaggi
* Classe di funzioni O
* Problemi
• Richiami di teoria della calcolabilità
* Modelli di calcolo, algoritmi e computazioni
* Grammatiche e linguaggi
* Macchine e linguaggi
* Riducibilità tra linguaggi
• Problemi, codifiche e linguaggi
* Problemi decisionali
* Codifica dei problemi decisionali
* Problemi complementari
* Altri tipi di problemi
• Misure di complessità
* Misure statiche e dinamiche
* Definizione assiomatica
* TEMPO e SPAZIO deterministico e non deterministico
* Altre misure di complessità
• Classi di complessità temporale
* Classi di linguaggi
* Confronto tra classi
* Classi di complessità
• La classe P
* La classe FP
* Esempi di problemi in P
* Alcune proprietà della classe P
* Diagonalizzazione uniforme
* Polinomialità non costruttiva
• La classe NP
* Linguaggi NP-completi
* Il teorema di Cook
* Dimostrazioni di NP-completezza
* Linguaggi p-isomorfi
* Linguaggi NP-intermedi
* Linguaggi radi ed unari
* Calcolo e verifica di una funzione
• Complessità dei problemi di ottimizzazione
* Problemi di ottimizzazione
* La classe NPO - PO
* Linguaggi soggiacenti
* Misura e soluzione ottima
* Approssimabilità: la classe APX - PAS - FPAS
• Oltre NP
* La classe coNP
* La gerarchia Booleana
* La gerarchia polinomiale
* Complessità esponenziale
• Classi di complessità spaziale
* Relazioni tra tempo e spazio
* La classe LOGSPAZIO
* La classe PSPAZIO
* Chiusura rispetto al complemento
* Inclusioni tra classi di complessità
• Relativizzazione
* Le classi P ed NP relativizzate
* Separazione forte
* Relativizzazione positiva
• Algoritmi probabilistici
* Un algoritmo probabilistico
* Monte Carlo o Las Vegas?
* Altri esempi
• Classi di complessità probabilistiche
* Macchine di Turing probabilistiche
* Classi probabilistiche
• Algoritmi probabilistici e PSPAZIO
* Dimostrazioni interattive e PSPAZIO
* IP = PSPAZIO
• Modelli di calcolo parallelo
* Modelli PRAM
* Il modello SIMDAG
* Inclusione stretta tra modelli SIMDAG
* Complessità circuitale di funzioni booleane
* Famiglie di circuiti
* Famiglie di circuiti uniformi
* Conglomerati
* Confronto tra modelli
• Calcolo parallelo
* Problemi parallelizzabili in modo efficace
* Esempi di problemi in NC
* La tesi del calcolo parallelo
* Problemi non parallelizzabili
Collana: Scienze e tecnologie informatiche
Argomenti: Scienza dei calcolatori
Livello: Textbook, strumenti didattici
Potrebbero interessarti anche
