Algoritmi e strutture dati
A.A. 2022/2023
Obiettivi formativi
L'insegnamento ha lo scopo di introdurre i concetti fondamentali riguardanti il progetto e l'analisi di algoritmi e delle strutture dati che essi utilizzano, illustrando le principali tecniche di progettazione e alcune strutture dati fondamentali, insieme all'analisi della complessità computazionale.
Risultati apprendimento attesi
Lo studente dovrà essere in grado di applicare i concetti e e le tecniche presentati nell'insegnamento al progetto di algoritmi per la soluzione di semplici problemi, alla scelta delle strutture dati adeguate, alla stima della complessità computazionale. Lo studente dovrà inoltre essere in grado di presentare in maniera efficace problemi e relativi algoritmi risolutivi, sapendo confrontare in maniera critica differenti soluzioni algoritmiche di un medesimo problema.
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
L'insegnamento si articola in una parte di teoria e in una parte di laboratorio.
La parte di teoria verte sui seguenti argomenti:
- Concetto di algoritmo. Algoritmi e programmi. Notazioni asintotiche. Stime di complessità di algoritmi.
- La macchina RAM.
- Strutture dati fondamentali: array, liste, pile, code, alberi.
- Ricerca sequenziale e ricerca binaria. Strutture ad albero per ricerche.
- Tecniche hash.
- Algoritmi di ordinamento elementari.
- Algoritmi di ordinamento evoluti: mergesort, heapsort, quicksort.
- Tecniche di ordinamento non basate su confronti.
- Tecniche algoritmiche: divide-et-impera, programmazione dinamica, greedy.
- Grafi.
- Problemi e algoritmi fondamentali su grafi: albero di ricoprimento minimo, cammini minimi in grafi.
- Problemi "difficili": algoritmi non deterministici e introduzione alla NP-competezza.
Nella parte di laboratorio lo studente dovrà familiarizzare con le tecniche algoritmiche attraverso l'implementazione concreta di algoritmi in un linguaggio di programmazione reale, il linguaggio Go.
In particolare verranno trattati i seguenti argomenti:
- Algoritmi di ordinamento
- Liste, pile e code
- Paradigma client-interfaccia-implementazione per la realizzazione di strutture dati
- Grafi
- Alberi di ricerca e bilanciamento
- Programmazione dinamica
- Heap e code con priorità
- Algoritmi greedy
Un elenco dettagliato degli argomenti trattati, lezione per lezione, viene pubblicato e aggiornato sul sito web dell'insegnamento.
La parte di teoria verte sui seguenti argomenti:
- Concetto di algoritmo. Algoritmi e programmi. Notazioni asintotiche. Stime di complessità di algoritmi.
- La macchina RAM.
- Strutture dati fondamentali: array, liste, pile, code, alberi.
- Ricerca sequenziale e ricerca binaria. Strutture ad albero per ricerche.
- Tecniche hash.
- Algoritmi di ordinamento elementari.
- Algoritmi di ordinamento evoluti: mergesort, heapsort, quicksort.
- Tecniche di ordinamento non basate su confronti.
- Tecniche algoritmiche: divide-et-impera, programmazione dinamica, greedy.
- Grafi.
- Problemi e algoritmi fondamentali su grafi: albero di ricoprimento minimo, cammini minimi in grafi.
- Problemi "difficili": algoritmi non deterministici e introduzione alla NP-competezza.
Nella parte di laboratorio lo studente dovrà familiarizzare con le tecniche algoritmiche attraverso l'implementazione concreta di algoritmi in un linguaggio di programmazione reale, il linguaggio Go.
In particolare verranno trattati i seguenti argomenti:
- Algoritmi di ordinamento
- Liste, pile e code
- Paradigma client-interfaccia-implementazione per la realizzazione di strutture dati
- Grafi
- Alberi di ricerca e bilanciamento
- Programmazione dinamica
- Heap e code con priorità
- Algoritmi greedy
Un elenco dettagliato degli argomenti trattati, lezione per lezione, viene pubblicato e aggiornato sul sito web dell'insegnamento.
Prerequisiti
Saper scrivere e mettere a punto programmi che usano i costrutti fondamentali della programmazione imperativa; conoscere e sapere utilizzare proficuamente almeno un linguaggio di programmazione imperativo.
Conoscere le principali funzioni matematiche quali polinomi, logaritmi ed esponenziali, le principali notazione asintotiche e le loro proprietà.
Il superamento dell'esame di Programmazione è propedeutico all'insegnamento di Algoritmi e Strutture Dati. E' inoltre fortemente consigliato il superamento di esami di Matematica del Continuo e Matematica del Discreto.
Conoscere le principali funzioni matematiche quali polinomi, logaritmi ed esponenziali, le principali notazione asintotiche e le loro proprietà.
Il superamento dell'esame di Programmazione è propedeutico all'insegnamento di Algoritmi e Strutture Dati. E' inoltre fortemente consigliato il superamento di esami di Matematica del Continuo e Matematica del Discreto.
Metodi didattici
La parte di teoria viene svolta mediante lezioni frontali. La parte di laboratorio alterna lezioni frontali a esercitazioni e attivita' pratiche svolte individualmente o in piccoli gruppi. E' fortemente raccomandata la frequenza sia a tutte lezioni che a tutte le attività di laboratorio.
Materiale di riferimento
Il testo di riferimento:
C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2008.
Per alcuni argomenti si utilizzano le dispense:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Ottobre 2011.
Ulteriore materiale integrativo, preparato dai docenti, viene reso disponibile sul sito web dell'insegnamento.
Sito web dell'insegnamento:
https://gpighizziniasd.ariel.ctu.unimi.it/
C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2008.
Per alcuni argomenti si utilizzano le dispense:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Ottobre 2011.
Ulteriore materiale integrativo, preparato dai docenti, viene reso disponibile sul sito web dell'insegnamento.
Sito web dell'insegnamento:
https://gpighizziniasd.ariel.ctu.unimi.it/
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova scritta, di una prova di laboratorio e di una prova orale.
Nella prova scritta, della durata di due ore, viene richiesta la risoluzione di alcuni esercizi, basati su domande a risposta aperta, e di un problema in cui viene chiesto di applicare una delle tecniche algoritmiche presentate nell'insegnamento.
Nella prova di laboratorio, della durata di 2 ore e mezza, sono assegnati esercizi che richiedono 1) di realizzare (oppure comprendere e modificare) programmi in Go che elaborano e utilizzano strutture di dati e 2) di progettare e implementare soluzioni algoritmiche per problemi specificati.
L'esame si conclude con la prova orale, alla quale si accede dopo il superamento della prova scritta e di laboratorio, che verte sulla discussione di alcuni argomenti trattati nell'insegnamento.
Al termine della prova orale viene formulata la valutazione complessiva, espressa in trentesimi, tenendo conto dei seguenti parametri: grado di conoscenza degli argomenti, capacità di applicare le conoscenze alla risoluzione di problemi concreti, capacità di ragionamento critico, chiarezza espositiva e proprietà di linguaggio.
Nella prova scritta, della durata di due ore, viene richiesta la risoluzione di alcuni esercizi, basati su domande a risposta aperta, e di un problema in cui viene chiesto di applicare una delle tecniche algoritmiche presentate nell'insegnamento.
Nella prova di laboratorio, della durata di 2 ore e mezza, sono assegnati esercizi che richiedono 1) di realizzare (oppure comprendere e modificare) programmi in Go che elaborano e utilizzano strutture di dati e 2) di progettare e implementare soluzioni algoritmiche per problemi specificati.
L'esame si conclude con la prova orale, alla quale si accede dopo il superamento della prova scritta e di laboratorio, che verte sulla discussione di alcuni argomenti trattati nell'insegnamento.
Al termine della prova orale viene formulata la valutazione complessiva, espressa in trentesimi, tenendo conto dei seguenti parametri: grado di conoscenza degli argomenti, capacità di applicare le conoscenze alla risoluzione di problemi concreti, capacità di ragionamento critico, chiarezza espositiva e proprietà di linguaggio.
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Lezioni: 72 ore
Docenti:
Lonati Violetta, Pighizzini Giovanni
Turni:
Docente:
Pighizzini Giovanni
Introduzione lab. - turno A
Docente:
Lonati ViolettaIntroduzione lab. - turno B
Docente:
Lonati ViolettaParte 2 lab.
Docente:
Lonati ViolettaSiti didattici
Docente/i
Ricevimento:
Il ricevimento studenti viene svolto sia in presenza (modalità preferibile), sia a distanza. Consultare la pagina http://pighizzini.di.unimi.it/ricevimento.html per dettagli e informazioni aggiornate