Algoritmi (2011/2012)



Codice insegnamento
4S02709
Crediti
12
Coordinatore
Roberto Segala
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
L'insegnamento è organizzato come segue:
Attività Crediti Periodo Docenti Orario
Teoria 8 II semestre, I semestre Roberto Segala
Laboratorio 4 II semestre, I semestre Roberto Segala

Orario lezioni

I semestre
Attività Giorno Ora Tipo Luogo Note
Teoria lunedì 8.30 - 9.30 lezione Aula A  
Teoria lunedì 9.30 - 11.30 lezione Aula A  
Teoria mercoledì 14.30 - 15.30 lezione Aula A  
Laboratorio mercoledì 15.30 - 17.30 esercitazione Aula A  
II semestre
Attività Giorno Ora Tipo Luogo Note
Teoria martedì 8.30 - 10.30 lezione Aula A  
Laboratorio martedì 10.30 - 11.30 esercitazione Aula A  

Obiettivi formativi

Fornire gli strumenti fondamentali per la progettazione di soluzioni algoritmiche a problemi concreti. Gli algoritmi
vengono valutati e confrontati in base alla quantità di risorse che richiedono.

Programma

Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza. Ordinamento e selezione: richiamo di insertion sort, richiamo di merge sort, heap sort, quick
sort, quick sort probabilistico. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di Selezione.
Strutture dati: heap, alberi binari di ricerca, alberi RB, B-alberi heap binomiali, tabelle hash, code con priorita`
insiemi disgiunti, tecniche di estensione di una struttura dati, grafi.
Progetto ed analisi di algoritmi: divide et impera, greedy, programmazione dinamica, ricerca locale, backtracking
e branch and bound.
Algoritmi fondamentali: alberi di copertura di costo minimo (Prim e Kruskal), programmazione lineare (simplesso
e cenno all'algoritmo polinomiale basato sugli ellissoidi) cammini minimi a sorgente singola (Dijkstra e Bellman-
Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su
grafo bipartito.

Modalità d'esame

L'esame consiste in una prova scritta di tre ore, suddivisa in due parti, e di un eventuale colloquio orale.

La prima parte della prova scritta è un test a risposte multiple e viene valutata con un punteggio tra 0 e 30. Chi ottiene una valutazione inferiore a 18 è respinto, mentre chi ottiene una valutazione compresa tra 18 e 23 termina l'esame. La seconda parte della prova scritta, alla quale si è ammessi ottenendo una valutazione di almeno 24 nella prima parte, consiste di uno o più esercizi di difficoltà crescente. Viene valutata con un punteggio tra 24 e 30.

La prova orale, facoltativa, è riservata a chi ottiene almeno 27 punti nella seconda parte della prova scritta.