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 una pagina Moodle che verrà utilizzato per
comunicazione e distribuzione di parte del materiale [link].
È prevista attività di tutorato (informazioni reperibili nel
canale Telegram FIUPd).
Programma di massima del corso
-
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.
-
Ordinamento. Heapsort, quicksort e ordinamento in tempo
lineare.
-
Strutture dati fondamentali. Pile e code. Liste. Tabelle
hash. Alberi di ricerca.
-
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 2022/2023.
Si terrà in presenza (aula LuM250), con
il seguente orario:
Giorno |
Orario |
Lunedì |
12.30 - 14.15 |
Martedì |
12.30 - 14.15 |
Giovedì |
14.30 - 16.15 |
Modalità d'Esame
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 (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, ora alla quarta edizione:
-
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
Introduction to Algorithms and Data Structures..
4th Edition. MIT Press, 2022.