Algoritmi e strutture dati

A.A. 2021/2022
12
Crediti massimi
120
Ore totali
SSD
INF/01
Lingua
Italiano
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.
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.
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.
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.
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.
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Turni:
Introduzione - Lab turno A
Docente: Lonati Violetta
Introduzione - Lab turno B
Docente: Lonati Violetta
Parte 2 - Lab turno unico
Docente: Lonati Violetta
Docente/i
Ricevimento:
Da settembre 2021 il ricevimento studenti viene svolto sia in presenza, sia a distanza. Consultare la pagina http://pighizzini.di.unimi.it/ricevimento.html per dettagli e informazioni aggiornate