Algoritmi e strutture dati
A.A. 2025/2026
Obiettivi formativi
L'insegnamento ha l'obiettivo di introdurre i concetti fondamentali relativi alla progettazione e analisi di algoritmi e delle strutture dati che questi utilizzano. L'insegnamento illustrerà le principali strutture dati e si focalizzerà su alcuni algoritmi specifici, studiandone anche la complessità computazionale.
Risultati apprendimento attesi
Lo studente dovrà conoscere e saper utilizzare le strutture dati e gli algoritmi di base presentati nell'insegnamento. Lo studente dovrà inoltre essere in grado di proporre soluzioni algoritmiche adeguate, utilizzando le strutture dati più appropriate, a problemi semplici, stimandone la complessità computazionale.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
1- Concetti fondamentali
Concetti di problema e di algoritmo; complessità computazionale di algoritmi, notazioni asintotiche; equazioni di ricorrenza
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, implementazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi AVL, alberi B
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità; minimum cost spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort (e sua analisi); sorting in tempo lineare
Concetti di problema e di algoritmo; complessità computazionale di algoritmi, notazioni asintotiche; equazioni di ricorrenza
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, implementazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi AVL, alberi B
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità; minimum cost spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort (e sua analisi); sorting in tempo lineare
Prerequisiti
E' richiesta la conoscenza dei concetti e costrutti fondamentali della programmazione imperativa.
E' richiesta la conoscenza delle principali funzioni matematiche e delle principali notazioni asintotiche.
Il superamento dell'esame di Programmazione è propedeutico all'insegnamento di Algoritmi e Strutture Dati. E' consigliato il superamento dell'esame di Matematica del Continuo.
E' richiesta la conoscenza delle principali funzioni matematiche e delle principali notazioni asintotiche.
Il superamento dell'esame di Programmazione è propedeutico all'insegnamento di Algoritmi e Strutture Dati. E' consigliato il superamento dell'esame di Matematica del Continuo.
Metodi didattici
Lezioni frontali
Materiale di riferimento
Sito web:
https://myariel.unimi.it/course/view.php?id=826
dove verranno messi a disposizionegli appunti delle lezioni
https://myariel.unimi.it/course/view.php?id=826
dove verranno messi a disposizionegli appunti delle lezioni
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in una prova scritta della durata di circa 2.30 ore, che include domande a risposta aperta ed esercizi.
La prova è volta a valutare la comprensione e l'apprendimento degli algoritmi e strutture dati studiati dall'insegnamento. La prova ha inoltre l'obiettivo di valutare la capacità di applicazione e utilizzo delle strutture dati e degli algoritmi studiati alla risoluzione di problemi semplici. Non è consentito consultare appunti o altro materiale durante la prova.
La valutazione della prova è espressa in trentesimi.
I risultati della prova vengono resi disponibili sulla pagina myAriel dell'insegnamento.
La prova è volta a valutare la comprensione e l'apprendimento degli algoritmi e strutture dati studiati dall'insegnamento. La prova ha inoltre l'obiettivo di valutare la capacità di applicazione e utilizzo delle strutture dati e degli algoritmi studiati alla risoluzione di problemi semplici. Non è consentito consultare appunti o altro materiale durante la prova.
La valutazione della prova è espressa in trentesimi.
I risultati della prova vengono resi disponibili sulla pagina myAriel dell'insegnamento.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente:
Foresti Sara
Turni:
Turno
Docente:
Foresti SaraDocente/i