Algoritmi e Strutture Dati

Laurea in Informatica - Università di Padova
Anno Accademico 2021/2022

Docenti

Obiettivi del corso

Il corso intende fornire un'introduzione agli algoritmi, ovvero alla formalizazione dei problemi, all'individuazione di soluzioni computazionali, e all'analisi di tali soluzioni, dal punto di vista della correttezza e dell'efficienza nell'uso di risorse. Verranno illustrati alcuni algoritmi e strutture dati fondamentali che sono alla base dello sviluppo di ogni sistema software. Il corso contribuisce a sviluppare una sensibilitè per la realizzazione di programmi efficienti e corretti. Il corso dà luogo al conseguimento di 9 CFU. Il corso ha un Moodle che verrà utilizzato per comunicazione e distribuzione di parte del materiale. È prevista attività di tutorato. Il gruppo Facebook relativo (link) fornisce informazioni in proposito.

Programma di massima del corso

  1. Fondamenti. Notazione per gli algoritmi. Primi esempi di algoritmi: tecniche di analisi e progettazione. Metodo incrementale (insertion sort). Divide et impera (merge sort). Analisi di complessità e notazione asintotica.
  2. Ordinamento. Heapsort, quicksort e ordinamento in tempo lineare.
  3. Strutture dati fondamentali. Pile e code. Liste. Tabelle hash. Alberi di ricerca.
  4. Tecniche avanzate di progettazione ed analisi degli algoritmi. Programmazione dinamica. Algoritmi greedy. Analisi ammortizzata.

Orario del corso

Il corso fa parte del II anno del Corso di Laurea in Informatica, Università di Padova, ed è collocato nel I semestre dell'Anno Accademico 2021/2022. Si terrà in forma telematica via zoom, con il seguente orario:
 
Giorno Orario
Lunedì 14.30 - 16.15
Martedì 12.30 - 14.15
Giovedì 14.30 - 16.15

Modalità d'Esame

Attenzione: Le modalità di esame potranno essere influenzate dall'evoluzione dell'emergenza COVID-19.

L'esame consiste in:

Per poter sostenere una determinata prova scritta

Le date degli appelli sono recuperabili dal sistema della gestione della didattica (query preconfezionata a questo link).

Chi si fosse registrato a una lista di prenotazione e decidesse di non presentarsi è pregato di cancellarsi dalla lista o, in caso la lista fosse già chiusa, di darne tempestiva comunicazione al docente.

Durante l'esame non è possibile consultare testi, appunti o altro materiale. Chi copia o consulta bigliettini (o affini) vedrà annullato lo scritto corrente e non potrà sostenere l'appello successivo.

Riferimenti bibliografici

Il libro adottato è oppure la versione originale inglese