Algoritmi e strutture dati

Corso di Algoritmi e strutture dati

Corso di laurea triennale di Informatica
Università degli Studi di Milano
Anno accademico 2011/2012

Turno unico diurno - Docenti: M. Goldwurm, V. Lonati (Laboratorio)

Fondamentale del secondo anno per la laurea triennale di Informatica
(Corso di 12 crediti)
Propedeuticità: i corsi di Programmazione, Matematica del discreto (consigliata), Matematica del continuo.

1. Programma del corso	5. Modalità d'esame
2. Corso di Laboratorio (V. Lonati).	6. Orario lezioni e ricevimento
3. Dispense e testi consigliati	7. Prossimi appelli
4. Esercizi e temi d'esame	8. Date degli appelli d'esame per l'a.a. 2011/2012

Risultati dell'ultima prova scritta
Ultimi temi d'esame (file ps , file pdf )

Modalità d'esame per il corso da 18 crediti (per gli studenti del precedente ordinamento)

Complementare per la laurea triennale di Informatica per le Telecomunicazioni
(Corso di 6 crediti)

1A. Programma (corso di 6 crediti)

2A. Modalità d'esame (corso di 6 crediti)

PROGRAMMA DEL CORSO

Prerequisiti svolti nei corsi del I anno: i principali costrutti di programmazione, le relazioni di equivalenza e di ordine, la notazione asintotica e le relative proprietà principali.

Introduzione
Nozione intuitiva di problema e algoritmo. Sintesi e analisi di algoritmi. La complessità di un algoritmo, analisi nel caso peggiore e nel caso medio. La classificazione dei problemi.
Modello di calcolo
Macchina ad accesso casuale (RAM). Criteri di costo uniforme e logaritmico. Schema di linguaggio ad alto livello e sua esecuzione sulla macchina RAM.
Strutture dati elementari
Strutture elementari: vettori, liste, pile, code e relative operazioni fondamentali. Esecuzione iterativa delle chiamate ricorsive: record di attivazione delle chiamate, loro gestione mediante una pila e analisi dello spazio di memoria utilizzato.
Grafi diretti e indiretti, grafi non etichettati, alberi, alberi immersi nel piano, alberi binari. Rappresentazione in memoria di alberi e grafi. Metodi di esplorazione di alberi: attraversamenti in preordine, postordine e in ordine simmetrico. Algoritmi di attraversamento di grafi in profondità e in ampiezza. Procedure di calcolo delle distanze dei nodi da una sorgente.
Algoritmi di ordinamento
Generalità sul problema dell'ordinamento. Ordinamento interno per confronti: numero minimo di confronti necessari per ordinare n elementi. L'algoritmo di ordinamento mediante inserimento. La struttura di heap e il relativo algoritmo di costruzione. L'algoritmo Heapsort. L'algoritmo Quicksort.
Algoritmi e strutture per la manipolazione di insiemi
Strutture di dati astratti e implementazione corretta. Le strutture elementari come strutture di dati astratti. Operazioni fondamentali sugli insiemi e le strutture dati associate.
Tabelle hash. Ricerca binaria. Alberi di ricerca binaria. Alberi bilanciati: alberi 2-3 e B-alberi.
Operazioni "union-find" su partizioni: algoritmi basati su alberi con bilanciamento e compressione.
Tecniche di progetto
Algoritmi "Divide et Impera": lo schema generale e la relativa analisi dei tempi di calcolo. L'algoritmo per il prodotto di interi. L'algoritmo Mergesort.
Programmazione dinamica. Algoritmo di calcolo della chiusura transitiva di un grafo. Procedure per determinare le lunghezze minime di cammino tra coppie di nodi.
Gli algoritmi Greedy: descrizione generale e analisi dei tempi di calcolo. I sistemi di indipendenza, i matroidi e il teorema di Rado. L'algoritmo di Kruskal. Gli algoritmi di Prim e Dijkstra.
Classificazione di problemi
Cenni alle classi P, NP e ai problemi NP-completi.

DISPENSE E TESTI CONSIGLIATI

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 2008.

Le dispense sono disponibili presso la libreria C.L.U.E.D., Settore Didattico, via Celoria 20, Milano,
oppure scaricabili dal seguente sito:
file ps (1,5Mb circa), file pdf .
Il capitolo riguardante i problemi NP-completi si trova anche in file ps , file pdf .
Testo principale
T. Cormen, C. Leiserson, R. Rivest, C. Stein
Introduzione agli algoritmi e strutture dati,
McGraw-Hill, 2005.
Altri testi di riferimento
M. Torelli, Appunti per il corso di Algoritmi e Strutture Dati , dispense scaricabili da file html.
C. Demetrescu, I. Finocchi, G. Italiano Algoritmi e strutture dati , McGraw-Hill, 2004.
A. Bertossi, Algoritmi e strutture dati, UTET Libreria, 2000.
A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974.

ESERCIZI E TEMI D'ESAME

