Algoritmi e strutture dati
A.A. 2023/2024
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 può essere seguito come corso singolo.
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 nel linguaggio di programmazione 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 nel linguaggio di programmazione 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://myariel.unimi.it/course/view.php?id=1221
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://myariel.unimi.it/course/view.php?id=1221
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova scritta, di un progetto 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.
Il progetto mira ad approfondire gli aspetti pratici di uno o più argomenti trattati nell'insegnamento. Viene richiesto di progettare e realizzare un programma, secondo specifiche assegnate, e di descrivere e giustificare le scelte progettuali fatte, in una relazione scritta seguita da un'eventuale discussione orale, che sarà obbligatoria nel caso in cui la relazione presentasse aspetti incompleti o poco chiari.
Le specifiche del progetto, che deve essere svolto individualmente, vengono fornite al termine delle lezioni di laboratorio. Il progetto deve essere consegnato durante entro le date che saranno comunicate attraverso il sito web dell'insegnamento e, al più tardi, entro il 15 settembre 2024.
L'esame si conclude con la prova orale, alla quale si accede dopo il superamento della prova scritta e del progetto. La prova verte sulla discussione di alcuni argomenti trattati nell'insegnamento.
Nella valutazione delle prove si terrà conto dei seguenti parametri: grado di conoscenza degli argomenti, capacità di applicare le conoscenze, capacità di ragionamento critico, chiarezza espositiva e proprietà di linguaggio. Oltre ai parametri precedenti, la valutazione del progetto terrà conto anche della capacità di applicare le conoscenze alla risoluzione di problemi concreti mediante lo sviluppo di programmi.
Al termine della prova orale viene formulata la valutazione complessiva, espressa in trentesimi, tenendo conto in modo paritetico delle valutazioni delle singole parti.
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.
Il progetto mira ad approfondire gli aspetti pratici di uno o più argomenti trattati nell'insegnamento. Viene richiesto di progettare e realizzare un programma, secondo specifiche assegnate, e di descrivere e giustificare le scelte progettuali fatte, in una relazione scritta seguita da un'eventuale discussione orale, che sarà obbligatoria nel caso in cui la relazione presentasse aspetti incompleti o poco chiari.
Le specifiche del progetto, che deve essere svolto individualmente, vengono fornite al termine delle lezioni di laboratorio. Il progetto deve essere consegnato durante entro le date che saranno comunicate attraverso il sito web dell'insegnamento e, al più tardi, entro il 15 settembre 2024.
L'esame si conclude con la prova orale, alla quale si accede dopo il superamento della prova scritta e del progetto. La prova verte sulla discussione di alcuni argomenti trattati nell'insegnamento.
Nella valutazione delle prove si terrà conto dei seguenti parametri: grado di conoscenza degli argomenti, capacità di applicare le conoscenze, capacità di ragionamento critico, chiarezza espositiva e proprietà di linguaggio. Oltre ai parametri precedenti, la valutazione del progetto terrà conto anche della capacità di applicare le conoscenze alla risoluzione di problemi concreti mediante lo sviluppo di programmi.
Al termine della prova orale viene formulata la valutazione complessiva, espressa in trentesimi, tenendo conto in modo paritetico delle valutazioni delle singole parti.
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Lezioni: 72 ore
Docenti:
Lonati Violetta, Pighizzini Giovanni
Turni:
Docenti:
Lonati Violetta, Pighizzini Giovanni
Introduzione lab. - turno A
Docente:
Lonati ViolettaIntroduzione lab. - turno B
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