Algoritmi

A.A. 2018/2019
Insegnamento per
9
Crediti massimi
89
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Il corso consiste di una parte di teoria e una di laboratorio. Obiettivo della prima parte è quello di presentare le strutture dati di base e gli algoritmi principali ponendo l'enfasi sui metodi di progettazione e sull'analisi di complessità delle procedure, inclusa la valutazione del tempo di calcolo e dello spazio di memoria richiesti. La parte di laboratorio è invece dedicata all'implementazione in linguaggio C delle principali strutture dati e dei principali algoritmi presentati a lezione.
La conoscenza dei metodi e delle tecniche di base per la progettazione e l'analisi di algoritmi è lo scopo principale del corso. Si vuole in particolare promuovere la capacità di progettare e analizzare soluzioni algoritmiche per un problema assegnato, e di realizzare in linguaggio C le implementazioni delle corrispondenti procedure e strutture dati.

Struttura insegnamento e programma

Edizione attiva
Responsabile
INF/01 - INFORMATICA - CFU: 9
Esercitazioni: 44 ore
Lezioni: 45 ore
Programma
Programma di 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) e corrispondente traduzione in linguaggio RAM.
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. Procedure ricorsive, loro traduzione iterativa mediante gestione della pila delle chiamate. Algoritmi di attraversamento di alberi e grafi. Visite in profondità e in ampiezza.
4) 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.
5) Strutture dati evolute.
Le strutture dati come algebre eterogenee e loro implementazione. Alberi di ricerca binaria, B-alberi. Operazioni "union-find" su partizioni: algoritmi basati su foreste con bilanciamento e compressione.
6) Metodi di progettazione.
Algoritmi Divide et Impera e analisi dei loro tempi di calcolo (Master Theorem). Mergesort, ricerca binaria, algoritmo divide et impera per il prodotto di interi.
Algoritmi di programmazione dinamica: chiusura transitiva di grafi e calcolo dei cammini minimi.
Algoritmi greedy. Algoritmo di Kruskal. Algoritmi di Prim e Dijkstra.

Programma di Laboratorio

Notazione asintotica. Valutazione asintotica di successioni numeriche e di somme. Principali equazioni di ricorrenza.
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.
Implementazione di strutture dati e algoritmi: procedure di ordinamento, liste, pile e code, grafi e alberi, procedure di attraversamento di grafi, alberi di ricerca bilanciati, esempi di programmazione dinamica e di algoritmi greedy.
Propedeuticità
Programmazione 1, Analisi matematica 1.
Prerequisiti e modalità di esame
Prerequisiti: Le nozioni e i costrutti fondamentali di programmazione. Nozioni matematiche di base. Principali sequenze, serie numeriche e loro proprietà asintotiche.

Modalità di esame: presentazione di un progetto per la parte di laboratorio e una prova orale per la parte di teoria. Il progetto consiste nella realizzazione di programma per la risoluzione di un problema assegnato da svolgere a casa. Le specifiche dei progetti proposti nei vari appelli saranno pubblicate sulla pagina web di laboratorio.
Metodi didattici
Il corso sarà erogato mediante lezioni o esercitazioni tradizionali, la frequenza è consigliata.
Materiale didattico e bibliografia
Teoria
Dispense
- A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso di Algoritmi e Strutture Dati tenuto nell'ambito del corso di laurea di Informatica), Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Ottobre 2008. Scaricabili da
http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)

Testi di riferimento:
- 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).
- A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, 1974.

Laboratorio
Testi di riferimento:
- K. N. King: Programmazione in C (C Programming: A Modern Approach (second edition)), W. W. Norton & Company, 2008.
- Al Kelley, Ira Pohl : C, Didattica e Programmazione (A book on C, 4th edition). Pearson, Italia, 2004.
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano
Ricevimento:
martedì dalle 14:30 alle 17:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).