Algoritmi e strutture dati
A.A. 2021/2022
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 C.
In particolare verranno trattati i seguenti argomenti:
Fondamenti di C:
- Compilatore gcc
- Tipi, operatori, selezione e iterazione
- Input/output
- Dati aggregati: array, matrici, stringhe e strutture
- Funzioni e ricorsione
Elementi avanzati di C:
- Puntatori
- Allocazione dinamica della memoria
- Struttura dei programmi, suddivisione in più file, preprocessore
Implementazione di strutture dati e algoritmi
- Algoritmi di ordinamento
- Liste, pile e code
- Grafi: visita in ampiezza e in profondità, componenti connesse
- Alberi di ricerca e bilanciamento
- Programmazione dinamica
- Heap e code di priorità
- Algoritmi greedy
- Paradigma client-interfaccia-implementazione per la realizzazione di strutture dati
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 C.
In particolare verranno trattati i seguenti argomenti:
Fondamenti di C:
- Compilatore gcc
- Tipi, operatori, selezione e iterazione
- Input/output
- Dati aggregati: array, matrici, stringhe e strutture
- Funzioni e ricorsione
Elementi avanzati di C:
- Puntatori
- Allocazione dinamica della memoria
- Struttura dei programmi, suddivisione in più file, preprocessore
Implementazione di strutture dati e algoritmi
- Algoritmi di ordinamento
- Liste, pile e code
- Grafi: visita in ampiezza e in profondità, componenti connesse
- Alberi di ricerca e bilanciamento
- Programmazione dinamica
- Heap e code di priorità
- Algoritmi greedy
- Paradigma client-interfaccia-implementazione per la realizzazione di strutture dati
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 a tutte le lezioni e 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.
Per la parte relativa al linguaggio C il riferimento principale è:
B. Kernighan, D. M. Ritchie, Il linguaggio C, Pearson Education Italia, 2019
Ulteriore riferimento consigliato:
R. Sedgewick, Algoritmi in C, Pearson Education Italia, 2002
Ulteriore materiale integrativo, preparato dai docenti, viene reso disponibile sul sito web dell'insegnamento.
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.
Per la parte relativa al linguaggio C il riferimento principale è:
B. Kernighan, D. M. Ritchie, Il linguaggio C, Pearson Education Italia, 2019
Ulteriore riferimento consigliato:
R. Sedgewick, Algoritmi in C, Pearson Education Italia, 2002
Ulteriore materiale integrativo, preparato dai docenti, viene reso disponibile sul sito web dell'insegnamento.
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 C 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 C 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 turno unico
Docente:
Lonati ViolettaDocente/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