Home » Laurea in Informatica » Corsi » ALGORITMI E STRUTTURE DATI

Laurea in Informatica

Salta il menu di secondo livello

ALGORITMI E STRUTTURE DATI - 9 CFU

Insegnante

Paolo Baldan

Periodo

II Anno - 2 Semestre | 26/02/2018 - 01/06/2018

Ore: 72 (16 esercitazione, 56 lezione)

Torna su ▲

Prerequisiti

Elementi di programmazione
Matematica discreta
Analisi matematica

Conoscenze e abilità da acquisire

Il corso intende fornire un'introduzione agli algoritmi e 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 aiuta lo studente a sviluppare 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 e RadixSort.

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

Attività di apprendimento previste e metodologie di insegnamento

Lezioni ed esercitazioni.

Eventuali indicazioni sui materiali di studio

Testi di riferimento

Torna su ▲