Home Introduzione Programma Orario Laboratorio Nettuno Esame Diario 02-03 Materiale Challenge News Link Forum Esoneri

horizontal rule

Programma per l'anno accademico 2007-08

(Testo di riferimento: Robert Sedgewick. Algoritmi in Java. Terza edizione. Pearson Education Italia, 2003, Milano)

Per tutte le strutture dati, salvo diversa indicazione, č prevista la conoscenza della loro implementazione in Java. Fra parentesi quadre sono indicate le sezioni del testo di riferimento corrispondenti agli argomenti elencati. La corrispondenza fra argomenti svolti a lezione e sezioni del testo č puramente indicativa, tesa a definire un sottoinsieme di sezioni che possano coprire gli argomenti del corso.

  1. Modello di analisi dei costi, equazioni di ricorrenza  e concetto di upper/lower bound  [2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7]
  2. Cenno alla Metodologia "divide et impera" e "master theorem" [5.2]
  3. Richiami su strutture dati lineari (liste, pile, code) [Cap. 3 (richiami), 4.0, 4.1, 4.2, 4.3, 4.4, 4.5, 4.7]
  4. Alberi
    bulletAlberi n-ari [5.4]
    bulletTipo astratto, implementazione, operazioni ed algoritmi
    bulletAttraversamento di alberi (visite in profonditā, visita in ampiezza)
    bulletAlberi binari [5.5, 5.6, 5.7]
    bulletImplementazione, operazioni ed algoritmi
    bulletAttraversamento di alberi binari (visite in profonditā, visita in ampiezza)
    bulletAlberi binari di ricerca (BST) [12.6, 12.7, 12.8, 12.9, 13.0, 13.4 (sono i red-black, possono essere studiati in alternativa agli alberi AVL)]
    bulletImplementazione, operazioni ed algoritmi
    bulletAlberi bilanciati (AVL, senza codice Java): proprietā ed algoritmi per il mantenimento del bilanciamento (rotazioni)
  5. Heap [9.0, 9.1, 9.2, 9.3, 9.5]
    bulletoperazioni, rappresentazione ed algoritmi
    bulletapplicazione alle code di prioritā
  6. Ordinamento [6.1, 6.3, 6.4, 6.6, 7.1, 7.2, 8.1, 8.3, 9.4]
    bulletSelectionSort, QuickSort, HeapSort, MergeSort, InsertionSort
    bulletAlberi di decisione e lower bound
    bulletLower bound dell'ordinamento
  7. Hashing [14.0, 14.1, 14.2, 14.3, 14.4]
    bullettavole hash
    bulletfunzioni hash
    bullettecniche di gestione delle collisioni
  8. Grafi [Non presenti nel testo di riferimento. Possono essere studiati sul volume [2], capitoli da 17 a 21 (il capitolo 21 č disponibile online)]
    bulletDefinizioni e proprietā
    bulletRappresentazioni dei grafi
    bulletAttraversamenti di un grafo (DFS e BFS)
    bulletApplicazioni della DFS (ordinamento topologico e individuazione cicli) 
    bulletCammini minimi (Dijkstra)
    bulletAlberi ricoprenti minimi (Kruskal e Prim)

 

Altro materiale per la preparazione dell'esame

bullettrasparenze usate a lezione
bulletdiario dell'attivitā di laboratorio

horizontal rule

Č bene precisare che nelle lezioni, nelle esercitazioni e nell'attivitā di laboratorio, la cronologia degli argomenti affrontati e sviluppati non coincide necessariamente con quella che si evince in maniera naturale dal programma illustrato.

 

horizontal rule

Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.37
by FdA