Anno accademico 2023-2024

ALGORITMI E STRUTTURE DATI E LABORATORIO

Docenti

Carla Piazza
Gabriele Puppis
Alessandro Giuseppe Privitera
Anno di corso
2
Totale crediti
12
Periodo didattico
Annualità
Tipologia
Base
Prerequisiti. È fondamentale che lo studente abbia buona padronanza con i contenuti dei corsi del I anno del corso di Laurea Triennale, con particolare riferimento ai corsi di Matematica Discreta (Elementi di Matematica e Algebra Lineare per il corso di laurea IBML), Analisi Matematica, Programmazione e Laboratorio.
Metodi didattici. Il corso consta di lezioni frontali, esercitazioni con il docente e lezioni di laboratorio. Nella pagina e-learning del corso sono reperibili tutte le informazioni utili ed esercizi aggiuntivi.
Modalità di verifica. L’esame consta di una parte scritta ed una orale oltre che di una prova di laboratorio. La prova scritta è volta prevalentemente a valutare le competenze acquisite nella risoluzione algoritmica di problemi e nella formalizzazione di tali soluzioni. La prova orale è volta prevalentemente a valutare la conoscenza delle strutture dati, degli algoritmi e delle tecniche di analisi presentate durante il corso e la capacità di ragionamento.

Relativamente ai criteri di valutazione facciamo riferimento al documento: https://www.uniud.it/it/didattica/corsi/area-scientifica/scienze-matematiche-informatiche-multimediali-fisiche/laurea/informatica/studiare/criteri.pdf

Obiettivi formativi
Obiettivi Formativi Specifici.

Indice:

Fondamenti

Ruolo degli algoritmi

Progettazione di algoritmi

Correttezza degli algoritmi

Complessità computazionale

Strutture Dati di Base e relativi Algoritmi

Vettori, Heap, Liste, Pile, Code, Alberi Binari, Tabelle di Hash, e varianti.

Algoritmi per l’ordinamento, la ricerca, l’inserimento e la cancellazione in strutture dati di base

Dimostrazione della correttezza di tali algoritmi

Valutazione della complessità computazionale di tali algoritmi

Strutture Dati Avanzate, Algoritmi e Tecniche Avanzate di progettazione

Bilanciamento di alberi binari con algoritmi di ricerca/inserimento/cancellazione 

B-alberi con algoritmi di ricerca/inserimento/cancellazione

Strutture Dati per insiemi disgiunti con operazioni Make, Union, Find e relative euristiche

Grafi e algoritmi di base sui grafi

Alberi minimi di copertura per grafi pesati

Cammini minimi in grafi pesati

Dimostrazione della correttezza e valutazione della complessità di tali algoritmi

CAPACITA’ RELATIVE ALLE DISCIPLINE

Lo/la studente/ssa dovrà:

1.1. Conoscenza e capacità di comprensione

Conoscere i concetti base relativi alle strutture dati statiche e dinamiche e alla progettazione di algoritmi

Conoscere un linguaggio formale per la descrizione degli algoritmi

Conoscere gli strumenti matematici per la valutazione della complessità computazionale

Conoscere le strutture dati e gli algoritmi presentati a lezione e le relative complessità spaziali e temporali

1.2 Capacità di applicare conoscenza e comprensione

Saper implementare e testare gli algoritmi visti a lezione nei linguaggi di programmazione più comuni

Saper utilizzare le strutture dati e gli algoritmi presentati nel corso per progettare nuovi algoritmi in grado di risolvere specifici problemi

Saper dimostrare la correttezza e valutare la complessità computazionale di tali algoritmi

CAPACITA’ TRASVERSALI / SOFT SKILLS

Lo/la studente/ssa dovrà:

2.1 Autonomia di giudizio

Saper valutare quali strutture dati, quali algoritmi e quali tecniche di progettazione utilizzare per fornire una soluzione efficiente ad un dato problema algoritmico

Saper scegliere tra più possibili soluzioni quella computazionalmente più efficiente

Saper combinare/estendere algoritmi esistenti per risolvere uno specifico problema

Saper dimostrare o confutare la correttezza e valutare la complessità computazionale di algoritmi da lui/lei progettati o reperiti in letteratura

Saper selezionare il linguaggio di programmazione e le librerie più adatte per l’implementazione degli algoritmi

Saper testare le implementazioni.

2.2 Abilità comunicative.

Essere in grado di motivare, le scelte effettuate in termini di strutture dati e algoritmi per la risoluzione di un dato problema.

Essere in grado di reperire le eventuali informazioni aggiuntive necessarie per la progettazione di un algoritmo efficiente.

2.3 Capacità di apprendimento

Saper reperire ed utilizzare risorse informatiche e scientifiche per l’approfondimento autonomo delle tematiche studiate a lezione

Saper affrontare lo studio di nuove problematiche di natura algoritmica

Saper individuare nuovi strumenti per lo sviluppo e l’implementazione di strutture dati e algoritmi

Si rimanda anche alle pagine:

– Laurea in Informatica “https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/L-informatica/all-B2” https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/L-informatica/all-B2

– Laurea in Internet of things, biga data, machine learning “https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/l-internet-things-big-data-machine-learning/all-B2” https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/l-internet-things-big-data-machine-learning/all-B2

Contenuti
Il corso si propone di introdurre ai fondamenti della teoria degli algoritmi, delle strutture dati e all’analisi della complessità computazionale di programmi. Il principale obiettivo del corso è familiarizzare lo studente con le principali problematiche e tecniche relative al disegno e alla progettazione di algoritmi. Ci si propone inoltre di introdurre i metodi di base utilizzati per stabilire la complessità di programmi e i criteri utilizzati per scegliere e progettare strutture dati.
Testi di riferimento
1. Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Fourth edition, 2022.

2. Altri testi utili:

1. A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Città Studi Edizioni, 2010.

2. C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.

3. P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.

4. Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.

5. Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.