ALGORITMI E LABORATORIO A - L

Modulo LABORATORIO

Conoscenza e comprensione (knowledge and understanding): gli studenti acquisiranno la conoscenza dei principi fondamentali dell'analisi delle prestazioni degli algoritmi e dei concetti chiave relativi alla complessità computazionale e alla correttezza algoritmica. 

Applicazione della conoscenza e comprensione (applying knowledge and understanding): gli studenti saranno in grado di applicare le tecniche di analisi agli algoritmi esistenti e impareranno a progettare soluzioni algoritmiche a problemi elementari che rispettino rigorosi standard di correttezza.

Autonomia di giudizio (making judgements): gli studenti sapranno identificare le situazioni in cui un algoritmo è preferibile ad un altro e potranno valutare la complessità computazionale di un algoritmo e la sua correttezza mediante dimostrazioni formali.

Abilità comunicative (communication skills): gli studenti impareranno a comunicare in modo chiaro ed efficace i risultati dell'analisi dell'efficienza e delle dimostrazioni di correttezza degli algoritmi, mediante relazioni scritte, presentazioni informali e discussioni tecniche, avvalendosi di una terminologia appropriata che possa adeguarsi ad interlocutori più o meno esperti.

Abilità di apprendimento (learning skills): gli studenti padroneggeranno il pensiero algoritmico acquisito nel corso e lo adatteranno a nuovi algoritmi e problemi informatici che incontreranno. Saranno capaci di apprendere autonomamente e acquisire nuove competenze nell'ambito dell'analisi della complessità di un algoritmo e della sua correttezza.

Si richiede una buona conoscenza degli elementi di matematica discreta e di analisi matematica e dei concetti presentati nei corsi di Programmazione.

DESCRIZIONE GENERALE DEL CORSO

Il corso offre un'approfondita comprensione delle fondamentali tecniche di analisi della complessità computazionale e delle metodologie per dimostrare la correttezza degli algoritmi informatici.

ARGOMENTI DEL CORSO

Introduzione

Strumenti per l'analisi degli algoritmi. Analisi di algoritmi elementari. Introduzione alle notazioni asintotiche.

Algoritmi ricorsivi

Analisi di algoritmi mediante il metodo di sostituzione e il metodo dell'albero di ricorsione. Heapify e Mergesort. Utilizzo del metodo master per la risoluzione di equazioni di ricorrenza. 

Hashing

Analisi delle tabelle hash: ricerca con successo e ricerca senza successo.

Alberi rosso-nero

Analisi dell'altezza di un albero rosso-nero. Operazioni di inserimento e cancellazione. 

Programmazione dinamica

Analisi della programmazione dinamica. Dimostrazione della proprietà di sottostruttura ottima. Esempio: Longest Common Subsequence.

Elementi della strategia Greedy

Scelta della soluzione ottima. Dimostrazione della scelta greedy per il problema della selezione di attività e per il caso dell'algoritmo di Huffman. Dimostrazione della proprietà di sottostruttura ottima e di scelta greedy nei problemi dello zaino e del resto.

Algoritmi elementari per grafi

Correttezza degli algoritmi di Bellman-Ford e del Topological Sort ed esempi di esecuzione. Correttezza dell'algoritmo di Dijkstra ed esempi di esecuzione.

Il libro di testo consigliato è:

(*) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Fourth Edition), The MIT Press, Cambridge - Massachusetts, 2022

disponibile anche nella traduzione italiana 

(1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.

Modalità di verifica dell'apprendimento

La prova di esame del modulo di Algoritmi è suddivisa in due parti: una prima prova scritta (obbligatoria) e una successiva prova orale (che potrà essere facoltativa per gli studenti ammessi senza riserva). Tali prove potranno avere luogo per via telematica, qualora le condizioni lo dovessero richiedere.
Alla fine della prova scritta lo studente riceverà una delle tre seguenti valutazioni:
- NON AMMESSO alla prova orale
- AMMESSO CON RISERVA alla prova orale 
- AMMESSO ala prova orale
In quest'ultimo caso allo studente verrà comunicato il voto ottenuto nella prova scritta, voto che sarà compreso tra 18 e 25.
La prova orale potrà svolgersi il giorno stesso in cui è stata svolta la prova scritta o a distanza di pochi giorni da esso. Tale prova avrà lo scopo di valutare più nel dettaglio la preparazione dello studente, la sua capacità di ragionamento relativamente agli argomenti trattati a lezione, nonché la sua proprietà di linguaggio. 
La valutazione della prova orale si dovrà intendere ad integrazione del voto ottenuto nella prova scritta e non a suo incremento.
Gli studenti AMMESSI alla prova orale potranno chiedere di essere esonerati dal sostenere tale prova, accettando quindi il voto comunicato ad essi alla fine della prova scritta. 
Gli studenti AMMESSI CON RISERVA non potranno usufruire della precedente possibilità e, qualora desiderassero continuare l'iter dell'esame, dovranno sostenere obbligatoriamente la prova orale per concludere l’esame del modulo di Algoritmi.
Gli studenti NON AMMESSI alla prova orale dovranno ripetere la prova scritta in un successivo appello.

Per l'attribuzione del voto finale si seguiranno di norma i seguenti criteri:

- non approvato: lo studente non ha acquisito i concetti di base e non è in grado di svolgere gli esercizi.

- 18-23: lo studente dimostra una padronanza minima dei concetti di base, le sue capacità di esposizione e di collegamento dei contenuti sono modeste, riesce a risolvere semplici esercizi.

- 24-27:  lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione e di collegamento dei contenuti sono buone,  risolve gli esercizi con pochi errori.

- 28-30 e lode: lo studente ha acquisito tutti i contenuti del corso ed è in grado di esporli compiutamente e di collegarli con spirito critico; risolve gli esercizi in modo completo e senza errori.

Per partecipare all'esame è necessario avere effettuato la prenotazione sul portale SmartEdu.

Si fa presente che l'esame del modulo di Algoritmi e quello del modulo di Laboratorio di Algoritmi si svolgeranno contestualmente e verranno quindi valutati contestualmente.