Anno di corso: 1

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale

Anno di corso: 2

Anno di corso: 3

ANALISI E PROGETTO DI ALGORITMI

Scheda dell'insegnamento

Anno accademico di regolamento: 
2015/2016
Anno di corso: 
3
Anno accademico di erogazione: 
2017/2018
Tipo di attività: 
Obbligatorio
Crediti: 
8
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
76
Prerequisiti: 

Algoritmi e strutture dati

Moduli

Metodi di valutazione

Modalita' di verifica dell'apprendimento: 

Prova scritta e orale

Valutazione: 
Voto Finale

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.

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.

Programma esteso

1 "• Crescita delle funzioni, notazioni asintotiche
• Calcolo del tempo di esecuzione per algoritmi iterativi
• Richiami sulla ricorsione: calcolo del fattoriale
• Ricorrenze e tempi di calcolo di algoritmi ricorsivi• Ricerca dicotomica, calcolo altezza di un albero binario"

2 "Programmazione Dinamica
• Verso la Programmazione Dinamica: introduzione del problema Weighted Interval Scheduling
• Programmazione delle catene di montaggio
• Il problema della LCS
• Catena di moltiplicazioni di matrici
• Determinazione della ricorrenza di programmazione dinamica
• Calcolo tabulare di m(i,j): programma, esecuzione manuale"
3 "Algoritmi greedy” 4 "Algoritmi di visita di grafi
• Nomenclatura su grafi
• Rappresentazione di grafi in memoria
• Algoritmo di visita in ampiezza (BFS)
• Algoritmo di visita in profondità (DFS)" 5 "Alberi di copertura minimi
• Algoritmi di Kruskal e Prim" 6 "Problemi di cammino minimo
• Algoritmo di rilassamento e proprietà
• Algoritmo di Dijkstra
• Algoritmo di Bellman-Ford
• Algoritmo di Floyd-Warshall" 7 "Reti di flusso
• Introduzione alle reti di flusso
• Algoritmo di Ford-Fulkerson" 8 "NP completezza e riducibilità
• P verso NP
• Verifica in tempo polinomiale
• Dimostrazioni di NP completezza
• Problemi NP completi""

Bibliografia consigliata

Cormen, Leiserson, Rivest, Stein. Introduzione agli algoritmi e strutture dati, McGraw Hill

Metodi didattici

Il corso consisterà di lezioni frontali, esercitazioni e progetti di laboratorio