Analisi e progetto di algoritmi (ITA)

Corso di Laurea Triennale in Informatica - 3° anno
Codice e denominazione insegnamento
E3101Q113 - Analisi e
progetto di algoritmi
N° cfu
8
Tipologia Attività
Formativa (TAF)
B - caratterizzante
SSD
semestre
INF/01
1
Tipo
insegnamento
obbligatorio
Contenuti:
L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy), con
particolare attenzione agli aspetti di efficienza degli algoritmi, con i relativi strumenti di analisi.
Obiettivi formativi:
Gli studenti acquisiranno la conoscenza delle principali tecniche di progetto e analisi degli algoritmi e la capacità
di individuare le più idonee tecniche algoritmiche per la soluzione di specifici problemi computazionali.
Prerequisiti:
Algoritmi e strutture dati
Docente responsabile dell'insegnamento:
MAURI Giancarlo
Turno
Docenti e attività didattica
docente
Tipologia attività didattica assistita
Lezione - turno unico
MAURI Giancarlo
Esercitazione - gruppo 1
DENNUNZIO Alberto
Esercitazione - gruppo 2
ZANDRON Claudio
Laboratorio - gruppo 1
DENNUNZIO Alberto
Laboratorio - gruppo 2
ZANDRON Claudio
totale
N° cfu
N° ore attività
didattica assistita
erogata
4
28
2
16
2
16
8
60
Metodi didattici
Il corso consisterà di lezioni frontali, esercitazioni e progetti di laboratorio
Testi di riferimento:
Cormen, Leiserson, Rivest, Stein. Introduzione agli algoritmi e strutture dati, McGraw Hill
Modalità di verifica dell'apprendimento
Prova scritta e orale
CV docente
CV docente
CV docente
CV docente
CV docente
Programma esteso – a.a. 2013-2014
argomento
• Crescita delle funzioni, notazioni asintotiche
• Calcolo del tempo di esecuzione per algoritmi iterativi
1 • Richiami sulla ricorsione: calcolo del fattoriale
• Ricorrenze e tempi di calcolo di algoritmi ricorsivi• Ricerca dicotomica, calcolo altezza
di un albero binario
Programmazione Dinamica
• Verso la Programmazione Dinamica: introduzione del problema Weighted Interval
Scheduling
• Programmazione delle catene di montaggio
2
• Il problema della LCS
• Catena di moltiplicazioni di matrici
• Determinazione della ricorrenza di programmazione dinamica
• Calcolo tabulare di m(i,j): programma, esecuzione manuale
Algoritmi greedy
• Elementi della strategia greedy
3
• Codici di Huffman
• Matroidi e teorema di Rado
tipologia attività
didattica
lezione frontale
2
esercitazione
2
laboratorio
studio individuale
9
Lezione frontale
5
esercitazione
2
laboratorio
4
studio individuale
4
esercitazione
2
laboratorio
2
Alberi di copertura minimi
• Algoritmi di Kruskal e Prim
3
esercitazione
2
laboratorio
2
18
Lezione frontale
4
esercitazione
2
laboratorio
2
studio individuale
Problemi di cammino minimo
• Algoritmo di rilassamento e proprietà
6 • Algoritmo di Dijkstra
• Algoritmo di Bellman-Ford
• Algoritmo di Floyd-Warshall
17
Lezione frontale
studio individuale
5
26
Lezione frontale
studio individuale
Algoritmi di visita di grafi
• Nomenclatura su grafi
• Rappresentazione di grafi in memoria
4
• Algoritmo di visita in ampiezza (BFS)
• Algoritmo di visita in profondità (DFS)
ore
17
Lezione frontale
3
esercitazione
2
laboratorio
2
studio individuale
18
Lezione frontale
4
Reti di flusso
esercitazione
2
• Algoritmo di Ford-Fulkerson
laboratorio
2
7 • Introduzione alle reti di flusso
studio individuale
NP completezza e riducibilità
• P verso NP
8 • Verifica in tempo polinomiale
• Dimostrazioni di NP completezza
• Problemi NP completi
17
Lezione frontale
3
esercitazione
2
laboratorio
2
studio individuale
18

Download Report