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).

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).
418
9788825173567
A.A. Bertossi; A. Montresor
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/89838
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact