Algoritmi e strutture dati
A.A. 2024/2025
Obiettivi formativi
L'insegnamento è dedicato allo studio degli algoritmi e delle loro strutture dati. Obiettivo generale è la conoscenza delle strutture dati fondamentali e dei principali metodi usati per il progetto e l'analisi di algoritmi. Particolare attenzione è dedicata alla complessità computazionale delle procedure, ovvero alla valutazione della quantità di risorse (tempo di calcolo e spazio di memoria) richiesta dalla loro esecuzione. Un ulteriore obiettivo è quello di realizzare un'attività di implementazione degli algoritmi verificando il loro funzionamento su un calcolatore reale, mediante l'uso di linguaggi di programmazione e strumenti software che rendano chiaro e trasparente all'utente l'esecuzione delle procedure da parte della macchina.
Risultati apprendimento attesi
Lo studente imparerà a progettare e analizzare algoritmi per la soluzione di semplici problemi, scegliendo le strutture dati più idonee e valutando in modo opportuno le risorse di calcolo richieste dalle corrispondenti procedure. Dovrà inoltre apprendere a confrontare criticamente algoritmi diversi per la soluzione del medesimo problema, tenendo conto anche dei principali aspetti implementativi e realizzativi delle procedure considerate.
Periodo: Secondo 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
Secondo semestre
Programma
Il programma si divide in due parti: Teoria e Laboratorio
TEORIA
1) Introduzione.
Nozione intuitiva di problema e algoritmo. Progettazione e analisi di algoritmi. La complessità di un algoritmo, analisi nel caso peggiore e in quello medio.
2) Modello di calcolo.
Macchina ad accesso casuale (RAM). Sintassi e semantica del linguaggio RAM. Criteri di costo uniforme e logaritmico. Tempi di calcolo e spazio di memoria dei programmi RAM. Confronto tra tempi polinomiali ed esponenziali. Linguaggio ad alto livello (Algol-like).
3) Strutture dati elementari.
Vettori, liste, pile, code e loro implementazioni. Grafi orientati e non orientati, alberi, alberi ordinati, alberi binari e loro rappresentazioni in memoria.
4) Gestione della ricorsione.
Algoritmi e procedure ricorsive, esempi guida. Traduzione iterativa delle procedure ricorsive mediante gestione della pila delle chiamate. Algoritmi di attraversamento di alberi e grafi. Visite in profondità e in ampiezza. Calcolo delle distanze dei nodi da una sorgente.
5) Algoritmi di ordinamento.
Classificazione delle procedure di ordinamento e valutazione del numero minimo di confronti. Algoritmo di inserimento. La struttura dati di heap e l'algoritmo Heapsort. Quicksort.
6) Algoritmi e strutture dati per la manipolazione di insiemi.
Le strutture dati come algebre eterogenee e loro implementazione. Dizionari Tabelle Hash. Alberi di ricerca binaria. Alberi bilanciati: alberi 2-3, B-alberi. Operazioni "union-find" su partizioni: algoritmi basati su foreste con bilanciamento e compressione.
7) Metodi di progettazione.
Algoritmi Divide et Impera. Paradigma generale delle procedure "divide et impera" e analisi dei loro tempi di calcolo (Master Theorem). Esempi fondamentali: Mergesort, ricerca binaria, algoritmo divide et impera per il prodotto di interi.
Algoritmi di programmazione dinamica. Algoritmi per la chiusura transitiva di grafi e calcolo dei cammini minimi.
Algoritmi greedy. Sistemi di indipendenza, matrodi e teorema di Rado. Algoritmo di Kruskal. Algoritmi di Prim e Dijkstra.
LABORATORIO
1) Notazione asintotica: valutazione asintotica di successioni numeriche e somme, principali equazioni di ricorrenza.
2) Richiami di linguaggio C: struttura dei programmi, tipi predefiniti, espressioni, istruzioni di controllo, input e output, strutture dati (array, matrici, stringhe, records), funzioni e procedure ricorsive, puntatori, allocazione dinamica della memoria.
3) Algoritmi di ordinamento
4) Liste, pile e code
5) Grafi e alberi, procedure di attraversamento, alberi di ricerca bilanciati
6) Esempi di programmazione dinamica e di algoritmi greedy
TEORIA
1) Introduzione.
Nozione intuitiva di problema e algoritmo. Progettazione e analisi di algoritmi. La complessità di un algoritmo, analisi nel caso peggiore e in quello medio.
2) Modello di calcolo.
Macchina ad accesso casuale (RAM). Sintassi e semantica del linguaggio RAM. Criteri di costo uniforme e logaritmico. Tempi di calcolo e spazio di memoria dei programmi RAM. Confronto tra tempi polinomiali ed esponenziali. Linguaggio ad alto livello (Algol-like).
3) Strutture dati elementari.
Vettori, liste, pile, code e loro implementazioni. Grafi orientati e non orientati, alberi, alberi ordinati, alberi binari e loro rappresentazioni in memoria.
4) Gestione della ricorsione.
Algoritmi e procedure ricorsive, esempi guida. Traduzione iterativa delle procedure ricorsive mediante gestione della pila delle chiamate. Algoritmi di attraversamento di alberi e grafi. Visite in profondità e in ampiezza. Calcolo delle distanze dei nodi da una sorgente.
5) Algoritmi di ordinamento.
Classificazione delle procedure di ordinamento e valutazione del numero minimo di confronti. Algoritmo di inserimento. La struttura dati di heap e l'algoritmo Heapsort. Quicksort.
6) Algoritmi e strutture dati per la manipolazione di insiemi.
Le strutture dati come algebre eterogenee e loro implementazione. Dizionari Tabelle Hash. Alberi di ricerca binaria. Alberi bilanciati: alberi 2-3, B-alberi. Operazioni "union-find" su partizioni: algoritmi basati su foreste con bilanciamento e compressione.
7) Metodi di progettazione.
Algoritmi Divide et Impera. Paradigma generale delle procedure "divide et impera" e analisi dei loro tempi di calcolo (Master Theorem). Esempi fondamentali: Mergesort, ricerca binaria, algoritmo divide et impera per il prodotto di interi.
Algoritmi di programmazione dinamica. Algoritmi per la chiusura transitiva di grafi e calcolo dei cammini minimi.
Algoritmi greedy. Sistemi di indipendenza, matrodi e teorema di Rado. Algoritmo di Kruskal. Algoritmi di Prim e Dijkstra.
LABORATORIO
1) Notazione asintotica: valutazione asintotica di successioni numeriche e somme, principali equazioni di ricorrenza.
2) Richiami di linguaggio C: struttura dei programmi, tipi predefiniti, espressioni, istruzioni di controllo, input e output, strutture dati (array, matrici, stringhe, records), funzioni e procedure ricorsive, puntatori, allocazione dinamica della memoria.
3) Algoritmi di ordinamento
4) Liste, pile e code
5) Grafi e alberi, procedure di attraversamento, alberi di ricerca bilanciati
6) Esempi di programmazione dinamica e di algoritmi greedy
Prerequisiti
Le nozioni e i costrutti fondamentali di programmazione. Nozioni matematiche di base. Principali sequenze, serie numeriche e loro proprietà asintotiche.
Si consiglia di aver superato gli esami di almeno un insegnamento di Programmazione e uno di Analisi Matematica, tenuti nel primo biennio di un corso di laurea triennale.
Si consiglia di aver superato gli esami di almeno un insegnamento di Programmazione e uno di Analisi Matematica, tenuti nel primo biennio di un corso di laurea triennale.
Metodi didattici
L'insegnamento consiste di una parte di teoria e una di laboratorio.
La parte di teoria sarà svolta attraverso lezioni tradizionali, alcune delle quali dedicate alla soluzione di semplici esercizi.
La parte di laboratorio prevede sia lezioni tradizionali che attività di programmazione da svolgersi in un'aula informatizzata.
La parte di teoria sarà svolta attraverso lezioni tradizionali, alcune delle quali dedicate alla soluzione di semplici esercizi.
La parte di laboratorio prevede sia lezioni tradizionali che attività di programmazione da svolgersi in un'aula informatizzata.
Materiale di riferimento
TEORIA
- Pagina web: http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
dove sarà riportato anche il link alla pagina MyAriel del corso per il nuovo anno accademico.
- Dispense:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Dispense del corso di Algoritmi,
Corso di Laurea Triennale in Matematica, a.a. 2018/19, Università degli Studi di Milano, Marzo 2019.
Reperibili al sito precedente.
- Testi di riferimento:
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati,
3/ed, McGraw-Hill Italia, 2010 (oppure edizione in inglese, 2009).
2) A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley Publishing Company, 1974.
LABORATORIO
- Pagina web (di prossima apertura):
https://homes.di.unimi.it/cordone/courses/2024-algo/2024-algo.html
- Testi di riferimento:
1) K. N. King: Programmazione in C (C Programming: A Modern Approach (second edition)),
W. W. Norton & Company, 2008.
2) Al Kelley, Ira Pohl : C, Didattica e Programmazione (A book on C, 4th edition). Pearson, Italia, 2004.
- Pagina web: http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
dove sarà riportato anche il link alla pagina MyAriel del corso per il nuovo anno accademico.
- Dispense:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Dispense del corso di Algoritmi,
Corso di Laurea Triennale in Matematica, a.a. 2018/19, Università degli Studi di Milano, Marzo 2019.
Reperibili al sito precedente.
- Testi di riferimento:
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati,
3/ed, McGraw-Hill Italia, 2010 (oppure edizione in inglese, 2009).
2) A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley Publishing Company, 1974.
LABORATORIO
- Pagina web (di prossima apertura):
https://homes.di.unimi.it/cordone/courses/2024-algo/2024-algo.html
- Testi di riferimento:
1) K. N. King: Programmazione in C (C Programming: A Modern Approach (second edition)),
W. W. Norton & Company, 2008.
2) Al Kelley, Ira Pohl : C, Didattica e Programmazione (A book on C, 4th edition). Pearson, Italia, 2004.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova di laboratorio e di una prova orale.
- La prova di laboratorio prevede la presentazione di un progetto individuale, da svolgere a casa, che consiste nella realizzazione di un programma in linguaggio C per la soluzione di un problema assegnato, corredato da una relazione scritta sugli algoritmi, le strutture dati usate, contenente una valutazione dei tempi di calcolo e dello spazio di memoria richiesti. Le specifiche dei problemi proposti, le modalità e i tempi di presentazione dei progetti nei vari appelli vengono pubblicati sul sito di Laboratorio del presente corso circa due settimane prima del termine di consegna degli stessi progetti, il quale termine a sua volta scade di norma una settimana prima dello svolgimento della prova orale. La prova di laboratorio mira a valutare la capacità dello studente di implementare e sviluppare gli algoritmi e le strutture dati presentati a lezione. Per il superamento della prova è indispensabile che il programma sia corretto e la relazione descriva adeguatamente le caratteristiche dell'implementazione realizzata. La valutazione terrà conto dell'efficienza delle procedure e delle scelte implementative adottate.
- Alla prova orale accedono solo gli studenti che hanno superato la prova di laboratorio nello stesso appello o in un appello tenutosi nei sei mesi precedenti. Durante la prova orale, oltre a discutere il progetto presentato, i candidati saranno tenuti a illustrare argomenti e tematiche del programma di teoria. Ai fini della valutazione sono ritenuti rilevanti la capacità di descrivere ad alto livello gli algoritmi e le strutture dati elencati nel programma, la conoscenza dei metodi di progettazione e analisi delle procedure presentate a lezione e delle tecniche di valutazione dei tempi di calcolo e dello spazio di memoria relativi.
L'esame si intende superato se entrambe le prove sono giudicate sufficienti. Il voto è espresso in trentesimi, sarà la media delle valutazioni ottenute nelle due prove e verrà comunicato immediatamente al termine della prova orale.
- La prova di laboratorio prevede la presentazione di un progetto individuale, da svolgere a casa, che consiste nella realizzazione di un programma in linguaggio C per la soluzione di un problema assegnato, corredato da una relazione scritta sugli algoritmi, le strutture dati usate, contenente una valutazione dei tempi di calcolo e dello spazio di memoria richiesti. Le specifiche dei problemi proposti, le modalità e i tempi di presentazione dei progetti nei vari appelli vengono pubblicati sul sito di Laboratorio del presente corso circa due settimane prima del termine di consegna degli stessi progetti, il quale termine a sua volta scade di norma una settimana prima dello svolgimento della prova orale. La prova di laboratorio mira a valutare la capacità dello studente di implementare e sviluppare gli algoritmi e le strutture dati presentati a lezione. Per il superamento della prova è indispensabile che il programma sia corretto e la relazione descriva adeguatamente le caratteristiche dell'implementazione realizzata. La valutazione terrà conto dell'efficienza delle procedure e delle scelte implementative adottate.
- Alla prova orale accedono solo gli studenti che hanno superato la prova di laboratorio nello stesso appello o in un appello tenutosi nei sei mesi precedenti. Durante la prova orale, oltre a discutere il progetto presentato, i candidati saranno tenuti a illustrare argomenti e tematiche del programma di teoria. Ai fini della valutazione sono ritenuti rilevanti la capacità di descrivere ad alto livello gli algoritmi e le strutture dati elencati nel programma, la conoscenza dei metodi di progettazione e analisi delle procedure presentate a lezione e delle tecniche di valutazione dei tempi di calcolo e dello spazio di memoria relativi.
L'esame si intende superato se entrambe le prove sono giudicate sufficienti. Il voto è espresso in trentesimi, sarà la media delle valutazioni ottenute nelle due prove e verrà comunicato immediatamente al termine della prova orale.
INF/01 - INFORMATICA - CFU: 9
Esercitazioni: 48 ore
Lezioni: 45 ore
Lezioni: 45 ore
Docenti:
Cordone Roberto, Goldwurm Massimiliano
Turni:
Docente/i
Ricevimento:
martedì dalle 14:30 alle 16:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).