Algoritmi e Strutture Dati

Prof. Alfredo De Santis

Anni accademici 2008/09 e 2007/08 (immatricolati dal 2003-04 con matricole congrue ad 1 mod 3), 2006/07 (matricole congrue ad 1 mod 3), 2005/06, 2004/05, 2003/04 (matricole dispari-pari), 2002/03 e 2001/02 (matricole 6-7-8-9)

Programma del corso

2. Ruolo degli algoritmi nell'elaborazione dei dati.
   Capitolo 1 di [CLRS]. 
3. Insertion sort, analisi degli algoritmi. Progettazione degli algoritmi.
   Capitolo 2 di [CLRS]. 
4. Notazione per l'analisi asintotica degli algoritmi. Notazione O grande, Theta e Omega.
   Capitolo 3 di [CLRS]. 
5. Heapsort.
   Capitolo 6 di [CLRS]. 
6. Limiti inferiori per l'ordinamento.
   Capitolo 8, paragrafo 8.1, di [CLRS]. 
7. Quicksort. Analisi nel caso pessimo. Analisi nel caso medio (senza dimostrazione formale).
   Capitolo 7 (eccetto paragrafo 7.4.2) di [CLRS]. 
8. Calcolo del minimo. Calcolo del minimo e del massimo. Calcolo del minimo e del secondo elemento. Calcolo della mediana: algoritmo lineare nel caso peggiore, algoritmo lineare nel caso medio (senza analisi formale),
   Capitolo 9 di [CLRS]. 
9. Programmazione dinamica.
   Capitolo 15 (eccetto paragrafo 15.5) di [CLR]. 
10. Algoritmi golosi.
    Capitolo 16 (eccetto paragrafi 16.4 e 16.5) di [CLRS]. 
11. Algoritmi di ricerca esaustiva. Backtrack. Branch and Bound.
    Capitolo 4, paragrafi 4.1.1, 4.1.2, 4.1.4, 4.1.6, di [RND]. 
12. Hashing.
    Capitolo 11 (eccetto paragrafi 11.3.3, 11.5 ed Analisi dell'hashing a indirizzamento aperto) di [CLRS]. 
13. Struttura dati dizionario: alberi di ricerca binari
    Capitolo 12 di [CLRS]. 
14. Alberi rosso-neri.
    Capitolo 13 di [CLR]. 
15. Strutture dati per insiemi disgiunti
    Capitolo 21 (eccetto paragrafo 21.4) di [CLRS]. 
16. Complessita' computazionale. Classi P e NP. Linguaggi NP-completi.
    Capitolo 34 (eccetto prova Lemma 34.6, Teoremi 34.11, 34.12, 34.13, 34.15) di [CLRS].

Testi di riferimento:

[CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, seconda edizione, McGraw-Hill

[RND] E. M. Reingold, J. Nievergelt, N. Deo, Combinatorials Algorithms, Theory and Practice, Prentice-Hall

Presentazione Alberi Binari di Ricerca ed Alberi Rosso-Neri a.a. 2002/03, a.a. 2003/04 html, a.a. 2003/04 pdf, a.a. 2005/06 pdf, a.a. 2007/08 pdf

Strutture Dati animate con JIVE: http://jive.dia.unisa.it/asd/

Prove di valutazione in itinere:

a.a. 2001/02: 22 novembre 2001, 11 febbraio 2002

a.a. 2002/03: 11 novembre 2002, 23 gennaio 2003

a.a. 2003/04: 20 novembre 2003, 23 gennaio 2004,

a.a. 2004/05: 29 novembre 2004, 14 febbraio 2005

a.a. 2005/06: 21 novembre 2005, 2 febbraio 2006,

a.a. 2006/07: 20 novembre 2006, 7 febbraio 2007,

Prove di esame:

a.a. 2003/04: 23 febbraio 2004, 15 luglio 2004, 27 settembre 2004

a.a. 2004/05: 14 febbraio 2005, 28 febbraio 2005, 19 luglio 2005, 14 settembre 2005. 21 novembre 2005

a.a. 2005/06: 2 febbraio 2006, 17 febbraio 2006, 19 aprile 2006, 18 luglio 2006, 19 settembre 2006

a.a. 2006/07: 7 febbraio 2007, 26 febbraio 2007, 20 aprile 2007, 19 giugno 2007, 16 luglio 2007, 19 settembre 2007

a.a. 2007/08: 23 gennaio 2008, 12 febbraio 2008, 18 giugno 2008, 11 luglio 2008, 8 settembre 2008

a.a. 2008/09: 14 gennaio 2009, 4 febbraio 2009, 20 febbraio 2009, 18 giugno 2009, 9 settembre 2009,

Gli studenti che vogliono sostenere la prova di Algoritmi e Strutture Dati devono comunicarlo (email oppure verbalmente) al docente dopo la prenotazione su ESSE3. In mancanza di una comunicazione sosterranno la prova di Algoritmi.