Algoritmi e strutture dati

A.A. 2015/2016
Insegnamento per
12
Crediti massimi
120
Ore totali
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 e gli algoritmi di base ponendo l'enfasi sui metodi di progettazione sull'analisi delle procedure. La parte di laboratorio ha invece come obiettivo la presentazione del linguaggio C e il suo utilizzo nella implementazione di strutture dati e algoritmi.

Struttura insegnamento e programma

Linea Milano
Edizione attiva
Responsabile
Laboratori: 48 ore
Lezioni: 72 ore
STUDENTI FREQUENTANTI
Programma
Programma del Corso:
Nozione intuitiva di problema e algoritmo. Progetto e analisi di un algoritmo. Modello di calcolo RAM e relativi criteri di costo uniforme e logaritmico. Nozioni matematiche: strutture combinatorie elementari, notazione asintotica, valutazione di somme, principali 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: inserimento, heapsort, quicksort. Algoritmi Divide et Impera e la relativa analisi dei tempi di calcolo (Master Theorem): mergesort, prodotto di interi, ricerca binaria.
Strutture di dati astratte e implementazione efficiente. Tabelle hash. Alberi di ricerca binaria. Alberi bilanciati: B-alberi.
Operazioni "union-find" su partizioni: algoritmi basati su alberi con bilanciamento e compressione. Algoritmi di programmazione dinamica: chiusura transitiva di grafi e cammini minimi. Tecniche greedy: sistemi di indipendenza, matroidi e teorema di Rado; gli algoritmi di Prim, Kruskal e Dijkstra. Classificazione di problemi. Le classi P e NP. Introduzione ai problemi NP-completi.

Programma del Laboratorio
Il corso verte sull'insegnamento del linguaggio C e sull'uso del C per implementare strutture dati e algoritmi.
Il linguaggio C:
Introduzione al C, panoramica sul linguaggio. Elementi lessicali, tipi di dati fondamentali. Espressioni. Flusso del controllo. Funzioni. Vettori, puntatori e stringhe. Strutture e unioni. Input e output. Libreria standard.
Algoritmi e strutture dati:
Ricorsione, algoritmi di ordinamento, Divide et Impera, backtracking, programmazione dinamica, liste, alberi binari di ricerca, alberi Red-Black, grafi.
Informazioni sul programma
Il corso complessivamente è di 12 crediti, 9 per la parte di teoria e 3 per quella di laboratorio.
Propedeuticità
Programmazione (obbligatoria), Matematica del continuo (obbligatoria), Matematica del discreto.
Prerequisiti e modalità di esame
Le nozioni e i costrutti fondamentali di programmazione. Nozioni matematiche di base. Sequenze, serie numeriche principali e notazioni asintotiche.
L'esame è comune alle due parti (teoria e laboratorio). Esso prevede uno scritto e un progetto per la parte di laboratorio e una prova orale per la parte di teoria.
Materiale didattico e bibliografia
Materiale per il Corso:
Dispense
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso di Algoritmi e Strutture Dati), Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli studi di Milano, Ottobre 2008.
scaricabili da http://homes.dsi.unimi.it/~goldwurm/algo/
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. Bertossi, A. Montresor, Algoritmi e strutture dati, Città Studi Edizioni, 2010.
C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004.

Materiale per il Laboratorio:
Dispense del docente.
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.
Brian W. Kernighan, Dennis M. Ritchie : Linguaggio C (seconda edizione), Nuova edizione italiana, Pearson, Italia, 2004.
STUDENTI NON FREQUENTANTI
Programma
Identico a quello per i frequentanti
Prerequisiti e modalità di esame
Le nozioni e i costrutti fondamentali di programmazione. Nozioni matematiche di base. Sequenze, serie numeriche principali e notazioni asintotiche.
L'esame è comune alle due parti (teoria e laboratorio). Esso prevede uno scritto e un progetto per la parte di laboratorio e una prova orale per la parte di teoria.
Materiale didattico e bibliografia
Identico a quello per i frequentanti
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano
Ricevimento:
Martedì 15-16
Via Celoria 18 - Stanza 3021
Ricevimento:
martedì dalle 14:30 alle 17:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).