Alcuni metodi di soluzione degli esercizi e una raccolta di temi d'esame si possono trovare in

A. Bertoni, M. Goldwurm,
Esercizi e complementi
Manoscritto, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Ottobre 2007 (file ps , file pdf ).

Il fascicolo è disponibile presso la libreria C.L.U.E.D., Settore Didattico, via Celoria 20, Milano.
Una raccolta di temi d'esame proposti a partire dall'a.a. 2002/2003 si trovano in file ps , file pdf .

MODALITÀ D'ESAME

L'esame consiste nella realizzazione di un progetto in linguaggio C e in una prova orale. Progetto e orale possono anche essere sostenuti in appelli diversi, tuttavia la prova orale va sostenuta solo dopo aver svolto il progetto con giudizio positivo.
Ad ogni appello viene pubblicato il testo del progetto sul sito di Laboratorio, con la data di consegna e quella di discussione dei progetti presentati; viene inoltre stabilita la data della prova orale che è sempre successiva a quella di discussione dei progetti. Un progetto sufficiente sarà tenuto valido per 6 mesi per sostenere la prova orale. Gli studenti sono pregati di iscriversi mediante terminale all'appello prescelto anche per svolgere una sola delle due prove.

Modalità d'esame per il corso da 18 crediti

Gli studenti iscritti al vecchio ordinamento che devono sostenere l'esame da 18 crediti saranno tenuti a svolgere il progetto e una prova orale (non si prevede lo scritto). Il progetto si svolgerà con le stesse modalità previste per il corso da 12 crediti. La prova orale sarà inoltre particolarmente dedicata allo svolgimento di esercizi e alle proprietà delle classi P e NP previste nel programma degli anni precedenti.

ORARIO DELLE LEZIONI

Primo semestre.

Inizio delle lezioni Lunedì 3 Ottobre 2011. Fine delle lezioni prevista per il 20 Gennaio 2012.

Turno unico diurno

Lunedì, ore 8.30-10.30, aula G10 ;
Martedì, ore 8.30-10.30, aula G10 ;
Giovedì, ore 8.30-10.30, aula V1 ;

ORARIO DI RICEVIMENTO

Prof. Massimiliano Goldwurm, stanza P102 (primo piano), martedì ore 11-13 oppure su appuntamento (accordi da stabilirsi per e-mail da inviare all'indirizzo cognome at dsi dot unimi dot it).
Si segnala che i ricevimenti previsti per i giorni 14/2/2012 e 21/2/2012 sono sospesi.

PROSSIMO APPELLO

La prossima prova orale (appello SIFA del 13 febbraio 2012) si terrà il 21 febbraio 2012 alle ore 9.30 in auletta 5 presso il DSI di via Comelico.
Le date di pubblicazione e consegna dei progetti per l'appello in corso sono reperibili al sito Avvisi del Corso di Laboratorio
Si ricorda agli studenti che anche per svolgere la sola prova orale è necessario iscriversi all'appello corrispondente mediante terminale SIFA.

DATE DEGLI APPELLI D'ESAME PER L'A.A. 2011/2012

Le date di pubblicazione dei testi dei progetti sono reperibili al sito Avvisi del Corso di Laboratorio
Date di consegna dei progetti (che appaiono sul SIFA): 24/1, 13/2, 18/6, 9/7, 21/9, 10/1/2013.
Date delle prove orali (corrispondenti ai precedenti appelli): 30/1, 21/2, 28/6, 19/7, 27/9, 17/1/2013.

PROGRAMMA del corso di 6 crediti

Nozione intuitiva di problema e algoritmo. Problematiche di sintesi e analisi di un algoritmo e classificazione dei problemi. Modello di calcolo RAM e relativi criteri di costo uniforme e logaritmico. Nozioni matematiche: notazione asintotica, valutazione di somme ed equazioni di ricorrenza.
Strutture dati principali: vettori, liste, pile, code. Grafi, alberi e loro rappresentazioni. Algoritmi di attraversamento di alberi e grafi; visite in profondità e in ampiezza.
Algoritmi di ordinamento. Algoritmi Mergesort e Heapsort.
Strutture di dati astratte e implementazione efficiente. Alberi di ricerca binaria, alberi di ricerca bilanciati (alberi 2-3, B-alberi). Operazioni "union-find" su partizioni: algoritmi basati su alberi con bilanciamento e compressione.
Gli algoritmi greedy: schema generale. L'algoritmo di Kruskal. Il metodo Divide et impera: schema generale e analisi dei tempi di calcolo. L'esempio di Mergesort. Algoritmi di programmazione dinamica: calcolo dei cammini minimi nei grafi pesati.
Le classi P, NP, e i problemi NP-completi.

Modalità d'esame (corso di 6 crediti)

L'esame consiste in una prova orale. La data d'esame va concordata direttamente con il docente via e-mail. Non occorre iscriversi.

Ultimo aggiornamento: 10 Febbraio 2012