L'algoritmica e' quella branca dell'informatica che riguarda la definizione e la progettazione degli algoritmi, l'analisi della loro correttezza ed efficienza, la dimostrazione delle loro inerenti limitazioni e complessita', e lo studio delle strutture di dati da essi elaborati. Il presente testo e' suddiviso in quattro parti, che corrispondono alle suddette quattro aree principali dell'algoritmica, ed e' rivolto agli studenti dei corsi di Algoritmi e Strutture di Dati dei Corsi di Laurea in Informatica. Sono presentate le principali strutture di dati (liste, pile, code, alberi, insiemi, dizionari, code con priorita', grafi). Sono descritte le tecniche basilari di progettazione (divide et impera, backtrack, greedy, programmazione dinamica, ricerca locale, randomizzazione) e i metodi per la valutazione dell'efficienza di algoritmi (risoluzione di relazioni di ricorrenza, metodo del potenziale per l'analisi ammortizzata). Sono inoltre considerate tecniche per dimostrare l'inerente intrattabilita' di problemi (riduzioni polinomiali) e per affrontare problemi intrattabili (approssimazione, branch-&-bound, euristiche).
A.A. Bertossi, A. Montresor (2010). Algoritmi e Strutture di Dati. NOVARA : Citta' Studi Edizioni (De Agostini).
Algoritmi e Strutture di Dati
BERTOSSI, ALAN ALBERT;
2010
Abstract
L'algoritmica e' quella branca dell'informatica che riguarda la definizione e la progettazione degli algoritmi, l'analisi della loro correttezza ed efficienza, la dimostrazione delle loro inerenti limitazioni e complessita', e lo studio delle strutture di dati da essi elaborati. Il presente testo e' suddiviso in quattro parti, che corrispondono alle suddette quattro aree principali dell'algoritmica, ed e' rivolto agli studenti dei corsi di Algoritmi e Strutture di Dati dei Corsi di Laurea in Informatica. Sono presentate le principali strutture di dati (liste, pile, code, alberi, insiemi, dizionari, code con priorita', grafi). Sono descritte le tecniche basilari di progettazione (divide et impera, backtrack, greedy, programmazione dinamica, ricerca locale, randomizzazione) e i metodi per la valutazione dell'efficienza di algoritmi (risoluzione di relazioni di ricorrenza, metodo del potenziale per l'analisi ammortizzata). Sono inoltre considerate tecniche per dimostrare l'inerente intrattabilita' di problemi (riduzioni polinomiali) e per affrontare problemi intrattabili (approssimazione, branch-&-bound, euristiche).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
