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:

• Prova scritta
  Domande ed esercizi sul contenuto del corso. Esempi di prove scritte possono essere trovati qui.
  
• Registrazione
  Con prova orale facoltativa (principalmente focalizzata su domande di teoria), nello stesso appello nel quale si sostiene lo scritto. Il colloquio orale è indispensabile per conseguire la lode, che non viene mai assegnata solo sulla base dello scritto.

Per poter sostenere una determinata prova scritta

• È indispensabile essersi registrati alla corrispondente prova mediante il sistema UNIWEB.
• Questo è normalmente possibile solo fino a due giorni prima dell'esame stesso (la lista chiude due giorni prima dell'esame stesso alla mezzanotte).
• La registrazione richiede che non vi siano voti in sospeso per lo stesso insegnamento, ovvero un voto precedentemente conseguito deve essere rifiutato.

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 è

• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
  Introduzione agli Algoritmi e Strutture Dati (terza edizione)..
  3a Edizione. McGraw-Hill, 2010.
  Il sito del libro contiene anche una selezione di esercizi svolti.

oppure la versione originale inglese

• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
  Introduction to Algorithms and Data Structures..
  3rd Edition. MIT Press, 2009.