Algoritmi e strutture dati

A.A. 2015/2016
Insegnamento per
6
Crediti massimi
48
Ore totali
Lingua
Italiano

Struttura insegnamento e programma

Edizione attiva
Responsabile
Lezioni: 48 ore
Docente: Foresti Sara
Programma
1- Concetti fondamentali
Concetti di problema e di algoritmo; analisi di algoritmi, complessità in spazio e complessità computazionale di algoritmi, notazioni asintotiche, analisi della complessità di algoritmi; classi di complessità

2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; tabelle di hash

3- Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi binari bilanciati

4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum spanning tree; problema del cammino minimo

5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion sort, merge sort, heap sort, quick sort (e sua analisi); sorting in tempo lineare

6- Tecniche di progettazione di algoritmi [cenni]
Divide-et-impera; algoritmi greedy; programmazione dinamica
Informazioni sul programma
La frequenza del corso è consigliata
Propedeuticità
Nessuna
Prerequisiti e modalità di esame
Prerequisiti: Nessuno
Modalità d'esame: L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso, volti a valutare la preparazione dello studente.
Metodi didattici
Lezioni
Materiale didattico e bibliografia
Testo di Riferimento:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 3/ed, 2009
The MIT Press
[ISBN: 9780262033848]

disponibile anche in italiano

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduzione agli algoritmi e strutture dati", 3/ed, 2010
McGraw-Hill
[ISBN: 9788838665158]
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
su appuntamento
via Celoria, 18 - Milano (MI)