Teoria e progetto di algoritmi fondamentali

Giorgio Ausiello, Alberto Marchetti Spaccamela, Marco Protasi

Teoria e progetto di algoritmi fondamentali

Pagine: 464

ISBN: 9788820474003

Edizione: 7a edizione 1996

Codice editore: 1385.2

Disponibilità: Fuori catalogo

Questo volume si rivolge a coloro che, dotati di una conoscenza elementare della programmazione dei calcolatori, desiderano acquisire la capacità di analizzare e progettare algoritmi efficienti per alcuni fondamentali problemi dell'informatica.

Nello studio dell'informatica la progettazione di algoritmi e strutture di dati ha un ruolo centrale sia dal punto di vista applicativo sia dal punto di vista teorico. Da un lato infatti la scelta dell'organizzazione dei dati e dei metodi più efficienti per la loro elaborazione rappresenta il primo passo nell'impostazione della soluzione di un problema mediante l'elaboratore; dall'altro lato gli studi svolti nell'ultimo decennio nel campo della teoria degli algoritmi hanno prodotto un insieme di tecniche e di risultati ormai consolidati che costituiscono un'importante base concettuale per la cultura informatica.

In questo volume vengono trattati entrambi gli aspetti, teorico ed applicativo, della progettazione di algoritmi. La prima parte introduce i concetti fondamentali alla base dell'analisi e del progetto di algoritmi e strutture di dati: modelli di calcolo, metodi risolutivi, limitazioni intrinseche alla possibilità di risolvere problemi complessi mediante elaboratori.

La seconda parte espone i principali algoritmi relativi a vari campi dell'informatica: algoritmi di ordinamento e ricerca, algoritmi su grafi, algoritmi per operare su polinomi, matrici, ecc.

Per le tematiche affrontate e per l'impostazione della trattazione, che conduce il lettore da un livello introduttivo fino alla soglia di recenti risultati di ricerca, il volume è destinato non solo a studenti universitari di corsi di laurea di tipo scientifico (informatica, matematica, ingegneria, ecc.) ma anche a quanti operano nel settore informatico e intendono arricchire le proprie competenze professionali.

Il volume è corredato di numerosi programmi basati sul linguaggio Pascal.

• Introduzione
* Complessità di problemi e di algoritmi
* Richiamo di concetti e notazione matematica
* Osservazioni sul linguaggio di descrizione degli algoritmi
* Esercizi
ANALISI DELLA COMPLESSITA' E PROGETTO DI ALGORITMI
• Analisi e valutazione della complessità degli algoritmi
* Misure di complessità di algoritmi
* Un semplice modello di calcolo: la macchina a registri
* Un esempio: il calcolo del valore di un polinomio in un punto
* Parametri per la valutazione degli algoritmi
* L'analisi asintotica
* Modelli di calcolo e relative misure
* L'analisi del caso medio
* Esercizi
• Tecniche di progetto di algoritmi
* Problemi e algoritmi
* Algoritmi di enumerazione
* Backtracking
* Il metodo «divide et impera»
* Tecniche per problemi di ottimizzazione
* Esercizi
• Caratterizzazione della complessità dei problemi
* Complessità intrinseca di un problema
* Classi di complessità. Le classi P ed NP
* Riduzioni tra problemi e gradi di complessità. Il grado NP-completo
* Esercizi
ALGORITMI FONDAMENTALI
• Algoritmi di ricerca e di orientamento
* Gestione di dizionari rappresentati mediante tabelle
* Gestione di dizionari rappresentati mediante alberi
* Gestione di code di priorità
* Metodi di ordinamento
* Determinazione di ordinamenti parziali
* Esercizi
• Algoritmi fondamentali su grafi
* Definizioni e rappresentazioni dei grafi in memoria
* Visita di un grafo
* Problemi di cammino minimo
* Chiusura transitiva
* Un approccio algebrico ai problemi di percorso
* Minimo albero ricoprente
* Problemi di flusso
* Problemi di accoppiamento
* Esercizi
• Algoritmi algebrici
* Prodotto di matrici
* Problemi computazionalmente correlati al prodotto di matrici
* Problemi di algebra lineare
* Problemi di percorso su grafi
* Valutazione e interpolazione di polinomi
* Massimo comun divisore
* Trasformata discreta di Fourier
* Problemi di algebra modulare: computazione dei residui e algoritmo dei resti cinesi
* Delimitazioni inferiori dei problemi algebrici
* Esercizi

Collana: Scienze e tecnologie informatiche

Livello: Textbook, strumenti didattici