Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Scienze
INFORMATICA
Insegnamento
ALGORITMI E STRUTTURE DATI
SCP4065531, A.A. 2017/18

Informazioni valide per gli studenti immatricolati nell'A.A. 2016/17

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INFORMATICA
SC1167, ordinamento 2011/12, A.A. 2017/18
N0
porta questa
pagina con te
Crediti formativi 9.0
Tipo di valutazione Voto
Denominazione inglese ALGORITHMS AND DATA STRUCTURES
Sito della struttura didattica http://informatica.scienze.unipd.it/2017/laurea
Dipartimento di riferimento Dipartimento di Matematica
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile PAOLO BALDAN INF/01

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Discipline Informatiche INF/01 9.0

Modalità di erogazione
Periodo di erogazione Secondo semestre
Anno di corso II Anno
Modalità di erogazione frontale

Organizzazione della didattica
Tipo ore Crediti Ore di
Corso
Ore Studio
Individuale
Turni
ESERCITAZIONE 2.0 16 34.0 Nessun turno
LEZIONE 7.0 56 119.0 Nessun turno

Calendario
Inizio attività didattiche 26/02/2018
Fine attività didattiche 01/06/2018

Syllabus
Prerequisiti: Elementi di programmazione
Matematica discreta
Analisi matematica
Conoscenze e abilita' 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.
Modalita' 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.
Attivita' di apprendimento previste e metodologie di insegnamento: Lezioni ed esercitazioni.
Eventuali indicazioni sui materiali di studio:
Testi di riferimento:
  • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein, Introduzione agli Algoritmi e Strutture Dati (terza edizione). --: McGraw-Hill Italia, 2010. Cerca nel catalogo