ALGORITMI E STRUTTURE DATI - MOD.2

L'insegnamento è uno dei corsi fondamentali del corso di studio e fornisce un'introduzione agli algoritmi, ovvero alla formalizzazione 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. Inoltre presenta varie strutture dati fondamentali e tecniche di base per la progettazione e l'analisi degli algoritmi.

Conoscenza e comprensione:
- conoscenza e comprensione dei principali algoritmi e strutture dati;
- comprensione e valutazione della complessità dei problemi informatici e capacità di selezionare metodi adeguati per la modellazione e risoluzione del problema.

Capacità di applicare conoscenza e comprensione:
- capacità logico-deduttive e di problem solving;
- capacità di formalizzare e implementare soluzioni per problemi reali e identificazione di pattern di soluzione appropriati;

Capacità di giudizio
- Sapere formulare ed argomentare soluzioni, sviluppando anche un approccio critico alla valutazione di soluzioni alternative.

Familiarità con i concetti di base della matematica discreta e dell'analisi matematica. Conoscenza del linguaggio C++ e dei rudimenti della programmazione.

Strutture dati elementari: Array, liste e alberi.

Alberi binari di ricerca.

Heap e code di priorità.

Tabelle Hash.

Ordinamento: Insertion sort, Merge sort, Heapsort, Quicksort.

Ordinamento in tempo lineare: counting sort, radix sort.

Programmazione dinamica.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati IV/ed. McGraw-Hill, 2023.

C. Demetrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati
(seconda edizione), McGraw-Hill, 2008.

La verifica dell'apprendimento avviene attraverso una prova scritta e una prova orale. La prova scritta ha durata di 3 ore ed è divisa in due parti. La prima parte consiste di 3 quesiti da svolgere in 30 minuti. Tali quesiti richiedono una risposta rapida su argomenti affrontati a lezione e mirano a verificare l'acquisizione dei concetti di base del corso. La seconda parte consiste di 4 esercizi, alcuni dei quali hanno lo scopo di accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso. La prova scritta può essere sostituita dal superamento di due prove intermedie, ciascuna delle quali ha una durata di 2 ore e consiste di 3 esercizi, aventi le stesse tipologie degli esercizi della seconda parte della prova scritta. Durante la prova scritta non è ammesso l'uso di libri, appunti, supporti elettronici.

Durante la prova orale lo studente deve dimostrare di conoscere gli argomenti svolti durante il corso e di saperli esporre in modo formale.

scritto e orale

Il/la docente ha il dovere di vigilare affinché siano rispettate le regole di autenticità e originalità delle prove d'esame. Di conseguenza, nei casi in cui vi sia il sospetto di un comportamento irregolare, l'esame può prevedere un ulteriore approfondimento, contestuale alla prova d'esame, che potrà essere realizzato anche in modalità differente rispetto alle modalità sopra riportate.

La gradazione del voto è stabilita come segue:

A. I punteggi nell'intervallo 18-22 verranno assegnati in presenza di:
- conoscenza sufficiente del programma
- limitata capacità di risolvere gli esercizi proposti all'esame
- sufficiente esposizione orale

B. I punteggi nell'intervallo 23-26 verranno assegnati in presenza di:
- buona conoscenza del programma
- discreta capacità di risolvere gli esercizi proposti all'esame
- adeguata esposizione orale

C. I punteggi nell'intervallo 27-30 verranno assegnati in presenza di:
- ottima conoscenza di tutte le tematiche del programma
- buona capacità di risolvere gli esercizi proposti all'esame
- esposizione orale pienamente appropriata

La lode verrà assegnata in presenza di un esame perfetto, in cui vengono fornite soluzioni ottimali per ciascun esercizio e a fronte di una esposizione orale brillante.

Insegnamento organizzato in lezioni frontali. Uso di Lavagna e tablet.