Home » Archivo » Archvio 2009 » Algoritmi e strutture dati - 2009/2010

Laurea in Informatica

Salta il menu di secondo livello

Algoritmi e strutture dati - 8 CFU - A.A. 2009/2010

Insegnante

Prof. Livio Colussi

Periodo

II anno - 1 trimestre | 01/10/2009 - 04/12/2009

Ore: 48 Frontali, 0 Laboratorio, 16 Esercizi

Torna su ▲

Programma del Corso

Orientativamente i primi 5 capitoli del libro di testo consigliato.
Precisamente:

I Fondamenti
Analisi dettagliata di InsertSort: Pseudocodice. Calcolo diretto del tempo calcolo in funzione di n. Tasso di crescita e notazione asintotica. L'algoritmo MergeSort e la tecnica divide et impera. Analisi della complessità di MergeSort. Soluzione delle ricorrenze. Il teorema dell'esperto. QuickSort. Complessità media di QuickSort e analisi probabilistica. Randomizzazione di QuickSort.

II Ordinamento e Statistiche d'Ordine
HeapSort e sua analisi. Limite inferiore per la complessità degli algoritmi di ordinamento. Implementazione di code con priorità mediante heap. Ordinamento in tempo lineare. Algoritmi CountingSort, RadixSort e BucketSort. Algoritmo di selezione in tempo medio lineare.

III Strutture Dati
Tavole hash. Alberi binari di ricerca. Alberi rosso-neri. Aumento di strutture dati. Teorema dell'aumento per alberi rosso-neri. Alberi di intervalli.

IV Tecniche avanzate di progettazione e analisi
Programmazione dinamica. Algoritmi golosi. Analisi ammortizzata.

V Strutture Dati Avanzate
B-alberi. Heap binomiali. Strutture dati per insiemi disgiunti.

Prerequisiti: Programmazione

Propedeuticità: - -

Ausili Didattici: Trasparenti delle lezioni ed esercizi svolti nel sito del docente.

Testi di Riferimento: Introduzione agli Algoritmi e Strutture Dati. (seconda edizione)
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
Editore McGraw-Hill Italia.

Torna su ▲