Home » Archivo » Archvio 2013 » ALGORITMI E STRUTTURE DATI - 2013/2014

Laurea in Informatica

Salta il menu di secondo livello

ALGORITMI E STRUTTURE DATI - 8 CFU - A.A. 2013/2014

Insegnante

Sig. Livio Colussi

Periodo

II Anno - 1 Trimestre | 01/10/2013 - 07/12/2013

Ore: 64 (16 esercitazione, 48 lezione)

Torna su ▲

Prerequisiti

Programmazione.

Conoscenze e abilità da acquisire

Il corso ha come finalità quella di fornire un'introduzione agli algoritmi ed alla loro analisi. Lo studente apprende alcuni algoritmi e strutture dati fondamentali che sono alla base dello sviluppo dei sistemi software. L'analisi di tali algoritmi consente inoltre di sviluppare nello studente una sensibilità per la realizzazione di programmi efficienti e corretti.

Modalità di esame

Prova scritta ed esame orale.

Criteri di valutazione

Gli esercizi della prova scritta mirano a valutare la capacità dello studente di utilizzare le nozioni apprese per l'individuazione di soluzioni algoritmiche efficienti a problemi assegnati. La prova orale verifica la conoscenza degli argomenti teorici discussi a lezione.

contenuti

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

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

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

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

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

Attività di apprendimento previste e metodologie di insegnamento

Lezioni ed esercitazioni in aula.

Eventuali indicazioni sui materiali di studio

I lucidi delle lezioni e una dispensa di esercizi svolti sono disponibili nel sito del docente.

Testi di riferimento

Torna su ▲